3 ms·
The first Python implementation is bad - removing the first element in each iteration is O(n), the C implementation gets this right by maintaining one index int
by danbruc 5y ago
The first Python implementation is bad - removing the first element in each iteration is O(n), the C implementation gets this right by maintaining one index into each list instead of modifying the lists.
- XelNika 5y agoYes, it says so in footnote 1 in the article. It's also not the benchmarked code so it doesn't really matter.
- danbruc 5y agoI missed the footnote. My point was more that one could have compared this with the C implementation as heapq.merge is a different algorithm and so there is no actual comparison of the same algorithm in C and Python.
- min-cut 5y agoNot only that, but also list(a + b) is producing two different new lists since (a + b) produces a list and list() constructs a new list copy. The benchmark would be faster if the OP just did def sort_test(): m2 = a + b; m2.sort() instead of def sort_test(): m2 = list(a + b); m2.sort() EDIT: It seems like OP fixed this issue in perf.py, but left it in test.py
- agbell 5y agoYou can check it, but I'm pretty sure the difference is negligible. But yeah, all benchmarks are using the code in perf and the pop code is just to demonstrate. It is not benched. Edit: dropping the extra list() from the blog code examples.
- min-cut 5y agoI see about a 10% performance improvement on my local machine on the input in test.py when not constructing the unnecessary second list. I don't really buy that it reads nicer in prose since you can just do (a + b).sort() if you want. Plus, I feel like it's important for readability to not be unnecessarily redundant. Having list(a + b) code also risks creating misconceptions about how lists can be constructed and used in Python.
- agbell 5y agoYeah, good point. I think you are right about it being incorrect. Updating...