Is O(n + log n) really a thing or should he just write O(n)?
I should just write O(n).
Thanks for catching the mistake, @dmurray. I'll fix that.
Using Python's Bisect Module
11–14 of 14 posts
Re: Using Python's Bisect Module
#12Earlier quoted context omitted.
Interesting to see the module defines a pure Python implementation first, then tries to import a fast C implementation. If the C version is present, it replaces the Python version. Bisect is a very old module, certainly present in Python 1.5.2 from 1999 that I started with. I expect the C implementations got added a year or two later.
Yes, but now I want to know: 1. Is there a C version? I don't see it in the same directory. 2. If there is a C version, does anyone who submits a PR (like the one in 2019 adding 'key'[0]) have to submit a C version along with it? [0] https://bugs.python.org/issue4356
The C version is in Modules/_bisectmodule.c, whereas the Python version is in Lib/bisect.py.
Python version: https://github.com/python/cpython/blob/master/Lib/bisect.py
C version: https://github.com/python/cpython/blob/master/Modules/_bisec...
Re: Using Python's Bisect Module
#13Earlier quoted context omitted.
Yes, but now I want to know: 1. Is there a C version? I don't see it in the same directory. 2. If there is a C version, does anyone who submits a PR (like the one in 2019 adding 'key'[0]) have to submit a C version along with it? [0] https://bugs.python.org/issue4356
The C version is in Modules/_bisectmodule.c, whereas the Python version is in Lib/bisect.py. Python version: https://github.com/python/cpython/blob/master/Lib/bisect.py C version: https://github.com/python/cpython/blob/master/Modules/_bisec...
Thanks. So it seems both were updated with 'key' at the same time: https://github.com/python/cpython/commit/871934d4cf00687b3d1...
Now I'm wondering - what is the point of the python version, if it will always be overridden by the C implementation? Are there circumstances (platforms, compile flags, ...) under which the C version would be unavailable when the python runtime is compiled?
Re: Using Python's Bisect Module
#14Earlier quoted context omitted.
The C version is in Modules/_bisectmodule.c, whereas the Python version is in Lib/bisect.py. Python version: https://github.com/python/cpython/blob/master/Lib/bisect.py C version: https://github.com/python/cpython/blob/master/Modules/_bisec...
Thanks. So it seems both were updated with 'key' at the same time: https://github.com/python/cpython/commit/871934d4cf00687b3d1... Now I'm wondering - what is the point of the python version, if it will always be overridden by the C implementation? Are there circumstances (platforms, compile flags, ...) under which the C version would be unavailable when the python runtime is compiled?
It may be that other Python implementations use CPython's standard library, or at least part of it.
I think that PyPy in particular does this, but I'm not 100% sure. I know for certain that it uses pure Python implementation of some modules from somewhere. One program I took great pains to be PyPy compatible ended up being a lot slower in it, and it turned out to be that the built-in sqlite3 module has a C implementation in CPython that's faster than the pure-Python version even when runing in PyPy.