There are a bunch of points X, given in n-dimensional space (suppose we have two-dimensional, that is, the dimension of the array X is a bunch of x 2),
there is a single point C in the same space (dimension 1x2)
and there is a dist (u, v) metric, defined over a space, which determines the distance between two points (let us have a Euclidean metric, dist () returns a float).

Is there in pure python or in numpy (or somewhere else, to peep) a way to calculate the distances from C to all points X, faster than

[dst(x,C) for x in X]

?

And it is corny for a very long time in seconds.
In principle, it is also sufficient to obtain only the sum of these distances, if it suddenly turns out to be easier.

  • Hardly. Is that the implementation of dist on C. Since the calculation depends on the metric - the external function dist. But if the question concerns not so much a one-time calculation, but multiple recalculations, then it is already necessary to look at what changes during recalculations. - alexlz
  • The array of points X often changes, or is it static? - ReinRaus
  • Array X is static, changing S. - bekabaka
  • Then (for dist (x, C) = sqrt ((xX-CX) ** 2+ (xY-CY) ** 2), it comes to mind a realization on C with transfer X once. - alexlz

2 answers 2

The algorithm for optimal calculation certainly depends on the dist function. Because for each function there is a dist such algorithm.

If we consider the plane and Eklid distance, then an obvious optimization will notice that dist (a, b) = dist (b, a). Therefore, the usual cycle:

 for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) a[i, j] = dist(dots[i], dots[j]);

Can be replaced by:

 for (int i = 0; i < n; i++) for (int j = i+1; j < n; j++){ a[i, j] = dist(dots[i], dots[j]); a[j, i] = a[i, j]; }

Obviously, the most costly operation to calculate the Euclidean distance is the root. But it is clear that it can be omitted (i.e., all distances should be calculated without taking the root from the sum of squares). Then the distance properties will be preserved (for example, they can also be compared and we will get the same result as when calculating the root).

In general, as I said, you need to investigate the dist function and try to optimize its calculation.

  • And here dist(a,b)=dist(b,a) if we are talking about the distance from the center of C? @bekabaka factor analysis, automatic classification? - alexlz
  • I painted a general case. - megacoder
  • Thank you, sensibly, but the answer is not my question. I consider not the distances from each to each point, but only the distances from each to one, therefore the symmetry of the metric does not help. As for the fact that the main load is the calculation of the metrics - very sensibly, I have already thrown the root out of the Euclidean distance. But, unfortunately, the gain from this is not too noticeable. Hoped that there is some more efficient cycle. - bekabaka
  • one
    Is that the whole task? Those. you just need to figure out how to do it faster? Or did you solve some other problem that brought you to the need to be able to quickly find such distances? - megacoder

The distance to the grid of points can be calculated using matrices, as the length of a vector in complex numbers.

 >>> import numpy as np >>> import cmath >>> a = np.array([[ 0.+0.j, 0.+1.j],[1.+0.j, 1.+1.j]], dtype=np.complex) >>> a array([[ 0.+0.j, 0.+1.j], [ 1.+0.j, 1.+1.j]]) >>> n=0+0j >>> L=an >>> L array([[ 0.+0.j, 0.+1.j], [ 1.+0.j, 1.+1.j]]) >>> abs(L) array([[ 0. , 1. ], [ 1. , 1.41421356]]) >>> n=0.5+0.5j >>> n (0.5+0.5j) >>> L=an >>> abs(L) array([[ 0.70710678, 0.70710678], [ 0.70710678, 0.70710678]])

Below is an example that calculates distances from four points.

At each point of the grid, the sines from the distance are summed, and we get an analogue of the addition of waves.

Code:

 #!/usr/bin/env python import numpy as np import matplotlib.cm as cm import matplotlib.pyplot as plt import cmath razner=400 k=np.zeros((razner, razner), dtype=np.complex) for kx in range (razner): for ky in range (razner): k[kx,ky]=kx+(ky)*1j L1=k-250-50*1j L2=k-50-250*1j L3=k-150-250*1j L4=k-100-150*1j Z =np.sin(0.1*np.abs((L4)))+ np.sin(0.1*np.abs((L1)))+np.sin(0.1*np.abs((L2)))+np.sin(0.1*np.abs((L3))) im = plt.imshow(Z, interpolation='bilinear', cmap=cm.RdYlGn, origin='lower', extent=[-3, 3, -3, 3], vmax=abs(Z).max(), vmin=-abs(Z).max()) plt.savefig("d:\V4.pdf") plt.show()

enter image description here