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

16.06.15

Разработка - Механизмы платформы 1С

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

Написал тут отчёт для экономистов, а он тормозит - 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 для выгрузки в ТаблицуЗначений и индексации.

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

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

поиск СписокЗначений ТаблицаЗначений Массив

См. также

Поинтегрируем: сервисы интеграции – новый стандарт или просто коннектор?

Обмен между базами 1C Администрирование СУБД Механизмы платформы 1С Платформа 1С v8.3 Бесплатно (free)

В платформе 8.3.17 появился замечательный механизм «Сервисы интеграции». Многие считают, что это просто коннектор 1С:Шины. Так ли это?

11.03.2024    3594    dsdred    48    

66

Как готовить и есть массивы

Механизмы платформы 1С Платформа 1С v8.3 Бесплатно (free)

Все мы используем массивы в своем коде. Это один из первых объектов, который дают ученикам при прохождении обучения программированию. Но умеем ли мы ими пользоваться? В этой статье я хочу показать все методы массива, а также некоторые фишки в работе с массивами.

24.01.2024    5036    YA_418728146    25    

62

Планы обмена VS История данных

Обмен между базами 1C Механизмы платформы 1С Платформа 1С v8.3 Бесплатно (free)

Вы все еще регистрируете изменения только на Планах обмена и Регистрах сведений?

11.12.2023    6164    dsdred    36    

110

1С-ная магия

Механизмы платформы 1С Бесплатно (free)

Язык программирования 1С содержит много нюансов и особенностей, которые могут приводить к неожиданным для разработчика результатам. Сталкиваясь с ними, программист начинает лучше понимать логику платформы, а значит, быстрее выявлять ошибки и видеть потенциальные узкие места своего кода там, где позже можно было бы ещё долго медитировать с отладчиком в поисках источника проблемы. Мы рассмотрим разные примеры поведения кода 1С. Разберём результаты выполнения и ответим на вопросы «Почему?», «Как же так?» и «Зачем нам это знать?». 

06.10.2023    18201    SeiOkami    46    

116

Дефрагментация и реиндексация после перехода на платформу 8.3.22

Механизмы платформы 1С Платформа 1С v8.3 Бесплатно (free)

Начиная с версии платформы 8.3.22 1С снимает стандартные блокировки БД на уровне страниц. Делаем рабочий скрипт, как раньше.

14.09.2023    11769    human_new    27    

72

Валидация JSON через XDTO (включая массивы)

WEB-интеграция Универсальные функции Механизмы платформы 1С Платформа 1С v8.3 Конфигурации 1cv8 Бесплатно (free)

При работе с интеграциями рано или поздно придется столкнуться с получением JSON файлов. И, конечно же, жизнь заставит проверять файлы перед тем, как записывать данные в БД.

28.08.2023    8561    YA_418728146    6    

139

Внешние компоненты Native API на языке Rust - Просто!

Механизмы платформы 1С Платформа 1С v8.3 Конфигурации 1cv8 Бесплатно (free)

Внешние компоненты для 1С можно разработывать очень просто, пользуясь всеми преимуществами языка Rust - от безопасности и кроссплатформенности до удобного менеджера библиотек.

20.08.2023    6200    sebekerga    54    

93

Все скопируем и вставим! (Буфер обмена в 1С 8.3.24)

Механизмы платформы 1С Платформа 1С v8.3 Конфигурации 1cv8 Бесплатно (free)

Рассмотрим новую возможность 8.3.24 и как её можно эффективно использовать

27.06.2023    15534    SeiOkami    31    

103
Комментарии
В избранное Подписаться на ответы Сортировка: Древо развёрнутое
Свернуть все
1. ojiojiowka 16.06.15 20:23 Сейчас в теме
Таблица значений не всегда приемлема (допустим код надо на клиенте выполнять). А теперь попробуйте заюзать соответствие и приятно удивитесь. Давно известно, что массив и список значений не индексированы...
2. vasyak319 150 16.06.15 20:46 Сейчас в теме
(1) ojiojiowka, была мысль и соответствие попробовать, но тут два "но":
1. Без долгого и нудного заполнения в цикле не обойтись, ибо нет у результата запроса метода вроде "ВыгрузитьВСоответствие".
2. Если время и опустится ниже 0.027 сек, то вряд ли значительно - и так шикарно.
4. DrAku1a 1678 17.06.15 03:46 Сейчас в теме
9. vasyak319 150 17.06.15 10:26 Сейчас в теме
(4) DrAku1a, а что, если записать цикл в одну строку, то это уже и не цикл вовсе? Глянул по вашей ссылке - автор делает неправильный вывод, что если цикл на миллион итераций записать в одну строку, то будет не миллион выполнений, а одно, при этом с тем же конечным результатом. Расписать, почему это чушь, или и так ясно? На самом деле итераций и так и так миллион. Очевидно, что замер производительности увеличивает счётчик обращений к строке в момент выполнения ядром опкода 1, что логично, а тут он будет выполнен один раз перед началом цикла. Опкод 1 это очень простая операция, так что заметно ускорить её исключением что-нибудь, превосходящее по сложности сложение двух чисел, не выйдет.
Из остальных приведённых вами ссылок я делаю тот же вывод - индексированная ТЗ наше всё. Соответствие быстрее на поиске, но на его заполнение надо потратить столько же времени (0.09 секунд на 10000 итераций), сколько уходит на поиск в индексированной ТЗ.
11. FlyVodolaz 17.06.15 11:40 Сейчас в теме
(9)
Выгрузка в таблицу значения и индексирование тоже происходит в нашей вселенной, содержащей время.
Что-бы закончить споры простой пример.
ТЗИсходная = Новый ТаблицаЗначений;
ТЗИсходная.Колонки.Добавить("Ч", Новый ОписаниеТипов("Число"));
Для Ин=1 По 10000 Цикл
	ТЗИсходная.Добавить().Ч = Ин;
КонецЦикла;
Запрос = Новый Запрос;
Запрос.УстановитьПараметр("ТЗ", ТЗИсходная);
Запрос.Текст = 
"Выбрать ТЗ.Ч Поместить ВТ_ТЗ Из &ТЗ КАК ТЗ;Выбрать * из ВТ_ТЗ";
Результат = Запрос.Выполнить();

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

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

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

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

Результат:
Соответствие: 78
Тз: 141
vasyak319; +1 Ответить
13. vasyak319 150 17.06.15 12:43 Сейчас в теме
(11) FlyVodolaz, попробовал это в своём отчёте. Результат и выводы добавил в конец публикации.
15. FlyVodolaz 17.06.15 13:04 Сейчас в теме
(13)
Не совсем понял вашу фразу
открытие выборки из результата запроса отъедает 0,050 секунд против 0,029 для выгрузки в ТаблицуЗначений и индексации.

Т.е лВыборка=лЗапрос.Выполнить().Выбрать(); медленнее чем выгрузить и индексировать?лтзИмпортныеТовары=лЗапрос.Выполнить().Выгрузить(); лтзИмпортныеТовары.Индексы.Добавить("Номенклатура");
18. vasyak319 150 17.06.15 15:08 Сейчас в теме
(15) FlyVodolaz, вы всё поняли верно
21. FlyVodolaz 17.06.15 16:53 Сейчас в теме
(18)
Если так, то лВыборка=лЗапрос.Выполнить().Выбрать() не может быть медленнее лтзИмпортныеТовары=лЗапрос.Выполнить().Выгрузить(). Что-то у вас не так. Возможно вы выполняете сначало лЗапрос.Выполнить().Выбрать(), а позже лЗапрос.Выполнить().Выгрузить(). Тогда выполнение запроса второй раз действительно может быть быстрее. Поэтому я писал в своем коде Результат = Запрос.Выполнить(); //один раз выполняем
а потом уже имея результат выполнения запроса делаем Выборка = Результат.Выбрать() и ТЗ = Результат.Выгрузить();
Попробуйте изменить порядок. Ну или использовать честный способ через Результат = Запрос.Выполнить();
22. vasyak319 150 17.06.15 18:10 Сейчас в теме
(21) FlyVodolaz, однако ж может. Что до порядка, то у меня это вообще не исполняется одновременно в одном замере. Для каждого замера я оставлял в исполняемом коде только один вариант, комментируя прочие, сохранял отчёт и запускал его заново с теми же параметрами.
17. Fragster 1137 17.06.15 14:59 Сейчас в теме
(9)
Соответствие быстрее на поиске, но на его заполнение надо потратить столько же времени (0.09 секунд на 10000 итераций), сколько уходит на поиск в индексированной ТЗ.

А сколько времени создается индекс?
19. vasyak319 150 17.06.15 15:12 Сейчас в теме
(17) Fragster, исчезающе мало по сравнению с длительностью других операций.
3. dj_serega 390 17.06.15 02:28 Сейчас в теме
(0) Красавчик :) Где-то догадывался, где-то знал. А вот руки не дошли замеров :(
5. cargobird 306 17.06.15 07:15 Сейчас в теме
Звезда авансом, попробую, спасибо...
6. fishca 1254 17.06.15 09:13 Сейчас в теме
Да, мало в 7.7 автор использовал 1СРР. А так бы знал про ИндексированнуюТаблицуЗначений и про быстрый поиск в ней, да не только про поиск.
Crusade; Зеленоград; +2 Ответить
7. Evil Beaver 8100 17.06.15 09:35 Сейчас в теме
Нет, я подозревал, что это может быть быстрее, но в 100 раз!

Вот и выросло поколение программистов, не знающих, что поиск по индексу на порядки быстрее простого перебора :(
avers_essp; Irwin; bforce; qwinter; axelerleo; speshuric; nSpirit2; ojiojiowka; VladC#; PowerBoy; h00k; JohnyDeath; delete; yukon; planar74; Поручик; Зеленоград; POLGA; +18 Ответить
8. vasyak319 150 17.06.15 10:07 Сейчас в теме
(7) Evil Beaver, раз не умеете читать, постарайтесь хотя бы не хамить.
Зеленоград; +1 Ответить
12. Evil Beaver 8100 17.06.15 12:19 Сейчас в теме
(8) не могли бы вы уточнить два момента:
1. что именно я не прочитал?
2. где именно я нахамил?

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

Вы меня, конечно, извините, но для профессионального разработчика (если человек себя таковым считает) высказывание "Я поискал с использованием индекса и удивился, что работает настолько быстрее" на мой взгляд недопустимо. Говорит просто о некомпетентности. Другое дело, если вы не программист по образованию, а просто пришли в мир 1С из другой профессии. Тогда примите мои извинения, вы не обязаны были этого знать.
alei1180; h00k; Yashazz; +3 Ответить
14. vasyak319 150 17.06.15 12:47 Сейчас в теме
(12) Evil Beaver,
1. "У меня как-то ещё со времён 7.7 привычка использовать для подобных целей объект СписокЗначений и была убеждённость, что разработчики платформы поддерживают некий хэш-индекс для быстрого поиска вхождений в список"
Вот с этим было связано моё удивление, что "аж в 100 раз". Думаю, это ответ и на ваш п.2.
16. Evil Beaver 8100 17.06.15 13:18 Сейчас в теме
(14) 7.7. я в этом плане не изучал. Если вы говорите, что там был поиск по хешу, готов поверить.
В восьмерке же, насколько мне хватает понимания, весь поиск в коллекциях выполняется, как правило, простым перебором. Исключение - это Соответствие и индексированная ТаблицаЗначений И если я не ошибаюсь, то СтрДлина тоже работает, как сишный strlen, т.е. длина строки не хранится, и платформа каждый раз сканирует строку в поисках нуль-символа.

В ту же тему методы СтрЧислоСтрок и СтрПолучитьСтроку. Читают каждый раз текст с начала, вычисляя нужный номер строки.
20. vasyak319 150 17.06.15 15:27 Сейчас в теме
(16) Evil Beaver,
Если вы говорите, что там был поиск по хешу
нет, не говорю :(
Я говорю: "была убеждённость", потому что сам бы так сделал на месте разработчиков.
10. molodoi1sneg 17 17.06.15 11:06 Сейчас в теме
А возможно сделать замер с соответсвием?
23. Yashazz 4707 17.06.15 19:09 Сейчас в теме
Самоочевидный баян, опять получивший не-пойми-почему гору плюсов. Интересно, когда "пионэры" матчасть учить станут, вместо чтобы эксперименты ставить?

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

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

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


А почему только с этим? Давайте уж, выкладывайте, что у вас там ещё в Синтакс-помощнике есть.
29. FlyVodolaz 23.06.15 14:12 Сейчас в теме
(25) DrAku1a,
Я так понимаю, не реализовали таблицу значений на клиенте, по причине отсутствия подходящего типа в JavaScript.

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

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