4

次の形式のデータのリストがあります。

[(id\__1_, description, id\_type), (id\__2_, description, id\_type), ... , (id\__n_, description, id\_type))

データは、同じグループに属するファイルからロードされます。各グループには、同じ ID が複数存在する可能性があり、それぞれが異なるファイルから取得されます。重複は気にしないので、これをすべて格納する良い方法は Set 型に入れることだと思いました。しかし、問題があります。

同じ ID でも、次のように説明が若干異なる場合があります。

IPI00110753

  • チューブリン α-1A チェーン
  • チューブリン α-1 鎖
  • αチューブリン1
  • α-チューブリン アイソタイプ M-α-1

(この例はuniprot タンパク質データベースから取得したことに注意してください。)

説明が異なっていても構いません。私が使用しているタンパク質データベースには、特定の識別子のリストが含まれていない可能性があるため、それらを捨てることはできません. これが発生した場合、人間が読める説明を生物学者に表示できるようにして、彼らが見ているタンパク質を大まかに知ることができるようにしたいと考えています.

現在、辞書型を使用してこの問題を解決しています。ただし、このソリューションは多くのメモリを使用するため、あまり好きではありません (これらの ID が多数あります)。これはそれらの中間のリストにすぎません。ID がデータベースに配置される前に、いくつかの追加処理が行われるため、データ構造を小さく保ちたいと考えています。

本当に2つの質問があります。まず、これには (辞書型よりも) Set 型を使用してメモリ フットプリントを小さくするか、またはリストに挿入するたびに ID が存在するかどうかを確認するソート済みリストを使用するか、または私が考えていなかった3番目の解決策は？第二に、セット型がより良い答えである場合、タプル全体ではなく最初の要素だけを見るようにキーを設定するにはどうすればよいですか?

私の質問を読んでくれてありがとう、
ティム

アップデート

私が受け取ったコメントのいくつかに基づいて、少し明確にさせてください。私がデータ構造で行うことのほとんどは、データ構造への挿入です。1 回は追加情報で注釈を付けるため、もう 1 回はデータベースに挿入するためです。ただし、データベースに挿入する前に追加の注釈が行われる場合があります。残念ながら、現時点でそれが起こるかどうかはわかりません。

現在、ハッシュテーブルに基づいていない構造（つまり、辞書）にこのデータを格納することを検討しています。私は新しい構造が挿入時にかなり迅速であることを望んでいますが、実際には2回しかやらないので、それを読むことは線形になる可能性があります. スペースを節約するために、ハッシュ テーブルから離れようとしています。より良い構造がありますか、それともハッシュテーブルはそれと同じくらい良いですか?

*情報は、uniprot を照会して取得した Swiss-Prot タンパク質識別子のリストです。

4

6 に答える 6

2

セットにはキーがありません。要素が鍵です。

キーが必要な場合は、マッピングがあります。多かれ少なかれ定義上。

二分探索を使用しても、シーケンシャル リスト ルックアップは遅くなる可能性があります。マッピングはハッシュを使用し、高速です。

このような辞書について話しているのですか？

{ 'id1': [ ('description1a', 'type1'), ('description1b','type1') ], 
  'id2': [ ('description2', 'type2') ],
...
}

これは確かに最小限のようです。ID は 1 回だけ表されます。

もしかして、こんなことありませんか？

{ 'id1': ( ('description1a', 'description1b' ), 'type1' ),
  'id2': ( ('description2',), 'type2' ),
...
}

structモジュールを使用しない限り、よりコンパクトなものを見つけることができるかどうかはわかりません。

于 2008-09-24T16:59:10.230 に答える
1

使用するメモリを削減することで解決しようとしている問題は、プロセスのアドレス空間の制限であると想定しています。さらに、高速な挿入と適切な順次読み取りを可能にするデータ構造を検索します。

文字列以外の構造体の使用を減らす (str)

あなたが尋ねる質問は、メモリの使用量を減らすために、1 つのプロセスでデータを構造化する方法です。これに対する1つの標準的な答えは、（連想ルックアップが必要な限り）できるだけ他の構造を使用せず、Python文字列（Unicodeではなくstr）を使用することです。Python ハッシュ (辞書) は、文字列への参照をかなり効率的に格納します (これは b ツリーの実装ではありません)。

ただし、直面しているのは巨大なデータセットであり、最終的にはプロセスアドレス空間と作業しているマシンの物理メモリを完全に超える可能性があるため、このアプローチではそれほど遠くには行かないと思います。

代替ソリューション

データ構造を挿入や解釈が難しいものに変更することを含まない別のソリューションを提案します。

  • 情報を複数のプロセスに分割し、それぞれがそのために便利なデータ構造を保持します。
  • プロセスが他のマシンに完全に存在する可能性があるように、ソケットを使用したプロセス間通信を実装します。
  • プロセス間通信を最小限に抑えるなど、データを分割してみてください (i/o は CPU サイクルに比べて非常に遅いです)。

私が概説するアプローチの利点は、

  • パフォーマンスのためにマシン上で 2 つ以上のコアを完全に使用することができます
  • 1 つのプロセスのアドレス空間や、1 台のマシンの物理メモリに制限されることはありません。

分散処理には多数のパッケージとアプローチがあり、そのうちのいくつかは

于 2008-09-24T17:32:59.523 に答える
1

重複を削除して n-way マージを実行している場合、次のものが探している可能性があります。

このジェネレーターは、任意の数のソースをマージします。各ソースはシーケンスでなければなりません。キーは 0 の位置にある必要があります。一度に 1 つのアイテムがマージされたシーケンスが生成されます。

def merge( *sources ):
    keyPos= 0
    for s in sources:
        s.sort()
    while any( [len(s)>0 for s in sources] ):
        topEnum= enumerate([ s[0][keyPos] if len(s) > 0 else None for s in sources ])
        top= [ t for t in topEnum if t[1] is not None ]
        top.sort( key=lambda a:a[1] )
        src, key = top[0]
        #print src, key
        yield sources[ src ].pop(0)

このジェネレーターは、シーケンスから重複を削除します。 

def unique( sequence ):
    keyPos= 0
    seqIter= iter(sequence)
    curr= seqIter.next()
    for next in seqIter:
        if next[keyPos] == curr[keyPos]:
            # might want to create a sub-list of matches
            continue
        yield curr
        curr= next
    yield curr

これらの関数を使用して、重複が削除されたすべてのソースの結合である結果のシーケンスを生成するスクリプトを次に示します。

for u in unique( merge( source1, source2, source3, ... ) ):
    print u

メモリ内で並べ替えを行っているため、各シーケンスの完全なデータ セットが一度メモリ内に存在する必要があります。ただし、結果のシーケンスは実際にはメモリ内に存在しません。実際、他のシーケンスを消費することで機能します。

于 2008-09-24T19:40:55.160 に答える
0

まだあいまいですが、 [(id, description, type)...] のリストがいくつかあるようです

ID はリスト内で一意であり、リスト間で一貫しています。

UNION を作成したい: 各 ID が 1 回発生し、複数の説明が含まれる単一のリスト。

何らかの理由で、マッピングが大きすぎるのではないかと考えています。これの証拠はありますか？実際の測定なしで過度に最適化しないでください。

これは、(私の推測が正しければ) 複数のソースからの標準的な「マージ」操作である可能性があります。

source1.sort()
source2.sort()
result= []
while len(source1) > 0 or len(source2) > 0:
    if len(source1) == 0:
        result.append( source2.pop(0) )
    elif len(source2) == 0:
        result.append( source1.pop(0) )
    elif source1[0][0] < source2[0][0]:
        result.append( source1.pop(0) )
    elif source2[0][0] < source1[0][0]:
        result.append( source2.pop(0) )
    else:
        # keys are equal
        result.append( source1.pop(0) )
        # check for source2, to see if the description is different.

これは、ソートとマージによって 2 つのリストのユニオンを組み立てます。マッピングなし、ハッシュなし。

于 2008-09-24T17:36:20.233 に答える
0

{id: (description, id_type)}辞書を使ってみませんか？または{(id, id_type): description}(id,id_type) がキーの場合は辞書。

于 2008-09-24T17:04:11.963 に答える
0

Python のセットは、ハッシュ テーブルを使用して実装されます。以前のバージョンでは、実際にはセットを使用して実装されていましたが、AFAIK が変更されました。セットを使用して保存できるのは、各エントリのポインター (値へのポインター) のサイズだけです。

ハッシュコードにタプルの一部のみを使用するには、タプルをサブクラス化し、ハッシュコード メソッドをオーバーライドする必要があります。

class ProteinTuple(tuple):
     def __new__(cls, m1, m2, m3):
         return tuple.__new__(cls, (m1, m2, m3))

     def __hash__(self):
         return hash(self[0])

この場合、追加の関数呼び出しに料金が__hash__かかることに注意してください。それ以外の場合は C メソッドになるためです。

私はコンスタンティンの提案に行き、タプルから id を取り出し、それがどれだけ役立つかを見ていきます。

于 2008-09-24T17:30:36.270 に答える