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

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

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

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