classification
Title: Unnecessary big intermediate result in Lib/bisect.py
Type: behavior Stage: resolved
Components: Library (Lib) Versions: Python 3.4, Python 2.7
process
Status: closed Resolution: not a bug
Dependencies: Superseder:
Assigned To: Nosy List: Sergey.Litvinov, mark.dickinson, rhettinger, serhiy.storchaka
Priority: normal Keywords:

Created on 2014-12-07 22:43 by Sergey.Litvinov, last changed 2014-12-11 14:24 by mark.dickinson. This issue is now closed.

Messages (7)
msg232286 - (view) Author: Sergey Litvinov (Sergey.Litvinov) Date: 2014-12-07 22:43
Bisection algorithms use
mid = (lo+hi)//2

Textbook formula is
mid = (hi-lo)//2 + lo

See
http://en.wikipedia.org/w/index.php?title=Binary_search_algorithm&oldid=634658510#Arithmetic

For "vanilla" lists and integers it is not a problem but one can run
into troubles with user defined types.
msg232299 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2014-12-08 09:32
What troubles?
msg232319 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2014-12-08 17:37
> What troubles?

Well, I imagine that something like "bisect(a, 155, lo=numpy.uint8(0), hi=numpy.uint8(254))" would be asking for trouble.  But (a) it's hard to imagine why anyone would want to do that given that NumPy has its own bisection code, and (b) you'd have to somehow make sure that you were using the plain Python bisect code and not the `_bisect` module code, which AFAIK does the right thing here.

Sergey: what troubles have you run into?  With what user-defined types?  Note that if you just do "from bisect import *" at a Python prompt, you're not even using the code in Lib/bisect.py: the main implementation is written in C.
msg232352 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2014-12-09 08:26
Sergey: do you have an example of the Lib/bisect.py code causing problems in real (non-contrived) code?  If not, I'd suggest closing this report as "not a bug".
msg232360 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2014-12-09 10:14
I agree with Mark.  This code is *very* old and AFAICT it has never caused a problem in practice.   

The "textbook" formula is more important in languages without something like Python long ints.  In Python, "textbook" form just slows down and obfuscates the intention of the code.
msg232477 - (view) Author: Sergey Litvinov (Sergey.Litvinov) Date: 2014-12-11 14:00
mark.dickinson> do you have an example of the Lib/bisect.py code

No. I was thinking about something hypothetical similar to the one you
provided.

rhettinger> The "textbook" formula is more important in languages
rhettinger> without something like Python long ints.  In Python,
rhettinger> "textbook" form just slows down and obfuscates the intention
rhettinger> of the code.

I agree and do not object to closing the report.
msg232478 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2014-12-11 14:22
Sergey: thanks for the response.  Closing.
History
Date User Action Args
2014-12-11 14:24:36mark.dickinsonsetstage: resolved
2014-12-11 14:22:47mark.dickinsonsetstatus: open -> closed

messages: + msg232478
2014-12-11 14:00:40Sergey.Litvinovsetmessages: + msg232477
2014-12-09 10:14:47rhettingersetstatus: pending -> open

messages: + msg232360
2014-12-09 09:52:17mark.dickinsonsetstatus: open -> pending
resolution: not a bug
versions: + Python 3.4, - Python 3.6
2014-12-09 08:26:14mark.dickinsonsetmessages: + msg232352
2014-12-08 17:37:49mark.dickinsonsetmessages: + msg232319
2014-12-08 09:32:49serhiy.storchakasetnosy: + serhiy.storchaka
messages: + msg232299
2014-12-08 00:42:59pitrousetnosy: + rhettinger, mark.dickinson
2014-12-07 22:43:11Sergey.Litvinovcreate