Forth http://fforum.winglion.ru/ |
|
поиск последовательностей битов в ячеке http://fforum.winglion.ru/viewtopic.php?f=19&t=2742 |
Страница 1 из 2 |
Автор: | chess [ Ср июл 27, 2011 15:41 ] |
Заголовок сообщения: | поиск последовательностей битов в ячеке |
Задачка в стиле задач Вопроса Дано 4 байтное число(ячейка) Найти все одинаковые последовательности битов в ячейке, определить характеристику для последовательности = число единичных бит в последовательности * количество последовательностей в ячейке. найти все последовательности, для которых характеристика максимальна. под последовательностью бит понимается последовательность битов длиной от 1 до 32 битов. Для лучшего понимания Код: ячейка 00100111110110110111011011110110
последовательность число 1-х бит в последовательности кол-во последовательностей характеристика 0 0 11 0*11=0 1 1 21 1*21=21 00 0 2 0*2=0 01 1 8 1*8=8 10 1 8 1*8=8 11 2 13 2*13=26 .... и тд PS. Из рассмотренных последовательностей длиной от 1 до 2 последовательность 11 имеет максимальную характеристику решение дать в виде : max-seq ( n -- seq1 ... seqn ) ... ; или так : max-seq ( n -- a u ) ... ; где a u адрес и длина массива с искомыми последовательностями |
Автор: | вопрос [ Ср июл 27, 2011 15:55 ] |
Заголовок сообщения: | Re: поиск последовательностей битов в ячеке |
Эта задача что-то мне напоминает Её решение представляет ( в отличие от поиска в строке) перебор числе от 1 и более, при том что числа представлены в двоичном коде |
Автор: | chess [ Ср июл 27, 2011 16:02 ] |
Заголовок сообщения: | Re: поиск последовательностей битов в ячеке |
вопрос писал(а): Эта задача что-то мне напоминает Её решение представляет ( в отличие от поиска в строке) перебор числе от 1 и более, при том что числа представлены в двоичном коде Это задача на перебор, точнее на способ его усечения в конкретной ситуации(привязать усечение к типу входных данных) |
Автор: | chess [ Ср июл 27, 2011 16:11 ] |
Заголовок сообщения: | Re: поиск последовательностей битов в ячеке |
А еще это обобщение (расширение) задачи о нахождении максимальной последовательности 1-х битов в ячейке, оптимальное решение которой нашел Winglion(частный случай этой задачи - при последовательности битов, которая имеет вид '1' ) |
Автор: | chess [ Чт июл 28, 2011 13:03 ] |
Заголовок сообщения: | Re: поиск последовательностей битов в ячеке |
Попробовал полный перебор с отсечением нулевых последовательностей: Код: : sumbit1 ( n -- nb1 ) C^C L1: $ 0 A=#? L2 J0= D=L\A C++ C=D\A0 L1 JMP L2: A=C ; \ число единичных бит в ячейке : b. ( n ls -- ) ls! 2 BASE ! 32 ls - SPACES ls .0 2 SPACES 0xA BASE ! ; \ вывод результатов : character ( n ls -- sq character ) \ поиск максимальной характеристики для заданной длины последовательности ls! nt! nt n! 0 mch! 0 sq! 0 nq! -1 ls LSHIFT INVERT m! m 1+ 1 DO 32 ls - 0 DO J 0<> IF n m AND J = IF nq 1+ is nq THEN n 1 RSHIFT is n ELSE LEAVE THEN LOOP I sumbit1 nq * DUP mch > IF I is sq is mch ELSE DROP THEN nt is n 0 is nq LOOP sq ls b. mch . CR ; : max-seq ( n -- ) n! 32 1 DO n I character LOOP n 32 b. n sumbit1 . CR ." end" CR ; \ вывод максимальных характеристик для всех длин от 1 до 32 \ EOF : n 0x12345678 ; STARTLOG n max-seq Лог Код: 1 13 11 10 011 6 0011 4 01111 4 001111 4 1001111 5 11001111 6 011001111 6 1011001111 7 01011001111 7 101011001111 8 0101011001111 8 00101011001111 8 000101011001111 8 1000101011001111 9 01000101011001111 9 101000101011001111 10 1101000101011001111 11 01101000101011001111 11 001101000101011001111 11 0001101000101011001111 11 10001101000101011001111 12 010001101000101011001111 12 0010001101000101011001111 12 10010001101000101011001111 13 010010001101000101011001111 13 0010010001101000101011001111 13 00100100011010001010110011110 13 001001000110100010101100111100 13 0010010001101000101011001111000 13 00010010001101000101011001111000 13 end Ok ps. Работает около 3-х минут. Очень долго, хотя подсчет количества 1-х битов сделан на ассме. Видимо последовательности для поиска надо брать не подряд, а из самого исходного числа. |
Автор: | вопрос [ Чт июл 28, 2011 14:46 ] |
Заголовок сообщения: | Re: поиск последовательностей битов в ячеке |
Поскольку необходимы повторяющиеся последовательности, из самого 4-байта достаточно брать повторяющиеся. Нужно, видимо, манипулировать исключающим ИЛИ Сдвигая ячейку, сравнивать её побитно с собственной копией (несдвинутой) |
Автор: | chess [ Чт июл 28, 2011 15:28 ] |
Заголовок сообщения: | Re: поиск последовательностей битов в ячеке |
chess писал(а): Видимо последовательности для поиска надо брать не подряд, а из самого исходного числа. Интуиция не обманула. Именно так и надо. Перебор усечен по максимуму. Работает мгновенно. Код: : sumbit1 ( n -- nb1 ) C^C L1: $ 0 A=#? L2 J0= D=L\A C++ C=D\A0 L1 JMP L2: A=C ; \ число единичных бит в ячейке Лог: b. ( n ls -- ) ls! 2 BASE ! 32 ls - SPACES ls .0 2 SPACES 0xA BASE ! ; \ вывод результатов : character ( n ls -- sq character ) \ поиск максимальной характеристики для заданной длины последовательности ls! nt! nt n! nt nl! 0 mch! 0 sq! 0 nq! -1 ls LSHIFT INVERT m! 32 ls - 0 DO 32 ls - 0 DO nl m AND 0<> IF n m AND nl m AND = IF nq 1+ is nq THEN n 1 RSHIFT is n ELSE LEAVE THEN LOOP nl m AND sumbit1 nq * DUP mch > IF nl m AND is sq is mch ELSE DROP THEN nt is n 0 is nq nl 1 RSHIFT is nl LOOP sq ls b. mch . CR ; : max-seq ( n -- ) n! 32 1 DO n I character LOOP n 32 b. n sumbit1 . CR ." end" CR ; \ вывод максимальных характеристик для всех длин от 1 до 32 \ EOF : n 0x12345678 ; STARTLOG n max-seq Код: 1 13 11 10 110 6 1100 4 11110 4 111100 4 1001111 5 11001111 6 110011110 6 1011001111 7 10110011110 7 101011001111 8 1010110011110 8 10101100111100 8 101011001111000 8 1000101011001111 9 10001010110011110 9 101000101011001111 10 1101000101011001111 11 11010001010110011110 11 110100010101100111100 11 1101000101011001111000 11 10001101000101011001111 12 100011010001010110011110 12 1000110100010101100111100 12 10010001101000101011001111 13 100100011010001010110011110 13 1001000110100010101100111100 13 10010001101000101011001111000 13 010010001101000101011001111000 13 0010010001101000101011001111000 13 00010010001101000101011001111000 13 end ps. А то меня уже сомнение посетило насчет способов сжатия информации без потерь. А про самое главное то я и забыл - за основу сжатия берется структура самой исходной информации. |
Автор: | chess [ Пт июл 29, 2011 16:37 ] |
Заголовок сообщения: | Re: поиск последовательностей битов в ячеке |
Появилось замечание по поводу последовательностей из единиц и нулей. Хотя последовательность вроде является числом, но оказалось что это не так. Последовательность не сводится к одному числу. Она сводится к двум числам. Первое число это количественная характеристика последовательности. Например последовательность 0101 сводится к числу 101. Последовательность 101 сводится к тому же числу 101. Но последовательности разные. Второе число для последовательности длина( можно еще взять количество начальных нулей что будет короче). То есть 0101 это 101 100 в виде чисел, а 101 это 101 11. То есть для хранения последовательности нужны две ячейки. Название 'последовательность' неудобное. Возможно существует какой-то другой термин для последовательностей, но я что-то его не обнаружил. |
Автор: | WingLion [ Пт июл 29, 2011 20:24 ] |
Заголовок сообщения: | Re: поиск последовательностей битов в ячеке |
В данном случае, как мне кажется, надо "последовательности" определять вот так: маска: 0000000000011111b биты: 0000000000000101b Маска выделяет, какие биты к последовательности относятся, какие нет. Затем, для подсчета - маска и биты сдвигаются, делается : TEST SOURCE @ bits @ XOR mask @ АND 0= IF ." совпало" ELSE ." не совпало THEN ; а дальше - цикл по маскам, (биты маской из исходного числа выделять)... 32 маски x 32 положения маски x 32 проверки - 32K исполнений слова TEST и вместо чепяти слов - запись статистики в массив... короче, пока неясно зачем сей изврат нужен, интерса кодить и нету... |
Автор: | вопрос [ Пт июл 29, 2011 20:42 ] |
Заголовок сообщения: | Re: поиск последовательностей битов в ячеке |
Цитата: 32 маски x 32 положения маски x 32 проверки Это ещё почему? если маска шире 1 бита то она не может быть 32 раза, а 32 - ширина |
Автор: | chess [ Пт июл 29, 2011 20:54 ] |
Заголовок сообщения: | Re: поиск последовательностей битов в ячеке |
WingLion писал(а): 32 маски x 32 положения маски x 32 проверки на самом деле 1 32 + 32 * 2/ 32 * ( 16896 ) |
Автор: | WingLion [ Пт июл 29, 2011 20:55 ] |
Заголовок сообщения: | Re: поиск последовательностей битов в ячеке |
вопрос писал(а): Это ещё почему? если маска шире 1 бита то она не может быть 32 раза, а 32 - ширина Взято всего лишь по максимуму... Ясен пень, что не все смещения маски/битов должны обсчитываться |
Автор: | chess [ Пт июл 29, 2011 20:59 ] |
Заголовок сообщения: | Re: поиск последовательностей битов в ячеке |
chess писал(а): Взято всего лишь по максимуму... Вам сказали что максимум не 32К, а меньше. Я дал точное значение максимума (16896 ). |
Автор: | WingLion [ Пт июл 29, 2011 21:40 ] |
Заголовок сообщения: | Re: поиск последовательностей битов в ячеке |
chess писал(а): Вам сказали что максимум не 32К, а меньше. Я дал точное значение максимума (16896 ). По порядку величины я даже не соврал... |
Автор: | chess [ Пт июл 29, 2011 22:07 ] |
Заголовок сообщения: | Re: поиск последовательностей битов в ячеке |
WingLion писал(а): По порядку величины я даже не соврал... Ну вы прямо как на экзамене. |
Страница 1 из 2 | Часовой пояс: UTC + 3 часа [ Летнее время ] |
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group http://www.phpbb.com/ |