Блог

Главная - Вопросы по программированию - bisect.bisect_right() в 3~4 раза быстрее, чем у меня

bisect.bisect_right() в 3~4 раза быстрее, чем у меня

#python

Вопрос:

Я написал свой bisect_right(). Это в 3 раза медленнее, чем bisect.bisect_right().

 def my_bisect_right(a, num):
  ok = len(a)
  ng = -1
  while abs(ok - ng) > 1:
    mid = (ok   ng) // 2
    if a[mid] <= num:
      ng = mid
    else:
      ok = mid
  return ok

Я создал список из 10 миллионов целых чисел и запустил bisect_right() против него.
Bisect.bisect_right() занял 24,82 секунды, в то время как my_bisect_right() занял 76,30 секунды.
Пожалуйста, дайте мне знать, что я делаю не так…

Комментарии:

1. вероятно abs() , в вашем состоянии в то время, как они мало чем отличаются друг от друга — github.com/python/cpython/blob/…

2. Спасибо. после удаления abs () я получил 58,23 секунды в том же списке размеров.

3. bisect Написан ли модуль на Python или C?

4. Сколько раз вы публиковали отдельные испытания или они усреднены по нескольким испытаниям?

5. усредненный. как я могу узнать, написан ли модуль bisect на Python или C? Я думал, что это написано на Python…

Ответ №1:

Предполагая, что вы используете CPython и _bisect он доступен, самая большая разница заключается в том, что bisect.bisect_right() реализован в C. Смотрите эти строки в bisect.py :

 # Overwrite above definitions with a fast C implementation
try:
    from _bisect import *
except ImportError:
    pass

Для справки, вы можете легко проверить, реализована ли функция на Python или C, по ее повторению:

 >>> import bisect
>>> bisect.bisect_right  # C
<built-in function bisect_right>
>>> import functools
>>> functools.wraps  # Python
<function wraps at 0x000001DDAB175F70>
Метки: ,