[Fred] >> We could allocate a second array of PyObject* to mirror the list >> contents; that would have only the keys. When two values are >> switched in the sort, the values in both the key list and the value >> list can be switched. When done, we only need to decref the >> computed keys and free the array of keys. [Guido] > I can't tell if that'll work, but if it does, it would be a great > solution. I mentioned that before -- doubling the amount of data movement would hurt, at best by blowing cache all to hell. There's a related approach, though: build a distinct vector of custom objects, each containing: 1. A pointer to the key. 2. The original index, as a C integer. This is similar to, but smaller than, something mentioned before. The comparison function for this kind of object redirects to comparing only the keys -- the integers are ignored during the sort. Sort this list with the sorting code exactly as it exists now. At the end of sorting, the integer members can be used to permute the original list into order. This can be done in-place efficiently (not entirely obvious; Knuth gives at least one algorithm for it).
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4