用于存储车牌和搜索是否存在给定车牌的最佳数据结构

Question

我正在尝试编写一个程序来确定特定的牌照是否是我存储的10,000个牌照之一.我想首先编写一个快速响应算法,将内存使用作为次要目标.平衡的二叉搜索树或哈希表是否足以存储10,000个车牌号码(也包含字母)？

Answer 1

哈希表需要O(1)时间来查找任何给定条目(即检查它是否在数据结构中),而二叉搜索树需要O(logn)时间.因此,就响应速度而言,哈希表将是更有效的选项.

二进制搜索树在需要按顺序显示内容或查找多个类似条目的场景中更有用.

Answer 2

听起来你真的想要一个 Python 集（它是基于哈希表的）。这是一个示例：

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

这将构建一个包含 10,000 个随机盘子（每个有 3 个大写字母和 3 个数字）的集合，然后检查一百万个随机盘子以查看它们是否在该集合中。这是输出：

ABCDEFGHIJKLMNOPQRSTUVWXYZ
0123456789
5.88199996948

所以在这个盒子上，检查一百万个盘子用了不到 6 秒的时间 -到目前为止，大部分时间都花在生成一百万个随机盘子上。改成：

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

而且速度快了 35 倍。即使在中等繁忙的道路上，这也应该足够快以应对交通；-)