Вот моя конкретная проблема. Мне нужно написать алгоритм, который:
1) Принимает эти 2 массива:
a) Массив из примерно 3000 почтовых индексов (или почтовых индексов, если вы находитесь в США) с долготой и широтой центральной точки областей, которые они покрывают (то есть 3 числа на элемент массива)
b) Массив из примерно 120 000 местоположений, состоящий из долготы и широты
2) Преобразует каждое местоположение в почтовый индекс, центральная точка которого близка к заданной долготе и широте
Обратите внимание, что долгота и широта местоположений очень маловероятно точно соответствуют значениям в массиве почтовых индексов Вот почему я ищу кратчайшее расстояние до центральной точки области, охватываемой почтовым индексом.
Я знаю, как рассчитать расстояние между двумя парами долгота / широта. Я также ценю то, что близость к центральной точке области, покрытой почтовым индексом, не обязательно означает, что вы находитесь в области, покрытой этим почтовым индексом - если вы находитесь в очень большой области почтового индекса, но вблизи границы, вы можете быть ближе к центральной точке соседней области почтового индекса. Однако в этом случае мне не нужно это учитывать - достаточно кратчайшего расстояния до центральной точки.
Очень простым способом решения этой проблемы было бы посетить каждое из 120000 мест и найти почтовый индекс с ближайшей центральной точкой, рассчитав расстояние до каждой из 3000 центральных точек почтового индекса. Это будет означать 3000 x 120 000 = 360 000 000 вычислений расстояния.
Если бы почтовые индексы и местоположения были в одномерном пространстве (то есть идентифицированы 1 номером вместо 2), я мог бы просто отсортировать массив почтовых индексов по его одномерной центральной точке, а затем выполнить двоичный поиск в массиве почтовых индексов для каждого местоположения.
Так что я думаю, что я ищу способ сортировки двумерного пространства долготы и широты центральных точек почтового индекса, чтобы я мог выполнить двумерный двоичный поиск для каждого местоположения. Я видел решения этой проблемы, но они работают только для прямых матчей, в то время как я ищу центральную точку , закрывает до заданного местоположения.
Я рассматриваю решения для кэширования, но если бы существовал быстрый двумерный двоичный поиск, который я мог бы использовать, это значительно упростило бы решение.
Это будет частью пакетной программы, поэтому я не считаю миллисекунды, но это также не может занять несколько дней. Он будет запускаться раз в месяц без ручного вмешательства.