1

タプルの 1 つのリストを別のタプルのリストから除外する 2 つのアプローチの速度の違いに驚きました。だから、なぜだろうと思っていました。

値でソートされた (int, float) の形式の 1,500 個のタプルのリストがありfloatます。(追加注: タプル リスト内の各 int 値は個別です。) サブリストを除外する最速の方法を見つけたかったのです。まず、除外するサブリストを作成しました。

exclude_list = [v for i,v in enumerate(tuple_list) if (i % 3) == 0]

exclude_list次に、から削除する 2 つの異なるアプローチの時間を計りましたtuple_list(ただし、これらは最終的に落ち着いた 2 つのアプローチではありません)。

remainder_list = [v for v in tuple_list if v not in exclude_list]

と、

remainder_set = set(tuple_list) - set(exclude_list)
remainder_list = sorted(remainder_set, key=itemgetter(1)) #edited to chance key to 1 from 0

時間の差は非常に大きく、最初のアプローチでは 14.7235 秒 (500 回)、2 回目のアプローチでは 0.3426 (500 回) でした。最初のアプローチでは、メイン リスト内の各アイテムの sub_list を検索する必要があるため、これら 2 つのアプローチの時間がこれほど異なる理由は理解できます。そこで、検索/除外するためのより良い方法を思いつきました:

exclude_dict = dict(exclude_list)
remainder_list = [v for v in tuple_list if v[0] not in exclude_dict]

リスト アイテムを除外するこのバージョンが、最初のバージョンよりもはるかに高速になるとは思いませんでした。最初のアプローチよりも高速だっただけでなく、2 番目のアプローチよりも高速でした。時間は 0.11177 (500 倍) です。これが私のセット差/リゾートアプローチよりも速いのはなぜですか?

4

3 に答える 3

3

リスト操作とセット操作の時間計算量を確認することをお勧めします。

remainder_list = [v for v in tuple_list if v not in exclude_list]

inここでの操作は O(N) です。tuple_list 内のすべての要素を調べて、その要素が exclude_list に存在するかどうかを確認します。したがって、その複雑さはO(len(tuple_list) * len(exclude_list))

セットの差分-操作は、O(n) の複雑さを持ちます。これは、セットが基になるデータ構造としてハッシュテーブルを使用し、O(1) のメンバーシップ チェックがあるためです。したがって、次の行：

remainder_set = set(tuple_list) - set(exclude_list).

O(len(tuple_list))複雑さがあります。

于 2013-02-22T14:07:20.833 に答える
2

inリストの演算子は、計算する O(N) です。線形検索を行うだけです。より良くするには、次のように変更できexclude_listますexclude_set。

exclude_set = {v for i,v in enumerate(tuple_list) if (i % 3) == 0}

または、既にお持ちの場合exclude_list:

exclude_set = set(exclude_list)

そして、remainder_list以前と同じように計算します：

remainder_list = [v for v in tuple_list if v not in exclude_set]

セットは非常に印象的な O(1) (平均) であるため、これははるかに優れています。inそして、ここでは、どちらも再ソートする必要がないremainder_listため、O(MlogM) ステップが削除されます (ここでM == len(remainder_list))

もちろん、この簡単な例では、1 つの list-comp ですべてを構築できます。

remainder_list = [v for i,v in enumerate(tuple_list) if (i % 3) != 0]
于 2013-02-22T14:01:29.843 に答える
2

あなたのアルゴリズムは同等ではありません。あなたの要素はカップルです。最初の 2 つの方法では、対を一致させることによって要素を除外します。3 番目の方法 (dict を使用) では、対の最初の要素のみを比較して要素を除外します。

カップルに異なる最初の要素がほとんどない場合、dict メソッドははるかに高速ですが、結果は異なる可能性があります。

于 2013-02-22T14:10:38.037 に答える