3

I have a very long lst containing unique elements. I want to design a function which takes a list of elements as the input and it can return a list of index efficiently. We assume the items needed to find their index are all in the lst.

Here is an example:

lst = ['ab','sd','ef','de']
items_to_find = ['sd', 'ef', 'sd']
>>> fo(lst, items_to_find)  
# Output: [1,2,1]

I have one solution of my own, but it looks less efficient.

>> [lst.index(x) for x in items_to_find]

Because the lst is very long, I need a very fast algorithm to solve it.

1
  • If you don't want to use a dictionary, another way would be to sort the list and then search for indexes using binary search. This won't be as fast as a dictionary though.
    – pgngp
    Commented Jan 18, 2018 at 20:49

5 Answers 5

8

First create a dictionary containing in the index location of each item in the list (you state that all items are unique, hence no issue with duplicate keys).

Then use the dictionary to look up each item's index location which is average time complexity O(1).

my_list = ['ab', 'sd', 'ef', 'de']
d = {item: idx for idx, item in enumerate(my_list)}

items_to_find = ['sd', 'ef', 'sd']

>>> [d.get(item) for item in items_to_find]
[1, 2, 1]
3
  • You could add a default value of -1 or None in the get method if the element is not found. Commented Jan 18, 2018 at 20:47
  • 1
    None is the default value of get when the key is not present in the dictionary, but yes, one could use another value if so desired.
    – Alexander
    Commented Jan 18, 2018 at 20:48
  • I would add also that a main main optimizations is to reduce multiple sequence.index() calls to a single sequence.enumerate(), reflecting a standard space vs time tradeoff.
    – cowbert
    Commented Jan 18, 2018 at 20:51
2

You could use a dictionary with elements from lst as the key and index and as the value. Search in a dictionary is O(1).

0

A simple first approximation...

def get_indices(data_list, query_list):
    datum_index_mapping = {datum:None for datum in query_list}
    for index, datum in enumerate(data_list):
        if datum in datum_index_mapping:
            datum_index_mapping[datum] = index
    return [datum_index_mapping[d] for d in query_list]

The above is the most simple, intuitive solution which makes some effort to be efficient (by only bothering to store a dictionary of indices for the elements you actually want to look up).

However, it suffers from the fact that- even if the initial query list is very short- it'll iterate through the entire data list / data generator. In addition, it has to do a dictionary write every time it sees a value it's seen before. The below fixes those inefficiencies, although it adds the overhead of a set, so it must do a set write for each unique element in the query list, as well as a dictionary write for each unique element in the query list.

def get_indices(data_list, query_list):
    not_found = set(query_list)
    datum_index_mapping = {}
    for index, datum in enumerate(data_list):
        if datum in not_found:
            datum_index_mapping[datum] = index
            not_found.remove(datum)
            if len(not_found) == 0:
                break
    return [datum_index_mapping[d] for d in query_list]

Obviously, depending on your program, you may not actually want to have a list of indices at all, but simply have your function return the mapping. If you'll be resolving multiple arbitrary query lists, you may want to simply do an enumerate() on the original dataset as other answers have shown and keep the dictionary that maps values to indices in memory as well for query purposes.

What counts as efficient often depends upon the larger program; all we can do here are pigeonhole optimizations. It also depends on whether the memory hierarchy and processing power (i.e. can we parallelize? Is compute more expensive, or is memory more expensive? What's the I/O hit if we need to fallback to swap?).

0

If you are sure all the searched values actually exist in the searching list and the lst is sorted (of course, the sorting itself might take some time), you can do that in one pass (linear complexity):

def sortedindex(lst,find):
    find.sort()
    indices  = []
    start = 0
    for item in find:
        start = lst.index(item,start)
        indices.append(start)
    return indices

The "start" shows the first index where the algorithm starts comparing the inspected item to the item in the main list. When the correct index is found, it will become the next starting mark. Because both lists are sorted in the same way, you do not have to worry that you skipped any of the next items.

-1

Although the answer you've accepted is very good, here's something that would be more memory efficient and is probably almost as fast. However @Alexander's answer creates a potentially huge dictionary if the list is very long (since the elements in it are all unique).

The code below also builds a dictionary to speed up searching, but it's for the target elements so is likely to be much smaller than the list being searched. For the sample data the one it creates (named targets) contains only: {'sd': [0, 2], 'ef': [1]}

It one pass through the sequence and checks each of the values in it are targets and, if so, updates the results list according. This approach requires a little more code to implement since the setup is slightly more involved, so that's another trade-off.

def find_indices(seq, elements):
    targets = {}
    for index, element in enumerate(elements):
        targets.setdefault(element, []).append(index)
    indices = [None for _ in elements]  # Pre-allocate.

    for location, value in enumerate(seq):
        if value in targets:
            for element, indexes in targets.items():
                if element == value:
                    for index in indexes:
                        indices[index] = location
    return indices

lst = ['ab', 'sd', 'ef', 'de']

indices = find_indices(lst, ['sd', 'ef', 'sd'])
print(indices)  # -> [1, 2, 1]

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.