2

私が辞書を持っているとしましょう：

myDict = {
    'title': 'a nice title',
    'nice_list': [1,2,3,4,5,6,6,7,...,99999],
    'nice_lists_last_item': 99999,
}

nice_list最終的なアイテムよりも大きい場合にのみ、アイテムを追加したい。

より速いもの：

  1. 使用:if new_element > nice_list[-1]

また

  1. 使用:if new_element > nice_lists_last_item

メソッド 1 は、nice_listそのアイテムを見つけるために、リスト全体をスキャンする (および/またはすべてを毎回メモリに入れる) 必要がありますか? どちらが速いですか？（私はこれらの比較を数十億回行うつもりですか？）

方法 2 は、最後の要素を独自の dict エントリとして格納するので、その方が高速ですか?

4

3 に答える 3

6

疑わしい場合は、次をテストします。

>>> %timeit if 1 > myDict['nice_list'][-1]: 0
10000000 loops, best of 3: 110 ns per loop
>>> %timeit if 1 > myDict['nice_lists_last_item']: 0
10000000 loops, best of 3: 68.8 ns per loop
>>> nice_list = myDict['nice_list']
>>> %timeit if 1 > nice_list[-1]: 0
10000000 loops, best of 3: 62.6 ns per loop
>>> nice_lists_last_item = myDict['nice_lists_last_item']
>>> %timeit if 1 > nice_lists_last_item: 0                      
10000000 loops, best of 3: 43.4 ns per loop

ご覧のとおり、ディクショナリの値に直接アクセスする方が、ディクショナリからリストにアクセスしてから最後の値にアクセスするよりも高速です。ただし、リストの最後の値に直接アクセスする方が高速です。これは当然のことです。Python のリストはそれ自体の長さを認識しており、配列としてメモリに実装されているため、最後の項目を見つけるのは、長さから 1 を引いてポインター演算を行うのと同じくらい簡単です。ディクショナリ キーへのアクセスは、衝突検出のオーバーヘッドのために少し遅くなります。ただし、数ナノ秒だけ遅くなります。最後に、さらに数ナノ秒節約したい場合は、最後の値を独自の値に格納できます。

両方を行うと、最大の速度低下が発生します。

于 2013-04-24T19:08:05.923 に答える
4

ここに記載されているように、リストからアイテムを取得するのは O(1)です。それでも、値を明示的に格納する方が高速です。ルックアップがどれほど高速であっても、ルックアップをまったく行わない場合よりも遅くなるためです。(ただし、値を明示的に保存する場合は、リストに新しいアイテムを追加するときに値を更新する必要があります。更新とチェックの合計コストが、毎回最後のアイテムを取得するコストよりも大きいかどうかは、これは、実際に新しいアイテムを追加する頻度に依存する可能性があります。)

nice_list「すべてをメモリに入れる」という問題はないことに注意してください。リストを含む dict がある場合、そのリスト全体が既にメモリ内にあります。その中の値を検索しても、それ以上メモリを消費することはありませんが、これらのリストが数十億ある場合、リストを作成するだけでメモリを使い果たすため、何かを検索しようとする前にメモリが不足します。メモリが多すぎます。

于 2013-04-24T18:58:31.460 に答える
0

CPython では、答えはおそらくノーです。list は動的配列を使用して実装されます。

于 2013-04-24T18:58:16.757 に答える