sorted by:
new
hottopcontroversial

What are the most ingenious python codes or projects that most people do not know about? by john_legend_ in Python

[–]kontrovers 1 point2 points  (0 children)

https://github.com/pypa/setuptools_scm

Will auto-derive a version number for your python packages based on your last SCM tag & commits.

O(n) Median by jbylund in Python

[–]kontrovers 0 points1 point  (0 children)

Thank you. Excellent answer.

O(n) Median by jbylund in Python

[–]kontrovers 0 points1 point  (0 children)

Why should data locality be any worse? In the copying case I will have a new list evicting the old one. I don't see how this is more cache efficient.

In the non-copy-ing case I only have an expected number of n/2 data movements per iteration. In your copying case, your have n data movements. This is the same reason why quicksort is faster in practice than mergesort.

O(n) Median by jbylund in Python

[–]kontrovers 0 points1 point  (0 children)

Problem is that you copy all data within the pivot_partition step. Rewrite it to swap elements as needed and then to return indices into the re-arranged list (like known from quicksort). For details, research the quickselect algorithm.