У меня есть нечто, похожее на решение.
На каждом шаге «повторного вычисления» требуется линейное время, которое, я думаю, не является большой проблемой, как вы делаете recompute_nearest (Actor A) для каждого актера.
Давайте перейдем к сути: идея для каждого актера, добавить определенное количество случайных друзей непосредственно перед вычислением recompute_nearest (Actor A). Это число не должно быть маленьким, иначе вы никогда не обнаружите ошибки. Он не должен быть слишком большим, иначе вычисление соседей соседей является квадратичным, это будет слишком дорого в вычислительном отношении.
Но что значит "не слишком маленький" или "не слишком большой"? Мы начнем с одного актера А и посмотрим, как будет обновляться его список соседей. Предположим, что для каждой точки вы добавляете p процентов от первоначальных K актеров. Затем, если другой пункт B приближается к A, но не является другом друга, мы должны «быстро» добавить его через «случайные друзья». На каждой итерации есть (1-p) шанс не выбирать его.
Быстрое вычисление показывает, что если вы хотите определить эту точку за 10 итераций или менее в 90% случаев, вам потребуется p=20%. Это ужасно дорого.
...
Однако еще не все потеряно! Первое, что я хочу сделать, это то, что если ошибки имеют тенденцию «идти вместе», то производительность резко возрастает! Представьте себе два капли, которые изначально находятся далеко друг от друга (люди в чате, звездные скопления и т. Д.). Если эти капли сталкиваются, друг друга никогда не увидит, что существует проблема. Но с моим алгоритмом, если вы обнаружите одну-единственную ошибку и правильно адаптируете свой список соседей, тогда алгоритм друга-друга исправит все оставшиеся ошибки.
Если у вас есть K=1.000 и два маленьких шарика, каждый из которых содержит только 1% точек, и вы хотите выделить 10 итераций или меньше с уверенностью 99%, вы можете вычислить, что вам понадобится только p=1%! (Чем больше K, тем меньше должно быть p!) Ну, это предполагает, что некоторые точки «идут вместе».
У меня есть еще одна оптимизация: адаптировать количество и качество случайных точек. Проще говоря, быстрым актерам нужно дать больше случайных друзей, чем медленным. И вы должны рандомизировать этих друзей, предпочитая других быстрых актеров. Я не могу определить это, но вы можете догадаться, почему это улучшит производительность!
Небольшая правка по вашему вопросу: «Что мне делать, когда актеры быстры»? Вы можете перевести скорость актеров с количеством шагов, которые вы даете себе, чтобы определить ошибку. Я имею в виду, что если вы считаете, что каждый актер окружает своих друзей. Этот теоретический круг соответствует его списку друзей. Если большинство актеров не могут полностью пересечь этот круг за 10 итераций, но могут за 15 итераций, вам следует подумать, что вы даете себе 10 итераций, чтобы определить проблему. Если ваши актеры настолько быстры, что могут пересечь этот «круг» за 3 шага, тогда, ну ... этот алгоритм не для вас (и я думаю, что иллюзорно пытаться вести список соседей, не пересчитывая его на каждом шаге)
По сути, ведение списка соседей предполагает наличие некоторой структуры (т.е. что-то примерно одинаковое между двумя итерациями). Скорость наоборот, быстрые актеры означают, что у вас нет структуры. В случае очень быстрых актеров, ведение списка соседей, вероятно, плохая идея.
Техническая информация о каплях.
У вас есть два больших объекта, каждый из которых содержит s% актеров (размер sK) (например, s = 1%)
Вы задаете себе погрешность в e% (пример 1%) и n шагов (пример 10)
Тогда есть верхняя граница для p: p <= [log(1-e^(1/n))]/[s*K²*log(1-s)]
Истинное значение моего примера - p <= 0.989%!
У вас есть p = [log(1-e^(1/n))]/[s*K²*log(1-s)], если s мало, а K большое. Если это не так, р намного меньше!