Доброго времени суток... Приспичило меня (просто ради интереса) сравнить скорость работы сортировки в ширину с сортировкой быстрой. Причём решил сделать это в firebug-е...
Код следующий:
console.clear();
// Формирование массива
var w = 10 * 1000; // разброс значений
var h = 400 * 1000; // количество элементов
var a = new Array(h); // массив
console.time('Make array');
for( var i = 0; i < h; ++i )
{
a[i] = Math.floor(Math.random() * w);
}
console.timeEnd('Make array');
// Cортировка "в ширину"
console.time('WideSort');
var b = new Array(w);
var c = new Array(h);
for( i = 0; i < h; ++i )
{
if( !b[ a[i] ] )
b[ a[i] ] = 1;
else
++b[ a[i] ];
}
var z = -1;
for( i = 0; i < w; ++i )
{
for( var t = 0; t < b[i]; ++t )
{
z++;
c[z] = i;
}
}
console.timeEnd('WideSort');
// Быстрая сортировка
console.time('QuickSort');
function qsort( mas, f, t )
{
var l = f, r = t;
var middle = Math.floor( (t + f)/ 2 );
var m = mas[ middle ];
do {
while( mas[l] < m ) ++l; // находим первый слева элемент больший центрального
while( mas[r] > m ) --r; // находим первый правый элемент меньший центрального
if( l <= r ) { // меняем местами больший чем М элемент слева, с меньшим чем М,
var temp = mas[l]; // элементом справа
mas[l] = mas[r];
mas[r] = temp;
++l; --r;
}
} while ( r >= l ); // пока не кончится отрезок массива
if( f < r ) qsort( mas, f, r );
if( t > l ) qsort( mas, l, t );
}
qsort( a, 0, a.length - 1 );
console.timeEnd('QuickSort');
// Проверка
for( i = 0; i < h; ++i )
if( a[i] != c[i] )
{
console.log('a[i] = ',a[i],' c[i] = ',c[i]);
break;
}
Результат ужасен, сортировка в ширину у меня всегда проигрывает, какие бы я исходные данные не ставил. Проверил тоже в Delphi, там ситуация более идеологически верная - быстрая сортировка медленнее примерно в 10 раз, вплоть до увеличения h до 2-3 миллионов.
|
Код:
|
program Project1;
{$APPTYPE CONSOLE}
uses
SysUtils,
Windows;
type
ar = array of integer;
var
v: ar;
procedure qSort(l,r:longint);
var i,j,p:longint;
w,q:longint;
begin
i := l; j := r;
q := v[(l+r) div 2];
repeat
while (v[i] < q)
do inc(i);
while (q < v[j])
do dec(j);
if (i <= j) then
begin
w:=v[i]; v[i]:=v[j]; v[j]:=w;
inc(i); dec(j);
end;
until (i > j);
if (l < j) then qSort(l,j);
if (i < r) then qSort(i,r);
end;
function wideSort( mas: ar; height: integer ): ar;
var
c: array of integer;
i, t, count: integer;
begin
SetLength( c, height + 1 );
for i:=0 to Length(mas)-1 do
c[ mas[i] ] := c[ mas[i] ] + 1;
SetLength( result, Length(mas) );
count := -1;
for i:=0 to height do
for t := 1 to c[i] do
begin
inc( count );
result[ count ] := i;
end;
end;
const
max = 50 * 1000 * 1000;
height = 10;
var
t: cardinal;
i: longint;
q: ar;
begin
Setlength( v, max );
for i:=0 to max-1 do
v[i] := random(height - 1) + 1;
t := getTickCount();
q := wideSort( v, height );
t := getTickCount() - t;
writeLn('WideSort = ', t);
t := getTickCount();
qSort( 0, length(v)-1 );
t := getTickCount() - t;
writeLn('QSort = ', t);
ReadLn;
end. |
Можно ли в Js вернуть "справедливость"?
Насколько я понимаю, всё дело в медленном создании массива...
P.S. Я в js совсем "зелёный"
#upd
Chrome:
|
Цитата:
|
Make array: 1558ms
WideSort: 3584ms
QuickSort: 444ms
|
