Gravity Sort: Возможно ли это программно?

Ответ 1

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

Представьте, какие действия необходимы для вашей процедуры:

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

Учитывая, что проблема дополнительно вводит дополнительные осложнения. Спросите себя: как высоко вам нужно позиционировать эти объекты? Очевидно, достаточно высокий, чтобы на самом деле упал самый большой. то есть дальше от Земли, чем радиус наибольшего объекта. Но откуда вы знаете, как далеко это? Вам нужно будет сначала определить самый большой объект в коллекции; это, опять же, потребует (возможно) итерации. Кроме того, можно предположить, что это моделирование может быть многопоточным, чтобы попытаться имитировать поведение в реальном времени понятия фактически падающих объектов; но тогда вы обнаружите, что пытаетесь добавить элементы в коллекцию (операция, которая, очевидно, занимает ненулевое время), потенциально одновременно с обнаружением новых коллизий. Таким образом, это также создаст проблемы с потоками.

Короче говоря, мне трудно представить, как эта идея может быть правильно реализована просто с помощью ООП без специального оборудования. Тем не менее, это действительно хорошая идея. Это на самом деле напоминает мне Bead Sort - алгоритм, который, хотя и не тот, что и ваша идея, также является решением для сортировки, которое принимает преимущество самой физической концепции гравитации и, что неудивительно, требует специализированного оборудования.

Ответ 2

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

Ответ 3

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

Ответ 4

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

Ответ 5

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

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

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

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

Ответ 6

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

Ответ 7

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

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

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

Ответ 8

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

Ответ 9

Хммм. Гравитация.

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

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

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

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

Ответ 10

http://www.youtube.com/watch?v=5C5_dOEyAfk

Ответ 11

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

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

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

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

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

Ответ 12

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

Ответ 13

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

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

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

Ответ 14

Я думаю, что проблему можно упростить следующим образом: вы хотите поместить днища сфер на разных высотах, чтобы при падении при одинаковых гравитациях наибольшее попало на землю сначала, второе по величине секунду и т.д. Это по существу эквивалентно использованию линий, а не сфер... В этом случае вы можете просто сказать, что 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)... с большой константой очень... постоянное количество дельта-значений, которые система будет работать. Недостаток заключается в том, что для очень большой величины этих дельта-значений вы, по сути, не приближаетесь к ответу: на любой заданной итерации очень вероятно, что все сферы/линии/все будет перемещено... но нет ударит.

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

Ответ 15

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

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

Хорошо, так что вы хотите имитировать это.

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

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

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

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

Ответ 16

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

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

Блестящая идея тем не менее.

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

O 0 o O oудаp >

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

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

Ответ 17

from Debilski answer:

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

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

Я бы упростил это еще раз и сказал, что эти объекты являются случайными положительными целыми числами. И мы хотим сортировать их в порядке возрастания по мере приближения к нулю, поэтому они имеют расстояние от нуля 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. Псевдокод выше - это моя идея псевдокода, пожалуйста, не стесняйтесь переписывать его более разборчивым или соответствующим образом, если он есть.

Ответ 18

На самом деле существует довольно известный алгоритм сортировки под названием Spaghetti sort, который похож на ваш. Вы можете проверить некоторые из многих анализов этого в Интернете. например на cstheory.

Ответ 19

• Я считаю, что приятно упомянуть/обратиться к: Какое отношение между P против NP и способностью природы решать проблемы NP эффективно? Сортировка O(nlog(n)), почему бы не попытаться решить NP-жесткие проблемы?
• По законам физики объекты падают пропорционально гравитационная константа масса незначительна.
• Имитация физического процесса может повлиять на фактическую сложность времени.

Ответ 20

Анализ: (1) Все центры сфер выровнены в начале (2) большее число == > масса выше == > радиус больше == > расстояние до земли ниже (3) в "вакууме" такое же ускорение = такая же эволюция скорости == > то же расстояние для центра == > как больший радиус... как раньше сфера ударит по земле == > концептуально ОК, хорошая физическая техника, если при попадании шара на землю он может отправить сигнал определения + время попадания..., которое даст отсортированный список Практически... не "хороший" числовой метод