Created on 2014-12-07 22:43 by Sergey.Litvinov, last changed 2022-04-11 14:58 by admin. 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) *  |
Date: 2014-12-08 09:32 |
| What troubles? |
|
|
| msg232319 - (view) |
Author: Mark Dickinson (mark.dickinson) * |
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) * |
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) * |
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) * |
Date: 2014-12-11 14:22 |
| Sergey: thanks for the response. Closing. |
|
|
| History |
|
|
|
| Date |
User |
Action |
Args |
| 2022-04-11 14:58:10 |
admin |
set |
github: 67196 |
| 2014-12-11 14:24:36 |
mark.dickinson |
set |
stage: resolved |
| 2014-12-11 14:22:47 |
mark.dickinson |
set |
status: open -> closedmessages: + |
| 2014-12-11 14:00:40 |
Sergey.Litvinov |
set |
messages: + |
| 2014-12-09 10:14:47 |
rhettinger |
set |
status: pending -> openmessages: + |
| 2014-12-09 09:52:17 |
mark.dickinson |
set |
status: open -> pendingresolution: not a bugversions: + Python 3.4, - Python 3.6 |
| 2014-12-09 08:26:14 |
mark.dickinson |
set |
messages: + |
| 2014-12-08 17:37:49 |
mark.dickinson |
set |
messages: + |
| 2014-12-08 09:32:49 |
serhiy.storchaka |
set |
nosy: + serhiy.storchakamessages: + |
| 2014-12-08 00:42:59 |
pitrou |
set |
nosy: + rhettinger, mark.dickinson |
| 2014-12-07 22:43:11 |
Sergey.Litvinov |
create |
|