Вид силы тяжести: действительно ли это возможно программно? [закрытый]

Хмммм. Гравитационная сортировка.

Игнорировать вашу конкретную модель гравитации неправильно, давайте посмотрим, куда нас приведет эта идея.

Физическая реальность имеет 10 ^ 80 процессоров.

Фактические нижние границы сортировки известны как log (N), если у вас есть N / 2 процессоров для сортировки N объектов.

Если у вас доступно несколько ядер ЦП, нет причин, по которым вы не можете запустить сортировку слиянием для нескольких потоков.

Игнорирование всех недостатков, о которых упоминали все остальные, по сути, сводится к алгоритму O (n ^ 2) , а не O (n) . Вам нужно будет перебрать все «сферы», найти «самый тяжелый» или «самый большой», а затем добавить его в список, затем промыть и повторить. то есть, чтобы найти тот, который первым ударяется о землю, вам нужно перебрать весь список, если он последний, потребуется O (n) времени, второй может занять ] O (n-1) и т.д ... но хуже того, вам нужно каждый раз выполнять кучу математических операций, чтобы вычислить какое-то бесполезное значение "времени", когда вы могли бы отсортировать по значению, которое вы были интересует в первую очередь.

Это определенно должно быть только у вас должно быть соответствующее оборудование для этого. В остальном это звучит очень круто. Надеюсь, кто-нибудь представит документ IEEE, чтобы воплотить эту безумную мечту в жизнь.

Мне нравится идея! Это умно. Хотя да, то, что другие говорят, в целом правильно, что граница O (n log n) является доказуемой нижней границей для задачи сортировки в целом, мы должны помнить, что эта нижняя оценка верна только для моделей, основанных на сравнении . То, что вы предлагаете, - это совершенно другая модель, она заслуживает дальнейшего рассмотрения.

Кроме того, как указали Джеймс и Матрикс, более тяжелый объект не движется быстрее, чем более легкий, вам, очевидно, нужно адаптировать модель к чему-то, где более тяжелый объект (число) действительно будет перемещаться быстрее / дальше (или медленнее / меньше дальше), чтобы можно было как-то различать числа (также приходит на ум центрифуга).

Требуется больше размышлений, но зато твоя идея острая!

(Edit) Теперь, глядя на идею Энрике Phys2D, я думаю, что она имеет гораздо больший смысл.

Я бы посоветовал пока полностью игнорировать аспект эффективности. (Я знаю, я знаю, что это была вся цель). Это новая модель, и нам сначала нужно преодолеть разрыв между идеей и ее реализацией. Только тогда мы сможем понять, что вообще означает временная сложность для этой модели.

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

EDIT: Упс. Забыл физику 101. Конечно, они все ударятся одновременно. :)

Любое моделирование, подобное этому, просто превращает одну проблему сортировки в другую. Вы ничего не выиграете.

Идея может показаться простой, но разница между реальным миром и смоделированным в данном случае состоит в том, что в реальном мире все происходит параллельно. Чтобы смоделировать гравитационную сортировку, как вы описываете, вам придется начать с обдумывания каждого объекта в отдельном потоке с поточно-безопасным способом добавить их в список в порядке их завершения. Реально с точки зрения производительности сортировки вы, вероятно, просто использовали бы быструю сортировку по временам, или поскольку они находятся на том же расстоянии, что и скорость падения. Однако, если ваша формула пропорциональна массе, вы просто пропустите все это и отсортируете массу.

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

Сортировка общего назначения доказуема в лучшем случае за O (n log n). Чтобы улучшить это, вы должны знать что-то о данных, кроме того, как сравнивать значения.

Если все значения являются числами, сортировка по основанию дает O (n), если у вас есть верхняя и нижняя границы для чисел. Этот подход может быть расширен для обработки любого числа - и в конечном итоге все данные на компьютере представлены с помощью чисел. Например, вы можете сортировать строки по основанию системы счисления, на каждом проходе сортируя их по одному символу, как если бы это была цифра.

К сожалению, обработка переменных размеров данных означает выполнение переменного числа проходов через сортировку по основанию. В итоге вы получите O (n log m), где m - наибольшее значение (поскольку k бит дает вам значение до (2 ^ k) -1 для беззнакового, половинное значение для подписанного). Например, если вы сортируете целые числа от 0 до m-1, хорошо - у вас снова снова O (n log n).

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

Расчет гравитации бесплатен только в реальном мире. В программе вам нужно его моделировать. Это будет еще n в сложности минимум

В фиктивном «гравитационном компьютере» для решения такого рода сортировки потребуется O (1). Но с настоящими компьютерами, какими мы их знаем, ваша боковая мысль не поможет.

Немного изменю вашу идею. У нас есть объекты, но они отличаются не по весу, а по скорости. Итак, вначале все объекты выровнены по стартовой линии, а при стартовом выстреле все они будут двигаться с соответствующей скоростью к финишу.

Достаточно ясно: первый объект на финише издаст сигнал, сообщая, что он там. Вы ловите сигнал и пишете в листе результатов, кто это был.

Хорошо, вы хотите смоделировать это.

Мы принимаем длину вашего поля равной L = 1 . При размере шага ∆t каждый из ваших N объектов перемещается на vᵢ ∙ ∆t за один раз. Это означает, что каждому объекту требуется sᵢ = L / (vᵢ ∙ ∆t) шагов до финиша.

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

В лучшем случае это означает, что объект 1 завершается за один шаг, объект 2 за два и так далее. Следовательно, общее количество шагов равно S = 1 + 2 +… + N = N ∙ (N + 1) / 2 . Это порядка N ∙ N .

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

Я думаю, что проблему можно упростить следующим образом: вы хотите расположить нижнюю часть сфер на разной высоте, чтобы при падении с одинаковой силой тяжести самый большой упал на землю первым, второй по величине - вторым и т. Д. эквивалентно использованию линий, а не сфер ... в этом случае вы можете просто сказать, что heightOffTheGround = MAX_VALUE - масса.

Вам также не нужно беспокоиться об ускорении с течением времени ... поскольку вас не волнует, насколько быстро они движутся или реалистичная физика, вы можете задать им всем начальную скорость x и двигаться оттуда.

Проблема в том, что мы, по сути, просто переформулировали проблему и решили ее следующим образом (псевдокод):

int[] sortedArray; // empty
int[] unsortedArray; // full of stuff
int iVal = MAX_INT_VALUE;
while (true)
{
    foreach (currentArrayValue in sortedArray)
    {
        if (iVal = current array value
        {
            put it in my sortedArray
            remove the value from my unsortedArray
        }
    }
    if (unsortedArray is empty)
    {
        break;  // from while loop
    } 
    iVal--
}

Проблема в том, что для запуска физического движка вы должны перебирать каждую единицу времени, и это будет O (1) ... с очень большой константой ... постоянным числом значений дельты, на которых будет работать система. Недостатком является то, что для очень большого количества этих значений дельты вы, по сути, не приблизитесь к ответу: на любой данной итерации очень вероятно, что все сферы / линии / что угодно будет перемещено ... но ни один ударит.

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

Несколько недель назад я думал о том же самом.

Я решил использовать библиотеку Phys2D для его реализации. Это может быть непрактично, но просто для развлечения. Вы также можете присвоить объектам отрицательные веса, чтобы представить отрицательные числа. С помощью библиотеки Phys2d вы можете определить силу тяжести, чтобы объекты с отрицательным весом переходили на крышу, а объекты с положительным весом падали вниз. Затем расположите все объекты посередине между полом и крышей на одинаковом расстоянии между полом и крышей. Предположим, у вас есть результирующий массив r [] длины = количеству объектов. Затем каждый раз, когда объект касается крыши, вы добавляете его в начало массива r [0] и увеличиваете счетчик, в следующий раз, когда объект касается крыши, вы добавляете его в r [1], каждый раз, когда объект достигает этажа, вы добавьте его в конец массива r [r.length-1], в следующий раз, когда вы добавите его в r [r.length-2]. В конце объекты, которые не двигались (оставались плавающими посередине), могут быть добавлены в середину массива (эти объекты - нули).

Это неэффективно, но может помочь вам реализовать вашу идею.

Если бы нужно было построить компьютер, который сортирует объекты на основе некоторых критериев (о которых не так уж и смешно думать), то я считаю, что порядок сложности не будет иметь ничего общего с количеством объектов, а скорее со скоростью местного ускорения свободного падения. Если предположить, что он смоделирован на Земле, сложность будет O (g ₀ ), где g ₀ равно:

Простым аргументом является то, что количество сферических объектов (n ) не имеет значения, если их центры выровнены в начале. Более того, ускорение свободного падения будет иметь гораздо большее влияние, чем сама высота, когда она увеличивается. Например, если мы увеличим высоту всех объектов в 10 раз, им потребуется не в 10 раз больше времени, чтобы упасть на землю, а гораздо меньше. Это включает в себя различные пренебрежимо малые приближения, поскольку ускорение фактически зависит от расстояния между двумя объектами, но его можно игнорировать, поскольку нас больше интересует более широкая картина, чем конкретное значение.

Тем не менее, блестящая идея.

Также мне нравится видео о сортировке монет, опубликованное @Jeremy. И, наконец, объектно-ориентированность была бы наименьшей из моих забот при создании такой машины. Если подумать, вот мои глупые два цента на создание такой машины:

O 0 o O o

. . . . .
. . . . .
. . . . .
= = = = =

Все объекты имеют разные размеры, пропорциональные критериям, по которым мы хотим сортировать. Изначально они удерживаются вместе по горизонтали тонким стержнем, который проходит через центр каждой сферы. = внизу специально разработаны для записи значения (необязательно их положения) где-нибудь, как только они сталкиваются со сферой.После того, как все сферы столкнутся, у нас будет порядок сортировки на основе записанных значений.