_radixSort_0 = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0];
/*
RADIX SORT
Use 256 bins
Use shadow array
- Get counts
- Transform counts to pointers
- Sort from LSB - MSB
*/
function radixSort(intArr) {
var cpy = new Int32Array(intArr.length);
var c4 = [].concat(_radixSort_0);
var c3 = [].concat(_radixSort_0);
var c2 = [].concat(_radixSort_0);
var c1 = [].concat(_radixSort_0);
var o4 = 0; var t4;
var o3 = 0; var t3;
var o2 = 0; var t2;
var o1 = 0; var t1;
var x;
for(x=0; x<intArr.length; x++) {
t4 = intArr[x] & 0xFF;
t3 = (intArr[x] >> 8) & 0xFF;
t2 = (intArr[x] >> 16) & 0xFF;
t1 = (intArr[x] >> 24) & 0xFF ^ 0x80;
c4[t4]++;
c3[t3]++;
c2[t2]++;
c1[t1]++;
}
for (x=0; x<256; x++) {
t4 = o4 + c4[x];
t3 = o3 + c3[x];
t2 = o2 + c2[x];
t1 = o1 + c1[x];
c4[x] = o4;
c3[x] = o3;
c2[x] = o2;
c1[x] = o1;
o4 = t4;
o3 = t3;
o2 = t2;
o1 = t1;
}
for(x=0; x<intArr.length; x++) {
t4 = intArr[x] & 0xFF;
cpy[c4[t4]] = intArr[x];
c4[t4]++;
}
for(x=0; x<intArr.length; x++) {
t3 = (cpy[x] >> 8) & 0xFF;
intArr[c3[t3]] = cpy[x];
c3[t3]++;
}
for(x=0; x<intArr.length; x++) {
t2 = (intArr[x] >> 16) & 0xFF;
cpy[c2[t2]] = intArr[x];
c2[t2]++;
}
for(x=0; x<intArr.length; x++) {
t1 = (cpy[x] >> 24) & 0xFF ^ 0x80;
intArr[c1[t1]] = cpy[x];
c1[t1]++;
}
return intArr;
}
EDIT:
На данный момент лучшая / единственная существенная оптимизация, выявленная в JS, - это массивы с типом JS.
Использование типизированного массива для теневого массива нормальной сортировки по радиусу дало наилучшие результаты. Я также смог выжать немного больше из быстрой сортировки на месте с помощью встроенного в стек JS push / pop.
последний тест jsfiddle
Intel i7 870, 4GB, FireFox 8.0
2mil
radixSort(intArr): 172 ms
radixSortIP(intArr): 1738 ms
quickSortIP(arr): 661 ms
200k
radixSort(intArr): 18 ms
radixSortIP(intArr): 26 ms
quickSortIP(arr): 58 ms
Кажется, стандартная сортировка по основанию действительно важна для этого рабочего процесса. Если у кого-то есть время поэкспериментировать с развертыванием цикла или другими модификациями, я был бы признателен.
У меня есть конкретный вариант использования, где я бы хотел максимально быструю реализацию сортировки в JavaScript. Будут большие (50 000 - 2 мил), несортированные (по существу случайные), целочисленные (32-битные) массивы, к которым будет обращаться клиентский сценарий, затем ему необходимо отсортировать и представить эти данные.
Я реализовал довольно быструю сортировку по радиусу по месту и быструю сортировку по месту jsfiddle benchmark , но для моей длины верхней границы массива они все еще довольно медленные. Быстрая сортировка работает лучше для размера моей верхней границы, тогда как радикальная сортировка работает лучше для моей нижней границы.
defaultSort is the built-in JavaScript array.sort with an integer compare function
Intel C2Q 9650, 4GB, FireFox 3.6
2mil
radixSortIP(intArr): 5554 ms
quickSortIP(arr): 1796 ms
200k
radixSortIP(intArr): 139 ms
quickSortIP(arr): 190 ms
defaultSort(intArr): 354 ms
Intel i7 870, 4GB, FireFox 8.0
2mil
radixSortIP(intArr): 990 ms
quickSortIP(arr): 882 ms
defaultSort(intArr): 3632 ms
200k
radixSortIP(intArr): 28 ms
quickSortIP(arr): 68 ms
defaultSort(intArr): 306 ms
Вопросы
- Есть ли лучшая реализация любого алгоритма сортировки, который бы соответствовал моему сценарию использования / потребностям?
- Есть ли какие-либо оптимизации, которые могут быть внесены в мои реализации radix / quick sort для повышения производительности?
- Существует ли эффективный способ преобразования сортировки по месту в рекурсивную функцию в итеративную? Память и скорость выполнения.
Цель
- Я надеюсь, что эти ответы помогут мне повысить производительность на ~ 20-30% в моем тесте производительности.
Разъяснение / Примечание
- "DEFINE FAST" Я бы предпочел общий случай, когда он хорошо работает во всех современных браузерах, но если есть оптимизация для конкретного браузера, которая дает значительное улучшение, которое может быть приемлемым.
- Сортировка МОЖЕТ быть выполнена на стороне сервера, но я бы предпочел избежать этого, поскольку приложение JS может стать автономным (в сочетании с некоторым проприетарным приложением, которое будет передавать данные датчика в файл).
- JavaScript может быть не лучшим языком для этого, но это требование.
- Я уже задавал этот вопрос https://stackoverflow.com/questions/7111525/fastest-way-to-sort-integer-arrays-in-javascript был поставлен неправильный ответ, и вопрос был закрыт.
- Я пытался использовать несколько экземпляров окна браузера как временную многопоточность; это не сработало. Я был бы заинтересован в полезной информации о создании нескольких окон для параллелизма.