Поиск совпадений цифр в списке чисел. Есть ли мысли?

← →
SergP. (2005-10-25 15:20) [0]

Имеется довольно много 14-разрядных чисел. Нужно из них выбрать пару, где было бы максимальное количество совпадений цифр (по позициям)

Например данная пара имеет 3 совпадения:
45236789315424
41896531386631

Пока кроме тупого перебора в голову ничего умного не приходит...
Есть ли какие-нить мысли по алгоритму такого поиска?

← →
Sandman29 © (2005-10-25 15:46) [1]

1. Отсортировать, найти совпадения в первой позиции.
2. Отбросить первую цифру.
3. Перейти на пункт 1 :)

← →
Sha © (2005-10-25 16:01) [2]

> Sandman29
не понял

← →
Sandman29 © (2005-10-25 16:08) [3]

>не понял

В массиве храним записи из
OriginalValue, CurrentValue, Counter

CurrentValue := OriginalValue;
Сортируем массив по CurrentValue.
Находим границы - индексы, на которых происходит смена первой цифры.
Для каждой группы увеличиваем Counter каждого элемента на (мощность группы - 1).
Убираем первую цифру у всех элементов в CurrentValue.
Повторяем.

В конце находим элемент с максимальным Counter. Берем исходное число из OriginalValue

← →
Sha © (2005-10-25 16:10) [4]

> В конце находим элемент с максимальным Counter
надо найти максимально близкую пару

← →
Sandman29 © (2005-10-25 16:12) [5]

Sha © (25.10.05 16:10) [4]

>надо найти максимально близкую пару

Тогда я балбес. Буду думать над новой (для меня :-) задачей.

← →
Sha © (2005-10-25 16:16) [6]

Похоже на перебор - O(n^2)

← →
Opilki_Inside © (2005-10-25 16:17) [7]

Жаль что числа заданы в десятичной системе... так можно было бы использовать побитывые сдвиги shr, shl

← →
Sha © (2005-10-25 16:20) [8]

> Opilki_Inside
Считай, что двоичные, 32 бита. От этого ничуть не легче.

← →
Sandman29 © (2005-10-25 16:21) [9]

Sha © (25.10.05 16:16) [6]

Да, согласен. Хотя можно попробовать отсортировать по сумме цифр. В худшем случае будет тот же O(n^2) + O(nlogn), в лучшем можно неплохо выиграть. в среднем тоже должен быть небольшой выигрыш.

← →
Sha © (2005-10-25 16:33) [10]

>Sandman29
>в среднем тоже должен быть небольшой выигрыш
хорошо бы это доказать для раномерного независимого распределения цифр :)

← →
Sandman29 © (2005-10-25 16:35) [11]

Sha © (25.10.05 16:33) [10]

Если бы у меня была такая курсовая, попробовал доказать бы :)

← →
MOA © (2005-10-25 16:54) [12]

Если задача позволяет, можно попытаться разменять память на скорость, например, во время сравнения (или заранее) строить списки (индексы) смысл которых "список чисел , в которых на К-той позиции стоит цифра Н" (числом 140 штук ;)). Тогда во время сравнения не нужно будет сравнивать числа, в которых в данной позиции не то.
Варианты "список чисел, в которых есть цифра 2", или "список чисел, в которых с 1-й по 6-ю позицию встречается цифра 3".
Если список целиком помещается в памяти - можно ещё как-нибудь память напрячь ;).

← →
MBo © (2005-10-25 16:54) [13]

Очень похоже:
http://algolist.manual.ru/sort/mqs/fast_strings6.php

← →
han_malign © (2005-10-25 17:04) [14]

Octree?

← →
Satirus (2005-10-25 17:08) [15]

похоже на коды пополнения карточек, там тоже обычно 14 чисел.
хочешь подобрать формулу, по которым они генерятся?%)

← →
Sha © (2005-10-25 17:16) [16]

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

← →
Satirus (2005-10-25 17:49) [17]

> 2Sha © (25.10.05 17:16) [16]

а вообще есть. какие-то алгоритмы, которые хоть приблизительно могут вычислить закономерность генерации кодов?
вот у меня накопилось много карточек пополнения и я как настоящий программист, хочу подобрать функцию, по которой они генерятся%)))
не ради денег, интереса ради)))

← →
Igorek © (2005-10-25 18:02) [18]

> SergP. (25.10.05 15:20)
> Имеется довольно много 14-разрядных чисел.

Думаю можно предложить линейний алгоритм (и не один). Но напр. с квадратичной памятью. Насколько много чисел?

← →
Sha © (2005-10-25 18:35) [19]

> Satirus (25.10.05 17:49) [17]
> какие-то алгоритмы, которые хоть приблизительно могут вычислить закономерность генерации кодов?

Если бы генерил я, ты бы не вычислил :)
В смысле существуют такие алгоритмы генерации.

← →
Sha © (2005-10-25 18:36) [20]

> Igorek © (25.10.05 18:02) [18]
> Думаю можно предложить линейний алгоритм (и не один).

Пожалуйста, предложи хоть один :)

← →
Igorek © (2005-10-25 20:10) [21]

> Sha © (25.10.05 18:36) [20]

Ээ.. дома подумаю. :)

← →
Kerk © (2005-10-25 21:06) [22]

Очень похоже на то, чего я для реализации одной фичи в Кладовке собрался делать. Только у меня числа разной разрядности (т.е. позиции цифр не учитываются) и система счисления 500ричная.

Решений кроме перебора пока не вижу. :(
Будет интересно проследить за веткой.

← →
SergP © (2005-10-25 21:51) [23]

> Satirus (25.10.05 17:08) [15]
> хочешь подобрать формулу, по которым они генерятся?%)

Смысл не в том что-бы найти какую-нить формулу генерации каких-нить кодов, а в том чтобы обнаружить наличие контрольных цифр, и алгоритма их расчета.

Когда-то искал такое в 8-разрядных числах (коды ЄДРПОУ), нашел сравнительно быстро.
Потом пришлось искать в 10-ти разрядных (ИНН) и 12-разрядных (код плат. НДС).
Программа ищущая метод формирования контрольных цифр работала бы довольно долго. Вот тогда и пришлось среди кучи кодов выбирать те, которые имеют наибольшее кол-во совпадений. После этого задача упрощалась. Например если прямой перебор занимал бы по времени 10^N, то после нахождения похожих кодов (например имеющих M совпадений) время поиска метода формирования контрольных цифр уменьшилось до 10^M + 10^(N-M)

Но в случае с 10-разрядными числами (кодами) у меня была БД с более чем 40000 таких кодов, так что там можно было отсортировать и выбрать с совпадением более чем половины цифр с начала числа. Сейчас же такого нет.
Вот и приходится отбирать максимально похожие...

← →
wicked © (2005-10-25 22:13) [24]

моё имхо - нету таких.... скорей всего, компания просто генерирует огромное кол-во псевдослучайных номеров, и записывает их в БД с пометкой, карточке какого номинала они присвоены.....
даже если есть автономные терминалы, выдающие код пополнения, то, скорей всего, они заранее "заряжены" последовательностью заранее сгенерированных кодов....
поэтому, такую вещь практически нереально взломать....

← →
Sha © (2005-10-26 00:49) [25]

> SergP © (25.10.05 21:51) [23]

> Смысл не в том что-бы найти какую-нить формулу генерации каких-нить
> кодов, а в том чтобы обнаружить наличие контрольных цифр, и алгоритма
> их расчета.

Во первых, не факт, что контрольные цифры жестко привязаны к месту,
место может определяться, например, по первым цифрам.
Во вторых, как бы ты определил алгоритм для такой простейшей схемы.
Первые 7 цифр используются как seed для генератора случайных чисел,
а следующие 7 (случайные) выработаны генератором.
Для любого генератора угадаешь? А если все цифры еще переставить?
Только полный перебор 10^7 комбинаций.

← →
MBo © (2005-10-26 07:38) [26]

Линейного алгоритма придумать не удалось.
Есть идея по реализации асимптотически квадратичного с ИМХО меньшим множителем, но нужна некая структура данных вроде быстрого разреженного двумерного массива, а может, чего-то графоподобного. Навскидку использовал StringList как ассоциативный массив, но скорость мала.

← →
Sha © (2005-10-26 09:47) [27]

> MBo
> Есть идея по реализации асимптотически квадратичного с ИМХО меньшим множителем
Поделишься?

← →
КаПиБаРа © (2005-10-26 10:15) [28]

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

← →
MBo © (2005-10-26 10:29) [29]

>Sha © (26.10.05 09:47) [27]
Вместо непосредственного вычисления расстояний Хемминга для всех пар - составляем таблицу 14(знакомест)*10(цифр), одним проходом по массиву занося в ее ячейки номера элементов, для которых на опред. знакоместе стоит данная цифра - у меня это списки.
Затем проходим по спискам, собирая все встреченные пары номеров (вот это квадратичный процесс) в разреженный массив или хэш-таблицу , для каждой пары инкрементируем счетчик.

Пока не доделал c хэш-таблицей, и не могу сказать, хорошо ли это всё ;)

← →
Sandman29 © (2005-10-26 10:34) [30]

>Затем проходим по спискам, собирая все встреченные пары номеров (вот это квадратичный процесс)

Разве не линейный? 140 списков по N элементов в каждом максимум

← →
Sandman29 © (2005-10-26 10:35) [31]

>Затем проходим по спискам, собирая все встреченные пары номеров (вот это квадратичный процесс)

Хотя да, торможу.

← →
КаПиБаРа © (2005-10-26 10:49) [32]

А если представить цифры как координаты в 14 мерном пространстве, а потом определить радиус и координаты сферы, в которой максимальная плотность точек... :)

← →
MOA © (2005-10-26 11:09) [33]

ПМСМ, если решается практическая задача, необходимо иметь в виду, что алгоритмы более сложные чем перебор будут эффективны начиная с массивов >10000 записей (это "на глаз", по аналогии с сортировкой ;)) поскольку всё равно нужно "сравнить каждый с каждым" - в отличии от сортировки - а значит, алгоритм всё равно будет О(n**2), уменьшаем только коэффициент - а накладные расходы на построение списков и сравнения указателей съедят время на небольших массивах.

← →
Igorek © (2005-10-26 11:15) [34]

Да, поспешил я с выводами.. В голове сразу возникли было мысли как в [29], но при ближайшем рассмотрении оказалось - все же квадратичная скорость.

← →
Sha © (2005-10-26 11:36) [35]

> MBo © (26.10.05 10:29) [29]
> Пока не доделал c хэш-таблицей, и не могу сказать, хорошо ли это всё ;)
Конечно хорошо. По идее (если не учитывать доп. расходы)
должно получиться в 10^2/10=10 раз быстрее.

← →
Sha © (2005-10-26 12:16) [36]

> MBo ©
Твой способ без хэша будет быстрее,
а экономии памяти по сравнению с обычной таблицей хэш почти не дает (0.9^14=0.23).

← →
MBo © (2005-10-26 12:59) [37]

>Sha © (26.10.05 12:16) [36]
>Твой способ без хэша будет быстрее,

Да, я уже осознал. Поначалу с 6-7 разрядными числами баловался, для них наполнение таблицы связей - не более трети, поэтому и динамическую структуру захотелось.

← →
MBo © (2005-10-26 13:22) [38]

const N = 500;//5000 //попарное сравнение (медленное ) procedure TForm1.Button2Click(Sender: TObject); var A: array of Int64; l1, l2: Int64; i, j, k, ii, jj, Cnt, Mx: Integer; t: DWord; begin SetLength(A, N); RandSeed := 2; for i := 0 to N - 1 do begin A[i] := 10000000000000 + Int64(1000000) * Random(90000000) + Random(1000000); // Memo1.Lines.Add(Format("%d %d", [i, A[i]])); end; t := GetTickCount; Mx := 0; ii := 0; jj := 0; for i := 0 to N - 2 do for j := i + 1 to N - 1 do begin l1 := A[i]; l2 := A[j]; Cnt := 0; for k := 1 to 14 do begin if (l1 mod 10) = (l2 mod 10) then Inc(Cnt); l1 := l1 div 10; l2 := l2 div 10; end; if Cnt > Mx then begin Mx := Cnt; ii := i; jj := j; end; end; Memo1.Lines.Add(Format("%d мс:", [GetTickCount - t])); Memo1.Lines.Add(Format("%d совпадений:", [Mx])); Memo1.Lines.Add(Format("%d %d", [ii, A[ii]])); Memo1.Lines.Add(Format("%d %d", [jj, A[jj]])); end; //матричный метод procedure TForm1.Button3Click(Sender: TObject); const Sz = 14; var A: array of Int64; l: Int64; i, j, k, ii, jj, AA, BB, Mx: Integer; M: array[1..Sz, 0..9] of TList; Conn: array of array of Byte; t: DWord; begin SetLength(Conn, N, N); SetLength(A, N); RandSeed := 2; for i := 0 to N - 1 do begin A[i] := 10000000000000 + Int64(1000000) * Random(90000000) + Random(1000000); // Memo1.Lines.Add(Format("%d %d", [i, A[i]])); end; for i := 1 to Sz do for j := 0 to 9 do M[i, j] := TList.Create; t := GetTickCount; for k := 0 to N - 1 do begin l := A[k]; for i := 1 to Sz do begin M[i, l mod 10].Add(Pointer(k)); l := l div 10; end; end; for i := Sz downto 1 do for j := 0 to 9 do if M[i, j].Count > 1 then begin for k := 0 to M[i, j].Count - 2 do begin AA := Integer(M[i, j][k]); for ii := k + 1 to M[i, j].Count - 1 do begin BB := Integer(M[i, j][ii]); if AA < BB then Inc(Conn[AA, BB]) else Inc(Conn[BB, AA]); end; end; end; Mx := 0; ii := 0; jj := 0; for i := 0 to N - 2 do for j := i + 1 to N - 1 do if Conn[i, j] > Mx then begin Mx := Conn[i, j]; ii := i; jj := j; end; Memo1.Lines.Add(Format("%d мс:", [GetTickCount - t])); Memo1.Lines.Add(Format("%d совпадений:", [Mx])); Memo1.Lines.Add(Format("%d %d", [ii, A[ii]])); Memo1.Lines.Add(Format("%d %d", [jj, A[jj]])); for i := 1 to Sz do for j := 0 to 9 do M[i, j].Free; end;

← →
Sha © (2005-10-26 15:55) [39]

> MBo © (26.10.05 13:22) [38]

Код еще не смотрел. Запустил, получил:

119656 мс: 10 совпадений: 253 52449711333529 2212 52449701333918 2813 мс: 10 совпадений: 253 52449711333529 2212 52449701333918

По теории разница должна быть в 10 раз, у тебя больше, чем в 40.
В чем дело?

← →
Sha © (2005-10-26 16:22) [40]

Если из цикла вынести лишнее, простой перебор ускоряется в 2 раза

procedure TForm1.Button3Click(Sender: TObject); //попарное сравнение (чуть быстрее) var A: array of Int64; l1, l2: Int64; i, j, k, ii, jj, Cnt, Mx: Integer; t: DWord; md: array[1..14] of integer; begin SetLength(A, N); RandSeed := 2; for i := 0 to N - 1 do begin A[i] := 10000000000000 + Int64(1000000) * Random(90000000) + Random(1000000); // Memo1.Lines.Add(Format("%d %d", [i, A[i]])); end; t := GetTickCount; Mx := 0; ii := 0; jj := 0; for i := 0 to N - 2 do begin l1 := A[i]; for k := 1 to 14 do begin md[k]:=l1 mod 10; l1 := l1 div 10; end; for j := i + 1 to N - 1 do begin l2 := A[j]; Cnt := 0; for k := 1 to 14 do begin Inc(Cnt,ord(l2 mod 10=md[k])); l2 := l2 div 10; end; if Cnt > Mx then begin Mx := Cnt; ii := i; jj := j; end; end; end; Memo1.Lines.Add(Format("%d мс:", [GetTickCount - t])); Memo1.Lines.Add(Format("%d совпадений:", [Mx])); Memo1.Lines.Add(Format("%d %d", [ii, A[ii]])); Memo1.Lines.Add(Format("%d %d", [jj, A[jj]])); end;

>Sha © (26.10.05 15:55) [39]

На P3-600 разница еще больше - в 200 раз
Самые глубоковложенный цикл выполняется в переборном методе примерно 7*N^2 раз, а во втором случае 0.7 * N^2 раз.

В матричном методе в цикле просто инкремент байта идет.
А в переборе в цикле выполняются 4 деления Int64 - это, конечно, маразм, и нужно оптимизировать, переходя к сравнению строковых значений.
Тогда разница всего в 1.6-2 раза будет, так что увы, овчинка с использованием доп. памяти в моей реализации выделки не стоит ;(

procedure TForm1.Button1Click(Sender: TObject); var A: array of Int64; B: array of string; i, j, k, ii, jj, Cnt, Mx: Integer; t: DWord; begin SetLength(A, N); SetLength(B, N); RandSeed := 2; for i := 0 to N - 1 do begin A[i] := 10000000000000 + Int64(1000000) * Random(90000000) + Random(1000000); B[i] := IntToStr(A[i]); // Memo1.Lines.Add(Format("%d %d", [i, A[i]])); end; t := GetTickCount; Mx := 0; ii := 0; jj := 0; for i := 0 to N - 2 do for j := i + 1 to N - 1 do begin Cnt:=0; for k:=1 to 14 do begin if B[i,k]=B[j,k] then Inc(Cnt); end; if Cnt > Mx then begin Mx := Cnt; ii := i; jj := j; end; end; Memo1.Lines.Add(Format("%d мс:", [GetTickCount - t])); Memo1.Lines.Add(Format("%d совпадений:", [Mx])); Memo1.Lines.Add(Format("%d %d", [ii, A[ii]])); Memo1.Lines.Add(Format("%d %d", [jj, A[jj]])); end;

Еще немного улучшил полный перебор:
- вычисляю модули один раз
- оптимизировал работу с индексами

Результат превосходит ожидания
657 мс: 10 совпадений: 3814 35129365269927 4733 28047279209345 procedure TForm1.Button4Click(Sender: TObject); //попарное сравнение (еще быстрее) var A: array of Int64; l1, l2: Int64; i, j, k, ii, jj, Cnt, Mx, jmax: Integer; t: DWord; md: array of integer; begin if N<2 then exit; SetLength(A, N); RandSeed := 2; for i := 0 to N - 1 do begin A[i] := 10000000000000 + Int64(1000000) * Random(90000000) + Random(1000000); // Memo1.Lines.Add(Format("%d %d", [i, A[i]])); end; SetLength(md,14 * N); t := GetTickCount; Mx := 0; ii := 0; jj := 0; j:=14*N; for i:=0 to N-1 do begin l1 := A[i]; for k := 1 to 14 do begin dec(j); md[j]:=l1 mod 10; l1 := l1 div 10; end; end; i:=(N-1)*14-1; jmax:=N*14-1; repeat j:=jmax; repeat k:=-13; Cnt := 0; repeat Inc(Cnt,ord(md[i+k]=md[j+k])); inc(k); until k>0; if Cnt > Mx then begin Mx := Cnt; ii := i; jj := j; end; dec(j,14); until j=i; dec(i,14); until i<0; Memo1.Lines.Add(Format("%d мс:", [GetTickCount - t])); Memo1.Lines.Add(Format("%d совпадений:", [Mx])); Memo1.Lines.Add(Format("%d %d", [ii div 14, A[ii div 14]])); Memo1.Lines.Add(Format("%d %d", [jj div 14, A[jj div 14]])); end;

Можно еще ускорить ~10..15% если в цикле перебора пар
вместо типа целочисленных индексов i, j использовать
указатели pIntegerArray.

>Sha © (26.10.05 16:59) [42]
Мощно ускорилось. Но со сравнением строк быстрее будет.

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

P600, 5000 элементов:

Перебор, сравнение строк - 2914
Матричный, TList 1813
Матричный, массивы 1342
Sha [42] 5909

> MBo © (26.10.05 17:25) [44]
> Мощно ускорилось. Но со сравнением строк быстрее будет.

На моем P4 сравнение строк медленнее:

797 мс: 10 совпадений: 253 52449711333529 2212 52449701333918

Но его тоже можно значительно ускорить,
если все данные хранить в одной строке

594 мс: ! procedure TForm1.Button6Click(Sender: TObject); var A: array of Int64; B, s: string; i, j, k, Cnt, Mx: Integer; t: DWord; p, q, r, ii, jj: pchar; begin SetLength(A, N); SetLength(s, N*14); p:=pointer(s); RandSeed := 2; for i := 0 to N - 1 do begin A[i] := 10000000000000 + Int64(1000000) * Random(90000000) + Random(1000000); B:= IntToStr(A[i]); move(b[1], p^, 14); inc(p,14); // Memo1.Lines.Add(Format("%d %d", [i, A[i]])); end; t := GetTickCount; Mx := 0; //ii := 0; //jj := 0; p:=pointer(s); r:=p+14*(N-2); repeat q:=p; repeat inc(q,14); Cnt:=0; k:=13; repeat inc(Cnt,ord(p[k]=q[k])); dec(k); until k<0; if Cnt > Mx then begin Mx := Cnt; ii := p; jj := q; end; until q>r; inc(p,14); until p>r; Memo1.Lines.Add(Format("%d мс:", [GetTickCount - t])); Memo1.Lines.Add(Format("%d совпадений:", [Mx])); //Memo1.Lines.Add(Format("%d %d", [ii, A[ii]])); //Memo1.Lines.Add(Format("%d %d", [jj, A[jj]])); end;

← →
SergP. (2005-10-26 18:24) [47]

> SergP. (26.10.05 18:24) [47]
> А чему у Вас равно N ?
5000

> Sha © (26.10.05 18:03) [46]
Было бы еще заметно быстрее, если б компилятор оптимально распределил
регистры.
Он r держит на регистре, а p - на стеке, а надо наоборот.
В общем, на BASMе можно еще процентов 15 отжать.

Если развернуть внутренний цикл, получим 500 мс:

p:=pointer(s); r:=p+14*(N-2); repeat q:=p; repeat inc(q,14); Cnt:=0; inc(Cnt,ord(p[00]=q[00])); inc(Cnt,ord(p[01]=q[01])); inc(Cnt,ord(p[02]=q[02])); inc(Cnt,ord(p[03]=q[03])); inc(Cnt,ord(p[04]=q[04])); inc(Cnt,ord(p[05]=q[05])); inc(Cnt,ord(p[06]=q[06])); inc(Cnt,ord(p[07]=q[07])); inc(Cnt,ord(p[08]=q[08])); inc(Cnt,ord(p[09]=q[09])); inc(Cnt,ord(p[10]=q[10])); inc(Cnt,ord(p[11]=q[11])); inc(Cnt,ord(p[12]=q[12])); inc(Cnt,ord(p[13]=q[13])); if Cnt > Mx then begin Mx := Cnt; //ii := p; //jj := q; end; until q>r; inc(p,14); until p>r;

Еще в 4 раза быстрее
//С использованием Lookup-таблицы //(в 4 раза быстрее ускоенного строкового) procedure TForm1.Button2Click(Sender: TObject); type pWord = ^tWord; tWord = array[0..MaxInt div 4] of word; const DigitsInNumber = 14; DigitsRounded = (DigitsInNumber+3) and -4; //16 Bytes = DigitsRounded div sizeof(word); //8 Words = Bytes div sizeof(word); //4 WordsTotal = N * Words; var Data: array of word; LookupTable: array[word] of byte; Distance, MaxDistance: byte; t: integer; p, q, r: pWord; begin; //Генерируем десятичные цифры //Храним в упакованном двоично-десятичном формате //Одно 16-значное число занимает 8 байт (4 слова) SetLength(Data, WordsTotal); p:=pointer(Data); pointer(r):=@p[WordsTotal-Words]; RandSeed:=183; q:=r; repeat; t:=Random(10); t:=t shl 4 + Random(10); t:=t shl 4 + Random(10); t:=t shl 4 + Random(10); q[0]:=t; dec(cardinal(q),sizeof(word)); until cardinal(p)>cardinal(q); //Заполняем lookup-таблицу for t:=0 to $FFFF do LookupTable[t]:=ord(t and $000F=0) + ord(t and $00F0=0) + ord(t and $0F00=0) + ord(t and $F000=0); //Ищем минимальное расстояние между числами чисел t:=GetTickCount; MaxDistance:=0; repeat; q:=r; repeat; Distance:=LookupTable[p[0] xor q[0]] + LookupTable[p[1] xor q[1]] + LookupTable[p[2] xor q[2]] + LookupTable[p[3] xor q[3]]; dec(cardinal(q),Bytes); if MaxDistance<Distance then MaxDistance:=Distance; until cardinal(p)>=cardinal(q); inc(cardinal(p),Bytes); until cardinal(p)>=cardinal(r); t:=integer(GetTickCount)-t; //Выводим результат Memo1.Lines.Add(Format("%d мс, %d совпадений", [t, MaxDistance])); end;

Только заменить идентификаторы надо :)
Distance -> Matched
MaxDistance -> MaxMatched

Sha © (27.10.05 01:38) [51]

Красивая идея!
Эх, если бы можно было сделать таблицу не до $FFFF, а до 99 999 999 999 999, тогда получалось бы готовое число совпадений по одному xor.

> Sandman29 © (27.10.05 09:22) [54]

Для CPU xor-ов dword-ов все равно будет не меньше 2-х,
поэтому таблица длиннее $FFFFFFFF (что тоже нереально)
не требуется.

Жаль время заполнения такой таблицы будет очень нехилое.

Sha © (27.10.05 09:47) [55]

Для CPU xor-ов dword-ов все равно будет не меньше 2-х,
поэтому таблица длиннее $FFFFFFFF (что тоже нереально)
не требуется.

Согласен, стормозил. Даешь 128-битные процессоры! :)

>Жаль время заполнения такой таблицы будет очень нехилое.

Можно в ПЗУ записать. Теоретически

Компилятор генерит более эффективный код (в 1.6 раза)
если ему немного помочь :)

Итого 78 мс:

//С использованием Lookup-таблицы //(в ~5-6 раз быстрее ускоенного строкового) //Оптимизировано с целью использования компилятором movzx procedure TForm1.Button10Click(Sender: TObject); type pWord = ^tWord; tWord = array[0..MaxInt div 4] of word; const DigitsInNumber = 14; DigitsRounded = (DigitsInNumber+3) and -4; //16 DigitsInByte = 2; Bytes = DigitsRounded div DigitsInByte; //8 Words = Bytes div sizeof(word); //4 WordsTotal = N * Words; var Data: array of word; LookupTable: array[word] of byte; Matched, MaxMatched: integer; t, w: integer; p, q, r: pWord; begin; //Генерируем десятичные цифры //Храним в упакованном двоично-десятичном формате //Одно 16-значное число занимает 8 байт (4 слова) SetLength(Data, WordsTotal); p:=pointer(Data); pointer(r):=@p[WordsTotal-Words]; RandSeed:=183; q:=r; repeat; t:=Random(10); t:=t shl 4 + Random(10); t:=t shl 4 + Random(10); t:=t shl 4 + Random(10); q[0]:=t; dec(cardinal(q),sizeof(word)); until cardinal(p)>cardinal(q); //Заполняем lookup-таблицу for t:=0 to $FFFF do LookupTable[t]:=ord(t and $000F=0) + ord(t and $00F0=0) + ord(t and $0F00=0) + ord(t and $F000=0); //Ищем минимальное расстояние между числами t:=GetTickCount; MaxMatched:=0; repeat; q:=r; repeat; w:=p[0]; w:=w xor q[0]; Matched:=LookupTable[w]; w:=p[1]; w:=w xor q[1]; Matched:=Matched+LookupTable[w]; w:=p[2]; w:=w xor q[2]; Matched:=Matched+LookupTable[w]; w:=p[3]; w:=w xor q[3]; Matched:=Matched+LookupTable[w]; dec(cardinal(q),Bytes); if MaxMatched<Matched then MaxMatched:=Matched; until cardinal(p)>=cardinal(q); inc(cardinal(p),Bytes); until cardinal(p)>=cardinal(r); t:=integer(GetTickCount)-t; //Выводим результат Memo1.Lines.Add(Format("%d мс, %d совпадений", [t, MaxMatched])); end;

Поиск совпадений цифр в списке чисел. Есть ли мысли? Найти похожие ветки