0

大きな2次元リストをループしたい：

authors = [["Bob", "Lisa"], ["Alice", "Bob"], ["Molly", "Jim"], ... ]

著者に出現するすべての名前を含むリストを取得します。

リストをループするとき、既に見た名前を格納するためのコンテナが必要です。リストと dict のどちらを使用するべきか迷っています。

リスト付き：

seen = []
for author_list in authors:
    for author in author_list:
        if not author in seen:
            seen.append(author)
result = seen

口述で：

seen = {}
for author_list in authors:
    for author in author_list:
        if not author in seen:
            seen[author] = True
result = seen.keys()

どちらが速いですか？またはより良い解決策はありますか？

4

6 に答える 6

8

あなたは本当にしたいですset。セットは一意の要素のみを含むことができ、ハッシュ テーブルとして実装できるため、リストよりも高速です。ハッシュ テーブルによりif element in my_set、時間内にメンバーシップ テスト ( ) が可能になりO(1)ます。これはリストとは対照的です。リストでは、要素がリストにあるかどうかを確認する唯一の方法は、リストのすべての要素を順番に (O(n)時間内に) チェックすることです。

は、両方とも一意のキーのみを許可し、両方ともハッシュ テーブルとして実装されるという点で に似dictています。どちらもメンバーシップのテストsetを許可します。O(1)違いは、 asetにはキーしかないのに対し、 adictにはキーと値の両方があることです (これは、このアプリケーションでは不要な余分なオーバーヘッドです)。

を使用しset、ネストされた for ループを に置き換えてitertools.chain()、2D リストを 1D リストにフラット化します。

import itertools
seen = set()
for author in itertools.chain(*authors):
    seen.add(author)

または短い：

import itertools
seen = set( itertools.chain(*authors) )

大きなリストのメモリ効率を高める編集 (@jamylak に感謝):

import itertools
seen = set( itertools.chain.from_iterable(authors) )

リストのリストの例:

>>> a = [[1,2],[1,2],[1,2],[3,4]]
>>> set ( itertools.chain(*a) )
set([1, 2, 3, 4])

PS : すべての一意の著者を見つける代わりに、各著者に会った回数を数えcollections.Counterたい場合は、ものを数えるために最適化された特別な種類の辞書である を使用します。

文字列内の文字数をカウントする例を次に示します。

>>> a = "DEADBEEF CAFEBABE"
>>> import collections
>>> collections.Counter(a)
Counter({'E': 5, 'A': 3, 'B': 3, 'D': 2, 'F': 2, ' ': 1, 'C': 1})
于 2012-05-10T08:16:59.250 に答える
3

setより速くする必要があります。

>>> authors = [["Bob", "Lisa"], ["Alice", "Bob"], ["Molly", "Jim"]]
>>> from itertools import chain
>>> set(chain(*authors))
set(['Lisa', 'Bob', 'Jim', 'Molly', 'Alice'])
于 2012-05-10T08:15:03.527 に答える
3

adictまたは asetを使用すると、aを使用するよりもはるかに高速です。list

import itertools
result = set(itertools.chain.from_iterable(authors))
于 2012-05-10T08:15:59.420 に答える
2

セットを使用できます-

from sets import Set

seen = Set()

for author_list in authors:
    for author in author_list:
        seen.add(author)

result = seen

このようにして、「if」チェックを回避しているため、解決策がより高速になります。

于 2012-05-10T08:13:00.080 に答える
1

リストには、特定の順序で一連のアイテムが格納されるだけです。著者のリストは、ボックス内の紙片に著者の名前が記載されたピジョンホールボックスの長い列と考えてください。名前は入力した順序のままで、特定の鳩小屋で著者を簡単に見つけることができますが、特定の著者が鳩小屋にいるかどうかを知りたい場合は、見つけるまでそれぞれを調べる必要がありますあなたが付けている名前。また、任意の数の鳩の穴に同じ名前を付けることができます。

辞書は電話帳に少し似ています。著者の名前を指定すると、著者が電話帳に記載されているかどうかをすばやく確認し、記載されている電話番号を見つけることができます。ただし、各著者を含めることができるのは1回だけ（電話番号は1つだけ）であり、著者を好きな順序で配置することはできません。電話帳に適した順序にする必要があります。実際の電話帳では、その順序はアルファベット順です。Python辞書では、順序は完全に予測できません（辞書に追加または削除すると順序が変わります）が、Pythonは、電話帳よりも辞書でエントリをすばやく見つけることができます。

一方、セットは、電話番号ではなく名前だけをリストする電話帳のようなものです。同じ名前を複数回含めることはできません。セットに含まれているかどうかは関係ありません。また、名前がセットに含まれている順序を有用なものに使用することはできません。ただし、名前がセットに含まれているかどうかをすばやく確認できます。

ユースケースを考えると、セットが当然の選択であるように見えます。著者に会った順序や各著者に会った回数は気にせず、特定の著者に会ったことがあるかどうかをすばやく確認できます。

この場合、リストは不適切です。指定した順序で重複を記憶するように努力し、検索に時間がかかります。ただし、キーを値にマップする必要もありません。これは、辞書の機能です。電話帳の例えに戻ると、「電話番号」に相当するものはありません。辞書の例では、全員の番号がとしてリストされている電話帳を書くのと同じことをしているのにTrue、なぜわざわざ電話番号をリストするのでしょうか。

セットOTOHは、まさに必要なことを実行します。

于 2012-05-10T08:35:14.590 に答える
1

ルックアップのパフォーマンスが気になる場合は、リスト内のルックアップはO(n)であり、辞書内のルックアップはO(1)に償却されます。

詳細については、こちらをご覧ください。

于 2012-05-10T08:16:19.563 に答える