Например, недавно увидел такой пункт, который фигурировал как типовая ошибка:
Использование SORT+DELETE ADJACENT DUPLICATES вместо цикла со вставкой в хеш-таблицу.
Где-то глубоко в подсознании давно засела мысль, что просто накидать в таблицу строк, сортирнуть один раз и потом грохнуть дубли - это быстрее чем на каждую строчку искать есть ли такая уже (либо бинарным поиском, либо хэш считать, не суть).
Ну и одно дело, когда ты делаешь так, как считаешь правильным, а другое - когда тебе это запрещают. И поскольку данное требование я встретил впервые, я решил разобраться, что же реально быстрее и насколько.
Внимание! Сразу хочу уточнить, что ранее здесь был другой текст с диаметрально противоположными результатами, поскольку я забыл про одну особенность SORT, на что мне и было указано в комментариях. Так что если вы его читали, а теперь видите совсем другое - не удивляйтесь. А выводы в принципе те же остались.
Для тестирования была накатана небольшая программка, которая измеряет время выполнения двух вариантов. В первом из исходной таблицы в обычную добавляются все строки, потом сортируются и потом удаляются дубликаты. Во втором варианте строки исходной таблицы добавляются в хэшированную (попадают туда, естественно, только уникальные). Количество строк в исходной таблице задается параметром LV_COUNT, количество выполнений - параметром LV_TIMES. Оба параметра увеличиваются в 10 раз на каждой итерации цикла.
Исходная таблица заполняется случайными целыми числами до выполнения измерений по любому из вариантов. Чтобы там заведомо были совпадения числа берутся по модулю 10.
В итоге выводится результат в виде таблицы. Это некие "попугаи", приблизительно соответствующие микросекундам, но нам это не очень важно - нам важно соотношение двух вариантов. Если программу будете сами запускать, она, скорее всего. упадет по таймауту, поскольку общее время выполнения около 20 минут - запускайте в фоне, потом смотрите в спул.
Смотрим на результаты:
- Одна строка в исходной таблице.
Что мы тут видим? Прежде всего примерный паритет между обоими вариантами. На самом деле эти измерения с 1 строкой - туфта... Во-первых, чисто логически, тут не было никаких поисков и сравнений, чтобы удалять там какие-то дубликаты - строка тупо одна, она просто добавилась и все. Все затраты времени тут скорее на накладные расходы - цикл, добавление строки, очистка таблицы. Во-вторых, реально цифры тут прыгали как хотели, то есть в том же варианте с 100000 повторов иногда вариант S+D вырывался вперед, иногда Hash.Смотрим дальше - 10 и более строк в исходной таблице
- Итак самое главное - вариант с Hash действительно раза в 1,5 быстрее S+D! (там, где деление на 0, я замеры не проводил поскольку просто долго, а картинка и так уже складывалась)
- Также видно, что результат на 1 повторе можно не рассматривать. Это следует из значений соотношения времени к количеству повторов (S+D/time и Hash/time). Например видно, что в случае S+D затраты на 1 прогон при 10-1000000 повторах в среднем одинаковые. А в случае 1 прогона цифра значительно выше - это опять же играют роль накладные расходы, а не основная логика. Вот поэтому и нужно несколько прогонов, чтобы нивелировать время на накладные расходы.
- Почему то большее ускорение Hash получает с увеличением числа строк в исходной таблице. Возможно тут сказывается выделение/освобождение памяти для S+D, которое и дает это отставание. Также на 10 строках Hash тоже почему то "более быстрый", чем на Hash на 100. Причина не понятна, да и не важно это. В среднем алгоритм Hash на ~50% быстрее чем S+D.
Итак, я был обескуражен результатами, но давайте смотреть на вещи реально. Возьмем последний вариант, когда в исходной таблице было 100тыс строк (что уже довольно редко бывает). И, как правило, нескольких прогонов как в этом тесте не бывает - он один. Поэтому, посмотрев на значение 5 и 6 столбцах, мы увидим, что S+D отработает за примерно 27 миллисекунд, а Hash - примерно за 16 миллисекунд. Милли-секунд! Вы не заметите эту разницу никак вообще! А значит требование как и запрет использовать то или другое - бред. Как удобнее в каждом конкретном случае, так и нужно делать. Кто знает что вы там дальше с этой таблицей делаете - может там потом поиск по полному ключу 100500 раз? А может по неполному? Нет и не может быть тут универсального совета.
Я не прав (опять)? - welcome в комменты.
