对多数表决算法的探究

在做大创的时候接触到多数表决算法，想象中应该是很可靠的算法，但是在测试的时候发现并不可靠，于是做一个试验来探究一下多数表决算法的可靠性。

• 先生成一个只含有0和1的列表，长度为10，重复50次得到一个新的列表，遍历新列表并不断生成随机数，根据随机数的值来改变对应的值。首先将阈值设为0.2，重复测试1000次，结果为
  count_True:1000 count_False:0
  可以看到测试1000次的情况下都是前后不变，可以认为在数据受影响程度为20%以下时多数表决算法是可靠的。

• 将阈值改为0.3，测试1000次，结果为
  count_True:979 count_False:21，正确率为98%，可以认为这种情况下算法可靠。

• 继续测试，将阈值改为0.4，测试1000次，结果为
  count_True:454 count_False:546
  可以看到结果不可靠。

• 接着更改初始列表的长度，将长度改为20，阈值改为0.2，继续测试1000次，结果为
  count_True:1000 count_False:0

  结果可靠。

• 将阈值改为0.3，结果为
  count_True:970 count_False:30
  仍然可靠。

• 将阈值改为0.4，结果为
  count_True:201 count_False:799

虽然结果同样是不可靠，但是与列表长度为10时的实验结果出现了不同，这次错误概率达到了80%，而列表长度为10时错误概率只有55%。

• 接续探究，首先设置阈值为0.500,这里为了精确表示用到了decimal格式，没有采用float格式。
  列表长度为10，从0.500开始，每个值测试1000次，当不满足正确率高于80%时，就将阈值减去0.001，再测试1000次，测试结果为
  The Best Threshold:0.361

可以看到列表长度为10的时候。能接受的最高的阈值为36.1%。

• 接下来测试列表长度为20的时候，能接受的最高阈值是多少。
  结果是
  The Best Threshold:0.343
  可以看到能接受的最高阈值为34.3%，低于列表长度为10的时候。即列表长度增长，增大了出错了概率。

下面是测试代码：

import random
import decimal


def CreList():
    ListA = [0,1,0,0,1,1,0,0,0,1,1,1,0,0,1,0,0,1,0,1]
    # ListA = [0,0,1,1,0,0,1,1,0,1]
    ListB = []
    length = len(ListA)
    for i in range(50):
        for j in range(length):
            ListB.append(ListA[j])
    return ListA,ListB,length

def RandomChange(ListB,Threshold):
    old_length = len(ListB)
    ListC = ListB
    for i in range(old_length):
        if random.random() < Threshold:
            if ListC[i] == 0:
                ListC[i] = 1
            else:
                ListC[i] = 0
    return ListC

def main(Threshold):
    ListA,ListB,length = CreList()
    ListC = RandomChange(ListB,Threshold)
    endList = []
    count_0 = 0
    count_1 = 0
    new_length = len(ListC) // length
    for i in range(length):
        for j in range(new_length):
            if ListC[i + j*length] == 0:
                count_0 += 1
            else:
                count_1 += 1
        if count_0 >= count_1:
            endList.append(0)
        else:
            endList.append(1)
        count_0 = 0
        count_1 = 0
    for i in range(len(endList)):
        if endList[i] != ListA[i]:
            return False
        elif endList[i] == ListA[i] and i == len(endList)-1:
            return True

if __name__ == '__main__':
    count_True = 0
    count_False = 0
    Threshold = decimal.Decimal('0.500')
    while count_True < 800:
        count_True = 0
        count_False = 0
        for i in range(1000):
            temp = main(Threshold)
            if temp == True:
                count_True += 1
            else:
                count_False += 1
        Threshold = Threshold - decimal.Decimal('0.001')
    print("The Best Threshold:"+str(Threshold))
        # print("count_True:"+str(count_True))
        # print("count_False:"+str(count_False))