Forth и другие саморасширяющиеся системы программирования Locations of visitors to this page
Текущее время: Чт мар 28, 2024 23:59

...
Google Search
Forth-FAQ Spy Grafic

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 19 ]  На страницу 1, 2  След.
Автор Сообщение
 Заголовок сообщения: поиск последовательностей битов в ячеке
СообщениеДобавлено: Ср июл 27, 2011 15:41 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2168
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 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 адрес и длина массива с искомыми последовательностями

_________________
С уважением, chess


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: поиск последовательностей битов в ячеке
СообщениеДобавлено: Ср июл 27, 2011 15:55 
Не в сети

Зарегистрирован: Вт май 09, 2006 12:31
Сообщения: 3438
Благодарил (а): 5 раз.
Поблагодарили: 16 раз.
Эта задача что-то мне напоминает :)
Её решение представляет ( в отличие от поиска в строке) перебор числе от 1 и более, при том что числа представлены в двоичном коде


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: поиск последовательностей битов в ячеке
СообщениеДобавлено: Ср июл 27, 2011 16:02 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2168
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 41 раз.
вопрос писал(а):
Эта задача что-то мне напоминает Её решение представляет ( в отличие от поиска в строке) перебор числе от 1 и более, при том что числа представлены в двоичном коде

Это задача на перебор, точнее на способ его усечения в конкретной ситуации(привязать усечение к типу входных данных)

_________________
С уважением, chess


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: поиск последовательностей битов в ячеке
СообщениеДобавлено: Ср июл 27, 2011 16:11 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2168
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 41 раз.
А еще это обобщение (расширение) задачи о нахождении максимальной последовательности 1-х битов в ячейке, оптимальное
решение которой нашел Winglion(частный случай этой задачи - при последовательности битов, которая имеет вид '1' )

_________________
С уважением, chess


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: поиск последовательностей битов в ячеке
СообщениеДобавлено: Чт июл 28, 2011 13:03 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2168
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 41 раз.
Попробовал полный перебор с отсечением нулевых последовательностей:
Код:
: 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-х битов сделан на ассме.
Видимо последовательности для поиска надо брать не подряд, а из самого исходного числа.

_________________
С уважением, chess


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: поиск последовательностей битов в ячеке
СообщениеДобавлено: Чт июл 28, 2011 14:46 
Не в сети

Зарегистрирован: Вт май 09, 2006 12:31
Сообщения: 3438
Благодарил (а): 5 раз.
Поблагодарили: 16 раз.
Поскольку необходимы повторяющиеся последовательности, из самого 4-байта достаточно брать повторяющиеся. Нужно, видимо, манипулировать исключающим ИЛИ

Сдвигая ячейку, сравнивать её побитно с собственной копией (несдвинутой)


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: поиск последовательностей битов в ячеке
СообщениеДобавлено: Чт июл 28, 2011 15:28 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2168
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 41 раз.
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


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: поиск последовательностей битов в ячеке
СообщениеДобавлено: Пт июл 29, 2011 16:37 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2168
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 41 раз.
Появилось замечание по поводу последовательностей из единиц и нулей.
Хотя последовательность вроде является числом, но оказалось что это не так.
Последовательность не сводится к одному числу. Она сводится к двум числам.
Первое число это количественная характеристика последовательности.
Например последовательность 0101 сводится к числу 101. Последовательность 101 сводится к тому же числу 101.
Но последовательности разные. Второе число для последовательности длина( можно еще взять количество начальных нулей что
будет короче).
То есть 0101 это 101 100 в виде чисел, а 101 это 101 11. То есть для хранения последовательности нужны две ячейки.
Название 'последовательность' неудобное. Возможно существует какой-то другой термин для последовательностей, но я что-то его
не обнаружил.

_________________
С уважением, chess


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: поиск последовательностей битов в ячеке
СообщениеДобавлено: Пт июл 29, 2011 20:24 
Не в сети
Administrator
Administrator
Аватара пользователя

Зарегистрирован: Вт май 02, 2006 13:19
Сообщения: 3565
Откуда: St.Petersburg
Благодарил (а): 4 раз.
Поблагодарили: 72 раз.
В данном случае, как мне кажется, надо "последовательности" определять вот так:

маска: 0000000000011111b
биты: 0000000000000101b

Маска выделяет, какие биты к последовательности относятся, какие нет.
Затем, для подсчета - маска и биты сдвигаются, делается

: TEST SOURCE @ bits @ XOR mask @ АND 0= IF ." совпало" ELSE ." не совпало THEN ;

а дальше - цикл по маскам, (биты маской из исходного числа выделять)...
32 маски x 32 положения маски x 32 проверки - 32K исполнений слова TEST и вместо чепяти слов - запись статистики в массив...

короче, пока неясно зачем сей изврат нужен, интерса кодить и нету...

_________________
С уважением, WingLion
Forth-CPU . RuF09WE
Мой Форт
Отсутствие бана это не заслуга юзера, а недоработка модератора (с)


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: поиск последовательностей битов в ячеке
СообщениеДобавлено: Пт июл 29, 2011 20:42 
Не в сети

Зарегистрирован: Вт май 09, 2006 12:31
Сообщения: 3438
Благодарил (а): 5 раз.
Поблагодарили: 16 раз.
Цитата:
32 маски x 32 положения маски x 32 проверки

Это ещё почему? если маска шире 1 бита то она не может быть 32 раза, а 32 - ширина


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: поиск последовательностей битов в ячеке
СообщениеДобавлено: Пт июл 29, 2011 20:54 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2168
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 41 раз.
WingLion писал(а):
32 маски x 32 положения маски x 32 проверки

на самом деле 1 32 + 32 * 2/ 32 * ( 16896 )

_________________
С уважением, chess


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: поиск последовательностей битов в ячеке
СообщениеДобавлено: Пт июл 29, 2011 20:55 
Не в сети
Administrator
Administrator
Аватара пользователя

Зарегистрирован: Вт май 02, 2006 13:19
Сообщения: 3565
Откуда: St.Petersburg
Благодарил (а): 4 раз.
Поблагодарили: 72 раз.
вопрос писал(а):
Это ещё почему? если маска шире 1 бита то она не может быть 32 раза, а 32 - ширина


Взято всего лишь по максимуму...

Ясен пень, что не все смещения маски/битов должны обсчитываться

_________________
С уважением, WingLion
Forth-CPU . RuF09WE
Мой Форт
Отсутствие бана это не заслуга юзера, а недоработка модератора (с)


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: поиск последовательностей битов в ячеке
СообщениеДобавлено: Пт июл 29, 2011 20:59 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2168
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 41 раз.
chess писал(а):
Взято всего лишь по максимуму...

Вам сказали что максимум не 32К, а меньше. Я дал точное значение максимума (16896 ).

_________________
С уважением, chess


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: поиск последовательностей битов в ячеке
СообщениеДобавлено: Пт июл 29, 2011 21:40 
Не в сети
Administrator
Administrator
Аватара пользователя

Зарегистрирован: Вт май 02, 2006 13:19
Сообщения: 3565
Откуда: St.Petersburg
Благодарил (а): 4 раз.
Поблагодарили: 72 раз.
chess писал(а):
Вам сказали что максимум не 32К, а меньше. Я дал точное значение максимума (16896 ).


По порядку величины я даже не соврал...

_________________
С уважением, WingLion
Forth-CPU . RuF09WE
Мой Форт
Отсутствие бана это не заслуга юзера, а недоработка модератора (с)


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: поиск последовательностей битов в ячеке
СообщениеДобавлено: Пт июл 29, 2011 22:07 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2168
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 41 раз.
WingLion писал(а):
По порядку величины я даже не соврал...

Ну вы прямо как на экзамене. :)

_________________
С уважением, chess


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 19 ]  На страницу 1, 2  След.

Часовой пояс: UTC + 3 часа [ Летнее время ]


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 15


Вы не можете начинать темы
Вы можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
phpBB сборка от FladeX // Русская поддержка phpBB