Best Data Structure for storing license plates and searching if a given license plate exists [closed]

Question

I am attempting to write a program that determines whether a specific license plate is one of 10,000 that I have stored. I want to write a fast response algorithm first and foremost, with memory usage as a secondary objective. Would a balanced binary search tree or a hash table be more sufficient in storing the 10,000 license plate numbers (which also contain letters)?

Answer 1

A hash table takes O(1) time to look up any given entry (i.e. to check whether or not it is in the data structure), whereas a binary search tree takes O(logn) time. Therefore, a hash table will be a more efficient option in terms of response speed.

Binary search trees are more useful in scenarios where you need to display things in order, or find multiple similar entries.

Answer 2

Sounds like you really want a Python set (which is hash-table based). Here's a sample:

from random import choice
from string import ascii_uppercase as LETTERS
from string import digits as DIGITS
print LETTERS
print DIGITS

def get_plate():
    return choice(LETTERS) + \
           choice(LETTERS) + \
           choice(LETTERS) + \
           choice(DIGITS) + \
           choice(DIGITS) + \
           choice(DIGITS)

licenses = set()
while len(licenses) < 10000:
    licenses.add(get_plate())

from time import time
t1 = time()
for _ in xrange(1000000):
    get_plate() in licenses
t2 = time()
print t2 - t1

That builds a set with 10,000 random plates (3 uppercase letters and 3 digits each), then checks a million random plates to see whether they're in that set. Here's the output:

ABCDEFGHIJKLMNOPQRSTUVWXYZ
0123456789
5.88199996948

So on this box it took under 6 seconds to check a million plates - and by far most of that time was consumed by generating the million random plates. Change to:

a_plate = get_plate()
t1 = time()
for _ in xrange(1000000):
    a_plate in licenses
...

and it's 35 times faster. That should be quick enough to handle the traffic on even a moderately busy road ;-)

Answer 3

A python dictionary is what you want. Dictionary lookups are O(1). A python dictionary is effectively a hash table so there is some memory overhead but lookups are fast.

Refer to a previous stackoverflow question here.

You could even store data meta-data about the license plate very easily. Your keys can be any form of license plate you want, integers, strings, or even a tuple.

Example code:

license_plates = {'AB-12-23' :{'make':'Dodge','color':'White'},
                  'SWINGER'  :{'make':'Alpha','color':'Blue'},
                  ('ABC',123):{'make':'Ford','color':'Yellow'},
                  123456     :{'make':'Ferrari','color':'Red'}}

print '%s in list of license plates? %s' % ('SWINGER', 'SWINGER' in license_plates)