[issue46488] listsort.txt wrongly assumes you cannot calculate leading zeros in O(1) time.
Raymond Hettinger
report at bugs.python.org
Sun Jan 23 17:11:12 EST 2022
Raymond Hettinger <raymond.hettinger at gmail.com> added the comment:
Presumably the OP is referring to this text:
"""
`powerloop()` emulates these divisions, 1 bit at a time, using comparisons,
subtractions, and shifts in a loop.
You'll notice the paper uses an O(1) method instead, but that relies on two
things we don't have:
- An O(1) "count leading zeroes" primitive. We can find such a thing as a C
extension on most platforms, but not all, and there's no uniform spelling
on the platforms that support it.
- Integer division on an integer type twice as wide as needed to hold the
list length. But the latter is Py_ssize_t for us, and is typically the
widest native signed integer type the platform supports.
But since runs in our algorithm are almost never very short, the once-per-run
overhead of `powerloop()` seems lost in the noise.
"""
----------
assignee: docs at python -> tim.peters
nosy: +rhettinger
_______________________________________
Python tracker <report at bugs.python.org>
<https://bugs.python.org/issue46488>
_______________________________________
More information about the Python-bugs-list
mailing list