[issue34561] Replace list sorting merge_collapse()?
Koos Zevenhoven added the comment: And by "looking at" Timsort, I mean reading your explanation. The motivation for merge ordering and so on was already quite clear from there. But that motivation does not imply that the stack has to be monotonous in run length, although memory considerations might. -- ___ Python tracker <https://bugs.python.org/issue34561> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue34561] Replace list sorting merge_collapse()?
Koos Zevenhoven added the comment: Sorry, I meant that the funny code in the "power" computation in powersort is a logarithmic measure. But I don't know where that came from. I just looked at Timsort and now figuring out how powersort is different. -- ___ Python tracker <https://bugs.python.org/issue34561> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue34561] Replace list sorting merge_collapse()?
Koos Zevenhoven added the comment: So it looks like we're working with a logarithmic measure of the "cost". I'm operating largely based on your description of Timsort in the link in msg324597, which the paper also refers to. But since the paper is sorting an array of Java ints (not Integers), I assume the performance comparisons of the code they timed is not really representative of Python equivalents. Probably galloping boosts are much larger in the Python case. I haven't tried running the attached code yet, because I mostly carry a tablet with me now. The never-equal assert probably doesn't get any more obvious by running the code, though, anyway?-). -- ___ Python tracker <https://bugs.python.org/issue34561> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue34561] Replace list sorting merge_collapse()?
Koos Zevenhoven added the comment: Haha ok. Cache optimization makes it pretty complicated to reason about true costs. Anyway, it’s not obvious to me even that the run lengths would need to be descending for best performace. I’m not even starting to think about how the merging order might affect galloping boosts on realistic data ;-). I didn’t get to that power thing at this point, but it looks like it’s unrelated to this consideration, except perhaps by chance. I might have time tonight to have a look at that. Surely we don’t want an algorithm that’s optimized for what they call ”Timsort drag” sequences in the literature ;-). -- ___ Python tracker <https://bugs.python.org/issue34561> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue34561] Replace list sorting merge_collapse()?
Koos Zevenhoven added the comment: It doesn’t seem like there’s a real problem here, but you seem to suggest there would be some useful improvements possible here. I don’t know much about sorting algorithms per se. What do you mean by galloping? -- nosy: +koos.zevenhoven ___ Python tracker <https://bugs.python.org/issue34561> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue33939] Provide a robust O(1) mechanism to check for infinite iterators
Koos Zevenhoven added the comment: That said, I agree with Antoine that being able to Ctrl-C would be the most useful of these fixes. But it seems clear that people are experiencing these issues differently (if at all). -- ___ Python tracker <https://bugs.python.org/issue33939> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue33939] Provide a robust O(1) mechanism to check for infinite iterators
Koos Zevenhoven added the comment: I'd say there are three different problems related to this: (1) The inability of infinite iterators/iterables to say anything about their length (2) The inability to interrupt C-level loops (3) The horrible consequences of things like list(itertools.count()) that fill up the memory The problems overlap only partially. Unfortunately, fixing any single one of these problems does not eliminate the two others. For example, (2) and (3) may happen just as well without the iterator protocol being involved. And (1) may just prevent you from checking if the iterable has enough elements for whatever you're doing. -- nosy: +koos.zevenhoven ___ Python tracker <https://bugs.python.org/issue33939> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue31815] Make itertools iterators interruptible
Koos Zevenhoven <k7ho...@gmail.com> added the comment: For the interactive user who uses an interactive environment such as the repl or a Jupyter notebook, the situation is a little different from "CPython as programming language runtime". The docs say a KeyboardInterrupt is "Raised when the user hits the interrupt key (normally Control-C or Delete). During execution, a check for interrupts is made regularly.". I suppose there's some ambiguity in what "regularly" means there ;). But regardless of whether anyone bothers to read that part of the docs, Ctrl-C or an interrupt button not working can feel like a correctness issue for someone that's using an interactive Python environment *as an application* in daily work. Python gives you the impression that you can always interrupt anything if it turns out to take too much time. And I remember that being one of the points that made me move away from matlab, which at that time had problems with interrupting computations. -- ___ Python tracker <rep...@bugs.python.org> <https://bugs.python.org/issue31815> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue31815] Make itertools iterators interruptible
Koos Zevenhoven <k7ho...@gmail.com> added the comment: To repeat one of my points in the linked threads, I'm not convinced that infinite iterators are the most common case for the problem of long uninterruptible loops. A general mechanism that can be easily used in many places with minimal maintenance burden would be nice. It could be used even in third-party extension modules. -- nosy: +koos.zevenhoven ___ Python tracker <rep...@bugs.python.org> <https://bugs.python.org/issue31815> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
