問題タブ [contiguous]

複数の型の要素を単一のベクトルに格納し、同じ型の要素を連続させたいと考えています。型は基本クラスから派生しており、開発サイクル全体でさまざまな型が実装されることを期待しています。このため、新しいタイプをリストに追加するプロセスが非常に単純であると役立ちます。

次の方法でこれを（ある程度）達成できます。

ただし、これはきれいではなく、保守が容易でもなく、コンパイルにも適していません (データを保持するクラスは多くの場所に含まれています)。

よりコンパイルしやすい（しかし醜い）オプションは、このようなことをしていると思いました

(うーん！)

このように一般的に機能するものはありますか？

編集：

この構造の動機は、Entity-Component デザイン パターンにコンポーネントを格納することです。

タイプ (というか、コンポーネント) を連続させたい理由は、キャッシュに適した方法でそれらを横断できるようにするためです。これは、インスタンス自体が連続していることを意味します。連続したポインターを使用すると、私が望むものと同様の動作が得られますが、それらがメモリ内の「ランダムな」場所を指している場合、データをフェッチするときにキャッシュミスが発生します。

メモリの断片化を回避することは、これの優れた追加の利点です。

主なアイデアは、これらの要素へのアクセスを保持および提供するクリーンなマネージャー型クラスを用意することです。他の開発者がこのクラスに追加する必要がある複数のメンバー ベクトルを持つことは、新しいクラスを作成するユーザーがこのマネージャー クラスを変更する必要がある限り、望ましくありません。このコンテナ クラスへの編集は、できる限り単純にするか、できれば存在しないようにする必要があります。

解決策が見つかりました

この記事を教えてくれた Dmitry Ledentsov に感謝します。これは私が探していたものです。

k個の数字のソートされたリストが与えられたとします。次に、このソートされたリストを連続した番号を持つリストに変換します。許可されている唯一の操作は、数値を 1 ずつ増減できることです。このような操作をすべて実行すると、総コストが 1 増加します。

さて、前述のようにリストを変換しながら、総コストを最小限に抑えるにはどうすればよいでしょうか?

私が持っている 1 つのアイデアは、並べ替えられたリストの中央値を取得し、中央値の周りに数字を配置することです。その後、新しく作成されたリストと元のリストの対応する番号の絶対差を追加するだけです。しかし、これはあくまでも直感的な方法です。私はそれの証拠を持っていません。

PS:

これはTopcoder の問題の一部です。

これは常に次の結果になりますか？

または、他の可能な結果は次のようになります。

私のマシンで何度も試してみたところ、n番目の値が常に連続していました。しかし、それは証拠ではありません;)。

目的:

一意の Kdtree を構築したいのですが、ベクターに重複があります。現在、中央値を見つけるために nth_element を使用しています。問題は、ベクトルを再度トラバースすることなく、一意の再構成可能な中央値を選択することです。中央値が連続している場合は、あまりトラバースせずに一意の中央値を選択できます。

コンティグ (incon= 初期コンティグ; DNA シーケンス) を受け取る DNA シーケンスを使用して辞書を作成するプログラムに関数を追加し、辞書のキーの形で重複部分を見つけて値を連結することにより、右に拡張します。 「+」演算子。

簡単な例を挙げます：

初期コンティグとして GATTTGAAGC

ATTTGAAGC:A は、ディクショナリ内の多数のエントリの 1 つです。

関数で、辞書のキーである重複部分 (昨日ここで質問したところ、それ自体と特定の値では正常に機能しましたが、変数を持つ関数内では機能しませんでした) を検索し、そのキーの値を連結して、最初のシーケンス（コンティグを右に拡張）し、新しいシーケンスを保存してから、inconこの辞書エントリを削除し、エントリがなくなるまで繰り返します（この部分はまだ試していません）。

まず、長さ 1 の値を持つ長さ 9 のキー (ATTTGAAGC:A) を検索し、長さ 2 の値を持つ長さ 8 のキーの重複部分がない場合 (fe ATTTGAAG:TG) などを検索する関数が必要です。

追加情報: 辞書 "suffixDicts" には、長さが 1 (キーの長さは 14) から 10 (キーの長さは 5) の値を持つエントリがあります。

「読み取り」は、シーケンスのリストが保存される場所です

ステップを次々と実行しようとすると、いくつかの作業（検索など）とそうでないものがありますが、そこから関数を構築しようとすると、文字通り何も起こりません。この関数は、可能な限り最小の拡張子を返すことになっています。

私はPythonに非常に慣れていないので、おそらく私が犯した非常に悲惨な間違いがあるので、それらを指摘してもらいたい. 私はこれで頭がいっぱいであることを知っていますが、既存のコードのほとんどの部分を理解していますが、おそらく間違ったシンタックスが原因で、自分で何かを実装する際にまだ問題があります. 使用できるプログラムがあることは知っていますが、その背後にあるすべてを理解したいと思います。

編集：求められたように、すでに与えられた機能を追加します。それらのいくつかは、与えられたコードに基づいて私が書いたいくつかの部分がすでに書かれていました（基本的に、いくつかの微調整を加えてコピーしました）。警告: かなり多いです:

Fasta ファイルの読み取り: 追加情報: Fasta ファイルには、大量の配列が次の形式で含まれています。

"> 1を読む

TTATGAATATTACCGCAATGGACGTCCAAGGTACAGCGTATTTGTACGCTA

"> 2 を読む

AACTGCTATCTTTCTTGTCCACTCGAAAATCCATAACGTAGCCCATAACG

"> 3を読む

TCAGTTATCCTATATACTGGATCCCGACTTTAATCGGCGTCGGAATTACT

ここにファイルをアップロードしました: http://s000.tinyupload.com/?file_id=52090273537190816031

編集: コードの大きなブロックを編集しましたが、必要ないようです。