Is there anything faster than a dictionary?

Question

I am leaning n-gram, and building a dictionary to save n-gram values. I have something like this:

{
  "it is" : 0.01,
  "this is" : 0.005,
  "hello i" : 0.2
  "hello you" : 0.3
  ...
}

My dictionary has about 3million keys and it takes 0.0002(s) to get a bigramvalue.

Is there anything faster than dict that I could use?

Have a look at [this question](https://stackoverflow.com/questions/19629682/ordereddict-vs-defaultdict-vs-dict) — Anuj, Nov 28 '17 at 10:37
Duplicate: https://stackoverflow.com/questions/40694470/is-there-anything-faster-than-dict — Nickpick, Nov 28 '17 at 10:46
Nope, just checked: Lookup is just as fast for a dict with 1000 or 1000000 random keys. Also, in both cases `d[k]` is twice as fast as `d.get(k)` — tobias_k, Nov 28 '17 at 10:47
dictionaries are like hashtables. Search, insertion and deletion are `O(1)`. — RoadRunner, Nov 28 '17 at 10:55

akash karothiya · Accepted Answer · 2017-11-28T11:04:06.233

No, I don't think there is anything faster than dict. The time complexity of its index checking is O(1).

-------------------------------------------------------
Operation    |  Average Case  | Amortized Worst Case  |
-------------------------------------------------------
Copy[2]      |    O(n)        |       O(n)            | 
Get Item     |    O(1)        |       O(n)            | 
Set Item[1]  |    O(1)        |       O(n)            | 
Delete Item  |    O(1)        |       O(n)            | 
Iteration[2] |    O(n)        |       O(n)            | 
-------------------------------------------------------

PS https://wiki.python.org/moin/TimeComplexity

Is there anything faster than a dictionary?

1 Answers1