CODEWITHSUNDEEP
pythondata-structureswindowrange
slashdottir
slashdottir

Reputation: 8536

Is there a python datastructure that would allow efficient range queries?

Say, you had a list of integers, e.g.

foo = [3,9,23,54,77,123,...]

Is there an efficient datastructure that would allow queries like

x = everything in foo between 10 and 100

so that 

x == [23,54,77]

or x = everything < 50

giving

x = [3,9,23]

etc?

Upvotes: 1

Views: 2240

Answers (2)

Taku
Taku

Reputation: 33714

There is the range function (or xrange in python 2):

foo = [3,9,23,54,77,123]

x = [y for y in foo if y in range(10,101)]
# x = [23,54,77]

If there's an infinite number on one side, use the operators and add float(y).is_integer() to match only integers:

x = [y for y in foo if y < 50 if float(y).is_integer()]
# x = [3,9,23]

Upvotes: 3

Daniel Roseman
Daniel Roseman

Reputation: 599610

Assuming these integers are already sorted it's not a data structure that you want, but an algorithm: that is, binary search. In Python this is provided by the bisect module.

So, for example, to find all the members that are less than 50:

from bisect import bisect_left
i = bisect_left(foo, 50)
result = foo[:i]

Upvotes: 6

Related Questions