3 ms·
Is there a reason to use galloping over an array vs a seek in a search tree? Better real world factors? Galloping, Demaine set intersection, worst case optima
by j-pb 5y ago
Is there a reason to use galloping over an array vs a seek in a search tree?
Better real world factors?
Galloping, Demaine set intersection, worst case optimal
joins, they all seem
to be different aspects of
the same underlying principle.
So I'm very curious about the peculiarities in the sorting case.
- tim-peters 5y agoSee CPython's https://github.com/python/cpython/blob/main/Objects/listsort.txt https://github.com/python/cpython/blob/main/Objects/listsort... for details about the sort. In fact, its "galloping" was inspired by a paper of which Demaine was a co-author (reference in the file already linked to). CPython's lists are implemented as contiguous C arrays of pointers (to Python objects). Any way of grafting a tree-ish structure on top of that would be unacceptably wasteful of space and/or time. So sorting "gallops" over arrays because it's array-in, array-out.
- j-pb 5y agoThank you for the explanation!