Algoritmo para encontrar 100 estrellas más cercanas al origen

Question

En primer lugar quiero expresar la pregunta adecuada:

Q: Hay un archivo que contiene más de un millón de puntos (x, y) cada uno de los cuales representa una estrella. Hay un planeta tierra en (a, b). Ahora, la tarea es construir un algoritmo que devuelva las 100 estrellas más cercanas a la tierra. Cuáles serían las complejidades de tiempo y espacio de su algoritmo.

Esta pregunta se ha hecho muchas veces en varias entrevistas. Traté de buscar las respuestas pero no pude encontrar una respuesta satisfactoria.

Una forma de hacerlo, que pensé que podría estar usando un montón máximo de tamaño 100. Calcule las distancias para cada estrella y compruebe si la distancia es menor que la raíz del montón máximo. Si es así, reemplázalo con la raíz y llama a heapify.

¿Alguna otra respuesta mejor/más rápida?

P.S: Esta no es una pregunta para la tarea.

Answer 1

Puede hacer esto en el tiempo O (n) y en el espacio O (k), donde k es el número de puntos más cercanos que desea, utilizando un truco muy inteligente.

El selection problem es como sigue: Dado un conjunto de elementos y algún índice i, reorganizar los elementos de la matriz de tal manera que el i-ésimo elemento es en el lugar correcto, todos los elementos más pequeños que el i-ésimo elemento están a la izquierda , y todos los elementos mayores que el i-ésimo elemento están a la derecha. Por ejemplo, dada la matriz

40 10 00 30 20 

Si tratara de seleccionar basado en el índice 2 (cero-indexada), un resultado podría ser

10 00 20 40 30 

Dado que el elemento en el índice 2 (20) está en el lugar correcto, los elementos a la izquierda son más pequeños que 20 y los elementos a la derecha son mayores que 20.

Resulta que, dado que este es un requisito menos estricto que la ordenación de la matriz, es posible hacer esto en el tiempo O (n), donde n es la cantidad de elementos de la matriz. Hacerlo requiere algunos algoritmos complejos como el algoritmo median-of-medians, pero de hecho es O (n) tiempo.

¿Cómo se usa esto aquí? Una opción es cargar todos los n elementos del archivo en una matriz, luego usar el algoritmo de selección para seleccionar la parte superior k en el tiempo O (n) y el espacio O (n) (aquí, k = 100).

¡Pero en realidad puede hacerlo mejor que esto! Para cualquier constante k que desee, mantenga un buffer de 2k elementos. Cargue 2k elementos del archivo en la matriz, luego use el algoritmo de selección para reorganizarlo de manera que los elementos k más pequeños estén en la mitad izquierda de la matriz y los más grandes estén en la derecha, luego descarte los elementos k más grandes (pueden ' t sea uno de los k puntos más cercanos). Ahora, cargue k más elementos del archivo en el búfer y vuelva a hacer esta selección, y repita esto hasta que haya procesado cada línea del archivo. Cada vez que haces una selección, descartas los elementos k más grandes en el búfer y conservas los k puntos más cercanos que has visto hasta ahora. En consecuencia, al final, puede seleccionar los elementos superiores k por última vez y encontrar la parte superior k.

¿Cuál es la complejidad del nuevo enfoque? Bueno, estás usando memoria O (k) para el buffer y el algoritmo de selección. Usted termina llamando a seleccionar en un búfer de tamaño O (k) un total de O (n/k) veces, ya que llama a seleccionar después de leer k elementos nuevos.Como seleccionar en un búfer de tamaño O (k) lleva el tiempo O (k), el tiempo de ejecución total aquí es O (n + k). Si k = O (n) (una suposición razonable), esto toma tiempo O (n), espacio O (k).

Espero que esto ayude!

Answer 2

Es una pregunta famosa y ha habido mucho de la solución para eso: http://en.wikipedia.org/wiki/K-nearest_neighbor_algorithm

si no les sea útil, hay algunos otros recursos como el libro de geometría computacional de Rurk.

Answer 3

Su algoritmo es correcto. Solo recuerde que la complejidad del tiempo de su programa es O (n. Log 100) = O (n), a menos que el número de puntos más cercanos para encontrar pueda variar.

Answer 4

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

Answer 5

dar más detalles sobre la solución MaxHeap usted construir un max-montón con los primeros k elementos del archivo (k = 100 en este caso).

La clave para el montón máximo sería su distancia desde la Tierra (a, b). Distancia entre 2 puntos en un plano 2D puede calcularse usando:

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

Esto llevaría tiempo O (k) para construir. Para cada elemento posterior de k a n. es decir, (n - k) elementos que necesita para recuperar su distancia de la tierra y compararla con la parte superior de max-heap. Si el nuevo elemento que se va a insertar está más cerca de la tierra que la parte superior del montón máximo, reemplace la parte superior de la pila máxima y llame a heapify en la nueva raíz del montón.

Esto tomaría O ((n-k) logk) tiempo para completar. Finalmente nos quedarían solo los k elementos en el montón máximo. Puedes llamar a heapify k veces para devolver todos estos elementos k. Este es otro O (klogk).

La complejidad del tiempo total sería O (k + (n-k) logk + klogk).