K ближайших элементов

Question

Это вопрос интервью.

Во Вселенной миллиарды и миллиарды звезд.Какую структуру данных вы бы использовали, чтобы ответить на вопрос «Дайте мне k звезд, ближайших к Земле».

Я думал о кучах.Как мы можем сделать heapify в O (n) и получить n_smallest в O (logn).Есть ли лучшая структура данных, подходящая для этой цели?

Answer 1

Предполагая, что входные данные не могут быть все одновременно сохранены в памяти (это будет проблемой!), Но это будет поток звезд во вселенной - как если бы вы получилиитератор или что-то в этом роде - вы могли бы извлечь выгоду из использования Max Heap (вместо Min Heap, которая может прийти в голову в первую очередь).

В начале вы просто нажмете звезды в куче, определяемые их расстояниемна земле, пока в вашей куче не будет k записей.

С тех пор вы игнорируете любую новую звезду, когда она находится на большем расстоянии, чем корень вашей кучи.Когда он ближе, чем корневая звезда, замените корень этой новой звездой и просейте его вниз, чтобы восстановить свойство кучи.

Ваша куча не вырастет больше, чем k элементов, иво все времена он будет состоять из k ближайших звезд из тех, что вы обработали.

Некоторые замечания:

• Поскольку это Max Heap, вы не знаете, какая ближайшая звезда (в постоянном времени).Когда вы остановите алгоритм, а затем вытянете корневой узел один за другим, вы получите k ближайших звезд в порядке убывания расстояния.

• AsНаблюдаемая (!) Вселенная имеет приблизительно 10 ²¹ количество звезд, вам потребуется один из лучших суперкомпьютеров ( 1 exaFLOPS ), чтобы надеяться обработать все эти звезды в разумные сроки.,Но, по крайней мере, этот алгоритм должен хранить в памяти k звезд.

Answer 2

Первая проблема, с которой вы столкнетесь, - это масштаб. В одной галактике Млечный Путь находится где-то между 100 и 400 миллиардами звезд. Есть приблизительно 10 миллиардов галактик. Если предположить в среднем 100 миллиардов звезд на галактику, это 10 ^ 19 звезд во вселенной. Вряд ли у вас будет память на это И даже если у вас было достаточно памяти, у вас, вероятно, нет времени. Если предположить, что ваша операция heapify может выполнять миллиард итераций в секунду, это займет триллион секунд (31 700 лет). И затем вам нужно добавить время, которое потребуется для удаления k наименьшего из кучи.

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

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

Однако отсортированный список будет довольно сложно обновить. Лучшей альтернативой будет дерево k-d . Обновление легче, и получение k ближайших соседей все еще достаточно быстро.