Сравнение массивов
 |
Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
|
| ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
| [18.117.229.180] |
|
|
правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке
Модераторы: Akina, shadeofgray
Сравнение массивов
|
Сообщ.
#1
,
|
|
|
|
нужно сравнить 2 массива, найти в них одинаковые куски, причем куски могут быть разной длины и в разных частях массива, их может быть разное количество т.е.
1 2 A M B N C A X B X C S Y должны найтись куски ABC, их смещения в файлах мне приходит в голову только самый простой перебор, вот только на каждый байт одного массива надо просмотреть другой, а это долго уже при 1mb... |
|
Сообщ.
#2
,
|
|
|
|
Можно попробовать так:
1) Сначала составляешь массивы остатков a[1] = "ABCXXS" a[2] = "BCXXS" a[3] = "CXXS" a[4] = "XXS" a[5] = "XS" a[6] = "S" b[1] = "MNABCY" b[2] = "NABCY" b[3] = "ABCY" b[4] = "BCY" b[5] = "CY" b[6] = "Y" Разумеется не физически (а то много памяти займет), а всего два массива указателей делаешь a[] и b[]. (O(N) - операций) 2) Потом каждый их них сортируешь по алфавиту (O(N*log(N)) - операций) (Перетасовываешь указатели) 3) Ищешь похожие элементы в двух УПОРЯДОЧЕННЫХ массивах. a[1] похож на b[3] в первых 3 символах... a[2] like b[4] -> 2 a[3] like b[5] -> 1 Сложность = O(N*Log(N) + N*g*c), где g - сложность сравнения двух строк, c- коэффициент количества похожих строк 0 < c < 100\% |
|
Сообщ.
#3
,
|
|
 |
Если немного переделать алгоритм Кнута-Мориса-Пратта, то получится как раз решение задачи.
|
|
Сообщ.
#4
,
|
|
|
|
А что за алгоритм Кнута-Морриса?
|
|
Сообщ.
#5
,
|
|
 |
хехе делал я нечто подобное, и даже дока была крутейшая, правда на наглийском...
если тебенадо точно, то полный перебор (правда это будет долго) если надо быстрее, то все решается хеш таблицей за 1, или полтора прохода по каждому из массивов (в моем случае это были 200 мб файлы) но при этом ессно будут найдены не все одинаковые куски.... |
|
Сообщ.
#6
,
|
|
 |
Цитата AGAMEMNUM, 03.12.02, 16:35:26 А что за алгоритм Кнута-Морриса? http://algolist.manual.ru/search/esearch/kmp.php ;D ;D ;D |
|
Сообщ.
#7
,
|
|
|
|
В свое время использовал циклический проход одного массива по другому. Т.е. производим сдвиг элементов массива В влево или вправо. И производим сравнение всех элементов обоих массивов. Общее количество операций n2, n - размер массивов
|
0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
0 пользователей:
[ Script execution time: 0,0243 ] [ 15 queries used ] [ Generated: 27.07.24, 13:56 GMT ]