Python - Finding elements in a list efficiently

Question

I have a list, list_a, that contains floating numbers:

list_a = [[[ 0 for i in range(40)] for j in range(1000)]for k in range(47)]

And I have a sorted version of this:

list_a_sorted = list_a
list_a_sorted[0].sort()

So list_a_sorted is sorted and contains values for list_a starting from the lowest first. Let's assume it is as follows:

[2.3,3.1.........9]

So 2.3 is the lowest value but how can I find out if this was the 8th element in list_a or the 15th or nth?

As my lists are quite large, I also need to do this as efficiently as possible? Any help would be appreciated, thanks

is the purpose of list_a_sorted only for efficient search? I ask because, the most efficient sort algorithm is of complexity o(n log n), whereas the worst find (traversing element by element) is of complexity o(n). If list_a_sorted is only to help you find an element, then it would be more performant if you were to just find within an unsorted list. — c-ram
– c-ram, Commented Jun 27, 2011 at 12:03
That is a good point. Ultimately I need to find n lowest values in the sorted list so I thought sorting the list would make finding the values easier. — Mandeep
– Mandeep, Commented Jun 27, 2011 at 12:26

Gryphius · Accepted Answer · 2011-06-27 11:59:37Z

5

to find the position of an element in a list you can use l.index(something)

http://docs.python.org/library/stdtypes.html#typesseq

answered Jun 27, 2011 at 11:59

Gryphius

79.8k6 gold badges52 silver badges56 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Duncan Over a year ago

That is true, but each lookup is then O(n) and he said the lists are quite large so it won't be very efficient. Also if any of the values are duplicates you'll just get the same index repeated rather than both values.

Fredrik Pihl · Accepted Answer · 2011-06-27 12:06:42Z

4

If speed is of essence (and you have something like "create once, lookup often" and if you don't have any duplicate entries (if you do use set) then I'd suggest that you create an dictionary upon creation of the list with each item as key and it's index as value. In this case you'll always have O(1) lookuptime regardless of the length of the dictionary. Many ifs there...

answered Jun 27, 2011 at 12:06

Fredrik Pihl

45.9k7 gold badges89 silver badges133 bronze badges

Comments

Duncan · Accepted Answer · 2011-06-27 13:54:03Z

3

if you want to find the n smallest values in an unsorted list look at heapq.nsmallest() which may be more efficient if n isn't too large. To find the position of the smallest values try this:

>>> from heapq import nsmallest
>>> from random import random
>>> values = [random() for i in range(20)]
>>> values
[0.012227103410989537, 0.9782624648209769, 0.9896111545377924, 0.9033620518745159, 0.6767780103989406, 0.4595455061820246, 0.39814471642551696, 0.6904798136040561, 0.8727083752258934, 0.6680153337266017, 0.606044647078923, 0.5644656135679249, 0.934351848916147, 0.05955628567745763, 0.7236000566917332, 0.8303865367817055, 0.9671576336593124, 0.3164892315873573, 0.8416372881413415, 0.5009057933309073]
>>> nsmallest(4, range(len(values)), key=lambda i: values[i])
[0, 13, 17, 6]

Or faster but slightly less clear:

>>> nsmallest(4, range(len(values)), key=values.__getitem__)
[0, 13, 17, 6]

For your list you may want something like (untested code):

def indices():
    for k in range(47):
        for j in range(1000):
            for i in range(40):
                yield k, j, i
def keyfn(ind):
    k, j, i = ind
    return list_a[k][j][i]

print(nsmallest(4, indices(), key=keyfn))

edited Jun 27, 2011 at 13:54

answered Jun 27, 2011 at 13:34

Duncan

96.4k15 gold badges129 silver badges160 bronze badges

3 Comments

Mandeep Over a year ago

This looks useful, in the case of my list, which is: list_a = [[[ 0 for i in range(40)] for j in range(1000)]for k in range(47)], how would I find the nsmallest in the k dimension?

Duncan Over a year ago

I've extended my answer to find the nsmallest overall, you could pick out the k values from that but it might give you duplicates. If you don't want duplicate k values then you probably want to use min() on the nested lists and just use nsmallest() at the outer level.

Mandeep Over a year ago

Thanks, duplicates are fine : )

John La Rooy · Accepted Answer · 2011-06-27 13:14:59Z

1

Answering the question in the comments...

If L is the list of numbers, this will return the indicies of the n smallest items

[j for i,j in sorted((j,i) for i,j in enumerate(L))[:n]]

Here is another way that is a little more tricky

sorted(range(len(L)), key=L.__getitem__)[:n]

Which is more efficient is left as an exercise for the reader :)

edited Jun 27, 2011 at 13:14

answered Jun 27, 2011 at 13:09

John La Rooy

306k54 gold badges378 silver badges513 bronze badges

Collectives™ on Stack Overflow

Python - Finding elements in a list efficiently

4 Answers 4

1 Comment

Comments

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

1 Comment

Comments

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related