Алгоритм поиска 100 ближайших звезд в начале координат

Сначала позвольте мне рассказать о правильном вопросе:

Q: Файл содержит более миллиона точек (x, y), каждый из которых представляет звезду. На (a, b) есть планета Земля. Теперь задача состоит в том, чтобы построить алгоритм, который вернет 100 ближайших звезд на Землю. Какими будут временные и пространственные сложности вашего алгоритма.

Этот вопрос задавался много раз в разных интервью. Я попытался найти ответы, но не смог найти удовлетворительный.

Один из способов сделать это, который, как я думал, может использовать максимальная куча размера 100. Рассчитайте расстояния для каждой звезды и проверьте, меньше ли расстояние, чем корень максимальной кучи. Если да, замените его корнем и вызовите heapify.

Любые другие лучшие/быстрые ответы?

P.S: Это не вопрос домашней работы.

Ответ 1

Фактически вы можете сделать это во времени O (n) и пространстве O (k), где k - это число ближайших точек, которое вы хотите, используя очень умный трюк.

Проблема выбора заключается в следующем: учитывая массив элементов и некоторый индекс i, измените элементы массива таким образом, чтобы i-й элемент находится в нужном месте, все элементы, меньшие, чем i-й элемент, находятся влево, а все элементы, большие, чем i-й элемент, находятся справа. Например, учитывая массив

40  10  00  30  20

Если я попытался выбрать на основе индекса 2 (с нулевой индексацией), один результат может быть

10  00  20  40  30

Поскольку элемент с индексом 2 (20) находится в нужном месте, элементы слева меньше 20, а элементы справа больше 20.

Оказывается, что, поскольку это менее строгое требование, чем фактическая сортировка массива, это можно сделать во времени O (n), где n - количество элементов массива. Для этого требуются некоторые сложные алгоритмы, такие как медианный медианы, но на самом деле O (n) время.

Итак, как вы это используете? Один из вариантов - загрузить все n элементов из файла в массив, а затем использовать алгоритм выбора для выбора верхнего k в O (n) времени и O (n) пробела (здесь k = 100).

Но вы действительно можете сделать это лучше! Для любой константы k, которую вы хотели бы, поддерживайте буфер из 2k элементов. Загрузите 2k элементов из файла в массив, затем используйте алгоритм выбора, чтобы перестроить его так, чтобы наименьшие k элементов находились в левой половине массива, а наибольшие - справа, а затем отбрасывали наибольшие k элементов (они могут " t - любая из k ближайших точек). Теперь загрузите еще больше элементов из файла в буфер и снова сделайте этот выбор, и повторите это, пока не обработаете каждую строку файла. Каждый раз, когда вы делаете выбор, вы отбрасываете наибольшие k элементов в буфере и сохраняете k ближайших точек, которые вы видели до сих пор. Следовательно, в самом конце вы можете выбрать верхние k элементов в последний раз и найти верхний k.

Какова сложность нового подхода? Ну, вы используете память O (k) для буфера и алгоритм выбора. Вы в конечном итоге вызываете выбор в буфере размера O (k) в сумме O (n/k) раз, поскольку вы вызываете select после чтения k новых элементов. Поскольку выбор в буфере размера O (k) занимает время O (k), общая продолжительность выполнения здесь O (n + k). Если k = O (n) (разумное предположение), это занимает время O (n), пространство O (k).

Надеюсь, это поможет!

Ответ 2

Чтобы разработать решение MaxHeap, вы должны построить максимальную кучу с первыми k элементами из файла (k = 100 в этом случае).

Ключом для максимальной кучи будет расстояние от Земли (a, b). Расстояние между 2 точками на 2d-плоскости можно рассчитать, используя:

dist = (x1,y1) to (x2,y2) = square_root((x2 - x1)^2 + (y2 - y1)^2);

Это потребовало бы времени O (k). Для каждого последующего элемента от k до n. т.е. (n - k) элементов, которые необходимо извлечь из земли и сравнить их с вершиной максимальной кучи. Если новый элемент, который нужно вставить, ближе к земле, чем верхняя часть максимальной кучи, замените верхнюю часть максимальной кучи и вызовите heapify на новый корень кучи.

Это займет время O ((n-k) logk). Наконец, мы оставили бы только k элементов в макс-куче. Вы можете вызвать heapify k раз, чтобы вернуть все эти k элементов. Это еще один O (klogk).

Общая временная сложность была бы равна O (k + (n-k) logk + klogk).

Ответ 3

Это известный вопрос, и для этого было много решений: http://en.wikipedia.org/wiki/K-nearest_neighbor_algorithm

если вы не нашли его полезным, есть другие ресурсы, такие как Rurk вычислительная геометрия.

Ответ 4

Ваш алгоритм правильный. Просто помните, что временная сложность вашей программы - O (n. Log 100) = O (n), если число ближайших точек не может меняться.

Ответ 5

import sys,os,csv

iFile=open('./file_copd.out','rU')
earth = [0,0]



##getDistance return distance given two stars
def getDistance(star1,star2):
    return sqrt((star1[0]-star2[0])**2 +(star1[1]-star2[1])**2 )


##diction dict_galaxy looks like this  {key,distance}  key is the seq assign to each star, value is a list [distance,its cordinance]
##{1,[distance1,[x,y]];2,[distance2,[x,y]]}
dict_galaxy={}
#list_galaxy=[]
count = 0
sour=iFile.readlines()
for line in sour:
    star=line.split(',')   ##Star is a list [x,y]
    dict_galaxy[count]=[getDistance(earth,star),star]
    count++

###Now sort this dictionary based on their distance, and return you a list of keys.
list_sorted_key = sorted(dict_galaxy,key=lambda x:dict_galaxy[x][0])

print 'is this what you want %s'%(list_sorted_key[:100].to_s)
iFile.close()