how to efficiently check contiguous ranges in python

Question

assigning grade on basis of range:

def getGrade(size):
    grade =''
    if size <= 32:
        grade = 'p4'
    elif size > 32 and size <=64:
        grade = 'p6'
    elif size > 64 and size <= 128:
        grade = 'p10'
    elif size > 128 and size <= 256:
        grade = 'p15'
    elif size > 256 and size <=512:
        grade = 'p20'
    elif size > 512 and size <= 1024:
        grade = 'p30'
    elif size > 1024 and size <= 2048:
        grade = 'p40'
    ......

Problem is need to add 20 more check so is there any way to do better than this approach.

Create a `dict` of `range` objects (as key) and grade strings (as value)? — UnholySheep, May 01 '18 at 09:34
start by throwing away all the min checks - they are not needed as an earlier if would have triggered — Patrick Artner, May 01 '18 at 09:36
[Related.](https://stackoverflow.com/questions/31095461/how-to-replace-many-if-elif-statements-in-python) — Aran-Fey, May 01 '18 at 09:37
@PatrickArtner certainly not able to throw min as need to assign grade to that value also — pylist, May 01 '18 at 09:37
`if size < 32: do somthing elif size < 64: do something` etc. if it is 33 you do not need to check `>32 and <=64` for the 2nd. If smaller then 33 the first one would have triggered. That roughly cuts your statements by 50% - but using a max-value:label dict would be better — Patrick Artner, May 01 '18 at 09:39
What @PatrickArtner said. So you don't need all those double tests. However, when you _do_ need double tests like that, it's better to write `32 < size <= 64` than `size > 32 and size <=64`. — PM 2Ring, May 01 '18 at 09:54

fferri · Accepted Answer · 2018-05-01T10:37:36.380

5

Due do the ranges being contiguous, you can avoid repeating the lower bound.

Putting all the ranges in tuples can save you some typing (if the first range does not go down to negative infinity, consider adding the tuple (0, None) before all others:

def getGrade(size):
    grades = (
         (32, 'p4'),
         (64, 'p6'),
        (128, 'p10'),
        ...
    )

    for maxVal, grade in grades:
        if size <= maxVal:
            return grade

Test:

>>> getGrade(45)
'p6'
>>> getGrade(100)
'p10'

Efficiency:

If the grades list is really long, you can achieve better runtime than scanning every item. Since the list is sorted, you can use bisect, by replacing the for loop:

    for maxVal, grade in grades:
        if size <= maxVal:
            return grade

with:

    index = bisect.bisect(grades, (size, ))
    if index < len(grades):
        return grades[index][1]

The number of steps is reduced (in the worst case) from N (the length of grades) to log₂(N).

edited May 01 '18 at 10:37

answered May 01 '18 at 09:38

fferri

18,285
5
46
95

1

or just `return next((grade for s, grade in grades if size <= s), None)`? – hiro protagonist May 01 '18 at 09:55
2

@hiroprotagonist that is only one line long, but it's longer in terms of number of tokens. Anyway the challenge about code length is silly here; the point is that the "verbose" `for` is more readable. (despite of how much I am a fan of oneliners) – fferri May 01 '18 at 09:58
@fferri i have to admit: i agree! – hiro protagonist May 01 '18 at 10:17

score 0 · Answer 2 · answered May 01 '18 at 10:26

0

A brute force approach would be simple as

all_grades = [i for i in chain(repeat('p4',32),repeat('p6',64-32) and so on)]

then you can get grade as

grade = all_grades[size-1]

it may require space if list is exponential

answered May 01 '18 at 10:26

newbie

137
2
11

if ranges are **20 more**, that means the uppermost range is 2147483648, definitely a waste of space! – fferri May 01 '18 at 10:35

how to efficiently check contiguous ranges in python

2 Answers2

Linked