Что ж, есть хороший шанс, что bisect_left - это операция O(logN) (бинарный поиск), поэтому ваша общая операция будет O(KlogN) where N relates to size of l, and K relates to size of m.
Если бы также был отсортирован второй список m, Вы можете сделать эту операцию O(N) просто запустив индекс по обоим спискам одновременно.
Но, если ваш комментарий "I подозреваемый это медленный", ваш первый шаг должен всегда для тестирования самого простого решения с наибольшим ожидаемым набором данных. Если это выполнимо, остановитесь прямо здесь! Только если она недостаточна, вы начинаете думать об оптимизации.
Например, рассмотрите следующую программу:
import random
import bisect
haystack = []
for _ in range(1000000):
haystack.append(random.random())
haystack.sort()
needles = []
for _ in range(10000):
needles.append(random.random())
result = [bisect.bisect_left(haystack, needle) for needle in needles]
print(result)
Это создаст стог сена в 1 000 000 элементов и список игл из 10 000 элементов, а затем использует ваше понимание списка bisect для выполнения работы. Выполнение этого на моем (не особенно грубом) рабочем столе с time показывает:
real 0m0.738s # < 3/4 of a second elapsed
user 0m0.578s
sys 0m0.109s
И это включает время, необходимое для создания списков, сортировки большого и распечатки результаты.
Использование timeit для избавления от всего этого времени установки может быть выполнено с помощью:
import timeit
import random
import bisect
haystack = []
for _ in range(1000000):
haystack.append(random.random())
haystack.sort()
needles = []
for _ in range(10000):
needles.append(random.random())
print(timeit.timeit('[bisect.bisect_left(haystack, needle) for needle in needles]', setup = 'from __main__ import bisect, haystack, needles', number = 1000))
Вывод этого 12.27 для тысячи итераций Это означает, что вы можете делать это примерно 75 раз в секунду, не потея.