В течение последних месяцев я создал в Java некоторые классы, внедряющие структуры данных, более конкретно перечисления, двоичные поисковые деревья и двоичные кучи. Я решил сделать стресс -тест, создав целочисленный массив n значений между 0 и 10*n , а затем сортируя различными способами и измеряя время. < /p>
Первоначально это было просто любопытство. Очевидно, я ожидал, что мои классы будут затратами гораздо больше, чем обычные массивы. Sort () метод. Однако, когда я прошел тесты и сравнил свои занятия друг с другом, я нашел неожиданные сюрпризы. < /p>
Это список тестов, с деталями и комментариями. < /p>
1. < /b> создается копия массива, затем копия сортируется с использованием метода Arrays.sort () < /code>, родной Java.
Оценивается время, которое является методом Arrays.sort () < /code>, то есть создание копии массива не учитывается.
Это самый быстрый способ < /b>, как и ожидалось.
Оценивается время, которое является методом сортировки, то есть создание списка из массива не учитывается.
Поскольку производительность сортировки вставки не совсем велика, этот метод стоит примерно в 50 раз больше метода массива < /b>.
3. < /b> двоичные поисковые деревья (BST с момента включения) создается из массива, повторяющего метод add () .
BST не является сбалансированным деревом, как AVL или красно-черный, просто обычный BST , как найдено в Википедии: у каждого узла есть ссылки на три других узла (parent, Leathchild и rightchild ), инкуляция значения и т. Д.
Этот метод стоит arount 500 раз больше метода списка , т.е. 25 000 раз больше метода массива . 4-5.BH_1 и bh_2 с момента включения) создаются из метода массива, повторяющего метод add () , затем они преобразуются в два (отсортированные) метод массива extractmin () . Оба bh принадлежит к одному классу и сохраняет значение в векторе . Оба bh стоит около 2 раза больше BST и 50 000 раз превышает метод массива . Однако есть поворот.
BH_2 создает массив с помощью метода convertheaptoarray () интерфейса Heap . ConvertheAptOarray () вызывает метод extractmin () для n раз, в то время как extractmin () в свою очередь вызывает метод heapify () один раз.
это не происходит в BH_1 , который использует метод ConvertheaptOarray_1 () . Вместо вызова extractmin () мой «новый» метод непосредственно выполняет код extractmin () - и когда extractmin () вызывает метод heapify () , bh_1 вместо этого выполнил его код. Короче говоря, копия вставка, которая позволяет избежать нескольких вызовов.
в теории BH_1 < /code> всегда должен стоить меньше, чем BH_2 < /code>: те же входные данные, тот же код, меньший вызов метода. Однако это верно только 73% времени! Сорта внедрения (вычислительная сложность n 2 , предпочтительнее, если n меньше 23)
2. baffling than ever, why making less calls is more costly than making more calls in one case out of 4?!
Code for convertHeapToArray():
public default T[] convertHeapToArray(){
T[] output = AArrays.createTarray(length(), min());
for(int i=0 ; i
Отчет (5000 тестов, по 100 случайных массивов каждый): < /b> < /p>
The array use a Comparator.
A Comparator executes a confront in 66083 nanoseconds.
The list use a Comparator.
A Comparator executes a confront in 85973 nanoseconds.
The BST, BH_1 and BH_2 use a Relationship.
A Relationship executes a confront in 107145 nanoseconds.
The total time for the array sorting is 239 717 392 nanoseconds.
The total time for the list sorting is 984 872 184 nanoseconds.
The total time for the BST sorting is 533 338 808 811 nanoseconds.
The total time for the BH_1 sorting is 1 055 836 440 689 nanoseconds.
The total time for the BH_2 sorting is 1 198 365 741 676 nanoseconds.
The medium time for the array sorting is 47 943 nanoseconds.
The medium time for the list sorting is 196 974 nanoseconds.
The medium time for the BST sorting is 106 667 761 nanoseconds.
The medium time for the BH_1 sorting is 211 167 288 nanoseconds.
The medium time for the BH_2 sorting is 239 673 148 nanoseconds.
The first method for the Binary Heap has been faster than the second for 3 634 times out of 5 000.
< /code>
edit: < /b> < /p>
Перечитав то, что я написал, я понял, что не совсем понял в своем первоначальном вопросе. Позвольте мне исправить мою ошибку. У меня никогда не было никаких сомнений в вычислительной сложности используемых методов: структуры данных просты, их код практически взят из Википедии. Я был уверен, что письменный код не очень хорошо работал. Это не было написано с производительности для начала с < /i>. Метод Arrays.sort () был включен в качестве эталонного параметра. Поскольку я не написал код с учетом производительности, я подозревал перед тестом, что результаты будут более дорогостоящими, чем ожидалось. Однако мой прогноз на Что точно стоило дороже, чем было добавлено в мусорное ведро результатами. Вся разница между двумя двоичными кучами заключалась в том, что первый выполненный один и тот же код второго, только с меньшим количеством вызовов методов (минимальный код для бинарного копа, включенного ниже). Я ожидал, что первая двоичная куча всегда будет иметь меньшую стоимость: это было доказано неправильно, и я не знаю Почему . Используемый массив создается случайным образом. В то время как с этим стартовым условием высота двоичного дерева поиска будет быть рядом с журналом (n) (Глава 12, пункт 4 из Введение в алгоритм , Кормен, Лейссон, Ривент, Стейн), я никогда не слышал об алгоритме, использующем бинарные поисковые деревья, чтобы сортировать массивы: я включил его в свой тест только в качестве курита. И все же для небольшого количества элементов (первоначально 100) бинарные поисковые деревья были обнаружены последовательно быстрее, чем двоичная куча. < /p>
Почему это происходит? Когда двоичная куча начинает быть более удобной? Включил ли включение кучи »массив ошибкой? Как и в случае с бинарными поисковыми деревьями, я включил в тест как любопытство. Алгоритм сортировки является очень базовой вставкой, которая быстрее только для ряда элементов гораздо меньше, чем то, что я использовал, и код всего класса наиболее окончательно не создан для быстроты. Я предполагал, что это показало бы как самое медленное из моих занятий, вместо этого это было самое быстрое! , и я до сих пор не знаю Почему . Я не включил код, потому что между всеми классами он находится вокруг строк кода ~ 3000, большинство из которых не используется тестом. i не читал бы 3K строки кода, и я не ожидал, что случайный стек-эвер этого сделает! Однако я включил код для BinaryHeap < /code>, который составляет ~ 300 строк. < /P>
код для BinaryHeap < /code>: < /b> < /p>
public class BinaryHeap implements Heap {
private static final int indexOfMinimum = 1;
private Vector storer = new Vector(indexOfMinimum + 10);
private Relationship relationship = null;
// The class Relationship has a single method whose signature is
// public boolean confront(T a, T b);
// The reason I included it instead of a Comparator is that, in my code, the value null represents -∞
//
// The following code works.
//
// public class Relationship{
// Comparator c;
// public Relationship(Comparator c){ this.c = c; }
// public boolean confront(T a, T b){ return a==null ? true : c.compare(a,b); }
// }
// TODO | Constructors
public BinaryHeap(Relationship relationship){
storer.add(null);
this.relationship = relationship;
}
// TODO | Methods of the interface Heap
public void add(T newData) {
storer.add(null);
updateValue(storer.size() - 1, newData);
}
public T extractMin() {
T min = storer.get(indexOfMinimum);
heapify(indexOfMinimum);
return min;
}
public void updateValue(int indexOfToBeUpgraded, T newValue) {
int i = indexOfToBeUpgraded;
T support;
if( i >= indexOfMinimum )
{
storer.set(i, newValue);
while( i > indexOfMinimum && ! relationship.confront(storer.get(i/2), storer.get(i)) )
{
support = storer.get(i);
storer.set(i, storer.get(i/2));
storer.set(i, support);
i = i/2;
}
}
}
private void heapify(int i){
int j = i;
int maximumIndexOfArray = storer.size();
while( j
Подробнее здесь: https://stackoverflow.com/questions/434 ... rting-test
