String Similarity

Очень долго долбался с задачей "String Similarity" с сайта InterviewStreet. И так, и эдак ковырял, но удавалось уложиться только в 8 тестов из 10.

А на самом деле оказалось, что нужно просто применить Z-функцию. Мда, пошел читать букварь... Кстати, не могу найти английское название Z-функции. Если кто знает, напишите, плз.

З.Ы. На Хабре можно почитать хороший разбор алгоритмов поиска подстрок.

Битхаки

Хороший сборник хаков по работе с битами — Bit Twiddling Hacks. Мне особенно понравился макрос инициализации таблицы для разворачивания битов.

Сортировка указателей

При необходимости сортировки массивов структур данных иногда полезно сортировать не сами данные, а массив указателей на эти структуры. Например, это может пригодиться, когда нам нужно отсортировать массив и записать его на диск, но указатель на массив — константный. А при работе с большими массивами мы можем получить выигрыш в производительности за счет того, что в памяти будут передвигаться не структуры, а указатели (понятно, что это имеет смысл, когда размер структуры больше размера указателя).

Слияние отсортированных массивов

Даны M отсортированных массивов по N элементов каждый. Необходимо слить их в одну отсортированную последовательность.

Есть несколько способов сделать это.

Первый способ - сливать сортированные последовательности по несколько штук (например, по две) до тех пор, пока не останется одна. Это и будет искомая последовательность. Например, для М=4, есть массивы М1, М2, М3 и М4 длиной по N элементов. На первом шаге сливаем M1 и М2, а потом М3 и М4. Получим два массива М5 и М6 длиной по 2*N элементов. На втором шаге сливаем М5 и М6 и получаем искомую последовательность длиной 4*N.

Второй способ - сливать массивы все сразу. То есть, получить искомый отсортированный массив за один шаг.

Вопрос в том, какой из способов более эффективный?

Можно попытаться посчитать приблизительное количество операций сравнения. Для простоты примем, что количество исходных массивов является степенью 2, то есть 2,4,8,... Для первого способа количество операций сравнения будет равно N*M*2*log₂M. А для второго - N*M².

Видно, что для М=2 или 4 количество операций будет одинаковое для обоих способов. А вот дальше количество операций для первого начнет уменьшаться. При М=32 соотношение количества операций будет примерно 1/3 в пользу первого способа.

Однако, все это верно, если проводить все слияние в памяти. Если же предположить, что памяти достаточно на одновременное размещение только части массивов, то дело принимает совсем другой оборот.

Предположим, что памяти хватает только на обработку пары массивов. Следовательно, после обработки каждой пары массивов на любом шаге слияния, нам нужно сохранять на диск промежуточную последовательность, чтобы считывать ее на следующем шаге слияния. То есть, используя пример, нужно считать последовательности М1 и М2 и записать последовательность М5. Затем считать М3 и М4 и записать последовательность М6. Затем считать М5 и М6 и записать результирующий массив.

Если попробовать подсчитать, то получится, что на каждом шаге нужно считать М*N элементов и записать М*N элементов. При увеличении М количество шагов растет - K=log₂M. То есть количество операций чтения/записи будет равно 2*M*N*log₂M. А используя второй способ нужно считать и записать только 2*М*N элементов (потому, что для второго способа нужен только один шаг).

Получается, что при слиянии последовательностей, не помещающихся в памяти, все переворачивается с ног на голову - так как создание промежуточных массивов на диске довольно дорогостоящая операция, то намного выгоднее сливать все последовательности за один шаг, не смотря на количество операций. Похоже, что так.