Сортировка вставкой в хэш-таблицу

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

Кому интересно – прошу под кат.


Итак, алгоритм работает следующим образом:
  1. На первом проходе находим минимальное и максимальное значения исходных данных для подсчёта коэффициента хэш-функции проецирования значений в диапазон индексов хэш-таблицы (Amin, Amax).
  2. На втором проходе вставляем исходные значения в хэш-таблицу, вычисляя индекс с помощью хэш-функции index=(int)(k*(Ai-Amin)*TMPLEN/(Amax-Amin)).
  3. На третьем проходе идём по хэш-таблице и копируем отсортированные данные в исходный массив.

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

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

Алгоритм относится к классу устойчивых сортировок, с комбинированием сравнения и вычисления.

Вычислительная сложность – от O(n*log n) (как я понял при сравнении с быстрой сортировкой, встроенной в Java) до O(n*n) в худшем случае. Если вы владеете матаппаратом, то сможете вывести это формально. Я уже всё позабыл. Жду ваших соображений в комментариях.

При равномерном распределении обнаружил, что алгоритм работает на 20-25% быстрее быстрой сортировки!

Затраты памяти – O(n).

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

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

Недостатки:
  • многовато памяти требует;
  • в малом диапазоне значений или при сильно неравномерном распределении производительность деградирует.

Не знаю, пригодится ли этот алгоритм на практике, но для академического изучения точно не помешает.

Мой исходный код для тестирования на Java.

Играя параметрами можно потестировать в разных режимах. Например, если установить SORTBLOCK=SOURCELEN, то будет применён чистый хэширующий алгоритм. С помощью MIN_VAL и MAX_VAL можно задать диапазон значений для генерации случайных чисел.

При SOURCELEN<300 отсортированные данные выводятся в консоль. За пустое значение в массиве я выбрал ноль, поэтому не стоит включать его в диапазон.

А понимаю, что измерение производительности не совсем корректно. Но для предварительной оценки вполне сгодится. Когда будет время — попробую на специальном фреймворке, как коллеги советуют.

import java.util.Arrays;
import java.util.Date;
import java.util.Random;

public class HashSort {

    // Размер массива исходных данных
    static int SOURCELEN = 1000000;
    int source[] = new int[SOURCELEN];
    
    // Копия исходных данных для сравнения с быстрой сортировкой
    int quick[] = new int[SOURCELEN];
    
    // Размер блока для хэширующей сортировки
    static int SORTBLOCK = 500;
    static int k = 3;
    
    // Временный массив
    static int TMPLEN = (SOURCELEN < SORTBLOCK * k) ? SORTBLOCK * k : SOURCELEN;
    int tmp[] = new int[TMPLEN];
    
    // Диапазон значений исходных данных
    static int MIN_VAL = 10;
    static int MAX_VAL = 1000000;

    int minValue = 0;
    int maxValue = 0;    
    double hashKoef = 0;
    
    long finishTime = 0;
    long startTime = 0;
    long finishTimeQuick = 0;
    long startTimeQuick = 0;
    
    // Заполнение массива исходных данных случайными значениями
    public void randomize() {
        int i;
        Random rnd = new Random();
        for(i=0; i<SOURCELEN; i++) {
            int rndValue = MIN_VAL + ((int)(rnd.nextDouble()*((double)MAX_VAL-MIN_VAL))); 
            source[i] = rndValue;
        }
    }

    // Поиск минимального и максимального значений плюс вычисление коэффициента для хэш-функции
    public void findMinMax(int startIndex, int endIndex) {
        int i;
        minValue = source[startIndex];
        maxValue = source[startIndex];
        for(i=startIndex+1; i<=endIndex; i++) {
            if( source[i] > maxValue) {
                maxValue = source[i];
            }
            if( source[i] < minValue) {
                minValue = source[i];
            }            
        }
        hashKoef = ((double)(k-1)*0.9)*((double)(endIndex-startIndex)/((double)maxValue-(double)minValue));
    }    
    
    // Склеивание двух смежных отсортированных частей массива
    public void stickParts(int startIndex, int mediana, int endIndex) {
        int i=startIndex;
        int j=mediana+1;
        int k=0;
        while(i<=mediana && j<=endIndex) {
            if(source[i]<source[j]) {
                tmp[k] = source[i];
                i++;
            } else {
                tmp[k] = source[j];
                j++;
            }
            k++;
        }
        
        if( i>mediana ) {
            while(j<=endIndex) {
                tmp[k] = source[j];
                j++;
                k++;
            }
        }
        if(j>endIndex) {
            while(i<=mediana) {
                tmp[k] = source[i];
                i++;
                k++;
            }
        }
        
        System.arraycopy(tmp, 0, source, startIndex, endIndex-startIndex+1);
    }
    
    // Сдвиг вправо во временном массиве для разрешения коллизий
    boolean shiftRight(int index) {
        
        int endpos = index;
        while( tmp[endpos] != 0) {
            endpos++;
            if(endpos == TMPLEN) return false;
        }
        
        while(endpos != index ) {
            tmp[endpos] = tmp[endpos-1];
            endpos--;
        }
               
        tmp[endpos] = 0;
        
        return true;
    }    

    // хэш-функция для хэширующей сортировки
    public int hash(int value) {
        return (int)(((double)value - (double)minValue)*hashKoef);
    }
    
    // вставка значений во временный массив с разрешением коллизий
    public void insertValue(int index, int value) {
        int _index = index;
        while(tmp[_index] != 0 && tmp[_index] <= value) { _index++; }
        if( tmp[_index] != 0) {
            shiftRight(_index);
        }
        tmp[_index] = value;
    }
    
    // копирование отсортированных данных из временного массива в исходный
    public void extract(int startIndex, int endIndex) {
        int j=startIndex;
        for(int i=0; i<(SORTBLOCK*k); i++) {
            if(tmp[i] != 0) {
                source[j] = tmp[i];
                j++;
            }
        }
    }    
    
    public void clearTMP() {
        
        if( tmp.length < SORTBLOCK*k) {
            Arrays.fill(tmp, 0);
        } else {
            Arrays.fill(tmp, 0, SORTBLOCK*k, 0);
        }
    }
    
    // Хэширующая сортировка
    public void hashingSort(int startIndex, int endIndex) {
        
        // 1. Поиск минимального и максимального значения с вычислением хэширующего коэффициента
        findMinMax(startIndex, endIndex);
        
        // 2. Очистка временного массива
        clearTMP();
        
        // 3. Вставка во временный массив с использованием хэш-функции
        for(int i=startIndex; i<=endIndex; i++) {
            insertValue(hash(source[i]), source[i]);
        }
        
        // 4. Перемещение отсортированных данных из временного массива в исходный
        extract(startIndex, endIndex);
    }
    
    // Рекурсивный спуск с дихотомией до уровня блока хэширующей сортировки 
    public void sortPart(int startIndex, int endIndex) {
        if( (endIndex - startIndex) <= SORTBLOCK ) {
           hashingSort(startIndex, endIndex);
           return;
        }
        
        int mediana = startIndex + (endIndex - startIndex) / 2;
        sortPart(startIndex, mediana);
        sortPart(mediana+1, endIndex);
        stickParts(startIndex, mediana, endIndex);
    }
    
    public void sort() {
        sortPart(0, SOURCELEN-1);
    }
    
    // Отображение результатов
    public String toString() {
        int i;
        String res = "";
        
        res += "Source:";
        if( SOURCELEN < 300) {
            for(i=0; i<SOURCELEN; i++) {
                res += " " + source[i];
            }
        }
        
        res += "\n";

        res += "Quick: ";
        if( SOURCELEN < 300) {
            for(i=0; i<SOURCELEN; i++) {
                res += " " + quick[i];
            }
        }
        
        res += "\n";
        
        res += "len: " + SOURCELEN + "\n";
        
        res += "hashing&merge sort time: " + (finishTime - startTime) + "\n";
        
        res += "quick sort time: " + (finishTimeQuick - startTimeQuick) + "\n";
        
        return res;
    }        
    
    // Копирование исходных данных для сравнения с быстрой сортировкой
    public void copyToQuick() {
        System.arraycopy(source, 0, quick, 0, source.length);
    }
    
    public static void main(String[] args) {

        HashSort hs = new HashSort();
        
        hs.randomize();
        hs.copyToQuick();
        
        hs.startTime = (new Date()).getTime();
        hs.sort();
        hs.finishTime = (new Date()).getTime();
        
       
        hs.startTimeQuick = (new Date()).getTime();
        Arrays.sort(hs.quick);
        hs.finishTimeQuick = (new Date()).getTime();
        
        System.out.println(hs.toString());
    }

}

AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама

Комментарии 19

    +2
    производительность соизмерима с быстрой сортировкой;

    таблицы/графики? Соизмерима в чью пользу? Если в пользу быстрой, то смысл использовать ее? Или есть какие-то исходные данные, на которых она показывает себя лучше? Как пример недавно упоминавшаяся сортировка на строках ABC.
      +1
      Будет желание и время — проведу подробные замеры и построю графики. Просто решил поделиться в таком виде, чтобы не потерять вдохновение :)
      +4
      Просто замечу, что код «сравнивающий» производительность Quick Sort с предложенным алгоритмом абсолютно ничего не доказывает.
      Если сравнивать «в лоб» сложности, то получается, что в среднем алгоритм медленнее Qucik Sort и потребляет памяти больше, чем Merge Sort. Область применимости остается загадкой.
        +1
        Не спорю ни разу. Надо всё хорошо померить, проанализировать, а потом и выводы делать.
        +1
        .
          +1
          На практике, увы, равномерное распределение данных (лучший случай для этого алгоритма) встречается редко.
          Однако, эта идея не лишена разумности и имеет право на существование.
          0
          Кроме того, хотелось бы обратить внимание автора на блочную сортировку
            +2
            Что-то Ваша хеш-функция и основная идея алгоритма немного мне напоминают FlashSort.

            В целом интересный метод, пополнит мою копилку алгоритмов сортировок.
              +2
              Спасибо за наводку. Не видел этого алгоритма. Действительно похож. Честно выводил сам.
                0
                Я «коллекционирую» методы сортировок (сейчас нашёл по интернетам более 60 штук) и Ваш способ вроде бы нигде не встречал. FlashSort он не эквивалентен, хотя, безусловно, это родственные алгоритмы.
                  +1
                  Нашёл что-то похожее: Здесь. Но автор стремится к O(n) и поэтому делает вставки немного по-другому, используя матрицу.
                    +1
                    И здесь тоже. Но опять немного по-другому. Ничто не ново под луной…
                +2
                Алгоритм относится к классу устойчивых сортировок? Правда?
                Он будет устойчив только в том случае, если из эквивалентности ключей (cmp(x,y)==0) следует равенство их хешей (h(x)==h(y)).
                Иначе может получиться так, что эквивалентные ключи окажутся в разных корзинах.

                Например, сравниваем строки нечувствительно к регистру. VASYA==Vasya==vasya, а хеши у этих строк одинаковые?

                Хеш-таблица служит для того, чтобы осмысленно разбить входной массив на подмассивы, так, что идентичные ключи окажутся в одной корзине.
                Но, во-первых, а существует ли какой-то выигрыш от этого? Если во входном наборе много дубликатов, то — выигрыш может быть, а может и не быть (вот как упадут все элементы в одну корзину, и что делать?)
                И, во-вторых, затраты на вычисление хеша — против тупого разбиения входного массива на случайные подмассивы.
                Причём, тупое разбиение на последовательные подмассивы как раз обеспечит устойчивость.
                  +1
                  «устойчивая сортировка не меняет взаимного расположения элементов с одинаковыми ключами» — из вики. Два одинаковых значения здесь претендуют на одно и тоже место. При разрешении коллизий порядок одинаковых значений не изменяется.

                  В чем проблема-то? К чему здесь сравнение строк и корзины я вообще, извините, не понял.
                    0
                    Ну, если алгоритм работает только над числами, и только с единственным отношением порядка — естественным для чисел — тогда конечно, проблемы нет.
                    Просто этот алгоритм не получится обобщить на произвольные типы данных.
                      0
                      А что значит произвольный тип данных? Как вы будите сортировать блоки например? По размеру? По весу? Когда требуется сортировка не чисел? Может я не понимаю вас, обьясните.
                        +1
                        Что, никогда строки не сортировали, например?

                        В общем случае, для упорядочивания произвольных данных достаточно лишь определения отношения порядка: что чего меньше-больше-равно. (Иначе, как можно было бы вообще понять, упорядочен набор данных или нет?)
                        И все эти квиксорты, мержсорты, пузырьки и вставки работают именно с отношением порядка, не вдаваясь в суть данных.
                        Что позволяет указывать произвольное отношение. Например, строки можно сортировать чувствительно и нечувствительно к регистру, с использованием национальных алфавитов или тупо сравнивая ascii/unicode-коды. А числа — по значению и по абсолютной величине, ну и так далее.

                        Некоторые типы данных можно сортировать, используя характерные особенности этого типа.
                        Целые числа — раскладывая на разряды, радиксом; разбивая на поддиапазоны — блочной сортировкой; подсчётом, наконец. Строки — префиксным деревом (trie).

                        Что делать с произвольными блоками — хозяйское дело. Можно трактовать их как сверхдлинные целые числа, как строки, как байтовые векторы, можно выделять из них какое-то нужное содержимое и сортировать по этому содержимому.
                          0
                          +1. Оправдываться не буду)
                  0
                  Просто оставлю это здесь: en.wikipedia.org/wiki/Bucket_sort

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

                  Самое читаемое