BOOKPYTHON Telegram 3451
Если вам нужно выполнить поиск в отсортированной коллекции, то бинарный поиск — это именно то, что вам нужно. Этот простой алгоритм сравнивает искомое значение с элементом в середине массива; результат определяет, какую половину нужно искать дальше.

Стандартная библиотека Python предоставляет возможность использовать бинарный поиск без его непосредственной реализации. Функция bisect_left возвращает самую левую позицию элемента в отсортированном списке, а bisect_right — самую правую.


from random import randrange
from bisect import bisect_left

n = 1000000
look_for = 555555
lst = sorted(randrange(0, n) for _ in range(n))

%timeit look_for in lst
# 69.7 ms ± 449 µs на цикл

%timeit look_for == lst[bisect_left(lst, look_for)]
# 927 ns ± 2.28 ns на цикл


Результаты демонстрируют, что использование бинарного поиска через bisect_left быстрее, чем стандартный поиск в списке с помощью оператора in.

👉 @BookPython
👍81



tgoop.com/BookPython/3451
Create:
Last Update:

Если вам нужно выполнить поиск в отсортированной коллекции, то бинарный поиск — это именно то, что вам нужно. Этот простой алгоритм сравнивает искомое значение с элементом в середине массива; результат определяет, какую половину нужно искать дальше.

Стандартная библиотека Python предоставляет возможность использовать бинарный поиск без его непосредственной реализации. Функция bisect_left возвращает самую левую позицию элемента в отсортированном списке, а bisect_right — самую правую.


from random import randrange
from bisect import bisect_left

n = 1000000
look_for = 555555
lst = sorted(randrange(0, n) for _ in range(n))

%timeit look_for in lst
# 69.7 ms ± 449 µs на цикл

%timeit look_for == lst[bisect_left(lst, look_for)]
# 927 ns ± 2.28 ns на цикл


Результаты демонстрируют, что использование бинарного поиска через bisect_left быстрее, чем стандартный поиск в списке с помощью оператора in.

👉 @BookPython

BY Библиотека Python разработчика | Книги по питону


Share with your friend now:
tgoop.com/BookPython/3451

View MORE
Open in Telegram


Telegram News

Date: |

fire bomb molotov November 18 Dylan Hollingsworth yau ma tei You can invite up to 200 people from your contacts to join your channel as the next step. Select the users you want to add and click “Invite.” You can skip this step altogether. Clear Find your optimal posting schedule and stick to it. The peak posting times include 8 am, 6 pm, and 8 pm on social media. Try to publish serious stuff in the morning and leave less demanding content later in the day. In the “Bear Market Screaming Therapy Group” on Telegram, members are only allowed to post voice notes of themselves screaming. Anything else will result in an instant ban from the group, which currently has about 75 members.
from us


Telegram Библиотека Python разработчика | Книги по питону
FROM American