CODEWITHSUNDEEP
pythonlistcounting
jamborta
jamborta

Reputation: 5210

Assign unique id to list of lists in python where duplicates get the same id

I have a list of lists (which can contain up to 90k elements)

[[1,2,3], [1,2,4], [1,2,3], [1,2,4], [1,2,5]]

I would like to assign an id to each elements, where the id is unique, except when the item is duplicated. So for the list above, I'd need this back:

[0,1,0,1,2]

What is the most effective way to do this?

Upvotes: 8

Views: 4589

Answers (3)

jamborta
jamborta

Reputation: 5210

I slight modification of Bakuriu's solution that works only with numpy arrays, it works better in terms of memory footprint and computation (as it does need to cast arrays to tuples):

from itertools import count
from collections import defaultdict
from functools import partial

def hashing_v1(seq):
    mapping = defaultdict(partial(next, count()))
    return [mapping[tuple(el)] for el in seq]

def hashing_v2(seq):
    mapping = defaultdict(partial(next, count()))
    result = []
    for le in seq:
        le.flags.writeable = False
        result.append(mapping[le.data])
    return result

In [4]: seq = np.random.rand(50000, 2000)

In [5]: %timeit hashing_v1(seq)
1 loop, best of 3: 14.1 s per loop

In [6]: %timeit hashing_v2(seq)
1 loop, best of 3: 1.2 s per loop

Upvotes: 0

RoadRunner
RoadRunner

Reputation: 26315

This is how I approached it:

from itertools import product
from random import randint
import time

t0 = time.time()
def id_list(lst):
    unique_set = set(tuple(x) for x in lst)
    unique = [list(x) for x in unique_set]
    unique.sort(key = lambda x: lst.index(x))

    result = [unique.index(i[1]) for i in product(lst, unique) if i[0] == i[1]]

    return result

seq = [[randint(1, 5), randint(1, 5), randint(1, 5)] for i in range(90000)]

print(id_list(seq))

t1 = time.time()

print("Time: %.4f seconds" % (t1-t0))

Which prints out the sequence of ids, along with an approximate time it took to compute a sequence of random integers in a list between 1 and 4, 90000 times. 

Time: 2.3397 seconds  # Will slightly differ from computation to computation

The actual time will always be a bit higher, since it needs to be accounted for in the print statement at the end, but it should not be too much of a difference.

I also used the time library to label the time intervals between the start and the end of the code block.

import time

t0 = time.time()

# code block here

t1 = time.time()

# Difference in time: t1 - t0

The itertools library along with product used in the code segment will speed up the computation too.

Upvotes: 1

Bakuriu
Bakuriu

Reputation: 101929

Keep a map of already seen elements with the associated id.

from itertools import count
from collections import defaultdict


mapping = defaultdict(count().__next__)
result = []
for element in my_list:
    result.append(mapping[tuple(element)])

you could also use a list-comprehension:

result = [mapping[tuple(element)] for element in my_list]

Unfortunately lists aren't hashable so you have to convert them to a tuple when storing them as keys of the mapping.

Note the trick of using defaultdict, and count().__next__ to provide unique increasing ids. On python2 you have to replace .__next__ with .next.

The defaultdict will assign a default value when it cannot find a key. The default value is obtained by calling the function provided in the constructor. In this case the __next__ method of the count() generator yields increasing numbers.

As a more portable alternative you could do:

from functools import partial

mapping = defaultdict(partial(next, count()))

An alternative solution, as proposed in the comments, is to just use the index as unique id:

result = [my_list.index(el) for el in my_list]

This is imple however:

  • It takes O(N^2) time instead of O(N)
  • The ids are unique, increasing but not consecutive (which may or may not be a problem)

For comparison of the two solutions see:

In [1]: from itertools import count
   ...: from collections import defaultdict

In [2]: def hashing(seq):
   ...:         mapping = defaultdict(count().__next__)
   ...:         return [mapping[tuple(el)] for el in seq]
   ...: 

In [3]: def indexing(seq):
   ...:    return [seq.index(i) for i in seq]
   ...: 

In [4]: from random import randint

In [5]: seq = [[randint(1, 20), randint(1, 20), randint(1, 20)] for _ in range(90000)]

In [6]: %timeit hashing(seq)
10 loops, best of 3: 37.7 ms per loop

In [7]: %timeit indexing(seq)
1 loop, best of 3: 26 s per loop

Note how for a 90k element list the mapping solution takes less 40 milliseconds while the indexing solution takes 26 seconds.

Upvotes: 10

Related Questions