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

голоса
8

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

  1. Почти все элементы дублируются несколько раз.
  2. Элементы не обязательно являются целыми числами или что-нибудь еще, что это так же просто. Диапазон клавиш даже не хорошо определены, не говоря уже мало. На самом деле, ключи могут быть произвольными Структуры. Это исключает самые простые формы подсчета рода.
  3. Мы заботимся об обеих асимптотических и неасимптотических свойствах, а п может быть небольшими иногда. Однако, когда п мало, производительность по-прежнему важна, потому что эта функция может быть вызвана несколько миллионов раз в цикле на миллионах маленьких наборов данных. Это исключает какой-либо дорогой хэш-функции или используя сложную структуру данных, которая должна выполнять множество распределений памяти.
  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].

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

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

Задан 09/12/2008 в 22:00
источник пользователем
На других языках...                            


9 ответов

голоса
10

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

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

EDIT: Позвольте мне добавить, что причина, по которой я предлагаю пользовательский хэш-карту, потому что я не знаю одного, который предоставляет достаточно его внутренней реализации для вас, чтобы получить значения из каждого сегмента. Там может быть такая реализация, что я не знаю. Есть много вещей, которые я не знаю. :)

Ответил 09/12/2008 в 22:04
источник пользователем

голоса
4

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

Ответил 09/12/2008 в 23:17
источник пользователем

голоса
3

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

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

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

Ответил 09/12/2008 в 22:10
источник пользователем

голоса
1

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

Ответил 09/12/2008 в 22:16
источник пользователем

голоса
1

3-полосная QuickSort работает очень хорошо , когда есть большое количество дубликатов.

Ответил 09/12/2008 в 22:14
источник пользователем

голоса
0

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

  1. Предположим, входной массив с именем как размер ввода, имеющий в качестве п.
  2. Выделяют память для возврата массива с таким же размером с именем, как результат
  3. Выделяет память для булевого массива с таким же размером с именем как посещенные и установить все посещаемые как ложь
  4. Предположим, что существует равноправный функция с именем Равно возвращает истину, если оба элемента равны еще ложь.
  5. Предположим, индекс массива начинается от 1 до п
  6. Пожалуйста, смотрите Псевдо 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;
}
Ответил 10/12/2008 в 08:16
источник пользователем

голоса
0

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

Ответил 09/12/2008 в 22:36
источник пользователем

голоса
0

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

Ответил 09/12/2008 в 22:19
источник пользователем

голоса
0

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

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;
    }
}
Ответил 09/12/2008 в 22:16
источник пользователем

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more