0

对于我正在实施的一系列算法，我需要模拟诸如称重的硬币组或汇集的血液样本之类的事情。最重要的目标是在一组其他相同的项目中识别一组稀疏的有趣项目。这种识别是通过一起测试项目组来完成的。例如，经典问题是在一组 81 枚（相同）硬币中找到一枚轻质假币，使用尽可能少的平底秤的权重。诀窍是将 81 枚硬币分成三组，然后将两组相互称重。然后，您在剩下 2 个硬币之前对不平衡的组执行此操作。

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

我需要的是一种测试整个向量的方法，该方法指示存在单个或多个向量，而无需逐个扫描向量。

即一种在 O(1) 操作中返回向量的汉明权重的方法 - 这将准确模拟在平底秤中汇集血液样本/称重硬币组。

关键是向量没有被扫描——但输出应该表明向量中至少有一个 1。通过扫描，我的意思是使用二进制搜索等算法查看向量或依次查看每个元素。这需要模拟项目（例如血液样本）的汇集组和表明存在 1 的组的单个测试。

我目前已经将这个“向量”实现为一个列表，但这不需要一成不变。任务是通过测试子列表的组来确定向量中的 1 所在的位置。该列表的一个示例是：

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

但这同样可能是一个很长/设置/其他的东西，如下所示。

目前我正在使用 any() 作为测试，但有人向我指出 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

如果此代码不是生产质量，我深表歉意。任何改进它的建议（除了 any() 测试）将不胜感激。

我正在尝试提出比 any() 更好的测试，因为有人指出 any() 将扫描列表 - 违背了我正在尝试做的事情。测试不需要返回准确的汉明权重——它只需要指出被测试的组中有（或没有！）1（即上面代码中的上/下）。

我也想过使用二进制异或，但不知道如何以非组件化的方式使用它。

4

3 回答 3

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类的同时，您可以监控列表中非零条目的数量，并可以O(1)使用hasOne()成员函数及时查询。

HTH。

于 2013-07-15T11:54:03.367 回答
0

好的，也许我会尝试其他答案。

如果您不事先了解您的数据，您就无法做到这一点。您唯一可以做的就是进行测试并缓存结果。您可以设计一个数据结构，以帮助您确定任何后续测试的结果，以防您的数据结构是可变的，或者设计一个能够在您的向量子集上更好地确定答案的数据结构。

但是，您的问题并未表明这一点。至少在写答案的时候没有。现在，您想对向量进行一次测试，以检查特定元素的存在，不提供有关数据的先验知识，时间复杂度在平均情况下小于 O(log n) 或在最坏情况下小于 O(n)。这是不可能的。

另请记住，您需要在某个点加载一个需要 O(n) 操作的向量，因此如果您有兴趣对一组元素执行一次测试，您不会丢失太多。在具有更多元素的平均情况下，加载时间将比测试花费更多的时间。

如果您想执行一组测试，您可以设计一个算法，在后续测试期间“积累”一些知识，这将有助于它在更好的时间确定结果。但是，仅当您要进行多个测试时才成立！

于 2013-07-15T12:12:12.140 回答
0

any如果在“向量”结束之前没有找到您所追求的，则只会扫描整个向量。从文档中它相当于

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

这确实成功了O(n)。如果您对事物进行了排序（在“二进制向量”中），则可以使用bisect。

例如position = index(myVector, value)

于 2013-07-15T11:41:05.943 回答