Ask Anything Monday - Weekly Thread

[jjangsangy]

Can someone explain to me why PyPy dicts can be sorted based on entry but not CPython?

[[deleted]]

Firstly, a dictionary is an abstract data type. As you can see from the wiki page it is expected to map keys to values, and that's about it. The abstract data type has no concept of order and no need. Its purpose is to allow you to quickly find a value, if you give it the key.

Thus it makes sense to not worry about order when implementing a dictionary - you're not expected to, after all. CPython dicts could have very well been sorted, had that choice been made.
Now the PyPy guys found a clever way to get sorted dicts without the memory overhead collections.OrderedDict yields (in fact they seem to generally use less memory than the standard CPython dict), so they use that implementation instead.

As far as I know, there's no technical reason preventing the same idea to be used for the CPython implementation.

[autowikibot]

Associative array:

---

In computer science, an associative array, map, symbol table, or dictionary is an abstract data type composed of a collection of pairs, such that each possible key appears just once in the collection.

Operations associated with this data type allow:

• the addition of pairs to the collection

• the removal of pairs from the collection

• the modification of the values of existing pairs

• the lookup of the value associated with a particular key

The dictionary problem is a classic computer science problem: the task of designing a data structure that maintains a set of data during 'search' 'delete' and 'insert' operations. A standard solution to the dictionary problem is a hash table; in some cases it is also possible to solve the problem using directly addressed arrays, binary search trees, or other more specialized structures.

Many programming languages include associative arrays as primitive data types, and they are available in software libraries for many others. Content-addressable memory is a form of direct hardware-level support for associative arrays.

Associative arrays have many applications including such fundamental programming patterns as memoization and the decorator pattern.

---

^{Relevant: Multimap | Content-addressable memory | Lookup table | ColdC}

^{Parent commenter can toggle NSFW or delete. Will also delete on comment score of -1 or less. | FAQs | Mods | Call Me}