实现 求解最接近点对问题 的代码 要求 1 随机产生输入点，数量为100, 1000, 10000 2 打印输出不同规模下求解所需的计算时间，运行50次，记录耗时的均值和方差

在Python中，我们可以使用一些高效的算法如近似最近邻搜索库（如`annoy`或`faiss`）来解决最接近点对问题。这里是一个简化的示例，我们将使用`faiss`库来实现，并使用`timeit`模块来测量运行时间。首先需要安装`faiss`：

pip install faiss-cpu

然后编写一个简单的脚本：

import numpy as np
from faiss import IndexFlatL2, RandIndex
from timeit import default_timer as timer
from random import uniform

# 定义函数来生成随机数据并计算距离
def generate_random_points(n):
    dim = 2  # 假设二维空间
    points = np.random.rand(n, dim) * 100  # 生成范围在[0, 100]内的随机点
    return points

# 使用Faiss创建索引
def create_index(points):
    index = IndexFlatL2(points.shape[1])  # 创建基于欧氏距离的扁平索引
    index.add(points)
    return index

# 计算最接近点对
def compute_nearest_neighbors(index, n_pairs=100):
    pairs = [[i, j] for i in range(len(index)) for j in range(i + 1, len(index))]
    start_time = timer()
    nearest_neighbors = index.search(np.array(pairs), 1)  # 查找每个点对之间的最近邻居
    end_time = timer()

    return end_time - start_time

# 主函数，运行实验并收集结果
def run_experiments(scales):
    times = []
    for scale in scales:
        print(f"Running for {scale} points:")
        
        # 生成数据、创建索引并测量时间
        points = generate_random_points(scale)
        index = create_index(points)
        mean_time, variance_time = [], []

        # 运行50次并计算平均时间和方差
        for _ in range(50):
            t = compute_nearest_neighbors(index)
            times.append(t)
            mean_time.append(np.mean(times))
            variance_time.append(np.var(times))

        print(f"Mean time: {np.mean(mean_time):.3f}s, Variance: {np.mean(variance_time):.3f}")

    print("\nExperiment completed.")

scales = [100, 1000, 10000]
run_experiments(scales)