Geek Answers Handbook

The best data structure for license plate storage and search if a specific license plate exists

I am trying to write a program that determines if a particular license plate is one of the 10,000 that I saved. I want to write a quick response algorithm, primarily using memory as a secondary target. Will a binary search tree or hash table be more balanced to store 10,000 license plate numbers (which also contain letters)?

+4
source share
4 answers

A hash table takes O (1) time to search for any given record (for example, to check if it is in the data structure), while the binary search tree takes O (logn) time. Therefore, a hash table would 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 several similar entries.

+5
source

It sounds like you really want to install Python (which is based on a hash table). 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

This creates a set of 10,000 random plates (3 capital letters and 3 digits each), then checks a million random plates to see if they are in this set. Here's the conclusion:

ABCDEFGHIJKLMNOPQRSTUVWXYZ
0123456789
5.88199996948

, 6 , , . :

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

35 . , ; -)

+3

python - , . O (1). python -, , .

.

. , , , .

:

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)
+1
source 
def plates(plateNum, hashTable):
  """
  input: plateNum is <type 'str'>, hashTable is <type 'dic'>
 output: Bool
  """
  if plateNum in hashTable:
    return True
  else:
    return False

Some code like this will do exactly what you are looking for.

-1
source

More articles:


All Articles