Find a number in list of lists

Question

I have nested list of numbers

my_list = [[0,1,2,3,4,5],[6,7,8,9,10,11],[12,56,86,9],[55,53,12]]

and I would like to know to which sublists a given number belongs to

For instance, if I'm searching for the number 1

the algorithm should return 0, because 1 belong the first sub-list.

If I'm looking for 9, I should get 1 and 2.

I've seen there's already a solution here Python search in lists of lists

but the problem is that I'm working with a very large number of lists and loops are not the best solution.

Is there any build-in python function that may come in handy?

Use a [generator](http://stackoverflow.com/questions/231767/what-does-the-yield-keyword-do-in-python/231855#231855). Look at the bottom answers in the question you provided. — RickyA, Aug 29 '14 at 13:56
*Why* are loops not the best solution? What property does your data structure have that makes it possible to find the element without looping? — Emil Vikström, Aug 29 '14 at 13:56
Will you be finding multiple items (such that the up-front cost of making `set`s is outweighed by the benefits of `O(1)` membership tests)? — jonrsharpe, Aug 29 '14 at 14:00

score 2 · Answer 1 · answered Aug 29 '14 at 14:00

You can use a list comprehension as shown in the example below. For each list it checks whether the numerical value is within the list. Note that this still uses iteration (in the form of a list comprehension) but unless you use something like numpy (which is not built-in) then you're going to have to iterate.

my_list = [[0,1,2,3,4,5],[6,7,8,9,10,11],[12,56,86,9],[55,53,12]]

def find(my_list, number):
    return [i for i, x in enumerate(my_list) if number in x]

print(find(my_list, 9))
# [1, 2]

score 0 · Answer 2 · answered Aug 29 '14 at 14:00

0

You could use list comprehension, however not sure that it will be better optimize than a loop :

def search(my_list, n)
  result = [i for i in range(len(my_list)) if n in my_list[i]]
  return result

answered Aug 29 '14 at 14:00

Gabz

124
3

score 0 · Answer 3 · answered Aug 29 '14 at 14:24

Optimization is an interesting topic and can have many different approaches depending on the problem.

In this case if the data is ordered then you can can start using assumptions to minimize the amount of times you need to use the expensive in keyword.

ie, make each sublist in chronological and order these list of lists based on the first element.

so first make a sort function that operates like so (I'll leave that to you)

>>> my_list = [[0,1,2,3,4,5],[6,7,8,9,10,11],[12,56,86,9],[55,53,12]]
>>> my_sort_func(my_list)
>>> print my_list
[[0,1,2,3,4,5],[6,7,8,9,10,11],[9,12,56,86],[12,53,55]]

Now you can design a more streamlined search function

/*
* @pre my_list is sorted
*/
def search(my_list, key):
    result = []
    for index, l in enumerate(my_list): 
        if(l[0] > key):
            break
        if(l[-1] < key):
            continue
        if (key in l):
            result.append(index)
    return result

score 0 · Accepted Answer · answered Sep 08 '14 at 15:31

Lists are not the best data structure to look for elements, you should consider using sets, which gives you O(1) time for lookup. There are better data structures and algorithms if your lists don't have intersections, but since you want all the lists, there are fewer alternatives.

lsts = [[0,1,2,3,4,5], [6,7,8,9,10,11], [12,56,86,9], [55,53,12]]
sets = map(set, lsts)

def find(iterables, element):
    return [i for i, iterable in enumerate(iterables) if element in iterable]

Find a number in list of lists

4 Answers4