О различных способах сортировки массивов в 1С наверняка написано уже немало статей. Я решил написать еще одну.
Здесь я не буду расписывать все существующие методы сортировки массивов, которых достаточно много, а просто покажу и сравню два основных, на мой взгляд метода — пузырьковый (тот, который в школах/университетах изучают) и быстрый (самый оптимальный, на мой взгляд).
Итак, вот небольшая функция, которая создает массив заданного размера:
1 2 3 4 5 6 7 8 9 10 11 | &НаКлиенте Функция ПолучитьМассивЭлементов() мВозврат = Новый Массив(); тГенератор = Новый ГенераторСлучайныхЧисел(Секунда(ТекущаяДата())); Для тСчет = 0 По фЧислоЭлементов-1 Цикл //фЧислоЭлементов - это поле на форме мВозврат.Добавить(тГенератор.СлучайноеЧисло(0, 10000000)); КонецЦикла; Возврат мВозврат; КонецФункции |
Отсортируем полученный массив пузырьковым алгоритмом:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | &НаКлиенте Процедура СортироватьПузырьком(Команда) тМассив = ПолучитьМассивЭлементов(); тДатаНачала = ТекущаяУниверсальнаяДатаВМиллисекундах(); Для тИндекс1 = 0 По тМассив.ВГраница() Цикл Для тИндекс2 = 0 По тМассив.Вграница() - тИндекс1 - 1 Цикл Если тМассив[тИндекс2] < тМассив[тИндекс2+1] Тогда //Если тМассив[тИндекс2] > тМассив[тИндекс2+1] Тогда - сортировка по возрастанию тБуфер = тМассив[тИндекс2]; тМассив[тИндекс2] = тМассив[тИндекс2+1]; тМассив[тИндекс2+1] = тБуфер; КонецЕсли; КонецЦикла; КонецЦикла; тДатаОкончания = ТекущаяУниверсальнаяДатаВМиллисекундах(); Сообщить("Время работы (пузырьком): "+(тДатаОкончания-тДатаНачала)+" мс."); КонецПроцедуры |
Теперь отсортируем быстрым алгоритмом:
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 | &НаКлиенте Процедура БыстраяСортировка(Команда) тМассив = ПолучитьМассивЭлементов(); тДатаНачала = ТекущаяУниверсальнаяДатаВМиллисекундах(); тНачИндекс = 0; тКонИндекс = тМассив.ВГраница(); БыстраяСортировкаРек(тМассив, тНачИндекс, тКонИндекс); тДатаОкончания = ТекущаяУниверсальнаяДатаВМиллисекундах(); Сообщить("Время работы (быстрая): "+(тДатаОкончания-тДатаНачала)+" мс."); КонецПроцедуры Процедура БыстраяСортировкаРек(тМассив, тНачИндекс, тКонИндекс) иНачИндекс = тНачИндекс; иКонИндекс = тКонИндекс; иИндекс = тМассив[Цел((иНачИндекс+иКонИндекс)/2)]; Пока иНачИндекс <= иКонИндекс Цикл Пока тМассив[иНачИндекс] > иИндекс Цикл //Пока тМассив[иНачИндекс] < иИндекс Цикл - сортировка по возрастанию иНачИндекс = иНачИндекс+1; КонецЦикла; Пока тМассив[иКонИндекс] < иИндекс Цикл //Пока тМассив[иКонИндекс] > иИндекс Цикл - сортировка по возрастанию иКонИндекс = иКонИндекс-1; КонецЦикла; Если иНачИндекс <= иКонИндекс Тогда тБуфер = тМассив[иНачИндекс]; тМассив[иНачИндекс] = тМассив[иКонИндекс]; тМассив[иКонИндекс] = тБуфер; иНачИндекс = иНачИндекс+1; иКонИндекс = иКонИндекс-1; КонецЕсли; КонецЦикла; Если тНачИндекс < иКонИндекс Тогда БыстраяСортировкаРек(тМассив, тНачИндекс, иКонИндекс); КонецЕсли; Если иНачИндекс < тКонИндекс Тогда БыстраяСортировкаРек(тМассив, иНачИндекс, тКонИндекс); КонецЕсли; КонецПроцедуры |
Теперь перейдем к результатам — массив из 1000 элементов:
10000 элементов:
Результаты, я думаю, говорят сами за себя: при увеличении количества элементов массива в 10 раз, время сортировки быстрым алгоритмом также увеличилось приблизительно в 10 раз, в том время как время сортировки пузырьковым алгоритмом увеличилось приблизительно в 100 раз.
100000 элементов:
Процедура СортировкаЧерезТЗ(Кнопка)
массив = ПолучитьМассивЭлементов();
тДатаНачала = ТекущаяУниверсальнаяДатаВМиллисекундах();
тз = Новый ТаблицаЗначений;
тз.Колонки.Добавить(«Цифра», Новый ОписаниеТипов(«Число»));
Для тСчет = 0 По фЧислоЭлементов-1 Цикл //фЧислоЭлементов — это поле на форме
нСтрока = тз.Добавить();
нСтрока.Цифра = Массив[тСчет];
КонецЦикла;
тз.Сортировать(«Цифра»);
массив = тз.ВыгрузитьКолонку(«Цифра»);
тДатаОкончания = ТекущаяУниверсальнаяДатаВМиллисекундах();
Сообщить(«Время работы (тз): «+(тДатаОкончания-тДатаНачала)+» мс.»);
КонецПроцедуры
Время работы (тз): 1 906 мс.
Время работы (быстрая): 42 734 мс.
Нда…
1 000 000 (миллион) записей
СписокЗначений = Новый СписокЗначений;
СписокЗначений.ЗагрузитьЗначения(Массив);
СписокЗначений.СортироватьПоЗначению();
Возврат СписокЗначений.ВыгрузитьЗначения();
Время работы: ~ 3,26 сек
Время работы (ТЗ): ~ 53,27 сек
Время работы (быстрая): даже не замерял
Полезная публикация, спасибо!
СписокЗначений.СортироватьПоЗначению(); это оч тормозная хрень у меня пара тысяч
элементов сортирует 16 сек
Ростислав , вот именно! Но люди не ищут лёгких путей!
Надо попробовать корзинную сортировку, еще
Она быстрая и линейно — зависима от количества элементов, а, также, сортирует одинаковое время любые массивы — неоптимальна для частично отсортированных массивов и весьма оптимальна для совсем неотсортированных поскольку время сортировки всегда одинаково
Также, ее недостатки:
1) Конский жор памяти(поскольку, делаются копии массивов);
2) слова ей сортировать неоптимально поскольку большое количество корзин(и, как следствие, много памяти)
Но, вот, в данном случае на больших числовых массивах с высоким коэффициентом энтропии она, возможно, выиграет, даже, у сортировки по Хоару(здесь: быстрая)