Самый эффективный алгоритм сортировки для множества идентичных ключей?

Question

Какой самый эффективный алгоритм для группировки идентичных элементов в массиве, учитывая следующее:

1. Почти все элементы продублированы несколько раз.
2. Элементы не обязательно являются целыми числами или чем-то еще, что так же просто. Диапазон клавиш даже не четко определен, не говоря уже о небольшом. На самом деле ключи могут быть произвольными структурами. Это исключает самые простые формы подсчета сортировки.
3. Мы заботимся об асимптотических и неасимптотических свойствах, и иногда n может быть небольшим. Однако, когда n мало, производительность по-прежнему важна, потому что эта функция может вызываться несколько миллионов раз в цикле для миллионов небольших наборов данных. Это исключает любую дорогостоящую хэш-функцию или использование сложной структуры данных, которая должна выполнять много выделений памяти.
4. Данные могут быть отсортированы в произвольном порядке, если все идентичные элементы сгруппированы.

Если это сбивает с толку, вот пример, предполагая, что такая функция называется groupIdentical:

uint[] foo = [1,2,3,2,1,5,4,5];
uint[] bar = groupIdentical(foo);
// One possibile correct value for bar:
// bar == [2,2,1,1,3,4,5,5].
// Another possible correct answer:
// bar == [1,1,2,2,5,5,4,3].

Однако, как напоминание, мы не можем предполагать, что данные составлены как целые числа.

Редактировать: Спасибо за ответы. Моя основная проблема с хешированием заключалась в том, что хеш-таблицы часто выполняют выделение памяти. В итоге я написал собственную хеш-таблицу, в которой использовался распределитель областей, который у меня был, чтобы обойти эту проблему. Хорошо работает.

Answer 1

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

Чтобы избежать коллизий между типами данных (чтобы строки не заканчивались в том же сегменте, что и удваивается, для одного примера), вам необходимо закодировать тип данных в хеш. Так, например, если у вас есть 32-битный хеш, возможно, первые 5 битов могут кодировать тип данных, так что вы можете иметь 32 разных типа в одной хэш-карте.

РЕДАКТИРОВАТЬ: Позвольте мне просто добавить, что причина, по которой я предлагаю настраиваемую хеш-карту, заключается в том, что я не знаю одну, которая предоставляет достаточно внутренней реализации, чтобы вы могли получать значения из каждого сегмента. Может быть такая реализация, о которой я не знаю. Есть много вещей, которые я не знаю. :)

Answer 2

Волшебное слово, которое вы ищете здесь: multiset (или bag ). На самом деле это совсем не так, поскольку вам не важен порядок, если все элементы с одинаковыми ключами сгруппированы вместе. Существует несколько доступных реализаций, в зависимости от языка, который вы используете, но в целом приведенная выше версия хеширования является асимптотически оптимальной, я считаю: insert() - это постоянное время, поскольку вы можете вычислить хеш в O (1 ) и добавлять встречные вставки в список за O (1) время; вы можете извлечь один элемент из бункеров за O (1) раз, вы просто берете первый из бункеров; и поэтому вы можете собрать их все за O (n) время, так как вы получаете n элементов с O (1) для каждого элемента.

Answer 3

Скачущая сортировка слиянием, такая как встроенная сортировка Python (cf timsort ), имеет хорошую ожидаемую производительность, когда есть большие серии уже отсортированных данных (как, например, в вашем примере, идентичные объекты) - - вы пропустите O (log (N)) работы на слияние. Вы также можете распределить сортировку слиянием по нескольким процессорам и дискам, если ваш набор данных очень большой (это называется «внешней» сортировкой). Тем не менее, это будет худший случай O (Nlog (N)).

Единственные сортировки, которые выполняются быстрее, чем Nlog (N), это подсчет сортировок, которые используют некоторые общие свойства ключей. Чтобы использовать линейную сортировку по времени (хеш-таблицу или сортировку по основанию / сегменту), вам нужно будет хешировать структуры, чтобы сгенерировать какой-либо числовой ключ.

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

Answer 4

Я думаю, что наилучшим решением будет хэширование в сегменты, если предположить, что есть хеш, который сохраняет оператор = отображение (0.0 может не хэшировать одно и то же -0.0, но они могут быть «равными»). Предполагая, что у вас есть только оператор равенства и меньше чем, вы могли бы реализовать рудиментарный алгоритм быстрой сортировки, выбирая первый элемент в качестве основного, и помещая меньше, чем в одной группе, и больше, чем в другой группе, и затем повторяя процесс по каждой группе.

Answer 5

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

Answer 6

Простой алгоритм с порядком производительности O (n (n-1) / 2) выглядит следующим образом:

1. Предположим, что входной массив с именем Input имеет размер n.
2. Выделите память для возвращаемого массива с тем же размером, что и Result.
3. Выделите память для логического массива с тем же размером, что и Visited, и установите для всех Visted значение false.
4. Предположим, что есть функция Equal с именем Equals, которая возвращает true, если оба элемента равны, иначе false.
5. Предположим, что индекс массива начинается с 1 до n
6. Пожалуйста, смотрите код Pseudo C ниже:

function groupIdentical(Input) 
{
    k=1;
    for i=1 to n 
    {
        Visited[i]=false ;
    }

    for i=1 to n
    {
        if( !Visited(i) )
        {   
            Result[k++]=Input[i];
            for j= (i+1) to n
            {
                if( Equals(i,j) )
                {
                    Result[k++]=Input[j];
                    Visited[j]=true;
                }   
            }
        }
    }
    return Result;
}

Answer 7

Может быть, дерево R + B или AVL? Опять же - это все равно будет в конечном итоге O (NlogN). Можно использовать и heapsort - хуже не будет и не будет лишнего использования памяти ...

Answer 8

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

Answer 9

Если вы знаете диапазон возможных значений, и он небольшой, вы можете сделать:

uint[] bucket = new int[10];
foreach(uint val in foo) {
    ++bucket[val];
}

uint bar_i = 0;
uint[] bar = new int[foo.length];
foreach(int val = 0; val < 10; val++) {
    uint occurrences = bucket[val];
    for(int i=0; i < occurrences; i++) {
        bar[bar_i++] = val;
    }
}