2

私はこのようなものを含むいくつかのPythonコードを書いていました

values = {}
for element in iterable:
    values.setdefault(element.name, []).append(element)

以前に入力をソートできたので、このように実装しました

values = {}

cur_name = None
cur_list = None

for element in iterable:
    if element.name != cur_name:
        values[cur_name] = cur_list
        cur_name = element.name
        cur_list = []
    cur_list.append(element)
if cur_list:
    values[cur_name] = cur_list
del values[None]

ここで、入力はすでに によってソートされていelement.nameます。

2 番目のアプローチは、最初のアプローチよりもはるかに高速であり、使用するメモリも少なくなりました。

これの理由は何ですか？

または、2番目のアプローチで何らかの間違いを犯しましたか?

4

3 に答える 3

4

ループを一周するたびに元のコードがリストを作成しますが、ほとんどの場合、リストは破棄されます。また、複数のディクショナリルックアップを実行します（メソッドsetdefaultのルックアップはディクショナリルックアップであり、メソッド自体がディクショナリルックアップを実行して、オブジェクトが設定されているかどうかを確認し、設定されていない場合は、値を格納するために別のルックアップを実行します）。.nameまた、.append()辞書ルックアップですが、改訂されたコードには引き続き存在します。

for element in iterable:
    values.setdefault(element.name, []).append(element)

改訂されたコードは、名前が変更されたときにのみ辞書を検索するため、すべてのループから2つの辞書検索とメソッド呼び出しが削除されます。それがより速い理由です。

メモリの使用に関しては、リストが大きくなると、データをコピーしなければならない場合がありますが、メモリブロックを拡張できる場合はそれを回避できます。私の推測では、これらの未使用の一時リストをすべて作成すると、メモリがさらに断片化され、より多くのコピーが強制される可能性があります。言い換えると、Pythonは実際にはより多くのメモリを使用していませんが、割り当てられているが未使用のメモリが多い可能性があります。

代わりにsetdefault使用することを検討する必要があると感じたとき。collections.defaultdictこれにより、必要な場合を除いてリストの作成が回避されます。

from collections import defaultdict
values = defaultdict(list)
for element in iterable:
    values[element.name].append(element)

名前がすべてグループ化されているという知識を利用していないため、2番目のコードよりも遅い可能性がありますが、一般的なケースでは、よりも優れていsetdefaultます。

別の方法は、を使用することitertools.groupbyです。このようなもの：

from itertools import groupby
from operator import attrgetter
values = { name: list(elements) for name,elements in
    groupby(elements, attrgetter('name')) }

これは順序付けを利用し、すべてを1つの辞書の理解にまで単純化します。

于 2012-08-16T08:10:25.470 に答える
2

2番目のアプローチが速い理由はいくつか考えられます。

values.setdefault(element.name, []).append(element)

ここではelement、使用する予定がない場合でも、それぞれに空のリストを作成しています。setdefaultまた、すべての要素に対してメソッドを呼び出しています。これは、 1回のハッシュテーブルルックアップと可能なハッシュテーブル書き込みに加えて、Pythonでは重要ではないメソッド自体を呼び出すコストに相当します。最後に、私がこの回答を投稿した後に他の人が指摘したように、常に同じメソッドを参照している場合でも、setdefault属性を1つずつ検索しています。element

2番目の例では、これらの非効率性をすべて回避します。必要な数のリストを作成するだけで、メソッドを呼び出さずにすべてを作成しますが、必要なものlist.appendは、辞書の割り当てが散在しています。また、事実上、ハッシュテーブルルックアップを単純な比較（element.name != cur_name）に置き換えています。これは、もう1つの改善点です。

リストにアイテムを追加するときにあちこちジャンプするのではなく（キャッシュミスが多く発生する）、一度に1つのリストで作業するため、キャッシュのメリットも得られると思います。このように、関連するメモリはおそらくCPUに非常に近いキャッシュ層にあるため、プロセスはより高速になります。この影響を過小評価してはなりません。RAMからのデータの取得は、L1キャッシュ（ソース）からのデータの読み取りよりも2桁（または約100倍）遅くなります。

もちろん、並べ替えには少し時間がかかりますが、Pythonには世界で最も優れた最適化された並べ替えアルゴリズムの1つがあり、すべてCでコーディングされているため、上記の利点を上回りません。

ただし、2番目のソリューションの方がメモリ効率が高い理由はわかりません。Jiriが指摘しているように、これは不要なリストである可能性がありますが、これらはガベージコレクターによってすぐに収集されるべきであるため、メモリ使用量はごくわずか（1つの空のリストのサイズ）だけ増加するはずです。ガベージコレクターが思ったより怠惰なためかもしれません。

于 2012-08-16T07:51:00.960 に答える
1

最初のバージョンには非効率的な部分が 2 つあります。

  1. ループ内でのvalues.setdefaultの呼び出しと逆参照。ループの前にass を実行values_setdefault = values.setdefaultすると、処理が少し速くなります。

  2. 他の回答が示唆しているように、リスト内のすべての要素に対して新しい空のリストを作成するのは非常に遅く、メモリ効率が悪いです。回避方法がわからずsetdefaultを一気に使用。

于 2012-08-16T08:07:30.403 に答える