كيف يمكن حساب المسافة الإقليدية باستخدام NumPy؟

Question

لدي نقطتان في 3D:

(xa, ya, za)
(xb, yb, zb)

وأريد حساب المسافة:

dist = sqrt((xa-xb)^2 + (ya-yb)^2 + (za-zb)^2)

ما هي أفضل طريقة للقيام بذلك مع NumPy، أو مع Python بشكل عام؟أملك:

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

Answer 1

numpy.linalg.norm :

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

Answer 2

وهناك وظيفة لأنه في SciPy. انه دعا الإقليدية .

مثال:

from scipy.spatial import distance
a = (1, 2, 3)
b = (4, 5, 6)
dst = distance.euclidean(a, b)

Answer 3

لأي شخص مهتم في حساب مسافات متعددة في وقت واحد، لقد فعلت القليل مقارنة باستخدام perfplot ( مشروع صغير من الألغام). وتبين أن

a_min_b = a - b
numpy.sqrt(numpy.einsum('ij,ij->i', a_min_b, a_min_b))

ويحسب المسافات الصفوف في a وb أسرع. هذا حاصل في الواقع ينطبق على صف واحد فقط، وكذلك!

---

ورمز لإعادة إنتاج المؤامرة:

import matplotlib
import numpy
import perfplot
from scipy.spatial import distance


def linalg_norm(data):
    a, b = data
    return numpy.linalg.norm(a-b, axis=1)


def sqrt_sum(data):
    a, b = data
    return numpy.sqrt(numpy.sum((a-b)**2, axis=1))


def scipy_distance(data):
    a, b = data
    return list(map(distance.euclidean, a, b))


def mpl_dist(data):
    a, b = data
    return list(map(matplotlib.mlab.dist, a, b))


def sqrt_einsum(data):
    a, b = data
    a_min_b = a - b
    return numpy.sqrt(numpy.einsum('ij,ij->i', a_min_b, a_min_b))


perfplot.show(
    setup=lambda n: numpy.random.rand(2, n, 3),
    n_range=[2**k for k in range(20)],
    kernels=[linalg_norm, scipy_distance, mpl_dist, sqrt_sum, sqrt_einsum],
    logx=True,
    logy=True,
    xlabel='len(x), len(y)'
    )

Answer 4

وثمة مثال آخر من هذا حل مشكلة طريقة :

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)

Answer 5

أريد أن أشرح الإجابة البسيطة مع ملاحظات الأداء المختلفة.ربما سيفعل 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

تذكر عدة أشياء:

• استدعاءات دالة بايثون باهظة الثمن.
• [العادي] لا تقوم لغة Python بتخزين عمليات البحث عن الأسماء مؤقتًا.

لذا

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 بدلاً من X^2، يمكننا التخلص من الجزء الأصعب من الحسابات.

# 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 وفي حدود Nm من Y"، حيث لا يتعين عليك حساب المسافة مرة أخرى).

ولكن ماذا لو كنا نبحث في قائمة كبيرة حقًا من 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))

Answer 6

وأجد وظيفة "حي" في matplotlib.mlab، لكنني لا أعتقد أنه مفيد بما فيه الكفاية.

وأنا نشرها هنا فقط للرجوع اليها.

import numpy as np
import matplotlib as plt

a = np.array([1, 2, 3])
b = np.array([2, 3, 4])

# Distance between a and b
dis = plt.mlab.dist(a, b)

Answer 7

ويمكن ان يتم ذلك كما يلي. أنا لا أعرف كيف سريع هو عليه، لكنها لا تستخدم نمباي.

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)))

Answer 8

ويمكنك فقط طرح ناقلات ثم innerproduct.

واقتداء بك،

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

tmp = a - b
sum_squared = numpy.dot(tmp.T, tmp)
result sqrt(sum_squared)

ووهو رمز بسيط وسهل الفهم.

Answer 9

وأنا أحب np.dot (دوت المنتج):

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

distance = (np.dot(a-b,a-b))**.5

Answer 10

بدء Python 3.8، و math حدة يوفر مباشرة في وظيفة dist ، التي ترجع المسافة الإقليدية بين نقطتين (نظرا بمثابة الصفوف (tuple) من ينسق):

from math import dist

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

إذا كنت تعمل مع القوائم بدلا من المجموعات:

dist(tuple([1, 2, 6]), tuple([-2, 3, 2]))

Answer 11

وبعد a وb كما كنت تعرف عليها، يمكنك أيضا استخدام:

distance = np.sqrt(np.sum((a-b)**2))

Answer 12

بطانة واحدة لطيفة:

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

ومع ذلك، إذا كانت السرعة مصدر قلق، فإنني أوصي بالتجربة على جهازك.لقد وجدت أن استخدام math المكتبة sqrt مع ال ** يعد مشغل المربع أسرع بكثير على جهازي من حل NumPy ذو الخطوط الواحدة.

لقد أجريت اختباراتي باستخدام هذا البرنامج البسيط:

#!/usr/bin/python
import math
import numpy
from random import uniform

def fastest_calc_dist(p1,p2):
    return math.sqrt((p2[0] - p1[0]) ** 2 +
                     (p2[1] - p1[1]) ** 2 +
                     (p2[2] - p1[2]) ** 2)

def math_calc_dist(p1,p2):
    return math.sqrt(math.pow((p2[0] - p1[0]), 2) +
                     math.pow((p2[1] - p1[1]), 2) +
                     math.pow((p2[2] - p1[2]), 2))

def numpy_calc_dist(p1,p2):
    return numpy.linalg.norm(numpy.array(p1)-numpy.array(p2))

TOTAL_LOCATIONS = 1000

p1 = dict()
p2 = dict()
for i in range(0, TOTAL_LOCATIONS):
    p1[i] = (uniform(0,1000),uniform(0,1000),uniform(0,1000))
    p2[i] = (uniform(0,1000),uniform(0,1000),uniform(0,1000))

total_dist = 0
for i in range(0, TOTAL_LOCATIONS):
    for j in range(0, TOTAL_LOCATIONS):
        dist = fastest_calc_dist(p1[i], p2[j]) #change this line for testing
        total_dist += dist

print total_dist

على جهازي، math_calc_dist يعمل بشكل أسرع بكثير من numpy_calc_dist: 1.5 ثانية عكس 23.5 ثانية.

للحصول على فرق قابل للقياس بين fastest_calc_dist و math_calc_dist كان علي أن أصعد TOTAL_LOCATIONS إلى 6000.ثم fastest_calc_dist يأخذ ~50 ثانية بينما math_calc_dist يأخذ ~60 ثانية.

يمكنك أيضًا تجربة numpy.sqrt و numpy.square على الرغم من أن كلاهما كان أبطأ من math البدائل على الجهاز الخاص بي.

تم إجراء اختباراتي باستخدام Python 2.6.6.

Answer 13

إليك بعض التعليمات البرمجية موجزة عن المسافة الإقليدية في بيثون نظرا نقطتين تمثل كقوائم في بيثون.

def distance(v1,v2): 
    return sum([(x-y)**2 for (x,y) in zip(v1,v2)])**(0.5)

Answer 14

import numpy as np
from scipy.spatial import distance
input_arr = np.array([[0,3,0],[2,0,0],[0,1,3],[0,1,2],[-1,0,1],[1,1,1]]) 
test_case = np.array([0,0,0])
dst=[]
for i in range(0,6):
    temp = distance.euclidean(test_case,input_arr[i])
    dst.append(temp)
print(dst)

Answer 15

import math

dist = math.hypot(math.hypot(xa-xb, ya-yb), za-zb)

Answer 16

ويمكنك بسهولة استخدام الصيغة

distance = np.sqrt(np.sum(np.square(a-b)))

والتي في الواقع لا شيء أكثر من استخدام نظرية فيثاغورس "لحساب المسافة، وذلك بإضافة مربعات Δx، Δy وΔz وتأصيل نتيجة.

Answer 17

وحساب المسافة الإقليدية للفضاء متعدد الأبعاد:

 import math

 x = [1, 2, 6] 
 y = [-2, 3, 2]

 dist = math.sqrt(sum([(xi-yi)**2 for xi,yi in zip(x, y)]))
 5.0990195135927845

Answer 18

وابحث عن الفرق اثنين مصفوفات أولا. ثم، وتطبيق عنصر الضرب الحكمة مع قيادة تتضاعف نمباي ل. بعد ذلك، والعثور على الجمع العنصر تضاعفت الحكمة مصفوفة جديدة. وأخيرا، والعثور على الجذر التربيعي للالجمع.

def findEuclideanDistance(a, b):
    euclidean_distance = a - b
    euclidean_distance = np.sum(np.multiply(euclidean_distance, euclidean_distance))
    euclidean_distance = np.sqrt(euclidean_distance)
    return euclidean_distance