以xy坐标为属性计算物体之间的距离

Question

假设我们有两种类型的对象，患者和医院：

import random

class Patient:
    def __init__(self):
        x = random.randint(0,100)
        y = random.randint(0,100)

class Hospital:
    def __init__(self):
        x = random.randint(0,100)
        y = random.randint(0,100)

假设我们有 25 名患者和 5 家医院的名单。

PatientList = []

for p in range(25):
    PatientList.append(Patient())

HospitalList = []

for p in range(5):
    HospitalList.append(Hospital())

目标是使用每个对象的 XY 坐标来找到距离单个患者最近的医院。理想情况下，我们还能够按照距离顺序对医院进行排名，或者至少能够在找到最近的医院后找到第二近的、第三近的等等。

Answer 1

import numpy as np
import random


class Patient:
    def __init__(self):
        self.x = random.randint(0, 100)  # you need to use self.x to access this variable
        self.y = random.randint(0, 100)


class Hospital:
    def __init__(self):
        self.x = random.randint(0, 100)
        self.y = random.randint(0, 100)


PatientList = []

for p in range(25):
    PatientList.append(Patient())

HospitalList = []

for p in range(5):
    HospitalList.append(Hospital())

# convert data to numpy arrays
PatientArray = np.array([[p.x, p.y] for p in PatientList])
HospitalArray = np.array([[p.x, p.y] for p in HospitalList])
PatientArray = PatientArray[:, np.newaxis]  # add an extra dimension

differences = PatientArray - HospitalArray  # broadcast
distances = np.linalg.norm(differences, axis=2)  # find euclidean distance
proximity_matrix = np.argsort(distances, axis=1)  # sort by proximity between patients and hospitals
PatientDict = {}  # create a dictionary with patients as keys and list of hospitals (ordered by proximity) as values

# iterate over the proximity matrix and the patient list simultaneously
for hospitals_proximity, patient in zip(proximity_matrix, PatientList):
    sorted_hospitals = [HospitalList[i] for i in hospitals_proximity]
    PatientDict[patient] = sorted_hospitals

现在

PatientDict

包含所有患者作为键，医院按距离排序作为值

Answer 2

首先，您需要分配字段：

class Patient:
    def __init__(self):
        self.x = random.randint(0,100) # use self.x
        self.y = random.randint(0,100)

class Hospital:
    def __init__(self):
        self.x = random.randint(0,100)
        self.y = random.randint(0,100)

您可以使用最小堆有效地找到最近的n家医院

import heapq
def closest_hospitals(patient, hospitals, n):
    heap = []
    for h in hospitals:
        # since we are not really concerned with the distance but closeness
        # we only need to compare dist^2
        dist = (patient.x - h.x)**2 + (patient.y - h.y)**2
        heap.append((dist, hospital))) 

    heapq.heapify(heap) # now we have a valid heap (this takes O(N=100))

    # then return n-closest
    closest = heapq.nsmallest(n, heap) #you choose n
    
    return closest

这很复杂

O(H + n * lg(H))

，其中H是医院的数量，n是距离您最近的医院的数量（相比之下，对所有内容进行排序需要

O(H lg H)

。