Форум программистов, компьютерный форум, киберфорум
JavaScript для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.75/4: Рейтинг темы: голосов - 4, средняя оценка - 4.75
392 / 294 / 121
Регистрация: 26.08.2016
Сообщений: 902
1

Скорость выполнения метода массивов sort

15.11.2018, 00:03. Просмотров 836. Ответов 5
Метки нет (Все метки)

Является ли оригинальный метод sort самым быстрым или же есть алгоритмы быстрее используемого в методе? Кто-то пробовал? Экспериментировал? Проводил замеры?
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
15.11.2018, 00:03
Ответы с готовыми решениями:

Скорость выполнения
В цикле строка выполняется примерно 10тыс раз, хотелось бы быстрее. // №1 if...

Скорость выполнения функций
Хотелось бы узнать, какие функции у JS выполняются быстро, а какие нет. Вот к примеру: что быстрее...

Скорость выполнения скрипта
Как проверить скорость выполнения скрипта?

Ограничить скорость выполнения цикла
Есть 2 цикла: for(var i=0;i<z10000;i++){ for(var j=0;j<z10000;j++){ //..тут что-то делаем }...

5
супермизантроп
Эксперт JS
3808 / 2895 / 681
Регистрация: 18.04.2012
Сообщений: 8,491
15.11.2018, 00:29 2
если довериться Кантору (чего я никому не советую), то разработчики всех браузеров использовали алгоритм "быстрой сортировки"
0
392 / 294 / 121
Регистрация: 26.08.2016
Сообщений: 902
15.11.2018, 01:21  [ТС] 3
kalabuni, Проверил в хроме: взял массив на 100 тысяч элементов, заполнил его рэндомными значениями, скопировал значения в другой. Первый отсортировал sort-ом второй кодом по алгоритму qsort, разница почти в два раза в пользу второго. 330 ms на 190 ms
0
супермизантроп
Эксперт JS
3808 / 2895 / 681
Регистрация: 18.04.2012
Сообщений: 8,491
15.11.2018, 02:30 4
Цитата Сообщение от renat_dmitriev Посмотреть сообщение
взял массив на 100 тысяч элементов, заполнил его рэндомными значениями,
а вот это вы зря, в нормальных условиях метод sort () используют для массивов значительно меньшей длины (несколько десятков, максимум сотня элементов)
вполне возможно, что в браузерах алгоритм каким-то образом оптимизирован именно под небольшие массивы
так что для чистоты повторите свой эксперимент, сортируя небольшой массив в 100 элементов тысячу раз
0
dev - investigator
Эксперт JSЭксперт HTML/CSS
2109 / 1458 / 644
Регистрация: 16.04.2016
Сообщений: 3,667
15.11.2018, 04:37 5
kalabuni, renat_dmitriev, приветствую.
Firefox - сортировка слиянием
V8 - сортировка вставками для малых массивов и быстрая для больших
Webkit - для числовых использует быструю, для смежных слиянием

Пруфик для вебкит - https://trac.webkit.org/browse... rev=138530

Пруф - для SpiderMonkey - https://dxr.mozilla.org/mozill... /Array.cpp

Для V8 - https://chromium.googlesource.... e-array.cc
https://github.com/v8/v8/blob/... e-array.cc
1
392 / 294 / 121
Регистрация: 26.08.2016
Сообщений: 902
15.11.2018, 11:13  [ТС] 6
Цитата Сообщение от kalabuni Посмотреть сообщение
а вот это вы зря, в нормальных условиях метод sort () используют для массивов значительно меньшей длины (несколько десятков, максимум сотня элементов)
На массивах значительно меньшей длины разница вообще будет неощутима. Даже если мы массивы по 100 элементов сортируем 1000 раз, то время этого процесса будет в десятки раз короче, чем единственная сортировка на 100 000 элементов и даже на слабых компьютерах вряд ли будет превышать 100 мс, соответственно разница между различными алгоритмами сортировки 100 элементов 1000 раз будет совсем мизерная, но интереса ради да, попробую. Спасибо за совет.

Добавлено через 38 минут
Проверил: на маленьких разница еще ощутимее в процентном отношении. Вчерашний свой код я увы потерял, сегодня переписал, работает почему-то несколько дольше, но все равно очевидно быстрее существующего.

Код теста:
Javascript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
function createRandomArray(cnt) {
   const arr = []
   for(var i = 0; i < cnt; i++) {
      arr.push(Math.random() * 10000)
   }     
   
   return arr
}
 
function swap(arr, i1, i2) {
   if(i1 === i2) return 
   
   const swap = arr[i1]
   arr[i1] = arr[i2]
   arr[i2] = swap
}
 
function qsort(arr) {
   
   var ranges = [[0, arr.length-1]]
   while(ranges.length) {
      
      var nextRanges = []
      
      for(var k = 0; k < ranges.length; k++) {
         
         var start = ranges[k][0]
         var finish = ranges[k][1]
      
         var pos = Math.floor((start + finish) / 2)
         var number = arr[pos]
 
         var pos1 = pos, pos2 = finish
         while(pos1 < pos2) {
            if(number > arr[pos2]) {
               swap(arr, pos2, pos1 + 1)   
               swap(arr, pos1 + 1, pos1)
               pos1++   
            } else {
               pos2--
            }
         }
         for(var i = pos - 1; i >= start; i--) {
            if(arr[i] > number) {
               swap(arr, i, pos1-1)   
               swap(arr, pos1-1, pos1)
               pos1--
            }
         }
 
         if(pos1 > start + 1) {
            nextRanges.push([start, pos1 - 1])
         } 
 
         if(finish - pos1 > 1) {
            nextRanges.push([pos1 + 1, finish]) 
         }      
      } 
      
      ranges = nextRanges
   }
}
 
function compareSort(cnt) {
   const arr1 = createRandomArray(cnt)
   const arr2 = [...arr1]
   
   console.time('BrowserSort')
   arr1.sort((a,b)=> a < b ? -1 : 1)
   console.timeEnd('BrowserSort')
   
   console.time('QuickSort')
   qsort(arr2)
   console.timeEnd('QuickSort')   
}
 
function compareSort2(cnt1, cnt2) {
   
   const arr1 = []
   for(var i = 0; i < cnt1; i++) {
      arr1.push(createRandomArray(cnt2))   
   }
   
   const arr2 = arr1.map(arr => [...arr])
   
   console.time('BrowserSort')
   arr1.forEach(arr => arr.sort((a,b)=> a < b ? -1 : 1))
   console.timeEnd('BrowserSort')
   
   console.time('QuickSort')
   arr2.forEach(arr => qsort(arr))
   console.timeEnd('QuickSort')   
}
 
compareSort(100000)
compareSort2(1000, 100)
Добавлено через 12 минут
PS Оказывается это только с хромом такие результаты. Опера и Мозилла дают лучшие результаты. Опера чуть хуже на большом массиве, но в два раза быстрее на маленьких. Мозилла в разы быстрее на большом, и аналогичное время на маленьком.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
15.11.2018, 11:13

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

Оценить скорость (время) выполнения метода
Нельзя ли никак сию задачу решить? То есть к примеру, написал я метод, показался он мне не...

Странное поведение метода Sort()
Добрый день. Подскажите пожалуйста по C#. У меня есть некоторый объект List. Применяют к нему...

Использовать метод transform() вместо метода sort()
Добрый день , надо исправить код , заменив метод sort() , методом transform(), не могу уловить...

Неправильная сортировка при использовании метода .sort
Суть проблемы: Есть таблица в Excel'e которую надо отсортировать по столбцу велосипед решил не...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.