Guía de Estructuras de datos básicas · 6/6

Real-World Use

Por ahora, este capítulo solo está disponible en inglés.

The structures in this guide sit underneath almost every program. Knowing how the standard libraries implement them explains many performance surprises and a few classic bugs.

Inside the standard libraries

CPython `list` is a dynamic array of pointers to objects. It over-allocates by a modest fraction on growth, so appends are amortized O(1) while wasting less memory than doubling.
CPython `dict` uses open addressing rather than chaining, with a compact layout that has kept insertion order since Python 3.6; the order is a language guarantee from 3.7. set is also a hash table with open addressing.
`collections.deque` is a doubly linked list of fixed-size blocks (64 items each in CPython), which is why both ends are O(1) but indexing the middle is O(n).
C++ `std::vector` grows geometrically; the factor is implementation-defined (libstdc++ and libc++ double, MSVC grows by 1.5). std::deque stores fixed-size chunks plus a map of chunk pointers, and std::unordered_map uses separate chaining with a default maximum load factor of 1.0.
Java `ArrayList` grows by about 1.5 times. HashMap uses a power-of-two bucket array, a default load factor of 0.75, and converts a bucket's chain into a red-black tree once it holds more than 8 entries and the table has at least 64 buckets.
JavaScript `Map` and `Set` are hash tables that iterate in insertion order.

Where they show up

Structure	Typical uses
Stack	Function call stack, undo history, expression parsing, depth-first search
Queue	Job and message queues, breadth-first search, print spooling, rate limiting windows
Ring buffer	Audio and network buffers, log tails, producer and consumer pipes
Linked list	OS kernel lists, free lists in memory allocators, the recency order in LRU caches
Hash table	Caches, symbol tables in compilers, database hash joins and indexes, deduplication

A good example of combining them is an LRU cache: a hash map finds an entry in O(1) and a doubly linked list keeps entries in recency order so the oldest can be evicted in O(1). Python's OrderedDict is exactly that pair:

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.data = OrderedDict()

    def get(self, key):
        if key not in self.data:
            return None
        self.data.move_to_end(key)          # mark as most recently used
        return self.data[key]

    def put(self, key, value):
        self.data[key] = value
        self.data.move_to_end(key)
        if len(self.data) > self.capacity:
            self.data.popitem(last=False)   # evict the least recently used

cache = LRUCache(2)
cache.put("a", 1); cache.put("b", 2); cache.get("a"); cache.put("c", 3)
print(list(cache.data))  # ['a', 'c'] -- 'b' was evicted

¿Tienes preguntas sobre este capítulo?

Real-World Use

Inside the standard libraries

Where they show up

Pitfalls

Summary

Further reading

0 comentarios