修改对列表的引用

Question

对于我正在进行基准测试的算法，我需要测试列表的某一部分（可能很长，但大部分都是0，偶尔是1）。其思想是，在一个n个项目的列表中，其中的d是感兴趣的，在期望中每个项目都是有缺陷的概率d/n。因此，检查一组大小为d/n的组（由于信息论的原因，它是根据floor和log函数定义的-这使得算法的分析更容易）。在

算法：

1./如果n<；=2*d-2（即超过一半的列表中都有1），则依次查看每个项目

2./如果n>；2*d-2：检查一组尺寸为aplha（=地板（binarylog（l/d），l=n-d+1，d=1s个数）。如果有1，对组进行二进制搜索以找到有缺陷的，并设置d=d-1和n=n-1-x（x=组的大小减去缺陷）。如果没有，设置n=n-groupSize并转到1（即检查列表的其余部分）。在

然而，当在随机位置用10个1填充列表时，算法只会找到一个1，然后继续循环，同时检查一个空列表。在

我认为问题在于，当丢弃一个包含所有0的组时，我没有正确地修改表示下一轮从何处开始的引用，这导致我的算法失败。在

以下是函数的相关部分：

import math

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

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

    return mid

def HGBSA(inList, num_defectives):

n = len(inList)
defectives = []

#initialising the start of the group to be tested        
start = 0    

while num_defectives > 0:
    defective = 0
    if(n <= (2*num_defectives - 2)):
        for i in inList:
            if i == 1:
                num_defectives = num_defectives - 1
                n = n - 1
                defectives.append(i)
    else:
        #params to determine size of group
        l = n - num_defectives + 1
        alpha = int(math.floor(math.log(l/num_defectives, 2)))
        groupSize = 2**alpha
        end = start + groupSize
        group = inList[start:end]
        #print(groupSize)
        #print(group)
        if any(group): 
            defective = binary_search(group)
            defective = start + defective 
            defectives.append(defective)
            undefectives = [s for s in group if s != 1]
            n = n - 1 - len(undefectives)
            num_defectives = num_defectives - 1
            print(defectives)
        else:
            n = n - groupSize

        start = start + groupSize    

print(defectives)
return defectives

下面是函数当前通过的测试：

^{pr2}$

也就是说，它在列表中确定地找到一个1、2和10 1，但是这个测试：

zeros = [0] * 1024
ones = [1] * 10
l =  zeros + ones
shuffle(l)
where_the_ones_are = [i for i, x in enumerate(l) if x == 1] 
assert HGBSA(l, 10) == where_the_ones_are

已经暴露了错误。在

对于上面的代码，此测试也失败

#identify two defectives next to each other
inlist = [0]*1024
inlist[123] = 1
inlist[124] = 1
assert GT(inlist, 2) == [123, 124]

以下修改（如果不确定，则丢弃整个组，但仅在有缺陷的组之前丢弃组中的成员）通过“两个相邻”测试，但不通过“连续10个”或随机测试：

def HGBSA(inList, num_defectives):

n = len(inList)
defectives = []

#initialising the start of the group to be tested        
start = 0    

while num_defectives > 0:
    defective = 0
    if(n <= (2*num_defectives - 2)):
        for i in inList:
            if i == 1:
                num_defectives = num_defectives - 1
                n = n - 1
                defectives.append(i)
    else:
        #params to determine size of group
        l = n - num_defectives + 1
        alpha = int(math.floor(math.log(l/num_defectives, 2)))
        groupSize = 2**alpha
        end = start + groupSize
        group = inList[start:end]
        #print(groupSize)
        #print(group)
        if any(group): 
            defective = binary_search(group)
            defective = start + defective 
            defectives.append(defective)
            undefectives = [s for s in group if s != 1 in range(0, groupSize//2)]
            print(len(undefectives))
            n = n - 1 - len(undefectives)
            num_defectives = num_defectives - 1
            start = start + defective + 1
            #print(defectives)
        else:
            n = n - groupSize
            start = start + groupSize  

print(defectives)
return defectives

也就是说，问题是当一个组中有多个1被测试时，在第一个1之后没有检测到。代码通过的最佳测试是在列表中随机分布的1，并找到所有缺陷。在

另外，我如何创建测试以在将来捕获这种错误？在

Answer 1

你的算法似乎有比线性扫描更糟糕的性能。在

一个幼稚的算法只会扫描一个d/n大小为O（d/n）的列表。在

defectives = [index for (index, element) in enumerate(inList[start:end], start)]

根据常识，如果不查看列表中的每个元素一次，就不可能检测出列表中所有1的位置，而且再多看一次也没有意义。在

您的“二进制搜索”多次使用any，有效地多次扫描列表的各个部分。这同样适用于像if any(group): ... [s for s in group if ...]这样的构造，它们扫描group两次，第一次是不必要的。在

如果你描述了你试图实现的实际算法，人们可以帮助解决它。从你的代码和帖子来看，算法还不清楚。不幸的是，你的HGBSA函数很长，而且没有完全注释，这一事实无助于理解。在

不要害怕告诉这里的人你的算法在做什么和为什么我们也是电脑怪人，我们会理解的：）