Форум на Исходниках.RU

Сравнение массивов

GrAnd — Mon, 09 Dec 2002 05:44:33 +0000

GrAnd: В свое время использовал циклический проход одного массива по другому. Т.е. производим сдвиг элементов массива В влево или вправо. И производим сравнение всех элементов обоих массивов. Общее количество операций n², n - размер массивов

Сравнение массивов

GrAnd — Mon, 09 Dec 2002 05:39:20 +0000

GrAnd:

Цитата AGAMEMNUM, 03.12.02, 16:35:26

А что за алгоритм Кнута-Морриса?

http://algolist.manual.ru/search/esearch/kmp.php
;D ;D ;D

Сравнение массивов

Demo_S — Thu, 05 Dec 2002 15:57:59 +0000

Demo_S: хехе делал я нечто подобное, и даже дока была крутейшая, правда на наглийском...
если тебенадо точно, то полный перебор (правда это будет долго)
если надо быстрее, то
все решается хеш таблицей за 1, или полтора прохода по каждому из массивов (в моем случае это были 200 мб файлы) но при этом ессно будут найдены не все одинаковые куски....

Сравнение массивов

AGAMEMNUM — Tue, 03 Dec 2002 13:35:26 +0000

AGAMEMNUM: А что за алгоритм Кнута-Морриса?

Сравнение массивов

PropellerMan — Mon, 25 Nov 2002 10:43:34 +0000

PropellerMan: Если немного переделать алгоритм Кнута-Мориса-Пратта, то получится как раз решение задачи.

Сравнение массивов

S.Yu.Gubanov — Mon, 25 Nov 2002 10:12:47 +0000

S.Yu.Gubanov: Можно попробовать так:

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\%

Сравнение массивов

AGAMEMNUM — Mon, 25 Nov 2002 05:29:47 +0000

AGAMEMNUM: нужно сравнить 2 массива, найти в них одинаковые куски, причем куски могут быть разной длины и в разных частях массива, их может быть разное количество т.е.

1 2

A M
B N
C A
X B
X C
S Y

должны найтись куски ABC, их смещения в файлах

мне приходит в голову только самый простой перебор, вот только на каждый байт одного массива надо просмотреть другой, а это долго уже при 1mb...