测试向量而不扫描它

Question

对于我正在实现的一系列算法，我需要模拟像一组硬币被称重或混合血样之类的东西。重写的目标是在一组其他相同的项目中标识一组稀疏的有趣项。此标识是通过测试一组项目来完成的。例如，经典的问题是在一组81枚(相同的)硬币中找到一枚轻型假币，使用尽可能少的盘式天平称重。诀窍是将81枚硬币分成三组，并对两组硬币进行称重。然后，你做这个小组，这是不平衡的，直到你有两个硬币。

上面讨论的关键点是，在更广泛的集合中，感兴趣的项集是稀疏的--对于这种类型的输入，我正在实现的算法都优于二进制搜索等等。

我需要的是一种测试整个向量的方法，它可以指示单个或多个向量的存在，而不需要对矢量分量进行扫描。

也就是说，在O(1)操作中返回矢量的Hamming重量的一种方法--这将准确地模拟在一个泛天平中汇集血样/一组硬币。

矢量没有被扫描是关键，但是输出应该表明向量中至少有一个1。通过扫描，我的意思是用二进制搜索等算法查看向量，或者依次查看每个元素。这就需要模拟集合一组项目(如血样)，并对该组进行单次测试，这表明存在1。

目前，我已经将这个“向量”实现为一个列表，但这并不一定是固定不变的。任务是通过测试子列表的组来确定向量中的1s位于何处。清单的一个例子是：

sparselist = [0]*100000
sparselist[1024] = 1

但是，这也很可能是一个长/集/其他东西，如下所示。

目前，我正在使用any()作为测试，但是有人告诉我，任何()都会扫描向量--这违背了我试图实现的目的。

下面是一个简单的二进制搜索示例，它使用any来测试组：

def binary_search(inList):
    low = 0
    high = len(inList)

    while low < high:
        mid = low + (high-low) // 2
        upper = inList[mid:high]
        lower = inList[low:mid]  
        if any(lower):
            high = mid
        elif any(upper):
            low = mid+1
        else:
            # Neither side has a 1
            return -1
   return mid

如果这个代码不是生产质量，我很抱歉。如有任何改进建议(超出任何()测试)，将不胜感激。

我正试图想出一个比任何()都更好的测试，因为有人已经指出，任何()都会扫描列表--这会使我试图做的事情落空。测试不需要返回准确的汉明重量-它只需要表明有(或不是！)A被测试组中的1(即上面代码中的上/下)。

我还考虑过使用二进制xor，但不知道如何以一种非组件的方式使用它。

Answer 1

下面是一幅素描：

class OrVector (list): 

    def __init__(self): 
        self._nonzero_counter = 0
        list.__init__(self)

    def append(self, x): 
        list.append(self, x)
        if x:
            self._nonzero_counter += 1

    def remove(self, x): 
        if x: 
            self._nonzero_counter -= 1
        list.remove(self, x) 

    def hasOne(self): 
        return self._nonzero_counter > 0


v = OrVector()

v.append(0)
print v
print v.hasOne()

v.append(1); 
print v
print v.hasOne()

v.remove(1); 
print v
print v.hasOne()

输出：

[0]
False
[0, 1]
True
[0]
False

其思想是从list继承，并添加一个变量来存储非零条目的数量。在将关键功能委托给基本list类的同时，您可以监视列表中的非零项的数量，并可以使用hasOne()成员函数在O(1)时间查询它。

HTH。

Answer 2

any只会扫描整个矢量，如果找不到你之前的“向量”结束。在文档中，它相当于

def any(iterable):
    for element in iterable:
        if element:
            return True
    return False

这使它成为O(n)。如果将事情排序(在“二进制向量”中)，则可以使用等分。

例如position = index(myVector, value)

Answer 3

好吧，也许我会尝试另一个答案。

如果事先不知道您的数据，就不能这样做。你能做的唯一的事情就是做一个测试并缓存结果。您可以设计一个数据结构，以帮助您确定后续测试的结果，以防数据结构是可变的，也可以设计一个数据结构，以便在更好的时间内确定向量子集上的答案。

然而，你的问题并没有说明这一点。至少在写答案的时候没有。现在，您希望在向量上进行一次测试，因为存在一个特定的元素，对数据没有先验知识，时间复杂度在平均情况下小于O(log )，在最坏情况下小于O(n)。这是不可能的

另外，请记住，您需要在某个点加载一个向量，这需要O(n)操作，所以如果您对对一组元素执行一次测试感兴趣，那么就不会有太多松动。在平均情况下，有更多的元素，加载时间将远远超过测试。

如果您想要执行一组测试，您可以设计一个算法，该算法将在随后的测试中“积累”一些知识，这将帮助它在更好的时间内确定结果。然而，只有当你想要做一个以上的测试时，这才成立！