Получение перестановки по номеру

Pahan

Код (Text):

1. .data
2.   N dd 100      ; степень
3.   result dd 32 dup (0)  ; 1024 бит
4. .code
5.   mov edx, [N]
6.   mov ecx, edx
7.   shr  edx, 5   ; N/32
8.   and ecx, 31   ; остаток от N/32
9.   mov eax, 1
10.   shl eax, cl   ; позиция 1 в старшем dword
11.   mov [edx + offset result], eax    ; поставить старший дворд на своё место

но далеко не все числа круглые в двоичной системе, т.е. представимы в виде 2^N

 

Y_Mur #19
Да, все правильно=)
Т.е. у меня грубо говоря вот такой псеводокод:
i:=0
while i<=2^100-1
{
d:=mybin(i); -- в переменную d записываю двоичное
-- представление i c учетом формата
-- т.е. чтобы добавить в d нули слева до нужной длины n.
<дальше обрабатываю d>
i++;
}
а d это либо строка, либо какой-нибудь тип из библиотеки для длинной арифметики, в зависимости от реализации mybin.
насчет кода Y_mur ничего не могу сказать - asm'ом не владею увы.

 

по поводу длинной арифметики: да, можно самому написать, у меня даже есть собственные реализованные алгоритмы курсу вычмата, но задача криптографическая, поэтому я и ищу оптимальный по времени способ.
Нашел по отзывам оптимальную бибилиотеку - GMP на http://gmplib.org/. там есть он-лайн тесты, 2 в 1000-ой за секунду подсчитала. но она под юникс. Кто-нибудь видел виндовую версию?

 

Pahan

Гы-гы код из #21 сделает это в миллионы раз быстрее )

Гы-гы ты для начала прикинь сколько времени займёт сам пустой цикл ) а потом уже ищи для него "быструю и полезную" загрузку
Лучше не парься с тупиковыми путями, а объясни толком что за "криптографический формат" из которого нужно перевести в двоичный, а ещё лучше постановку задачи целиком - наверняка тогда станет очевидным либо альтернативный путь, либо принципиальная тупиковость затеи

 

Ну да, может быть оптимизация поможет.
задача такая: на входе строка алфавита {0,1} длины n=1000.
необходимо подсчитать количество вхождений всевозможных подстрок алфавита {0,1} длины m=1, 2, 3 ..., 1000 в исходную строку.
т.е. например для m=1 нужно подсчитать сколько раз встретилоя 0 и сколько 1, для m=2 нужно подсчитать сколько раз в исходной строке встретилось 00, сколько раз 01, сколько раз 10 и сколько раз 11 и т.д. до m=1000.
Ну и я решаю напрямую - генерурую для кадого m одну из 2^m цепочек и проверяю сколько раз она встретилась.
Потом беру следующую m и повтрояю операцию.
Понятно, что для m=1000 можно не генерировать все цепочки, итак ясно, что количество вхождений всевозможных цепочек будет равно 1 (сама последовательность). Но это не сильно большая оптимизация, так что я вижу путь решения только в длинной арифметике(= Как-то еще можно оптимизировать решение?

 

Pahan
Как сказал Y_Mur

 

Pahan
Строй "иерархию" - например если комбинация 101010 ни разу не встретилась в строке то значит и все содержищие её варианты xxxx101010 тоже уже не встретятся, т.е. продолжай наращивать разрядность только тех комбинаций которые хотя бы раз встречаются.

 

Да, грамотно, я тоже думал об этому пути. Но все равно же получается что так или иначе будет присутсвовать цикл от 0 до 2^m-1. Смотрите:
Вот допустим на входе 11100.
Пусть m=2 и соответсвенно такая ситуация
0 00 +
1 01 -
2 10+
3 11+
Я вижу, что для m=3 итерацию цикла, где в двоичный вид переводится число 1, 5 (101b) проводить не стоит. Но ведь в коде то это будет выглядеть как (псевдокод)
while i<2^m-1
{
if i в (1,5,....) then continue;
}
т.е. получается, что итерация цикла все равно провдится. Пока такие мысли, сейчас еще голову поломаю как быть.

 

Pahan
До 4 бит лучше прямым перебором, затем берёшь 5 битное число начинающееся с нулевого бита и сравниваешь его со всеми 5 битными начинающимися с 1, 2, 3 и т.д. битов (994 сравнений), затем 5 битное начинающееся с 1-го бита с остальными с 2,3,4 и т.д. бит (993 сравнений) и т.д. до 5 битного начинающегося с 994 бита, сравнивая его один раз с начинающимся с 995 бита. Всего будет менее 500 тыс. сравнений (вполне нормальное количество).
При этом строишь базу данных вида:
комбинация ааа встречается 2 раза по адресам А1 и А2
комбинация bbb встречается 5 раз по адресам B1, B2, B3, B4, B5
комбинация ccc встречается 3 раза по адресам С1, С2, С3
и т.д.
остальные комбинации либо не встречаются либо встречаются без повторов.
В этой базе будет меньше чем 995 комбинаций. Адреса А1, A2, B1 и т.д. есно битовые позиции с которых начинаются комбинации в строке.
Затем берёшь 6 битное число по адресу А1 и сравниваешь его с 6 битным числом по адресу А2, если не совпало - вычёркиваешь его из базы данных, затем 6 битное по адресу B1 сравниваешь с 6 битными числами по адресам B2, B3, B4, B5, для не повторяющихся чисел адреса вычёркиваешь и т.д. Затем по адресу B2 сравниваешь с B3, B4, B5, затем B3 с B4, B5 и т.д. При этом последовательности с многими повторами bbb, ccc возможно разделятся на несколько с меньшими повторами, т.е. база перестраивается по ходу но только на основе самой себя, без её перепостроения, требующего только в первый раз 500 тыс. сравнений. Из-за того что внутри базы остаётся принцип "сравнить все со всеми" внутри кадой записи, как раз и целесообразно начинать её применение с 5 бит, где количество повторов будет намного меньше чем при 1-4 битах (за исключением редких экзотических "плохих случаев" типа вся строка заполнена 1, но это не важно).
Никакие другие комбинации сравнивать уже не надо
Тоже самое с 7 битными и т.д. - соответственно база данных будет таять по мере роста разрядности m.
Кроме этой базы данных учитывающей повторяющиеся комбинации при каждом добавлении бита (m+1) будет появляться 1000 - m комбинаций по m бит начинающихся с 0, 1, 2, ..., (1000 - m) бита, эти комбинации не нужно ни с чем сравнивать, но из них нужно исключить повторяющиеся (адреса и значения повторяющихся известны из базы данных).
При таком сравнении значение имеет совпадение или не совпадение только одного добавляемого бита поэтому длинная арифметика не нужна - т.е. младшие биты не помещающиеся в регистр можно храбро игнорировать - они уже проверены в прошлых заходах (от 1 до m-1) и одинаковы.
-----------------
А если прямым перебором как ты хотел, то 2^100 = 1267650600228229401496703205376 комбинаций, даже если затрачивать всего 1 такт процессора на комбинацию (что конечно же нереально мало), то при частоте 1ГГц получим 2^100 / (1е9*60*60*24*365) = 40196936841331 лет )
-----------------
ЗЫ: а почему 1000, а не 1024 ?

 

Небольшое пояснение:

Код (Text):

1.  строка:
2. 010010111011101010001110100101110101000101010101000001000011111010100010111....
3. содержит подстроки:
4. === 5 - битные ===
5. 01001
6.  10010
7.   00101
8.    01011
9.     10111
10.      01110
11.       11101
12.        11011
13.         10111
14.          01110
15.           11101
16.            11010
17.             10101
18.              01010
19.               .....
20. === 6 - битные ===
21. 010010
22.  100101
23.   001011
24.    010111
25.     101110
26.      011101
27.       111011
28.        110111
29.         101110
30.          011101
31.           111010
32.            110101
33.             101010
34.              010100
35.               ......
36. и т.д.

других подстрок кроме полученных по этому алгоритму в ней нет, а таких в 1000 битной строке всего навсего 500 тыс. шт. Но среди них есть повторяющиеся - посчитать повторы можно тупым сравнением всех со всеми из своей разрядности (250 млн. "длинных" сравнений), но лучше сравнивать только те у которых ранее совпали младшие биты (тогда сравнение не длинное, а однобитное). Для этого и нужно завести базу данных в которой в наихудшем случае будет 995 адресов (если построить её на 5-битном заходе), т.е. расход памяти весьма скромен и пробег по базе быстр, к тому же она будет сокращаться по мере роста разрядности подстроки, а наихудший случай (в строке только 0 или только 1) легко исключить отдельной проверкой.

 

Уточнение:

Поскольку добавляется только по 1 биту то запись в базе не может разделиться на более чем 2 записи (добавлен 0 или добавлена 1) а значит сравнивать "все со всеми" не обязательно - достаточно за один заход рассортировать каждую запись на две и включить в обновлённую базу только те записи в которых больше одного адреса.
А поскольку 5 бит это всего 32 комбинации, то и при построении базы не нужно сравнивать "все со всеми" а лучше сделать 32 прохода напрямую (32 тыс. сравнений вместо 500 тыс.). А построить и начать использовать базу можно не только на 5 битах, а в диапазоне m=5-8 бит., дальше >9 бит. прямое сравнение перебором комбинаций становится чрезмерно громоздким.
Организовать эту базу данных лучше связанным списком потому что легко добавлять/удалять/корректировать записи.

 

Y_Mur
Прежде всего респект. Изучаю Ваш алгоритм - очень нравится идея.
Небольшое уточнение из #29:

При нумерации битов входной цепочки с 0...999- первое 5 битное число (0,1,2,3,4 биты )будет последовательно сравниваться с 5-ю битами входной цепочки, начиная с 1 бита по 995 (995,996,997,998,999 - последние пять бит, с которыми будет сравнена ) т.е. получается на первой итерации 995 сравнений. Это не принципиально, просто я хочу удостоверится, что правильно Вас понимаю.

С остальным вроде все ясно более менее, сейчас сяду за реализацию. Если появятся вопросы, то еще спрошу.
Спасибо.

 

994 = 995 - 1 потому что число не нужно сравнивать с самим собой и это первая итерация для базы данных повторов (где эта база строится) а для алгоритма в целом это 5-я итерация - первые четыре прямым перебором, как ты и хотел в самом начале. Прямой перебор однозначно лучше до m=4, в диапазоне m=5-8 лучшим может оказаться как прямой перебор, так и база данных (зависит от конкретной разбираемой строки), а дальше однозначно лучше база данных.

 

хм..ну мы ведь и сравниваем первое 5-битовое число с 5-ю битовыми последовательностями начиная с 1-го бита, а не с 0-го.
Допустим, входная последовательность
0 0 1 0 1 1 0 0 1 0 (n=10)
0 1 2 3 4 5 6 7 8 9
и возьмем для примера m=2, а не 5-ти. Тогда на первой итерации мы сравним 00 с
01, 10, 01, 11, 10, 00, 01, 10, (1..8), т.е. цикл по битам: с 1 по (n-1)-(m+1) => 1..n-m.
А для нашего примера из алгоритма: с 1..(1000-5) =>1..995, т.е. 995 сравнений.

 

Да действительно малость тормозю )

 

2 Y_Mur:
Реализовал этот алгоритм следующим образом:
Есть vector Base, в котором хранятся повторяющиеся подстроки длины m c указанием адресов, с которых они начинаются. Есть vector Temp, в который генерируются все подстроки длины m+1, сгенерированные по порядку, начиная с первого символа строки.
Таким образом, индекс подстроки в массиве Temp совпадает с номером бита, с которого она начинается в строке. Следовательно, на этапе перестроения базы Base, для нахождения совпадений, достаточно сравнить между собой элементы массива Temp по индексам, указанным в поле адресов повторений в соответствующем элементе массива Base. Совпадения находятся, база перестраивается и затем, на основе массивов Temp и Base происходит перенос информации о подстроках и количествах их повторов уже в словарь (еще один vector), который далее и используется при вычислениях.
Однако реализованный таким образом алгоритм работает оочень долго - видимо, из-за длительности вставок/удалений элементов vector'а - и появилась необходимость его оптимизировать.
При попытке использовать для хранения элементов класс list возникла проблема, связанная с невозможностью обратиться к элементу массива Temp по индексу на этапе нахождения совпадений. В качестве выхода я вижу сравнение между собой не элементов массива Temp, а использование при сравнении каждый раз какой-нибудь функции на подобе substr, которая бы возвращала искомую подстроку по номеру ее бита в строке и нужной длины. При этом, в случае совпадения подстрок - запоминать их адреса в общий по всем подстрокам Base дополнительный массив адресов Y. А уже после этого начинать генерировать массив Temp, при этом на каждой итерации смотреть - если адрес генерируемой подстроки уже есть в Y (т.е эта последовательность повторяется и уже занесена в Base), то не записывать ее в Temp; иначе - записывать и количество повторений ставить равным 1.
Но частый вызов substr-функции, а также постоянный поиск по массиву Y на этапе генерации вызывает у меня опасения, что работа алгоритма опять будет замедлена.
Подскажите, пожалуйста, какие-нибудь советы или рекомендации по структуре данных и выбранному пути реализации алгоритма.

 

Код (Text):

1. print(bit* bits,int N)
2. {
3. int next[N];
4. int alter[N];
5.  
6. for(int i=0;i<N;i++)
7.   next[i]=i+1;
8. int mark=N;
9. for(int len=1;l<=N;len++,mark--)
10. {
11.   for(int i=0;i<N;i++)
12.     alter[i]=mark;
13.   for(int i=N-l;i>=0;i--)
14.     if(next[i]<mark)
15.   {
16.     if(bit[i+len-1]==bit[next[i]+len-1])
17.       alter[i]=alter[next[i]];
18.     else
19.     {
20.       alter[i]=next[i];
21.       next[i]=alter[next[i]];
22.     }
23.   }
24.   for(int i=0;i<=N-len;i++)
25.     if(next[i]>=mark)
26.   {
27.     for(int j=j;j<i+len;j++)
28.        printf("%d",bit[j]);  
29.     printf("\n");      
30.   }
31. }
32.  
33. }

 

третья строка основного цикла:
for(int i=N-len;i>=0;i--)

 

В первой строке основного цикла тоже не l, а len.
А можно пару комментов:
что вообще делает ф-ция print и что подается в качестве аргументов?

 

и что в массиве alter хранится?