gifts2017

Немного о скорости поиска в коллекциях

Опубликовал Василий Коровин (vasyak319) в раздел Программирование - Практика программирования

Решил попробовать в одном отчёте разные методы поиска элемента в коллекциях и получил неожиданные для меня результаты.

Написал тут отчёт для экономистов, а он тормозит - 30 секунд формируется. Частое использование не предполагалось, но не люблю, когда отчёты тормозят, а тут ещё и сортировка по хитро рассчитанному полю понадобилась - переписал. Всё равно почти 10 секунд. Замер производительности вывел в рекордсмены строку

Если лсзИмпортныеТовары.НайтиПоЗначению(лНоменклатура)=Неопределено Тогда

с результатом 3.1 сек. для 3819 вызовов

Список перед этим был заполнен уникальными значениями из результата запроса:

лсзИмпортныеТовары=Новый СписокЗначений;
лсзИмпортныеТовары.ЗагрузитьЗначения(лЗапрос.Выполнить().Выгрузить().ВыгрузитьКолонку("Номенклатура"));

У меня как-то ещё со времён 7.7 привычка использовать для подобных целей объект СписокЗначений и была убеждённость, что разработчики платформы поддерживают некий хэш-индекс для быстрого поиска вхождений в список (в 7.7 для этого даже есть специальный метод Принадлежит()). Результат замера, тем не менее, намекал, что стоит ещё поискать. Попробовал так:

Формируем тем же запросом индексированную таблицу значений:

лтзИмпортныеТовары=лЗапрос.Выполнить().Выгрузить();
лтзИмпортныеТовары.Индексы.Добавить("Номенклатура");

и слегка меняем строку с поиском: 

Если лтзИмпортныеТовары.Найти(лНоменклатура,"Номенклатура")=Неопределено Тогда

результат - 0.027 сек.

Нет, я подозревал, что это может быть быстрее, но в 100 раз!

Чтобы два раза не вставать, попробовал с массивом:

лмИмпортныеТовары=лЗапрос.Выполнить().Выгрузить().ВыгрузитьКолонку("Номенклатура");

и

Если лмИмпортныеТовары.Найти(лНоменклатура)=Неопределено Тогда

результат - 3.3 сек. Скорости не ожидал - скорости не получил.

Больше значащих цифр во временах не даю, потому что они заметно меняются от запуска к запуску, но порядок величин сохраняется. Массив, например, попадал в диапазон 3.25-3.55 секунд.

Вывод очевиден - индексированная ТаблицаЗначений - наше всё.

Причём именно индексированная, важность чего многие (включая меня до сегодняшнего дня) склонны недооценивать. Я попробовал закомментировать создание индекса и сразу получил время 3.15 сек.

P.S. В каментах неоднократно упомянули Соответствие, а FlyVodolaz даже привёл код процедуры, сравнивающей в смысле поиска Соответствие и индексированную ТаблицуЗначений. Единственный минус той процедуры - искуственность примера (запрос выполняется к временной таблице, заполненной последовательными числами). Я решил проверить это на своём отчёте, для чего изменил соответствующие фрагменты:

	лсвИмпортныеТовары=Новый Соответствие;
	лВыборка=лЗапрос.Выполнить().Выбрать();
	Пока лВыборка.Следующий() Цикл лсвИмпортныеТовары.Вставить(лВыборка.Номенклатура); КонецЦикла;

и

Если лсвИмпортныеТовары[лВыборкаОборотовНоменклатура.Номенклатура]=Неопределено Тогда

Действительно, поиск выполняется быстрее (0.017 секунд), но вот открытие выборки из результата запроса отъедает 0,050 секунд против 0,029 для выгрузки в ТаблицуЗначений и индексации.

В итоге, суммарное время выполнения при использовании Соответствия получается больше, чем при использовании ТаблицыЗначений, но однозначного вывода в пользу того или другого способа для всех случаев жизни я из этого сделать не могу.

Скорее так: в том случае, когда в алгоритме массово используется поиск в одном и том же множестве и при этом результатом поиска является либо сам факт нахождения, либо какое-то одно значение, связанное с ключом поиска, однозначно надо брать Соответствие - оно быстрее.
В остальных случаях я бы использовал ТаблицуЗначений: во-первых, преимущество Соответствия в поиске, как показано выше, не всегда приводит к ускорению всего алгоритма, во-вторых, выгрузка в неё записывается короче, в-третьих, у неё больше возможностей. Например, в случае необходимости в неё легко добавить ещё колонок.

См. также

Подписаться Добавить вознаграждение

Комментарии

1. Николай Терновой (ojiojiowka) 16.06.15 20:23
Таблица значений не всегда приемлема (допустим код надо на клиенте выполнять). А теперь попробуйте заюзать соответствие и приятно удивитесь. Давно известно, что массив и список значений не индексированы...
2. Василий Коровин (vasyak319) 16.06.15 20:46
(1) ojiojiowka, была мысль и соответствие попробовать, но тут два "но":
1. Без долгого и нудного заполнения в цикле не обойтись, ибо нет у результата запроса метода вроде "ВыгрузитьВСоответствие".
2. Если время и опустится ниже 0.027 сек, то вряд ли значительно - и так шикарно.
3. Сергей Галюк (dj_serega) 17.06.15 02:28
(0) Красавчик :) Где-то догадывался, где-то знал. А вот руки не дошли замеров :(
4. Андрей Акулов (DrAku1a) 17.06.15 03:46
5. Даниил Матвеев (cargobird) 17.06.15 07:15
Звезда авансом, попробую, спасибо...
6. Сергей Рудаков (fishca) 17.06.15 09:13
Да, мало в 7.7 автор использовал 1СРР. А так бы знал про ИндексированнуюТаблицуЗначений и про быстрый поиск в ней, да не только про поиск.
Зеленоград; +1 Ответить
7. Андрей Овсянкин (Evil Beaver) 17.06.15 09:35
Нет, я подозревал, что это может быть быстрее, но в 100 раз!

Вот и выросло поколение программистов, не знающих, что поиск по индексу на порядки быстрее простого перебора :(
avers_essp; Irwin; bforce; qwinter; axelerleo; speshuric; nSpirit2; ojiojiowka; VladC#; PowerBoy; h00k; JohnyDeath; delete; yukon; planar74; Поручик; Зеленоград; POLGA; +18 Ответить 1
8. Василий Коровин (vasyak319) 17.06.15 10:07
(7) Evil Beaver, раз не умеете читать, постарайтесь хотя бы не хамить.
Зеленоград; +1 Ответить 1
9. Василий Коровин (vasyak319) 17.06.15 10:26
(4) DrAku1a, а что, если записать цикл в одну строку, то это уже и не цикл вовсе? Глянул по вашей ссылке - автор делает неправильный вывод, что если цикл на миллион итераций записать в одну строку, то будет не миллион выполнений, а одно, при этом с тем же конечным результатом. Расписать, почему это чушь, или и так ясно? На самом деле итераций и так и так миллион. Очевидно, что замер производительности увеличивает счётчик обращений к строке в момент выполнения ядром опкода 1, что логично, а тут он будет выполнен один раз перед началом цикла. Опкод 1 это очень простая операция, так что заметно ускорить её исключением что-нибудь, превосходящее по сложности сложение двух чисел, не выйдет.
Из остальных приведённых вами ссылок я делаю тот же вывод - индексированная ТЗ наше всё. Соответствие быстрее на поиске, но на его заполнение надо потратить столько же времени (0.09 секунд на 10000 итераций), сколько уходит на поиск в индексированной ТЗ.
10. Илья Коротков (molodoi1sneg) 17.06.15 11:06
А возможно сделать замер с соответсвием?
11. Виталий Б. (FlyVodolaz) 17.06.15 11:40
(9) vasyak319,
Выгрузка в таблицу значения и индексирование тоже происходит в нашей вселенной, содержащей время.
Что-бы закончить споры простой пример.
ТЗИсходная = Новый ТаблицаЗначений;
ТЗИсходная.Колонки.Добавить("Ч", Новый ОписаниеТипов("Число"));
Для Ин=1 По 10000 Цикл
	ТЗИсходная.Добавить().Ч = Ин;
КонецЦикла;
Запрос = Новый Запрос;
Запрос.УстановитьПараметр("ТЗ", ТЗИсходная);
Запрос.Текст = 
"Выбрать ТЗ.Ч Поместить ВТ_ТЗ Из &ТЗ КАК ТЗ;Выбрать * из ВТ_ТЗ";
Результат = Запрос.Выполнить();

НачВремя = ТекущаяУниверсальнаяДатаВМиллисекундах();
Соотв = Новый Соответствие;
Выборка = Результат.Выбрать();
Пока Выборка.Следующий() Цикл Соотв.Вставить(Ин);КонецЦикла;

Для Ин=1 По 10000 Цикл
	А = Соотв[Ин];
КонецЦикла;
Сообщить("Соответствие: " + (ТекущаяУниверсальнаяДатаВМиллисекундах() - НачВремя));

НачВремя = ТекущаяУниверсальнаяДатаВМиллисекундах();
ТЗ = Результат.Выгрузить();
ТЗ.Индексы.Добавить("Ч");

Для Ин=1 По 10000 Цикл
	А = ТЗ.Найти(Ин, "Ч");
КонецЦикла;
Сообщить("Тз: " + (ТекущаяУниверсальнаяДатаВМиллисекундах() - НачВремя));
...Показать Скрыть

Результат:
Соответствие: 78
Тз: 141
12. Андрей Овсянкин (Evil Beaver) 17.06.15 12:19
(8) vasyak319, не могли бы вы уточнить два момента:
1. что именно я не прочитал?
2. где именно я нахамил?

Мое возмущение - это не хамство, это именно возмущение. А обоснованно возмущаться в приличном обществе вполне допустимо, разве нет?

Вы меня, конечно, извините, но для профессионального разработчика (если человек себя таковым считает) высказывание "Я поискал с использованием индекса и удивился, что работает настолько быстрее" на мой взгляд недопустимо. Говорит просто о некомпетентности. Другое дело, если вы не программист по образованию, а просто пришли в мир 1С из другой профессии. Тогда примите мои извинения, вы не обязаны были этого знать.
h00k; Yashazz; +2 Ответить 1
13. Василий Коровин (vasyak319) 17.06.15 12:43
(11) FlyVodolaz, попробовал это в своём отчёте. Результат и выводы добавил в конец публикации.
14. Василий Коровин (vasyak319) 17.06.15 12:47
(12) Evil Beaver,
1. "У меня как-то ещё со времён 7.7 привычка использовать для подобных целей объект СписокЗначений и была убеждённость, что разработчики платформы поддерживают некий хэш-индекс для быстрого поиска вхождений в список"
Вот с этим было связано моё удивление, что "аж в 100 раз". Думаю, это ответ и на ваш п.2.
15. Виталий Б. (FlyVodolaz) 17.06.15 13:04
(13) vasyak319,
Не совсем понял вашу фразу
открытие выборки из результата запроса отъедает 0,050 секунд против 0,029 для выгрузки в ТаблицуЗначений и индексации.

Т.е лВыборка=лЗапрос.Выполнить().Выбрать(); медленнее чем выгрузить и индексировать?лтзИмпортныеТовары=лЗапрос.Выполнить().Выгрузить(); лтзИмпортныеТовары.Индексы.Добавить("Номенклатура");
16. Андрей Овсянкин (Evil Beaver) 17.06.15 13:18
(14) vasyak319, 7.7. я в этом плане не изучал. Если вы говорите, что там был поиск по хешу, готов поверить.
В восьмерке же, насколько мне хватает понимания, весь поиск в коллекциях выполняется, как правило, простым перебором. Исключение - это Соответствие и индексированная ТаблицаЗначений И если я не ошибаюсь, то СтрДлина тоже работает, как сишный strlen, т.е. длина строки не хранится, и платформа каждый раз сканирует строку в поисках нуль-символа.

В ту же тему методы СтрЧислоСтрок и СтрПолучитьСтроку. Читают каждый раз текст с начала, вычисляя нужный номер строки.
17. Антонио (Fragster) 17.06.15 14:59
(9) vasyak319,
Соответствие быстрее на поиске, но на его заполнение надо потратить столько же времени (0.09 секунд на 10000 итераций), сколько уходит на поиск в индексированной ТЗ.

А сколько времени создается индекс?
18. Василий Коровин (vasyak319) 17.06.15 15:08
(15) FlyVodolaz, вы всё поняли верно
19. Василий Коровин (vasyak319) 17.06.15 15:12
(17) Fragster, исчезающе мало по сравнению с длительностью других операций.
20. Василий Коровин (vasyak319) 17.06.15 15:27
(16) Evil Beaver,
Если вы говорите, что там был поиск по хешу
нет, не говорю :(
Я говорю: "была убеждённость", потому что сам бы так сделал на месте разработчиков.
21. Виталий Б. (FlyVodolaz) 17.06.15 16:53
(18) vasyak319,
Если так, то лВыборка=лЗапрос.Выполнить().Выбрать() не может быть медленнее лтзИмпортныеТовары=лЗапрос.Выполнить().Выгрузить(). Что-то у вас не так. Возможно вы выполняете сначало лЗапрос.Выполнить().Выбрать(), а позже лЗапрос.Выполнить().Выгрузить(). Тогда выполнение запроса второй раз действительно может быть быстрее. Поэтому я писал в своем коде Результат = Запрос.Выполнить(); //один раз выполняем
а потом уже имея результат выполнения запроса делаем Выборка = Результат.Выбрать() и ТЗ = Результат.Выгрузить();
Попробуйте изменить порядок. Ну или использовать честный способ через Результат = Запрос.Выполнить();
22. Василий Коровин (vasyak319) 17.06.15 18:10
(21) FlyVodolaz, однако ж может. Что до порядка, то у меня это вообще не исполняется одновременно в одном замере. Для каждого замера я оставлял в исполняемом коде только один вариант, комментируя прочие, сохранял отчёт и запускал его заново с теми же параметрами.
23. Яков Коган (Yashazz) 17.06.15 19:09
Самоочевидный баян, опять получивший не-пойми-почему гору плюсов. Интересно, когда "пионэры" матчасть учить станут, вместо чтобы эксперименты ставить?

Про соответствия уже всё сказали.

Кстати, подозреваю, что не просто так таблицы значений не существуют на клиенте. Сдаётся мне, какой-то они к этому движок приделали, а то и просто каждая табзначений существует как таблица в СУБД, и делаемый нами индекс - её кластерный. Мало ли...
24. Василий Коровин (vasyak319) 17.06.15 19:17
(23) Yashazz, интересно, когда же буйная фантазия перестанет заменять пионэрам разум? "каждая табзначений существует как таблица в СУБД" - это в перлы, однозначно.
ojiojiowka; Evil Beaver; +2 1 Ответить
25. Андрей Акулов (DrAku1a) 18.06.15 03:14
(23) Возможно есть какие-то сложности с реализацией таблицы значений в веб-клиенте... Не думаю, что ТЗ существует где-либо, кроме оперативной памяти - реализация подобного, например в Delphi - компонент JvMemoryTable (с индексами и т.п.).

(0) Автор, советую ещё познакомиться с методом ТЗ.НайтиСтроки() - поиск по нескольким индексированным полям, такого в соответствии нет (без извращений если).
26. Василий Коровин (vasyak319) 18.06.15 09:38
(25) DrAku1a,
Автор, советую ещё познакомиться с методом


А почему только с этим? Давайте уж, выкладывайте, что у вас там ещё в Синтакс-помощнике есть.
27. Андрей Овсянкин (Evil Beaver) 18.06.15 11:23
(23) Yashazz, интересно, откуда вообще у вас возникли предпосылки думать, что таблица значений существует в СУБД? Хоть что-нибудь в поведении платформы на это намекает?
ojiojiowka; +1 Ответить 2
28. Андрей Вахрин (dolter) 20.06.15 13:46
(27) Возможно мысль появилась из-за знания как это работает в семерке. Там создается dbf-файл.
Я, честно говоря, не очень удивлюсь, если ТЗ в восьмерке создается-храниться так же ))
К сожалению нет времени на эксперименты...
29. Виталий Б. (FlyVodolaz) 23.06.15 14:12
(25) DrAku1a,
Я так понимаю, не реализовали таблицу значений на клиенте, по причине отсутствия подходящего типа в JavaScript.

Массив, соответствие и структуру в JavaScript можно описать через массив и ассоциативный массив.
30. Василий Коровин (vasyak319) 23.06.15 15:41
(29) FlyVodolaz, точно так же, как сейчас выходят из положения программисты 1С, желающие поиметь на клиенте нечто вроде ТЗ, могли бы выйти из положения и программисты платформы.
31. Андрей Казанцев (ander_) 27.06.15 09:46
(28) dolter,
Не перевелись еще сказочники :)
32. Яков Коган (Yashazz) 01.07.15 10:21
(27) Evil Beaver, хорошо, откуда предпосылки думать обратное? Я вот нигде не видел сведений, как в нынешних версиях 1С реализована таблица значений, но наличие метода индексации ВНЕ запроса несколько намекает. Ну не стали ж в 1С делать свою механику наряду с движком СУБД... Вот, например, динамику изменений TempDB никто не отслеживал при работе с крупными таблицами? Может, кроме собственно служебных времянок, туда и таблица значений пихается?

(28) Вряд ли. DBF в понимании 1С это уже не модно.
33. Дмитрий Тарасов (tarassov) 21.08.15 15:22
в том случае, когда в алгоритме массово используется поиск в одном и том же множестве и при этом результатом поиска является либо сам факт нахождения, либо какое-то одно значение, связанное с ключом поиска, однозначно надо брать Соответствие - оно быстрее
- то, что надо!
Для написания сообщения необходимо авторизоваться
Прикрепить файл
Дополнительные параметры ответа