[issue46488] listsort.txt wrongly assumes you cannot calculate leading zeros in O(1) time.
Barry Schwartz added the comment: I meant constant bounded -- ___ Python tracker <https://bugs.python.org/issue46488> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue46488] listsort.txt wrongly assumes you cannot calculate leading zeros in O(1) time.
Barry Schwartz added the comment: Yes. Actually the issue is branching, not order of complexity, because looping at most 64 times is a linear-bounded operation. The methods I point out involve no branching! And so can be rather fast. I don't suggest they be used, but that the listsort.txt be revised. -- ___ Python tracker <https://bugs.python.org/issue46488> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue46488] listsort.txt wrongly assumes you cannot calculate leading zeros in O(1) time.
New submission from Barry Schwartz : The Objects/listsort.txt incorrectly implies that it is not possible to compute leading zero bits in O(1) time, using only standard C. For a fixed integer size it can be done, for instance, using de Bruijn sequences. See https://www.chessprogramming.org/BitScan (The existence of such methods is not as widely known as it ought to be.) -- assignee: docs@python components: Documentation messages: 411384 nosy: chemoelectric, docs@python priority: normal severity: normal status: open title: listsort.txt wrongly assumes you cannot calculate leading zeros in O(1) time. type: performance versions: Python 3.11 ___ Python tracker <https://bugs.python.org/issue46488> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
