What is a Pythonic way to search or manipulate sorted sequence?
Answers:
Thank you for visiting the Q&A section on Magenaut. Please note that all the answers may not help you solve the issue immediately. So please treat them as advisements. If you found the post helpful (or not), leave a comment & I’ll get back to you as soon as possible.
Method 1
bisect is part of the standard library – is that the sort of thing you’re looking for?
Method 2
It’s worth noting that there are a couple high-quality Python libraries for maintaining a sorted list which also implement fast searching: sortedcontainers and blist. Using these depends of course on how often you’re inserting/removing elements from the list and needing to search. Each of those modules provide a SortedList class which efficiently maintains the items in sort order.
From the documentation for SortedList:
L.bisect_left(value)
Similar to the bisect module in the standard library, this returns
an appropriate index to insert value in L. If value is already present
in L, the insertion point will be before (to the left of) any existing
entries.
L.bisect(value)
Same as bisect_left.
L.bisect_right(value)
Same as bisect_left, but if value is already present in L, the
insertion point will be after (to the right of) any existing entries.
Both implementations use binary search to find the correct index of the given value. There’s a performance comparison page for choosing between the two modules.
Disclaimer: I am the author of the sortedcontainers module.
Method 3
Python:
import bisect
def find_in_sorted_list(elem, sorted_list):
# https://docs.python.org/3/library/bisect.html
'Locate the leftmost value exactly equal to x'
i = bisect.bisect_left(sorted_list, elem)
if i != len(sorted_list) and sorted_list[i] == elem:
return i
return -1
def in_sorted_list(elem, sorted_list):
i = bisect.bisect_left(sorted_list, elem)
return i != len(sorted_list) and sorted_list[i] == elem
L = ["aaa", "bcd", "hello", "world", "zzz"]
print(find_in_sorted_list("hello", L)) # 2
print(find_in_sorted_list("hellu", L)) # -1
print(in_sorted_list("hellu", L)) # False
All methods was sourced from stackoverflow.com or stackexchange.com, is licensed under cc by-sa 2.5, cc by-sa 3.0 and cc by-sa 4.0