python - 如何加快指数时间码

Question

我正在写一个模拟。我需要解决的问题如下。

我得到一个长度为 l 的随机二进制向量 t(python 中的列表)。然后，我对相同长度的二进制向量进行采样，并测量每个采样向量与 t 之间的汉明距离(即对齐不匹配的数量)并存储结果。我想确定有多少长度为 l 的二进制向量与目前找到的距离兼容。显然 t 是，但也可能有许多其他人也是。

我的代码如下。

import random
import itertools
import operator

l=23
t = [random.randint(0,1) for b in range(l)]
stringsleft = set(itertools.product([0,1],repeat=l))

xcoords = []
ycoords = []
iters = l
for i in xrange(iters):
    print i, len(stringsleft)
    xcoords.append(i)
    ycoords.append(math.log(len(stringsleft)))
    pattern = [random.randint(0,1) for b in range(l)]
    distance = sum(itertools.imap(operator.ne, pattern, t))
    stringsleft = stringsleft.intersection(set([y for y in stringsleft if sum(itertools.imap(operator.ne, pattern, y)) == distance]))

不幸的是，它非常慢并且使用大量内存，如果我将 l 增加到 30 则根本不起作用。是否可以加快速度以解决 l=30 的情况？

更新
我通过用整数替换列表做了一个小的优化，所以现在它以 l=26 运行。

l=26
t = random.randint(0,2**l)
stringsleft = set(range(2**l))
xcoords = []
ycoords = []
iters = l
for i in xrange(iters):
    print i, len(stringsleft)
    if (len(stringsleft) > 1):
        xcoords.append(i)
        ycoords.append(math.log(len(stringsleft),2))
    pattern = random.randint(0,2**l)
    distance = bin(pattern ^ t).count('1')
    stringsleft = stringsleft.intersection(set([y for y in stringsleft if bin(pattern ^ y).count('1') == distance]))

阻止我到达 l=30 的问题是 RAM 使用而不是时间。

Answer 1

我一直在思考这个问题，最后写的程序基本上就是Sneftel的方法。起初，没有做出任何选择，我们有汉明距离列表。然后假设我们选择 1 作为第一个值，那么所有具有 0 的序列只有在序列的其余部分与汉明距离 - 1 兼容时才是兼容的。1 也是如此。

一开始我也有一个递归版本，但将其更改为使用堆栈的循环，以便我可以使用 yield 将其转换为生成兼容序列的生成器。

我做的一个优化是，如果有一个猜测的汉明距离 > l/2，我翻转 0 和 1，这样新的猜测就保证了汉明距离 <= l/2。

如果 l=30，我会得到不错的表现，尽管这取决于猜测的次数和他们的幸运程度。

由于我早期的 Mastermind 思想，我仍然以“猜测”的方式思考，试图找出“顺序”。

代码:

import random

LENGTH = 30
NUMGUESSES = 20


def guess():
    return [random.randint(0, 1) for i in range(LENGTH)]

SEQUENCE = guess()
GUESSES = [guess() for i in range(NUMGUESSES)]


def hamming(a, b):
    return sum(aelem != belem for aelem, belem in zip(a, b))


# Flip if hamming > LENGTH / 2
mid = LENGTH / 2
for i in range(NUMGUESSES):
    if hamming(SEQUENCE, GUESSES[i]) > mid:
        GUESSES[i] = [1 - g for g in GUESSES[i]]

HAMMINGS = [hamming(SEQUENCE, g) for g in GUESSES]

print "Sequence:", SEQUENCE
print
for h, g in zip(HAMMINGS, GUESSES):
    print "Guess and hamming:", g, h
print


def compatible_sequences(guesses, hammings):
    # Use a stack instead of recursion, so we can make this a generator.
    stack = []
    # Start: we have chosen nothing yet, and the hammings have start values
    stack.append(([], hammings))

    while stack:
        so_far, hammingsleft = stack.pop()

        if -1 in hammingsleft:
            # Skip, choices so far are incompatible with the guesses
            continue

        if len(so_far) == LENGTH:
            # Success if all the Hamming distances were exactly correct
            if all(h == 0 for h in hammingsleft):
                yield so_far
            continue

        # Not done yet, add choices 0 and 1 to the queue
        place_in_guess = len(so_far)
        for choice in (1, 0):
            stack.append(
                (so_far + [choice],
                 [h - (g[place_in_guess] != choice)
                  for h, g in zip(hammingsleft, guesses)]))

print "Compatible sequences:"
for nr, sequence in enumerate(compatible_sequences(GUESSES, HAMMINGS), 1):
    print nr, sequence