из ответа Дебильски:
Немного адаптирую вашу идею. У нас есть объекты, но они отличаются не по весу, а по скорости. Итак, вначале все объекты выровнены по стартовой линии, и при стартовом выстреле все они будут двигаться с соответствующей скоростью к финишу.
Достаточно ясно: первый объект на финише издаст сигнал, сообщая, что он там. Вы ловите сигнал и пишете в листе результатов, кто это был
Я бы упростил его еще на один шаг и сказал, что эти объекты являются случайными положительными целыми числами. И мы хотим отсортировать их в порядке возрастания по мере приближения к нулю, чтобы у них было расстояние от нуля d, которое изначально равно самому целому числу.
Предполагая, что моделирование происходит с дискретными временными шагами, то есть кадрами, в каждом кадре новое расстояние каждого объекта будет: d = d - v, и объект будет добавлен в список, когда его d ≤ 0. Это одно вычитание и одно условие. Два дискретных шага для каждого объекта, поэтому вычисления кажутся O (n): линейными.
Загвоздка в том, что она линейна только для одного кадра! Он умножается на количество f кадров, необходимых для завершения. Сама симуляция O (nf): квадратичная.
Однако, если мы возьмем продолжительность кадра в качестве аргумента t, мы получим возможность влиять на количество кадров f обратно пропорционально. Мы можем увеличить t, чтобы уменьшить f, но это происходит за счет точности: чем больше мы увеличиваем t, тем больше вероятность того, что два объекта закончатся в один и тот же период времени, поэтому они будут перечислены как эквивалентные, даже если это не так. Таким образом, мы получаем алгоритм с регулируемой точностью (как в большинстве контекстов моделирования методом конечных элементов).
Мы можем дополнительно уточнить это, превратив его в адаптивный + рекурсивный алгоритм. В человеческом коде это будет:
function: FESort: arguments: OriginalList, Tolerance
define an empty local list: ResultList
while OriginalList has elements
define an empty local list: FinishedList
iterate through OriginalList
decrement the distance of each object by Tolerance
if distance is less than or equal to zero, move object from OriginalList to FinishedList
check the number of elements in FinishedList
when zero
set Tolerance to double Tolerance
when one
append the only element in FinishedList to ResultList
when more
append the result of FESort with FinishedList and half Tolerance to ResultList
return ResultList
Мне интересно, есть ли какая-нибудь похожая реализация, которая работает для кого-то.
Действительно интересная тема :)
PS. Приведенный выше псевдокод является моей идеей псевдокода, пожалуйста, не стесняйтесь переписать его более разборчивым или совместимым образом, если он есть.
person
edgerunner
schedule
10.09.2010
planetsсо мной согласуется. Я использовал его, чтобы создать симуляцию с большой сферой посередине, а также средними и меньшими сферами с обеих сторон, а затем нажал кнопку «Вперед». Один среднего размера засветился на большом среднем раньше, чем тот, что поменьше. Таким образом, если предположить, что он точно закодирован, может показаться, что более крупные объекты действительно «падают быстрее», если они проявляют значительную гравитационную силу. - person intuited schedule 27.03.2010