與小型和大型字典測試差不多相同:
In [31]: random_key = lambda: ''.join(np.random.choice(list(string.ascii_letters), 20))
In [32]: few_keys = {random_key(): np.random.random() for _ in xrange(100)}
In [33]: many_keys = {random_key(): np.random.random() for _ in xrange(1000000)}
In [34]: few_lookups = np.random.choice(few_keys.keys(), 50)
In [35]: many_lookups = np.random.choice(many_keys.keys(), 50)
In [36]: %timeit [few_keys[k] for k in few_lookups]
100000 loops, best of 3: 6.25 µs per loop
In [37]: %timeit [many_keys[k] for k in many_lookups]
100000 loops, best of 3: 7.01 µs per loop
編輯:對於你來說,@ShadowRanger - 錯過查找是相當接近太:
In [38]: %timeit [few_keys.get(k) for k in many_lookups]
100000 loops, best of 3: 7.99 µs per loop
In [39]: %timeit [many_keys.get(k) for k in few_lookups]
100000 loops, best of 3: 8.78 µs per loop
固定時間常數。 –
@JustinNiessner:'字典'查找不是O(1)。它通常是* O(1)。它是O(m),'m'是桶中物品的數量。 – Amadan
@Amadan - 我從來沒有說過,但如果OP假設算法是O(1)(這是恆定的時間),那麼應該沒有區別。 –