3

解析して行からキー値を取得している非常に大きなファイルがあります。最初のキーと値だけが必要です。値は1つだけです。つまり、重複する値を削除します

したがって、次のようになります。

{
A:1
B:2
C:3
D:2
E:2
F:3
G:1
}

そしてそれは出力します：

{E:2,F:3,G:1}

キーが何であるかはあまり気にしないので、少し混乱します。したがって、上記のEをBまたはDに置き換え、FをCに置き換え、GをAに置き換えることができます。

これが私が見つけた最善の方法ですが、ファイルが大きくなるにつれて非常に遅くなります。

mapp = {}
value_holder = []

for i in mydict:
 if mydict[i] not in value_holder:
   mapp[i] = mydict[i]
   value_holder.append(mydict[i])

毎回value_holderを調べる必要があります:(これを行うためのより速い方法はありますか？

4

6 に答える 6

6

はい、些細な変更ではるかに高速になります。

value_holder = set()

（まあ、あなたもに変更する必要がありますappend。addしかし、それでもかなり簡単です。）

リストの代わりにセットを使用すると、各ルックアップはO（N）ではなくO（1）になるため、操作全体はO（N ^ 2）ではなくO（N）になります。つまり、10,000行ある場合、50,000,000回の比較ではなく、10,000回のハッシュルックアップを実行します。

このソリューション（および投稿された他のすべて）に関する1つの注意点は、値がハッシュ可能である必要があることです。blistそれらがハッシュ可能ではないが、比較可能である場合でも、（たとえば、ライブラリから）ソートされたセットを使用することにより、O（N ^ 2）の代わりにO（NlogN）を取得できます。ハッシュ可能でもソート可能でもない場合…まあ、「最初のチェック」として使用するハッシュ可能（またはソート可能）なものを生成し、実際の一致については「最初のチェック」の一致のみをウォークする方法を見つけたいと思うでしょう。 、O（NM）に移動します。ここで、Mはハッシュ衝突の平均数です。

標準ライブラリのドキュメントのレシピにどのようunique_everseenに実装されているかを確認することをお勧めします。itertools

辞書には実際には順序がないため、「最初の」複製を選択する方法がないことに注意してください。任意に1つ取得します。その場合、これを行う別の方法があります。

inverted = {v:k for k, v in d.iteritems()}
reverted = {v:k for k, v in inverted.iteritems()}

（これは事実上、処理なしの装飾-プロセス-非装飾イディオムの形式です。）

しかし、を構築してdictフィルタリングする代わりに、読みながらフィルタリングすることで、物事をより良くすることができます（よりシンプルで、より速く、よりメモリ効率が高く、順序を維持できます）。基本的に、あなたが進むにつれて、set一緒に保ちます。dictたとえば、これの代わりに：

mydict = {}
for line in f:
    k, v = line.split(None, 1)
    mydict[k] = v

mapp = {}
value_holder = set()

for i in mydict:
    if mydict[i] not in value_holder:
        mapp[i] = mydict[i]
        value_holder.add(mydict[i])

これを行うだけです：

mapp = {}
value_holder = set()
for line in f:
    k, v = line.split(None, 1)
    if v not in value_holder:
        mapp[k] = v
        value_holder.add(v)

実際、これをまとめたものを書くことを検討することをお勧めしますone_to_one_dict（または、PyPIモジュールとActiveStateレシピを検索して、誰かがすでにそれを書いているかどうかを確認します）。

mapp = one_to_one_dict()
for line in f:
    k, v = line.split(None, 1)
    mapp[k] = v
于 2012-12-27T22:59:12.490 に答える
2

他の人が述べているように、これを高速化する最初の方法はset、セットのメンバーシップのチェックがはるかに高速であるため、を使用して表示された値を記録することです。

dictの理解により、これを大幅に短くすることもできます。

seen = set()
new_mapp = {k: v for k, v in mapp.items() if v not in seen or seen.add(i)}

ifの場合は少し説明が必要です。以前に値を見たことがないキーと値のペアのみを追加しますorが、見えない値がセットに追加されるように少しハックを使用します。set.add()リターンとしてNone、それは結果に影響を与えません。

いつものように、2.xでは、ユーザーdict.iteritems()はdict.items()。

于 2012-12-27T23:24:01.933 に答える
2

私はあなたが何をしているのか完全にはわかりませんがset、重複を取り除くための素晴らしい方法です。例えば：

>>> k = [1,3,4,4,5,4,3,2,2,3,3,4,5]
>>> set(k)
set([1, 2, 3, 4, 5])
>>> list(set(k))
[1, 2, 3, 4, 5]

ロードする入力の構造に少し依存しますsetが、一致するキーがあるかどうかを確認するためにオブジェクト全体を毎回繰り返す必要がないように、単純に使用する方法があるかもしれません。一度実行しますset。

于 2012-12-27T22:59:30.483 に答える
0

setの代わりに使用すると、listかなりスピードアップします...

于 2012-12-27T22:59:38.580 に答える
-1

非常に大きなファイルから読み取っていて、キーの最初の出現のみを保持したいとおっしゃいました。私は当初、これは、非常に大きなファイルでキーと値のペアが発生する順序を気にすることを意味すると想定していました。このコードはそれを行い、高速になります。

values_seen = set()
mapp = {}
with open("large_file.txt") as f:
    for line in f:
        key, value = line.split()
        if value not in values_seen:
            values_seen.add(value)
            mapp[key] = value

listコードが見たキーを追跡するためにを使用していました。リストの検索listは非常に遅くなります。リストが大きくなるほど遅くなります。ルックアップは一定時間に近いため、 Asetははるかに高速です（リストが大きくなるほど遅くなることはありません。または、まったく遅くなることはありません）。（Adictも動作するようにset動作します。）

于 2012-12-27T22:59:54.007 に答える
-1

問題の一部は、dictが繰り返されるときに、いかなる種類の論理的な順序も保持しないことです。彼らはハッシュテーブルを使用してアイテムにインデックスを付けます（このすばらしい記事を参照してください）。したがって、この種のデータ構造には「価値の最初の出現」という実際の概念はありません。これを行う正しい方法は、おそらくキーと値のペアのリストです。例：

kv_pairs = [(k1,v1),(k2,v2),...]

または、ファイルが非常に大きいため、Pythonが提供する優れたファイル反復を使用してk/vペアを取得することをお勧めします。

def kv_iter(f):
    # f being the file descriptor
    for line in f:
        yield ... # (whatever logic you use to get k, v values from a line)

Value_holderは、セット変数の優れた候補です。あなたは本当にvalue_holderかどうかをテストしているだけです。値は一意であるため、同様のハッシュ方法を使用してより効率的にインデックスを作成できます。したがって、最終的には次のようになります。

mapp = {}
value_holder = set()

for k,v in kv_iter(f):
    if v in value_holder:
       mapp[k] = v
       value_holder.add(v)
于 2012-12-27T23:44:39.943 に答える