0

私は仕事の問題を解決しようとしていて、初心者のプログラマーです。タブ区切りの 3 つのファイルがあります。

File1 には 2 つのフィールドがあります: *Marker_id* & positionこのファイルは位置 (0-26) でソートされ、Marker_id は別のアプリケーションの結果であるがアルファベット順ではありません。Marker_id の順序は重要です。私のプログラムの目的は、開始 Marker_id を見つけて、それと終了 Marker の間の Marker の数を数えることです。このファイルには、約 2,500,000 のエントリが含まれています。

File2 には 1 つのフィールド *Marker_id* があります。これは File1 で使用されている Marker_id と同じですが、このファイルには約 2,200,000 エントリしか含まれていません。このファイルは、プログラムでカウントする必要がある「アクティブな」マーカーまたはマーカーのリストです。

File3 にはフィールドposition *starting_marker*終了マーカー*number_markers* およびその他のフィールドがあります。基本的に、開始と終了の間のマーカーの数を数えて number_markers フィールドを更新する必要があります。

file1 を読み込むコードが既にあります

vector< list<marker> >;

ここで、marker は構造体です:

struct MARKER{
 string snp_id;
 bool included;
 MARKER(string temp_id) : snp_id(temp_id), included(false) { }
};

ファイル 1 の位置 (0 ～ 26) は、マーカーを格納するベクトル内のインデックスを指定します。また、開始と停止の間のマーカーの数で file3 のカウントを正常に更新します。

しかし、リストを「アクティブなマーカー」のみにトリミングする機能の実装に問題があります。私は単純に MARKER.included(true); を実行するつもりでした。file2 に位置が含まれていないことに気付くまで、file2 のエントリを検索します。そのため、各ベクトル インデックスですべてのリストを検索する必要があります。これは可能ですが、非常に多くのエントリがあると信じられないほど遅くなるように感じます.

キーがMarker_idであるマップにfile1を保存するなどの代替案を考えようとしていますが、カウントのためにMarker_idを元の順序で保持する必要があるため、ハングアップします。

誰かアドバイスはありますか？ありがとう。

更新 (サンプル ファイル):

***File1***
Marker_id                position
  test_marker_1              1
  test_marker_2              1 
  test_marker_3              1
  test_marker_4              1
  test_marker_5              1
  test_marker_6              1
  test_marker_7              1
  test_marker_8              1   
  test_marker_9              1

.

***File2***
Marker_id         C20020.Log R Ratio    C20020.B Allele Freq
test_marker_1         0.0180                       0.0010
test_marker_3        -0.0340                       0.5000
test_marker_4         0.0500                       0.0700
test_marker_5         0.0500                       0.0700
test_marker_6         0.0500                       0.0700
test_marker_7         0.0500                       0.0700
test_marker_9         0.0500                       0.0700

注: test_marker_2 と test_marker_8 はファイル 2 から省略されているため、カウントには含まれません。

***File3***
position  copy_num  sampleID   startMarker     endMarker          conf         num_Markers
   1         4      C20020    test_marker_1     test_marker_3     1774.967          0
   1         3      C20020    test_marker_3     test_marker_5      17.967           0
   1         0      C20020    test_marker_7     test_marker_9    107.967           0

.

***My desired output***
position  copy_num  sampleID   startMarker     endMarker          conf         num_Markers
   1         4      C20020    test_marker_1     test_marker_3     1774.967          2
   1         3      C20020    test_marker_3     test_marker_5      17.967           3
   1         0      C20020    test_marker_7     test_marker_9    107.967           2

現時点では、file2 に見つからないマーカーを除外していないため、3 つの例すべてでカウントが 3 になる以外はすべて機能しています。

4

1 に答える 1

0

いくつかのアプローチが思い浮かびます。

ファイル 1 と 2 をマーカー ID (もちろん一時コピー) で並べ替えると、ファイル 1 にはあるがファイル 2 にはないマーカーを 1 回のパスで簡単に判別できます。次に、この「除外リスト」を使用して、アルゴリズムの他の部分で無視するマーカーを決定できます。あなたの数字によると、これは約 300,000 個のアイテムになり、すばやく検索できるようにハッシュ マップに挿入できます。

もちろん、大量のメモリがある場合は、いつでもファイル 2 のすべてをハッシュ マップに入れて、同じ方法で使用できます。

メモリが実際の問題であるが、マーカー値が完全な空間 (たとえば、100 万から 1000 万など) を定義するようなものであり、マーカーをオフセットにマップできる場合は、空間全体のビット マップを作成できます。 、アクティブなマーカーのみが 1 になります。繰り返しますが、このビットマップを使用して、無視するマーカーを除外します。

基本的に、包含/除外テストの一定時間のチェックを取得できる限り、あなたは笑っています。

于 2014-02-04T09:40:39.603 に答える