lookup function for repeated elements in an array

user_5431734 0
Viewed 343

I have a list-like python object of positive integers and I want to get which locations on that list have repeated values. For example if input is [0,1,1] the function should return [1,2] because the value of 1, which is the element at position 1 and 2 of the input array appears twice. Similarly:

[0,13,13] should return [[1, 2]]

[0,1,2,1,3,4,2,2] should return [[1, 3], [2, 6, 7]] because 1 appears twice, at positions [1, 3] of the input array and 2 appears 3 times at positions [2, 6, 7]

[1, 2, 3] should return an empty array []

What I have written is this:

def get_locations(labels):
    out = []
    label_set = set(labels)
    for label in list(label_set):
        temp = [i for i, j in enumerate(labels) if j == label]
        if len(temp) > 1:
            out.append(np.array(temp))

    return np.array(out)

While it works ok for small input arrays it gets too slow when size grows. For instance, The code below on my pc, skyrockets from 0.14secs when n=1000 to 12secs when n = 10000

from timeit import default_timer as timer
start = timer()
n = 10000
a = np.arange(n)
b = np.append(a, a[-1]) # append the last element to the end
out = get_locations(b)
end = timer()
print(out)
print(end - start) # Time in seconds

How can I speed this up please? Any ideas highly appreciated

big-o python-3.x numpy arrays python
5 Answers

Your nested loop results in O(n ^ 2) in time complexity. You can instead create a dict of lists to map indices to each label, and extract the sub-lists of the dict only if the length of the sub-list is greater than 1, which reduces the time complexity to O(n):

def get_locations(labels):
    positions = {}
    for index, label in enumerate(labels):
        positions.setdefault(label, []).append(index)
    return [indices for indices in positions.values() if len(indices) > 1]

so that get_locations([0, 1, 2, 1, 3, 4, 2, 2]) returns:

[[1, 3], [2, 6, 7]]
user_68909120

Your code is slow because of the nested for-loop. You can solve this in a more efficient way by using another data structure:

from collections import defaultdict
mylist = [0,1,2,1,3,4,2,2]

output = defaultdict(list)
# Loop once over mylist, store the indices of all unique elements
for i, el in enumerate(mylist):
    output[el].append(i)

# Filter out elements that occur only once
output = {k:v for k, v in output.items() if len(v) > 1}

This produces the following output for your example b:

{1: [1, 3], 2: [2, 6, 7]}

You can turn this result into the desired format:

list(output.values())
> [[1, 3], [2, 6, 7]]

Know however that this relies on the dictionary being insertion ordered, which is only the case as of python 3.6.

user_54953810

Heres a code i implemented. It runs in linear time:

l = [0,1,2,1,3,4,2,2]
dict1 = {}

for j,i in enumerate(l): # O(n)
    temp = dict1.get(i) # O(1) most cases
    if not temp:
        dict1[i] = [j]
    else:
        dict1[i].append(j) # O(1) 

print([item for item in dict1.values() if len(item) > 1]) # O(n)

Output:

[[1, 3], [2, 6, 7]]
user_91345280

This is essentially a time-complexity issue. Your algorithm has nested for loops that iterate through the list twice, so the time complexity is of the order of n^2, where n is the size of the list. So when you multiply the size of the list by 10 (from 1,000 to 10,000), you see an approximate time increase of 10^2 = 100. This is why it goes from 0.14 s to 12 s.

Here is a simple solution with no extra libraries required:

def get_locations(labels):
    locations = {}
    for index, label in enumerate(labels):
        if label in locations:
            locations[label].append(index)
        else:
            locations[label] = [index]

    return [locations[i] for i in locations if len(locations[i]) > 1]

Since the for loops are not nested, the time complexity is approximately 2n, so you should see about a 4-times increase in time whenever the problem size is doubled.

user_63174300

you can try using "Counter" function from "collections" module

from collections import Counter
list1 = [1,1,2,3,4,4,4]
Counter(list1)

you will get an output similar to this

Counter({4: 3, 1: 2, 2: 1, 3: 1})
user_70431430
Related