Проблема скорости работы пользовательских алгоритмов сортировки

Question

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

После нескольких тестов я обнаружил, что мой heapsort намного быстрее, чем quicksort (я думаю, что это должно быть наоборот), мой выборсортировка также быстрее, чем сортировка вставкой.Кто-нибудь знает, в чем здесь проблема?

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

вот мои коды, если они помогут.Я запускаю таймер, запускаю функцию класса exec (), останавливаю таймер и вычисляю истекшее время.Коды приходят из Википедии.проблема с heapsort vs quicksort:

public class Quick {
public static function exec(seq:Vector.<int>):Vector.<int> {
    if (seq.length<=1) {
        return seq;
    }
    var smallPart:Vector.<int>=new Vector.<int>
    var bigPart:Vector.<int>=new Vector.<int>
    var n:int=seq.length;
    var pivotPosition:int=Math.floor(Math.random()*n);
    var pivot:int=seq.splice(pivotPosition,1)[0];
    for (var i:int=0; i<n-1; i++) {
        if (seq[i]<=pivot) {
            smallPart.push(seq[i]);
        } else {
            bigPart.push(seq[i]);
        }
    }
    seq=exec(smallPart).concat(exec(bigPart),Vector.<int>([pivot]));
    return seq;
}

}

public class Heap{
public static function exec(seq:Vector.<int>) {
    var n:int=seq.length;
    heapify(seq);
    var end:int=n-1;
    while (end > 0) {
        var temp:int=seq[end];
        seq[end]=seq[0];
        seq[0]=temp;
        siftDown(seq, 0, end-1);
        end--;
    }
    return seq
}
public static function heapify(seq:Vector.<int>) {
    var n:int=seq.length
    var start:int=n/2-1
    while (start >= 0) {
        siftDown(seq, start, n-1);
        start--;
    }
}
public static function siftDown(seq:Vector.<int>, start:int, end:int) {
    var root:int=start;
    while (root * 2 + 1 <= end) {
        var child:int=root*2+1;
        var swap:int=root;
        if (seq[swap]<seq[child]) {
            swap=child;
        }
        if (child+1<=end&&seq[swap]<seq[child+1]) {
            swap=child+1;
        }
        if (swap!=root) {
            var temp:int=seq[root];
            seq[root]=seq[swap];
            seq[swap]=temp;
            root=swap;
        } else {
            break;
        }    
    }
}

}

проблема с сортировкой вставки и сортировкой выбора:

public class Insertion{
public static function exec(seq:Vector.<int>) {
    var n:int=seq.length;
    for (var i:int=1; i<n; i++) {
        var holder:int=seq[i];
        var j:int=i-1;
        while (seq[j]>holder) {
            seq[j+1]=seq[j];
            j-=1;
            if (j<0) {
                break
            }
        }
        seq[j+1]=holder;
    }
    return seq
}

}

public class Selection{
public static function exec(seq:Vector.<int>):void{
    var currentMinimum:int;
    var n:int=seq.length;
    for (var i:int = 0; i < n-1; i++) {
        currentMinimum=i;
        for (var j:int = i+1; j < n; j++) {
            if (seq[j]<seq[currentMinimum]) {
                currentMinimum=j;
            }
        }
        if (currentMinimum!=i) {
            var temp:int=seq[i];
            seq[i]=seq[currentMinimum];
            seq[currentMinimum]=temp;
        }
    }
}

}

Answer 1

Хорошо, я на самом деле не знаю ActionScript, но для этого есть много возможностей:

Языковые проблемы

Я не знаю, как работает actionscript, но в C ++ и, возможно, в других языках, если вы передадите векторы по значению вместо ссылки, это может значительно замедлить процесс. )

В случае быстрой сортировки вы, похоже, создаете много новых векторов. Если эта операция медленная (я еще раз напоминаю вам, я не знаю actioncript), она может сместить ее в пользу heapsort.

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

Проблемы алгоритма

Вы используете 5000 значений из [-100, 100]. Это означает, что будет большое количество дубликатов. Одной из основных причин быстрой сортировки является то, что вы можете использовать много оптимизаций. Обычная (без оптимизации) быстрая сортировка может быть очень медленной, если есть повторяющиеся значения.

Кроме того, существует множество других оптимизаций, которые на практике часто ускоряют быструю сортировку.

Проблемы восприятия

Хех. Проблемы восприятия. Трололол;)

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

Надеюсь, это поможет.

Answer 2

Я думаю, что для того, чтобы действительно ответить на этот вопрос, вам нужно сделать шаг назад и проверить свои предположения.Когда вы говорите что-то вроде «heapsort должен быть быстрее, чем quicksort», что заставляет вас это говорить?

Если ваша причина - «потому что у кого-то лучше большие обозначения O», вам нужно пересмотреть, что на самом деле означает большое O,нотация Big O игнорирует постоянные факторы, а при использовании малых чисел, таких как 5000, постоянные факторы могут подавлять асимптотическое поведение.

Если ваша причина такова: «потому что википедия говорит, что обычно это быстрее», вам нужно сосредоточиться на «обычно".Ряд факторов может повлиять на то, какой из них быстрее, например, насколько велик размер вашей выборки, были ли числа уже частично отсортированы, сколько у вас повторяющихся чисел.Другие факторы включают поведение кеша - некоторые алгоритмы предполагают более ограниченный доступ к памяти и могут лучше использовать кеш.С другой стороны, интерпретируемый язык может или не может испортить эту локализацию по сравнению с скомпилированной программой, что еще больше сбивает с толку.

Одна вещь, которую вы обязательно должны попробовать, это запустить с разными тестовыми данными - попробовать 10 миллионовпредметы, где предметами являются цифры от 0 до 4 миллиардов или около того.Затем попробуйте 10 пунктов, варьирующихся от 0 до 20. Вы не обязательно должны ожидать, что один и тот же алгоритм «победит» в обоих случаях.

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

Еще одна вещь, которую стоит рассмотреть - насколько вы уверены в своей функции времени?Вы знаете, интерпретируется ли actionScript или компилируется?Вы проводите свои тесты 100 раз или около того, чтобы амортизировать любую работу по инициализации, которая должна быть выполнена?

Answer 3

Если вы хотите сравнить скорость этих алгоритмов сортировки. Тогда почему бы вам заранее не создать случайный вектор / массив. Тогда проверь его скорость. Нравится:

var source:Vector = new Vector().<5000, true>;
genRandomNumber(source);

var t:int = getTimer();
quicksort(source ....);
t = getTimer() - t;
trace("quicksort:" + t + "ms");

genRandomNumber(source);
t = getTimer();
heapsort(source ...);
t = getTimer() - t;
trace("heapsort:" + t + "ms");
.
.
.

Вот демоверсия quicksort от kirupa. Я уже тестировал некоторые алгоритмы сортировки, и быстрая сортировка - самая быстрая.