python - 有效计算欧氏距离内的随机值(就时间而言)Python

Question

你能帮我计算 N 个大小为 d 的随机对向量 x 和 y ，使得 x_i 和 y_i 属于实数范围 U[-1,1] ，并且 x 和 y 之间的欧几里得距离可以小于或等于小T吗？我需要在 Python 中有效地计算这 N 对(就时间而言)。

我试过了

 import numpy as np
 d = 4
 inv_d = 1.0 / d
 random_lst = []
 T = 0.05
 N = 10
 for i in range(N):
     while(1):
         x = np.random.uniform(low=-1, high=1, size=d)
         y = np.random.uniform(low=-1, high=1, size=d)
         length = np.linalg.norm(x-y)
         if length <= T:
             random_lst.append([x,y])
             print(length)
             break
 print(random_lst)

但是花了很多时间(40秒)，而且我需要N接近10^6，也就是说可能需要更多时间

Answer 1

这是该问题的快速且直接的近似解决方案。所得向量将始终小于且足够接近，但不等于给定长度。首先，让我们实现一个辅助函数，用于将任何自然数拆分为一组正随机数，这些随机数加起来等于给定的输入数。

def split(num, buckets=1, result=None):

    if result is None:
        result = []

    if buckets < 2:
        result.append(num)
        np.random.shuffle(result)
        return result

    bucket = np.random.uniform(low=0, high=num) if num > 0 else 0
    result.append(bucket)

    return split(num - bucket, buckets - 1, result)

这是它的工作原理

>>> xs = split(10, buckets=3)
>>> xs
[7.60495737395197, 0.6968567573189194, 1.698185868729111]
>>> sum(xs)
10.0

现在，让我们创建一个函数，在给定坐标边界、维数和距离的情况下，从欧几里德空间返回一对点。

def point_pair(low=-1, high=1, dim=2, dist=0.05):
    x = np.random.uniform(low=-1, high=1, size=dim)
    diff = split(dist, dim)
    y = np.clip(x + diff, low, high)
    return x, y

它是这样工作的:

>>> point_pair(dim=4, dist=0.05)
(array([ 0.18856095, -0.02635086, -0.59616698, -0.51447733]),
 array([ 0.20485765, -0.01791704, -0.59026813, -0.49510669]))

最后，让我们测试一下:

>>> pairs = []
>>> for _ in range(10):
        pairs.append(point_pair(dim=4, dist=0.05))
>>> all(np.linalg.norm(x - y) < 0.05 for x, y in pairs)
True

这是在相当慢的机器 Intel(R) Core(TM) m5-6Y54 CPU @ 1.10GHz 上进行的简单运行测试:

>>> %timeit point_pair(dim=4, dist=0.05)
38.6 µs ± 4.52 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)