[python] NumPy로 유클리드 거리를 어떻게 계산할 수 있습니까?

다양한 성능 메모로 간단한 답변에 대해 설명하고 싶습니다. np.linalg.norm은 아마도 필요한 것보다 더 많은 것을 할 것입니다 :

dist = numpy.linalg.norm(a-b)

첫째 -이 기능에서의 거리를 비교하기 위해, 예를 목록을 통해 일을하고 모든 값을 반환하도록 설계 pA점의 세트 sP:

sP = set(points)
pA = point
distances = np.linalg.norm(sP - pA, ord=2, axis=1.)  # 'distances' is a list

몇 가지 사항을 기억하십시오.

• 파이썬 함수 호출은 비싸다.
• [일반] 파이썬은 이름 조회를 캐시하지 않습니다.

그래서

def distance(pointA, pointB):
    dist = np.linalg.norm(pointA - pointB)
    return dist

보이는 것처럼 결백하지 않습니다.

>>> dis.dis(distance)
  2           0 LOAD_GLOBAL              0 (np)
              2 LOAD_ATTR                1 (linalg)
              4 LOAD_ATTR                2 (norm)
              6 LOAD_FAST                0 (pointA)
              8 LOAD_FAST                1 (pointB)
             10 BINARY_SUBTRACT
             12 CALL_FUNCTION            1
             14 STORE_FAST               2 (dist)

  3          16 LOAD_FAST                2 (dist)
             18 RETURN_VALUE

첫째, 우리가 호출 할 때마다 “np”에 대한 전역 조회, “linalg”에 대한 범위 조회 및 “norm”에 대한 범위 조회를 수행해야하며 단순히 함수 호출 의 오버 헤드 가 수십 개의 파이썬과 동일 할 수 있습니다. 명령.

마지막으로 결과를 저장하고 다시로드하기 위해 두 가지 작업을 낭비했습니다 …

개선시 첫 번째 단계 : 조회 속도를 높이고 상점을 건너 뜁니다.

def distance(pointA, pointB, _norm=np.linalg.norm):
    return _norm(pointA - pointB)

훨씬 간소화되었습니다.

>>> dis.dis(distance)
  2           0 LOAD_FAST                2 (_norm)
              2 LOAD_FAST                0 (pointA)
              4 LOAD_FAST                1 (pointB)
              6 BINARY_SUBTRACT
              8 CALL_FUNCTION            1
             10 RETURN_VALUE

그러나 함수 호출 오버 헤드는 여전히 일부 작업에 해당합니다. 그리고 자신이 수학을 더 잘 수행 할 수 있는지 판단하기 위해 벤치 마크를 수행하려고합니다.

def distance(pointA, pointB):
    return (
        ((pointA.x - pointB.x) ** 2) +
        ((pointA.y - pointB.y) ** 2) +
        ((pointA.z - pointB.z) ** 2)
    ) ** 0.5  # fast sqrt

일부 플랫폼에서는 **0.5보다 빠릅니다 math.sqrt. 귀하의 마일리지가 다를 수 있습니다.

**** 고급 성능 정보.

왜 거리를 계산합니까? 유일한 목적으로 표시하는 경우

 print("The target is %.2fm away" % (distance(a, b)))

를 따라 이동. 그러나 거리를 비교하거나 범위 검사 등을 수행하는 경우 유용한 성능 관찰을 추가하고 싶습니다.

거리를 기준으로 정렬하거나 범위 제약 조건을 충족하는 항목으로 목록을 컬링하는 두 가지 경우를 살펴 보겠습니다.

# Ultra naive implementations. Hold onto your hat.

def sort_things_by_distance(origin, things):
    return things.sort(key=lambda thing: distance(origin, thing))

def in_range(origin, range, things):
    things_in_range = []
    for thing in things:
        if distance(origin, thing) <= range:
            things_in_range.append(thing)

가장 먼저 기억해야 할 것은 피타고라스 를 사용하여 거리 ( dist = sqrt(x^2 + y^2 + z^2)) 를 계산하여 많은 sqrt통화를하고 있다는 것입니다. 수학 101 :

dist = root ( x^2 + y^2 + z^2 )
:.
dist^2 = x^2 + y^2 + z^2
and
sq(N) < sq(M) iff M > N
and
sq(N) > sq(M) iff N > M
and
sq(N) = sq(M) iff N == M

간단히 말해 실제로 X ^ 2가 아닌 X 단위로 거리가 필요할 때까지 계산에서 가장 어려운 부분을 제거 할 수 있습니다.

# Still naive, but much faster.

def distance_sq(left, right):
    """ Returns the square of the distance between left and right. """
    return (
        ((left.x - right.x) ** 2) +
        ((left.y - right.y) ** 2) +
        ((left.z - right.z) ** 2)
    )

def sort_things_by_distance(origin, things):
    return things.sort(key=lambda thing: distance_sq(origin, thing))

def in_range(origin, range, things):
    things_in_range = []

    # Remember that sqrt(N)**2 == N, so if we square
    # range, we don't need to root the distances.
    range_sq = range**2

    for thing in things:
        if distance_sq(origin, thing) <= range_sq:
            things_in_range.append(thing)

두 함수 모두 더 이상 고가의 제곱근을 수행하지 않습니다. 훨씬 빠릅니다. in_range를 발전기로 변환하여 향상시킬 수도 있습니다.

def in_range(origin, range, things):
    range_sq = range**2
    yield from (thing for thing in things
                if distance_sq(origin, thing) <= range_sq)

다음과 같은 일을 할 때 특히 이점이 있습니다.

if any(in_range(origin, max_dist, things)):
    ...

하지만 다음에해야 할 일에 거리가 필요한 경우

for nearby in in_range(origin, walking_distance, hotdog_stands):
    print("%s %.2fm" % (nearby.name, distance(origin, nearby)))

튜플 생성을 고려하십시오.

def in_range_with_dist_sq(origin, range, things):
    range_sq = range**2
    for thing in things:
        dist_sq = distance_sq(origin, thing)
        if dist_sq <= range_sq: yield (thing, dist_sq)

거리 확인을 연쇄 할 수있는 경우 ( ‘거리를 다시 계산할 필요가 없으므로 X 근처에 있고 Y의 Nm 내에있는 것을 찾으십시오’) 특히 유용합니다.

그러나 우리가 정말로 큰 목록을 검색 things하고 많은 것을 고려할 가치가 없다면 어떻게해야 할까요?

실제로 매우 간단한 최적화가 있습니다.

def in_range_all_the_things(origin, range, things):
    range_sq = range**2
    for thing in things:
        dist_sq = (origin.x - thing.x) ** 2
        if dist_sq <= range_sq:
            dist_sq += (origin.y - thing.y) ** 2
            if dist_sq <= range_sq:
                dist_sq += (origin.z - thing.z) ** 2
                if dist_sq <= range_sq:
                    yield thing

이것이 유용한 지 여부는 ‘사물’의 크기에 달려 있습니다.

def in_range_all_the_things(origin, range, things):
    range_sq = range**2
    if len(things) >= 4096:
        for thing in things:
            dist_sq = (origin.x - thing.x) ** 2
            if dist_sq <= range_sq:
                dist_sq += (origin.y - thing.y) ** 2
                if dist_sq <= range_sq:
                    dist_sq += (origin.z - thing.z) ** 2
                    if dist_sq <= range_sq:
                        yield thing
    elif len(things) > 32:
        for things in things:
            dist_sq = (origin.x - thing.x) ** 2
            if dist_sq <= range_sq:
                dist_sq += (origin.y - thing.y) ** 2 + (origin.z - thing.z) ** 2
                if dist_sq <= range_sq:
                    yield thing
    else:
        ... just calculate distance and range-check it ...

그리고 다시 dist_sq를 산출하는 것을 고려하십시오. 핫도그 예제는 다음과 같습니다.

# Chaining generators
info = in_range_with_dist_sq(origin, walking_distance, hotdog_stands)
info = (stand, dist_sq**0.5 for stand, dist_sq in info)
for stand, dist in info:
    print("%s %.2fm" % (stand, dist))

답변

def dist(x,y):
    return numpy.sqrt(numpy.sum((x-y)**2))

a = numpy.array((xa,ya,za))
b = numpy.array((xb,yb,zb))
dist_a_b = dist(a,b)

from math import dist

dist((1, 2, 6), (-2, 3, 2)) # 5.0990195135927845

dist([1, 2, 6], [-2, 3, 2]) # 5.0990195135927845

from math import sqrt
a = (1, 2, 3) # Data point 1
b = (4, 5, 6) # Data point 2
print sqrt(sum( (a - b)**2 for a, b in zip(a, b)))