Сравнение массивов больших размеров

[Lotos]

Имеются два массива строк; 1-й на 26 тысяч, 2-й на 16 тысяч. Нужно сравнить имеются ли во втором массиве строки из первого. Подскажите рациональный алгоритм или литературку на эту тему.

[Maslov]

Второй отсортировать, затем искать в нем строки из первого двоичным поиском.

[Lotos]

Спасибо, про сортировку одного думала.

[Pavia]

Для массивов строк считаем хэши потом сортируем хэши и сравниваем массивы. Вначале по хэшам потом по символьно строки.
В STD вроде это уже реализовано если не ошибаюсь. Советую поискать в интернете вопрос частый.

[e2e4]

Маленькое дополнение: конечно, предложение Pavia - одно из самых эффективных (на ум другое не приходит), да и предложение Maslov тоже содержит значительную оптимизацию процесса, но, как и в любой задаче, можно для начала прикинуть PROFIT:
1. Пускай каждая строка содержит по 256 символов
2. Пускай расхождение находится (если находится) всегда на последнем символе строки (уж невезет, так невезет ).
3. Размер первого массива: 6,4 Мб; Размер второго массива: 4 Мб. Легко помещаются в ОЗУ, а на современных процессорах еще и большая их часть поместится в L2 - кеше процессора. Таким образом, временем доступа пренебрегаем.
4. Считаем кол-во операций сравнения: $26000*256*16000 = 1,07*10^{11}$.
5. Берем относительно современный (но и не топовый) одноядерный процессор Intel Pentium IV@3.2 GHz и смотрим, что у него около 10 MIPS, т.е. около 10 миллионов целочисленных операций в сек. Предполагаем, что операция сравнения не займет более 1-й целочисленной операции, имеем время работы: $1,07*10^{11} / 1*10^7 = 10 700$ сек $ = 3$ часа. Заметим, что топовые процы (четырехядерные атлоны и core 2) имеют более 40 MIPS, т.е. сравнение займет меньше часа, там правда надо морочиться с распараллеливанием на несколько ядер, но задача параллелится оч. легко - достаточно разбить первый массив на четыре части, записать их в отдельные файлы, запустить 4 эксземпляра программы каждый со своим файлом и с помощью программы типа process explorer закрепить каждый процесс (set affinity) за своим ядром. Т.е. на код это не влияет вообще .
6. Учитываем, что на практике сравнение завершится гораздо быстрее, т.к. несовпадения будут находиться, конечно, ранее чем на самом последнем символе.

Вывод: если нужна однократная сортировка, то подход "лоб" даст эффект быстрее, чем писать и отлаживать всякие хэши .

[venco]

Да вы что!
Если бы я учил программированию, и мне кто-нибудь из учеников принёс программу, которая вместо предполагаемых секунд работает час из-за неэффективного алгоритма, я бы в лучшем случае поставил тройку за то, что хоть какой-то результат есть.
Делайте как Maslov посоветовал. С использованием STL собственно алгоритм, вез ввода/вывода, займёт меньше десятка операторов. Можно ещё не сортировать массив, а сразу использовать std::set.

-- Чт окт 08, 2009 18:10:49 --

e2e4, я подозреваю, что вы так пошутили, но, боюсь, Lotos шутки не оценит.

[Maslov]

e2e4 в сообщении #250260 писал(а):

Предполагаем, что операция сравнения не займет более 1-й целочисленной операции, имеем время работы: $1,07*10^{11} / 1*10^7 = 10 700$ сек $ = 3$ часа.

Какие страшные ужасы Вы рассказываете
2 массива по 50000 строк по 260 символов с общим префиксом 256 байт сравниваются "в лоб" все-со-всеми около 20 сек (на одном процессоре Core2Duo 2.4 GHz). При этом все работает под .Net, так что все строки юникодные (2 байта на символ). C++ будет работать быстрее.
Но дело не в этом. Какое-то немного неэстетичное решение Вы предлагаете
А вообще было бы интересно сравнить по времени работы и затратам на программирование/отладку все три способа - без сортировки, с сортировкой только второго, и с сортировкой хэшей и последующим их сравнением за один параллельный проход по двум массивам.
Правда на таких незначительных объемах данных разница может просто не прозвучать.

[e2e4]

venco писал(а):

e2e4, я подозреваю, что вы так пошутили, но, боюсь, Lotos шутки не оценит.

Да нет, вроде не шутил. Я попытался показать некоторый "инженерный" подход к делу - может быть, конкретно здесь и не очень удачный, т.к. алгоритмы сортировки уже написаны дядей Васей (и даже с большой долей верятности не содержат ошибок ).
Если задача не учебная, а реальная - всегда ее нужно оценивать с разных сторон, и быстрота написания кода/простота (а, следоватлеьно, надежность) отладки - выливаются в конце концов в экономику. Когда я вижу такую постановку задачи, как в первом сообщении - есть какие-то определенные цифры, четко очерчены рамки - всегдя тянет прикинуть несколько вариантов, и, если самый простой возможен - принимается как правило, именно он.

-- Пт окт 09, 2009 02:39:04 --

Maslov писал(а):

Какое-то немного неэстетичное решение Вы предлагаете

Полностью с Вами согласен . Я не предлагаю, я только предлагаю его обсудить, а потом - отклонить .

Maslov писал(а):

А вообще было бы интересно сравнить по времени работы и затратам на программирование/отладку все три способа - без сортировки, с сортировкой только второго, и с сортировкой хэшей и последующим их сравнением за один параллельный проход по двум массивам.

Еще один способ - хэши посчитать, но их не сортирвать. В качестве хэша можно взять простую контрольную сумму по модулю $2^{16}$, к примеру. Уже будет существенное ускорение без необходимости писать сортировку, что сложнее.

Maslov писал(а):

2 массива по 50000 строк по 260 символов с общим префиксом 256 байт сравниваются "в лоб" все-со-всеми около 20 сек (на одном процессоре Core2Duo 2.4 GHz). При этом все работает под .Net, так что все строки юникодные (2 байта на символ). C++ будет работать быстрее.

Хммм... я ошибся в $10 700/20$ = 535 раз? Странно. Вряд ли дело в оптимизации на уровне процессора. Где же ошибка? Завтра сам напишу подобную программу и потестирую на рабочем Pentium M @1,86 GHz.

[Maslov]

e2e4 в сообщении #250276 писал(а):

Если задача не учебная, а реальная - всегда ее нужно оценивать с разных сторон, и быстрота написания кода/простота (а, следоватлеьно, надежность) отладки - выливаются в конце концов в экономику.

Ну тут тоже все не так однозначно. Кроме экономики, оцениваемой чисто по трудозатратам, есть еще вложения в "человеческий капитал". И на мой взгляд, всегда лучше стимулировать человека два часа осваивать что-то новое, чем заставлять его эти же два часа разливать и сливать файлы и копировать их с машины на машину.

[e2e4]

e2e4 писал(а):

Хммм... я ошибся в = 535 раз? Странно. Вряд ли дело в оптимизации на уровне процессора. Где же ошибка?

Ежкин кот, брал MIPS'ы вот отсюда, на автомате подумал, что для Pentium 4 Extreme Edition 9,726 MIPS - это 9 целых, 726 сотых (что-то как-то сразу не смутила такая низкая производительность ). А они запятой просто тысячи отделяют. В общем ошибка прикидки в 1000 раз. Итого имеем 11 сек для исходной задачи (прикидочно), и 24 сек для Вашей задачи (2 массива по 50 000 строк, 260 байт на строку, core 2 duo), что довольно точно, я доволен - иду спать . Насчет того, что у Вас unicode - т.е. 16 бит на символ, так это процессору все-равно, он как минимум 16-битными операндами и оперирует.

P. S.

e2e4 писал(а):

Завтра сам напишу подобную программу и потестирую на рабочем Pentium M @1,86 GHz.

Естественно, отменяется .

[Maslov]

e2e4 в сообщении #250279 писал(а):

Насчет того, что у Вас unicode - т.е. 16 бит на символ, так это процессору все-равно, он как минимум 16-битными операндами и оперирует.

Ну это Вы бросьте
Может оперировать с байтами - CMP AL,1
может со словами (16 бит) - CMP AX,1
может с двойными словами (32 бита) - CMP EAX,1

[PAV]

venco в сообщении #250267 писал(а):

Если бы я учил программированию, и мне кто-нибудь из учеников принёс программу, которая вместо предполагаемых секунд работает час из-за неэффективного алгоритма, я бы в лучшем случае поставил тройку за то, что хоть какой-то результат есть.

Хорошо видно типичное отличие учебного подхода от промышленного. Если задача прикладная и одноразовая, а цена вопроса, как тут посчитали - секунд 10 работы, то можно совершенно спокойно писать самый простейший лобовой алгоритм за 5-10 минут и переходить к другим задачам.

[Maslov]

Maslov в сообщении #250275 писал(а):

2 массива по 50000 строк по 260 символов с общим префиксом 256 байт сравниваются "в лоб" все-со-всеми около 20 сек (на одном процессоре Core2Duo 2.4 GHz). При этом все работает под .Net, так что все строки юникодные (2 байта на символ). C++ будет работать быстрее.

Опровержение!
Это я ночью куда-то не туда смотрел.
Там существенно медленнее все получается. Минимум на порядок. Так что есть куда оптимизировать.

[PAV]

Думаю, что достаточно добавить какое-нибудь готовое хеширование и все будет работать вполне себе скоро.

[Maslov]

Некоторые соображения по поводу средней вычислительной сложности в разных случаях:

Вне зависимости от того, работаем мы с хэшами или с исходными строками, можно рассмотреть следующие варианты (m - длина первого массива, n - длина второго массива):

1. Ни один массив не отсортирован; линейный поиск элементов первого во втором.
Сложность поиска - $O(m\cdot n)$

2. Отсортирован только второй; двоичный поиск элементов первого во втором.
Сложность сортировки - $O(n \cdot log(n))$, сложность поиска - $O(m \cdot log(n))$, общая - $O((m+n) \cdot log(n))$

3. Отсортированы оба; параллельный поиск в двух массивах за один проход.
Сложность сортировки - $O(m \cdot log(m)) + O(n \cdot log(n))$, сложность поиска $O(m+n)$

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

В связи с тем, что в нашем случае m > n, второй вариант, скорее всего, будет работать немного быстрее третьего.

В наихудшем случае сложность сортировки $O(N^2)$, и разницу между тремя вариантами надо определять экспериментально.

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