performance - 仅过滤包含给定数字集的数字序列

Question

我有一大堆像这样的数字串。各个字符串相对较短(比如少于 50 位)。

data = [
  '300303334',
  '53210234',
  '123456789',
  '5374576807063874'
]

我需要找到一个高效的数据结构(速度第一，内存第二)和算法，它只返回那些由给定数字集组成的字符串。

示例结果:

filter(data, [0,3,4]) = ['300303334']
filter(data, [0,1,2,3,4,5]) = ['300303334', '53210234']

数据列表通常会适合内存。

Answer 1

对于每个数字，预先计算一个不包含该数字的帖子列表。

postings = [[] for _ in xrange(10)]
for i, d in enumerate(data):
    for j in xrange(10):
        digit = str(j)
        if digit not in d:
            postings[j].append(i)

现在，要查找仅包含数字 [1, 3, 5] 的所有字符串，您可以合并其他数字(即:0, 2, 4, 6, 7, 8, 9).

def intersect_postings(p0, p1):
    i0, i1 = next(p0), next(p1)
    while True:
         if i0 == i1:
            yield i0
            i0, i1 = next(p0), next(p1)
         elif i0 < i1: i0 = next(p0)
         else: i1 = next(p1)

def find_all(digits):
    p = None
    for d in xrange(10):
        if d not in digits:
            if p is None: p = iter(postings[d])
            else: p = intersect_postings(p, iter(postings[d]))
    return (data[i] for i in p) if p else iter(data)

print list(find_all([0, 3, 4]))
print list(find_all([0, 1, 2, 3, 4, 5]))