4

Couldnt track down a solid enough reasoning for why dictionary functions such as .values() and .keys() are considered to be O(1) in big O notation. (not sure if .items() is also considered O(1) )

ShadowRanger
  • 143,180
  • 12
  • 188
  • 271
Vanessa Ventura
  • 99
  • 1
  • 9

2 Answers2

6

It is likely that the reference you found to .keys() and .values() (and .items()) being O(1) emphasized the performance because it is a contrast to Python 2, where those functions returned lists and required O(N) time to copy references to all the relevant objects out of the dictionary.

Iterating on the view objects returned by those methods in Python 3 will still take O(N) time, as there's no way to avoid visiting each item, since that's the whole point of iteration. The keys and items views do offer O(1) membership tests (e.g. (somekey, somevalue) in somedict.items()), which is a lot more efficient than searching for an item in a list.

Blckknght
  • 100,903
  • 11
  • 120
  • 169
5

I am not versed in python, but I found this:

Dictionary view objects

The objects returned by dict.keys(), dict.values() and dict.items() are view objects. They provide a dynamic view on the dictionary’s entries, which means that when the dictionary changes, the view reflects these changes.

Dictionary views can be iterated over to yield their respective data, [...]

Which means that dict.keys() and such don't return a new object, but just a thin wrapper that can iterate over the dictionary. So getting this view is O(1). Iterating over elements it's not.

bolov
  • 72,283
  • 15
  • 145
  • 224
  • 7
    To be clear, actually iterating the views would be `O(n)`; it's just creating them that's `O(1)`. They're not magic. :-) – ShadowRanger Jul 20 '19 at 00:44
  • I would think this has to do with a dictionary essentially being a hashtable. To create the view and have it ready to be iterated over, you would only need to find the beginning of allocated memory space? –  Jul 20 '19 at 00:58
  • 1
    @MikeSperry: Creating the view just makes a new view object that stores a pointer to the underlying `dict`. Even creating the iterator doesn't look at the hashtable itself, it's only when you begin iterating that it has to start reading that memory. It has nothing to do with being a hashtable; the same basic work is done by `iter()` called on all built-in collections: Make a wrapper that refers to the underlying collection and initializes basic state to begin iteration (e.g. store the starting index of `0` or the like). – ShadowRanger Jul 26 '19 at 16:46
  • *"don't return a new object, but just a thin wrapper"* - That wrapper *is* a new object. Maybe it wouldn't need to be, but a test with `d = {}` `print(d.keys() is d.keys())` [shows](https://tio.run/##K6gsycjPM7YoKPr/P0XBVqG6lqugKDOvRCNFLzu1slhDUyGzWAHG1vz/HwA) `False`. – Kelly Bundy Aug 22 '21 at 14:37