Python: efficiently check if integer is within *many* ranges
<p>I am working on a postage application which is required to check an integer postcode against a number of postcode ranges, and return a different code based on which range the postcode matches against.</p>

<p>Each code has more than one postcode range. For example, the <strong>M</strong> code should be returned if the postcode is within the ranges 1000-2429, 2545-2575, 2640-2686 or is equal to 2890.</p>

<p>I could write this as:</p>

<pre><code>if 1000 &lt;= postcode &lt;= 2429 or 2545 &lt;= postcode &lt;= 2575 or 2640 &lt;= postcode &lt;= 2686 or postcode == 2890:
    return 'M'
</code></pre>

<p>but this seems like a lot of lines of code, given that there are 27 returnable codes and 77 total ranges to check against. Is there a more efficient (and preferably more concise) method of matching an integer to all these ranges using Python?</p>

<hr />

<p>Edit: There's a lot of excellent solutions flying around, so I have implemented all the ones that I could, and benchmarked their performances.</p>

<p>The environment for this program is a web service (Django-powered actually) which needs to check postcode region codes one-by-one, on the fly. My preferred implementation, then, would be one that can be quickly used for each request, and does not need any process to be kept in memory, or needs to process many postcodes in bulk.</p>

<p>I tested the following solutions using <code>timeit.Timer</code> with default 1000000 repetitions using randomly generated postcodes each time.</p>

<h3>IF solution (my original)</h3>

<pre><code>if 1000 &lt;= postcode &lt;= 2249 or 2555 &lt;= postcode &lt;= 2574 or ...:
    return 'M'
if 2250 &lt;= postcode &lt;= 2265 or ...:
    return 'N'
...
</code></pre>

<p>Time for 1m reps: 5.11 seconds.</p>

<h3>Ranges in tuples (Jeff Mercado)</h3>

<p>Somewhat more elegant to my mind and certainly easier to enter and read the ranges. Particularly good if they change over time, which is possible. But it did end up four times slower in my implementation.</p>

<pre><code>if any(lower &lt;= postcode &lt;= upper for (lower, upper) in [(1000, 2249), (2555, 2574), ...]):
    return 'M'
if any(lower &lt;= postcode &lt;= upper for (lower, upper) in [(2250, 2265), ...]):
    return 'N'
...
</code></pre>

<p>Time for 1m reps: 19.61 seconds.</p>

<h3>Set membership (gnibbler)</h3>

<p>As stated by the author, "it's only better if you are building the set once to check against many postcodes in a loop". But I thought I would test it anyway to see.</p>

<pre><code>if postcode in set(chain(*(xrange(start, end+1) for start, end in ((1000, 2249), (2555, 2574), ...)))):
    return 'M'
if postcode in set(chain(*(xrange(start, end+1) for start, end in ((2250, 2265), ...)))):
    return 'N'
...
</code></pre>

<p>Time for 1m reps: 339.35 seconds.</p>

<h3>Bisect (robert king)</h3>

<p>This one may have been a bit above my intellect level. I learnt a lot reading about the <code>bisect</code> module but just couldn't quite work out which parameters to give <code>find_ge()</code> to make a runnable test. I expect that it would be extremely fast with a loop of many postcodes, but not if it had to do the setup each time. So, with 1m repetitions of filling <code>numbers</code>, <code>edgepairs</code>, <code>edgeanswers</code> etc for just one postal region code (the <strong>M</strong> code with four ranges), but not actually running the <code>fast_solver</code>:</p>

<p>Time for 1m reps: 105.61 seconds.</p>

<h3>Dict (sentinel)</h3>

<p>Using one dict per postal region code pre-generated, cPickled in a source file (106 KB), and loaded for each run. I was expecting much better performance from this method, but on my system at least, the IO really destroyed it. The server is a not-quite-blindingly-fast-top-of-the-line Mac Mini.</p>

<p>Time for 1m reps: 5895.18 seconds (extrapolated from a 10,000 run).</p>

<h2>The summary</h2>

<p>Well, I was expecting someone to just give a simple 'duh' answer that I hadn't considered, but it turns out this is much more complicated (and even a little controversial).</p>

<p>If every nanosecond of efficiency counted in this case, I would probably keep a separate process running which implemented one of the binary search or dict solutions and kept the result in memory for an extremely fast lookup. However, since the IF tree takes only five seconds to run a million times, which is plenty fast enough for my small business, that's what I'll end up using in my application.</p>

<p>Thank you to everyone for contributing!</p>
