CODEWITHSUNDEEP
pythonsearch
RocketSocks22
RocketSocks22

Reputation: 411

Improving index search speed in a large (million entry) list

I have a list which is a million items long of random, repeatable integers. I need to sort that list, and then find the index of the first iteration of every unique element in the list. When I do this, I am running into run time >5 minutes long. Can anyone give me any suggestions to speed up my code? An example of my process is shown below.

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]

Upvotes: 2

Views: 492

Answers (3)

snakecharmerb
snakecharmerb

Reputation: 55600

You can use the bisect_left function from the standard library's bisect module to do this. On a sorted list, a bisection search is faster than searching through the list as index does.

>>> 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

On my machine, using bisect.bisect_left is faster than iterating over the list and accumulating indexes on the way:

>>> 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

Upvotes: 1

lcastillov
lcastillov

Reputation: 2153

Just store the first position for every unique element:

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

And then replace a.index(i) for first_position[i]

Or just use:

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

Upvotes: 3

John Coleman
John Coleman

Reputation: 51998

inds = [a.index(i) for i in sorted(unique_a) if i not in inds] is implicitly quadratic is a.index(i) is linear. Use a dictionary to grab the indices in one pass over the sorted list:

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)]

Upvotes: 3

Related Questions