闲逛，看到了一个很有意思的问题，在给定一个随机函数，有偏差的生成0或者1（生成0的概率是p，生成1的概率是1-p），设计一个函数，使生成0或者1的概率相等

import random
import argparse


def biased_function(p=0.7):
    """模拟有偏比特源，以概率 p 返回 1，否则返回 0"""
    return 1 if random.random() < p else 0


def peres_algorithm(p=0.7, count_recursion=False):
    """Peres 算法原始版本"""
    a = biased_function(p)
    b = biased_function(p)

    if a != b:
        if count_recursion:
            return a, 0  # 没有递归，递归次数为0
        else:
            return a
    else:
        # 递归调用并记录递归次数
        _result, _recursion_count = peres_algorithm(p, True)
        if count_recursion:
            return _result, _recursion_count + 1
        else:
            return _result


def peres_algorithm_v1(p=0.7, count_recursion=False, prev_a=None):
    # 生成当前的 a 和 b
    a = biased_function(p)
    b = biased_function(p)

    # 检查当前 a 和 b 是否相等
    if a != b:
        if count_recursion:
            return a, 0  # 没有递归，递归次数为0
        else:
            return a
    else:
        # 检查是否有上一次的 a 值，并且与当前 a 不同
        if prev_a is not None and prev_a != a:
            if count_recursion:
                return a, 0  # 返回当前 a，递归次数为0
            else:
                return a
        else:
            # 递归调用并记录递归次数，传入当前的 a 作为 prev_a
            _result, _recursion_count = peres_algorithm_v1(p, True, a)
            if count_recursion:
                return _result, _recursion_count + 1
            else:
                return _result


def analyze_algorithm(algorithm_func, p_values, num_runs=1000):
    """分析指定算法在不同p值下的递归次数"""
    results = {}

    for p_val in p_values:
        total_recursions = 0
        total_output_ones = 0  # 统计输出1的次数

        for _ in range(num_runs):
            result, recursions = algorithm_func(p=p_val, count_recursion=True)
            total_recursions += recursions
            total_output_ones += result  # 如果结果是1，则加1

        avg_recursions = total_recursions / num_runs
        output_one_prob = total_output_ones / num_runs

        results[p_val] = {
            'total_recursions': total_recursions,
            'avg_recursions': avg_recursions,
            'output_one_prob': output_one_prob
        }

        print(
            f"p={p_val}: 总递归次数={total_recursions}, 平均递归次数={avg_recursions:.4f}, 输出1的概率={output_one_prob:.4f}")

    return results


def compare_algorithms(p_values, num_runs=1000):
    """比较两个算法的性能"""
    print("=" * 60)
    print("原始 Peres 算法性能:")
    print("=" * 60)
    original_results = analyze_algorithm(peres_algorithm, p_values, num_runs)

    print("\n" + "=" * 60)
    print("优化版 Peres 算法 v1 性能:")
    print("=" * 60)
    v1_results = analyze_algorithm(peres_algorithm_v1, p_values, num_runs)

    print("\n" + "=" * 60)
    print("性能比较:")
    print("=" * 60)
    for p_val in p_values:
        orig_avg = original_results[p_val]['avg_recursions']
        v1_avg = v1_results[p_val]['avg_recursions']
        reduction = (orig_avg - v1_avg) / orig_avg * 100 if orig_avg > 0 else 0

        print(f"p={p_val}: 原始平均递归={orig_avg:.4f}, v1平均递归={v1_avg:.4f}, 减少={reduction:.2f}%")


def main():
    parser = argparse.ArgumentParser(description='比较不同Peres算法版本的性能')
    parser.add_argument('--algorithm', '-a', choices=['original', 'v1', 'compare'], default='compare',
                        help='选择要测试的算法版本 (original, v1 或 compare)')
    parser.add_argument('--runs', '-r', type=int, default=10000000,
                        help='每个p值的运行次数')
    parser.add_argument('--p-values', '-p', nargs='+', type=float, default=[0.1, 0.3, 0.5, 0.7, 0.9],
                        help='要测试的p值列表')

    args = parser.parse_args()

    if args.algorithm == 'compare':
        compare_algorithms(args.p_values, args.runs)
    else:
        if args.algorithm == 'original':
            algorithm = peres_algorithm
            print("测试原始 Peres 算法")
        else:
            algorithm = peres_algorithm_v1
            print("测试 Peres 算法 v1")

        print(f"每个p值运行 {args.runs} 次")
        print(f"测试的p值: {args.p_values}")
        print("-" * 50)

        analyze_algorithm(algorithm, args.p_values, args.runs)


if __name__ == "__main__":
    main()

E:\WorkSpaces\py-workspace\.venv\Scripts\python.exe E:\WorkSpaces\py-workspace\practices\peres_algorithm.py 
============================================================
原始 Peres 算法性能:
============================================================
p=0.1: 总递归次数=45552379, 平均递归次数=4.5552, 输出1的概率=0.5002
p=0.3: 总递归次数=13818528, 平均递归次数=1.3819, 输出1的概率=0.5004
p=0.5: 总递归次数=10004429, 平均递归次数=1.0004, 输出1的概率=0.5002
p=0.7: 总递归次数=13811390, 平均递归次数=1.3811, 输出1的概率=0.5002
p=0.9: 总递归次数=45528876, 平均递归次数=4.5529, 输出1的概率=0.4998

============================================================
优化版 Peres 算法 v1 性能:
============================================================
p=0.1: 总递归次数=42727577, 平均递归次数=4.2728, 输出1的概率=0.5173
p=0.3: 总递归次数=10602775, 平均递归次数=1.0603, 输出1的概率=0.5192
p=0.5: 总递归次数=6666487, 平均递归次数=0.6666, 输出1的概率=0.4999
p=0.7: 总递归次数=10597108, 平均递归次数=1.0597, 输出1的概率=0.4808
p=0.9: 总递归次数=42739576, 平均递归次数=4.2740, 输出1的概率=0.4827

============================================================
性能比较:
============================================================
p=0.1: 原始平均递归=4.5552, v1平均递归=4.2728, 减少=6.20%
p=0.3: 原始平均递归=1.3819, v1平均递归=1.0603, 减少=23.27%
p=0.5: 原始平均递归=1.0004, v1平均递归=0.6666, 减少=33.36%
p=0.7: 原始平均递归=1.3811, v1平均递归=1.0597, 减少=23.27%
p=0.9: 原始平均递归=4.5529, v1平均递归=4.2740, 减少=6.13%