Geek Answers Handbook

Python - effectively finding where something will land in a sorted list?

I have a list:

x = ['c', 'a', 'e']

I can sort this list:

x_sorted = sorted(x)

x_sorted Now ['a', 'c', 'e']

Now let's say that I have a new variable y = 'd'

I want to know where in x_sortedthis new variable it will fall. In this example, the new variable ycontains a string 'd', so it will be placed as ['a', 'c', 'd', 'e']in index 2 of the list. I want to find out this index number as efficiently as possible (since I have to repeat this process many times).

Here is how I wrote that makes the task very simple:

def f(x_sorted, y):
    new_list = x_sorted[:] + [y]
    return sorted(new_list).index(y)

This gives me the correct answer.

I am wondering if there is a more efficient way to do this, since it fwill be called 100,000+ times.

Thanks in advance!

+4
source share
3

bisect

from bisect import bisect

l = ['a', 'c', 'e']

print(bisect(l,"d"))
2

:

from bisect import insort


l = ['a',"b", 'c', 'e']

insort(l, "d")
print(l)
insort(l, "f")
print(l)

['a', 'b', 'c', 'd', 'e']
['a', 'b', 'c', 'd', 'e', 'f']

, blist, insort:

O(log**2 n)  vs  O(n)

insort

from blist import blist

b = blist(["a", "b", "c", "e"])
insort(b, "f")
insort(b, "d")
print(b)
blist(['a', 'b', 'c', 'd', 'e', 'f'])

blist.sortedlist, .add:

from blist import sortedlist

l = ['b',"a", 'c', 'e']
b = sortedlist(l)

b.add("f")
print(b)
sortedlist(['a', 'b', 'c', 'e', 'f'])

sortedcontainers, sortedlist.

+9

x , , . O(n logn) O(logn) .

x , :

>>> x = ['c', 'a', 'e']
>>> y = 'd'
>>> sum(y > el for el in x)
2

O(n).

+2

, , , . , , m , O(m*n*log(m)), , , , O(n). , O(log(n)). .

0

More articles:


All Articles