Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

small change at bisect_left function for easy understanding #82807

Closed
Windsooon mannequin opened this issue Oct 29, 2019 · 4 comments
Closed

small change at bisect_left function for easy understanding #82807

Windsooon mannequin opened this issue Oct 29, 2019 · 4 comments
Labels
3.8 only security fixes stdlib Python modules in the Lib dir

Comments

@Windsooon
Copy link
Mannequin

Windsooon mannequin commented Oct 29, 2019

BPO 38626
Nosy @tim-one, @rhettinger, @miss-islington, @Windsooon
PRs
  • bpo-38626: Add comment explaining why __lt__ is used. #16978
    		•

    Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.

    Show more details

    GitHub fields:

    assignee = None
closed_at = <Date 2019-10-29.03:30:28.840>
created_at = <Date 2019-10-29.03:03:16.796>
labels = ['3.8', 'library']
title = 'small change at bisect_left function for easy understanding'
updated_at = <Date 2019-10-29.04:38:56.486>
user = 'https://github.com/Windsooon'

    bugs.python.org fields:

    activity = <Date 2019-10-29.04:38:56.486>
actor = 'miss-islington'
assignee = 'none'
closed = True
closed_date = <Date 2019-10-29.03:30:28.840>
closer = 'rhettinger'
components = ['Library (Lib)']
creation = <Date 2019-10-29.03:03:16.796>
creator = 'Windson Yang'
dependencies = []
files = []
hgrepos = []
issue_num = 38626
keywords = []
message_count = 4.0
messages = ['355606', '355607', '355608', '355612']
nosy_count = 4.0
nosy_names = ['tim.peters', 'rhettinger', 'miss-islington', 'Windson Yang']
pr_nums = ['16978']
priority = 'normal'
resolution = 'rejected'
stage = 'resolved'
status = 'closed'
superseder = None
type = None
url = 'https://bugs.python.org/issue38626'
versions = ['Python 3.8']
    @Windsooon
    Copy link
    Mannequin Author

    Windsooon mannequin commented Oct 29, 2019

    bisect_left should be similar to bisect_right. However, the current implement didn't reflect it. A little bit update for the bisect_left function could make the user easy to understand their relation.

    def bisect_left(a, x, lo=0, hi=None):
    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        # <= should be the only difference between bisect_left and bisect_right
        if x <= a[mid]: hi = mid
        else: lo = mid+1
    return lo

    @Windsooon Windsooon mannequin added 3.8 only security fixes stdlib Python modules in the Lib dir labels Oct 29, 2019
    @rhettinger rhettinger self-assigned this Oct 29, 2019
    @tim-one
    Copy link
    Member

    tim-one commented Oct 29, 2019

    So as far as possible, CPython only uses __lt__ ("<") element comparisons for its order-sensitive algorithms. This is documented for list.sort(), but the bisect and heapq modules strive to do the same.

    The point is to minimize the number of comparison methods a new type needs to implement to participate (and "just one: __lt__" is ideal).

    Your change would require they implement "__le__" too, so is unlikely to be accepted for CPython.

    @rhettinger
    Copy link
    Contributor

    I concur with Tim.

    Thank you for the suggestion though.

    @miss-islington
    Copy link
    Contributor

    New changeset 3c88199 by Miss Skeleton (bot) (Raymond Hettinger) in branch 'master':
    bpo-38626: Add comment explaining why __lt__ is used. (GH-16978)
    3c88199

    @ezio-melotti ezio-melotti transferred this issue from another repository Apr 10, 2022
    Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
    Assignees
    No one assigned
    Labels
    3.8 only security fixes stdlib Python modules in the Lib dir
    Projects
    None yet
    Milestone
    No milestone
    Development

    No branches or pull requests
    3 participants
    @rhettinger @tim-one @miss-islington