私がベンチマークしているアルゴリズムでは、リストの一部をテストする必要があります (非常に長くなる可能性がありますが、ほとんどが 0 で、場合によっては 1 で満たされています)。アイデアは、n 個のアイテムのリストで、それらのうちの d 個が対象であると予想され、それぞれが確率 d/n で欠陥があるというものです。したがって、サイズ d/n のグループを確認してください (情報理論上の理由から、フロア関数とログ関数の観点から定義されています。これにより、アルゴリズムの分析が容易になります)。
アルゴリズム：
1./ n <= 2*d -2 の場合 (つまり、リストの半分以上が 1 で埋められている場合)、各項目を順番に見ていきます
2./ If n > 2*d -2: aplha (= floor(binarylog(l/d), l = n - d + 1, d = 1 の数) のサイズのグループを確認します。1 がある場合、グループで二分探索を行って不良品を見つけ、d = d - 1 および n = n - 1 - x (x = グループのサイズから不良品を差し引いたサイズ) を設定します。1 がない場合は、n = n - を設定します。 groupSize を変更し、1 に移動します (つまり、リストの残りを確認します)。
ただし、ランダムな場所に 10 個の 1 をリストに入力すると、アルゴリズムは 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
また、関数が現在パスしているテストは次のとおりです。
from GroupTesting import HGBSA
#idenitify a single defective
inlist = [0]*1024
inlist[123] = 1
assert HGBSA(inlist, 1) == [123]
#identify two defectives
inlist = [0]*1024
inlist[123] = 1
inlist[789] = 1
assert inlist[123] == 1
assert inlist[789] == 1
assert HGBSA(inlist, 2) == [123, 789]
zeros = [0]*1024
ones = [1, 101, 201, 301, 401, 501, 601, 701, 801, 901]
for val in ones:
zeros[val] = 1
assert HGBSA(zeros, 10) == ones
つまり、リストに決定論的に配置された単一の 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]
次の変更 (欠陥がない場合はグループ全体を破棄しますが、欠陥のあるグループの前のグループのメンバーのみを破棄します) は、「隣り合った 2 つ」のテストに合格しますが、「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 であり、すべての欠陥が検出されます。
また、将来この種のエラーをキャッチするためのテストを作成するにはどうすればよいですか?