PYTHON Effektivt finne lengste vector basert på en liste

6. september 2016

Scenarioet er at jeg har en liste med vectorer, det jeg ønsker å gjøre er å finne vector-parrene som er lengst unna hverandre.

Eksempel:

Kode

# Vector-posisjoner:
xyVectors = [[126, 627], [288, 607], [288, 733]]

Kode

# Vector-posisjonene som er lengst unna hverandre
xyVectors[0] ([126, 627])
xyVectors[2] ([288, 733])
# Distanse
193.59752064528098

Jeg har forsåvidt en egen løsning på dette, men jeg er sikker på at det finnes bedre, kortere, raskere og mer effektive måter å gjøre dette på.

Her er løsningen min:

Kode

# Create variables to store the result in
vector1 = []
vector2 = []

# Generate 8 vector-positions (x,y)
xyVectors = [[rand.randint(100,400),rand.randint(600,900)] for x in range(1,8)]

# Create a variable to store the largest distance in
largestDist = 0

# Outer loop: For each item in the list
for x in range(0, len(xyVectors)):
    # Inner loop: For each item in the list
    for y in range(0, len(xyVectors)):
        # If the outer loop is not the same as the inner loop
        if x != y:
            # Find the distance between the current elements
            dist = math.sqrt(math.pow((xyVectors[x][0]-xyVectors[y][0]),2) + math.pow((xyVectors[x][1]-xyVectors[y][1]),2))
            # If the current distance is larger than largestDist
            if dist > largestDist:
                # Update the variables
                largestDist = dist
                vector1 = xyVectors[x]
                vector2 = xyVectors[y]

Spørsmål:
Er det noen som har tips til hvordan man kan skrive denne koden bedre (uten å bruke scipy)?

Ozma

55535 HP

3.680 1.125

6. september 2016

Det finnes en raskere algoritme. Trikset er å først finne "the convex hull" av punktmengden. Kort forklart, om du putter en strikk rundt punktene dine og strammer til, kommer noen av punktene til å være i kontakt med strikken. Om du tenker litt etter, er det tydelig at punktene som er lengst unna hverandre må være noen av disse punktene, og du kan derfor konsentrere deg om kun disse.

Det neste trikset er at det også finnes en rask algoritme for å finne par med punkt som er lengst unna hverandre på en slik konveks linje.
https://en.wikipedia.org/wiki/Rotating_calipers

Sist endret av Ozma; 6. september 2016 kl. 15:44.

Xasma

dumstein

2.156 2.023

6. september 2016

Den raskeste optimaliseringen å gjennomføre er vel å se på hvordan du rent logisk går igjennom listene dine. Med din implementasjon nå, så sjekker du alle avstander to ganger. Du vil ved å bare loope naivt over samme liste regne ut distanse for 0->1 og så litt senere sjekke distansen 1->0. Jeg gir deg ikke løsningen før du har gjort et forsøk, men det skal gå relativt greit om du har skrevet koden over selv.

Sist endret av Xasma; 6. september 2016 kl. 16:21. Grunn: presiserte formulering

steili

1. d4

1.745 518

6. september 2016

En litt mer naiv metode du kan bruke hvis ikke ytelse er veldig viktig for deg, er å bruke itertools.combinations for å finne alle kombinasjoner av punkter og bruke den innebygde max-metoden for å lettere finne det største paret:

Kode

from itertools import combinations
from math import sqrt

def dist(v1, v2):
    return sqrt((v1[0]-v2[0])**2 + (v1[1]-v2[1])**2)

xyVectors = [[126, 627], [288, 607], [288, 733]]
max_length, v1, v2 = max(((dist(v1, v2), v1, v2) for (v1, v2) in combinations(xyVectors, 2)), key=lambda i: i[0])

Sist endret av steili; 6. september 2016 kl. 16:12.