Блог

У меня есть список длиной в миллион элементов из случайных, повторяемых целых чисел. Мне нужно отсортировать этот список, а затем найти индекс первой итерации каждого уникального элемента в списке. Когда я делаю это, у меня время выполнения превышает 5 минут. Кто-нибудь может дать мне какие-либо предложения по ускорению моего кода? Пример моего процесса показан ниже.

 import random

a = []
for x in range(1000000):
    a.append(random.randint(1,10000))
unique_a = set(a)
inds=[0]
inds = [a.index(i) for i in sorted(unique_a) if i not in inds]
  

inds = [a.index(i) for i in sorted(unique_a) if i not in inds] неявно квадратичный является a.index(i) линейным. Используйте словарь для захвата индексов за один проход по отсортированному списку:

 a =sorted([0,4,3,5,21,5,6,3,1,23,4,6,1,93,34,10])
unique_a = set(a)
first_inds = {}
for i,x in enumerate(a):
    if not x in first_inds:
        first_inds[x] = i
my_inds = [first_inds[x] for x in sorted(unique_a)]
  

Просто сохраняйте первую позицию для каждого уникального элемента:

 first_position = {}
for i, value in enumerate(a):
    if value not in first_position:
        first_position[value] = i
  

А затем замените a.index(i) на first_position[i]

Или просто используйте:

_, indices = zip(*sorted(first_position.items()))

Для этого вы можете использовать bisect_left функцию из модуля bisect стандартной библиотеки. В отсортированном списке поиск с разделением пополам выполняется быстрее, чем поиск по списку, как это делает index .

 >>> L = [random.randint(0, 10) for _ in range(100)]
>>> L.sort()
>>> L.index(9)
83
>>> bisect.bisect_left(L, 9)
83

>>> timeit.timeit(setup="from __main__ import L", stmt="L.index(9)")
2.1408978551626205
>>> timeit.timeit(setup="from __main__ import L;from bisect import bisect_left", stmt="bisect_left(L, 9)")
0.5187544231303036
  

На моей машине использование bisect.bisect_left быстрее, чем перебор списка и накопление индексов по пути:

 >>> L = [random.randint(0, 100) for _ in range(10000)]
>>> L.sort()
>>> def iterative_approach(list_):
...     unique = set(list_)
...     first_inds = {}
...     for i, x in enumerate(list_):
...         if x not in first_inds:
...             first_inds[x] = i
...     return [first_inds[x] for x in sorted(unique)]
... 
>>> ia = iterative_approach(L)

>>> bisect_left = bisect.bisect_left
>>> def bisect_approach(list_):
...     unique = set(list_)
...     out = {}
...     for x in unique:
...         out[x] = bisect_left(list_, x)
...     return [out[x] for x in sorted(unique)]
... 
>>> ba = bisect_approach(L)
>>> ia == ba
True


>>> timeit.timeit(setup="from __main__ import L, iterative_approach", stmt="iterative_approach(L)")
1488.956467495067
>>> timeit.timeit(setup="from __main__ import L, bisect_approach", stmt="bisect_approach(L)")
407.6803469741717