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

...
Google Search
Forth-FAQ Spy Grafic

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




Ответить
Имя пользователя:
Заголовок:
Текст сообщения:
Введите текст вашего сообщения. Длина сообщения в символах не более: 60000

Размер шрифта:
Цвет шрифта
Настройки:
BBCode ВКЛЮЧЕН
[img] ВЫКЛЮЧЕН
[flash] ВЫКЛЮЧЕН
[url] ВКЛЮЧЕН
Смайлики ВЫКЛЮЧЕНЫ
Отключить в этом сообщении BBCode
Не преобразовывать адреса URL в ссылки
Вопрос
Теперь гостю придется вводить здесь пароль. Не от своей учетной записи, а ПАРОЛЬ ДЛЯ ГОСТЯ, получить который можно после регистрации на форуме через ЛС.:
Этот вопрос предназначен для выявления и предотвращения автоматических регистраций.
   

Обзор темы - поиск последовательностей битов в ячеке
Автор Сообщение
  Заголовок сообщения:  Re: поиск последовательностей битов в ячеке  Ответить с цитатой
Дык тогда решение уже некрасивое будет.
Ладно, взял алгоритм сверху и тупо переделал его на два прохода.
На первом проходе находится максимальная характеристика.
На втором проходе выводятся все последовательности с такой характеристикой.
Код:
HEX 55AA55AA VALUE n \ Пресловутая ячейка

0 VALUE МАКСИМУМ \ Максимальная характеристика
TRUE VALUE ПРОХОД? \ Первый или второй проход ?
: SEQUENCE ( mask seq i -- mask seq )
  1+ >R
  0 R@ 0 DO OVER I RSHIFT 1 AND + LOOP \ Число единичных бит
  0 21 R@ - 0 DO 2OVER n I RSHIFT ROT AND = - LOOP \ Число повторений
  * \ Характеристика
  DUP МАКСИМУМ = ПРОХОД? AND
  IF
    2 BASE !
    OVER 0 <# R> 0 DO # LOOP #> TYPE SPACE \ Вывод последовательности
    DECIMAL . CR \ Вывод характеристики
  ELSE
    МАКСИМУМ MAX TO МАКСИМУМ RDROP
  THEN
;
: SEQ ( -- )
  0 TO МАКСИМУМ
  BEGIN
    ПРОХОД? INVERT TO ПРОХОД?
    20 0 DO
      1 I LSHIFT 2* 1- \ Маска
      TRUE 20 I - 0 DO OVER n I RSHIFT AND UMIN LOOP \ Мин.последовательность длины I+1
      BEGIN
        I SEQUENCE TRUE
        20 I - 0 DO
          n I RSHIFT 2OVER -ROT AND TUCK U<
          IF UMIN ELSE DROP THEN
        LOOP NIP DUP TRUE =
      UNTIL 2DROP
    LOOP ПРОХОД?
  UNTIL
;

SEQ BYE
101 24
10101 24
Сообщение Добавлено: Вс июл 31, 2011 14:53
  Заголовок сообщения:  Re: поиск последовательностей битов в ячеке  Ответить с цитатой
Ethereal писал(а):
Тогда останутся последовательности длиной меньше 32-х. Их можно снабдить ведущим незначащим единичным битом.

Ага, старший 1бит ограничивает длину последовательности.
Кстати, чтобы решить задачу по исходному заданию, надо вывести только разные последовательности, у которых характеристика равна максимальной. Пока это не сделано.
А так за 15 мксек (если TYPE отключить) все выводится.
Сообщение Добавлено: Сб июл 30, 2011 22:14
  Заголовок сообщения:  Re: поиск последовательностей битов в ячеке  Ответить с цитатой
chess писал(а):
Появилось замечание по поводу последовательностей из единиц и нулей.
Хотя последовательность вроде является числом, но оказалось что это не так.
Последовательность не сводится к одному числу. Она сводится к двум числам.
Первое число это количественная характеристика последовательности.
Например последовательность 0101 сводится к числу 101. Последовательность 101 сводится к тому же числу 101.
Но последовательности разные. Второе число для последовательности длина( можно еще взять количество начальных нулей что
будет короче).
То есть 0101 это 101 100 в виде чисел, а 101 это 101 11. То есть для хранения последовательности нужны две ячейки.
Не совсем так.
Последовательность длиной 32 бита всего одна и её характеристика равна числу единичных бит в ячейке. Эту последовательность можно обработать первым делом, сначала и отдельно, чтобы задать начальное значение для поиска максимальной характеристики. Тогда останутся последовательности длиной меньше 32-х. Их можно снабдить ведущим незначащим единичным битом. Тогда
0.) Можно будет последовательность хранить в одной ячейке.
1.) Более длинные последовательности всегда будут численно больше более коротких.
2.) Выводить последовательность лежащую на стеке можно как
2 BASE ! 0 <# #S #> 1- SWAP CHAR+ SWAP TYPE
Сообщение Добавлено: Сб июл 30, 2011 18:00
  Заголовок сообщения:  Re: поиск последовательностей битов в ячеке  Ответить с цитатой
Как всегда всё на стеке, кроме пресловутой ячейки.
Последовательности некоторой длины, взятые из ячейки, по своему значению сортируются по такому принципу :
К верхушке стека благодаря UMIN прилипает наименьшая последовательность, большая той, что под вершиной стека. Прилипшая последовательность обрабатывается словом SEQUENCE, проваливается под вершину стека и все начинается с начала. В итоге разные последовательности обрабатываются строго в порядке возрастания (реализована сортировка).
Код:
HEX 55AA55AA VALUE n \ Пресловутая ячейка

: SEQUENCE ( mask seq i -- mask seq ) \ Вывод данных о последовательности
  >R 2 BASE !
  DUP 0 <# R@ TRUE DO # LOOP #> TYPE SPACE DECIMAL \ Вывод последовательности
  0 20 R> - 0 DO n I RSHIFT 2OVER -ROT AND = - LOOP >R \ Число повторений >R
  0 OVER BEGIN DUP >R 0< - R> 2* ?DUP 0= UNTIL \ Число единичных бит
  R> * . CR \ Перемножить Число_повторений на Число_единичных_бит и вывести
;
: SEQ ( -- )
  20 0 DO
    1 I LSHIFT 2* 1- \ Маска
    TRUE 20 I - 0 DO OVER n I RSHIFT AND UMIN LOOP \ Минимальная последовательность длины I+1
    BEGIN
      I SEQUENCE TRUE
      20 I - 0 DO
        n I RSHIFT 2OVER -ROT AND TUCK U<
        IF UMIN ELSE DROP THEN
      LOOP NIP DUP TRUE =
    UNTIL 2DROP
  LOOP
;

SEQ BYE
0 0
1 16
00 0
01 14
10 14
11 4
001 1
010 12
011 4
100 1
101 24
110 4
0010 1
0100 1
0101 20
0110 4
1001 2
1010 20
1011 6
1101 6
00101 2
01001 2
01010 16
01011 6
01101 6
10010 2
10100 2
10101 24
10110 6
11010 6
001010 2
010010 2
010100 2
010101 18
010110 6
011010 6
100101 3
101001 3
101010 18
101011 8
101101 8
110101 8
...
01010101101010100101010110101 15
01010110101010010101011010101 15
10101011010101001010101101010 15
10101101010100101010110101010 15
010101011010101001010101101010 15
010101101010100101010110101010 15
101010110101010010101011010101 16
0101010110101010010101011010101 16
1010101101010100101010110101010 16
01010101101010100101010110101010 16
Сообщение Добавлено: Сб июл 30, 2011 14:29
  Заголовок сообщения:  Re: поиск последовательностей битов в ячеке  Ответить с цитатой
WingLion писал(а):
По порядку величины я даже не соврал...

Ну вы прямо как на экзамене. :)
Сообщение Добавлено: Пт июл 29, 2011 22:07
  Заголовок сообщения:  Re: поиск последовательностей битов в ячеке  Ответить с цитатой
chess писал(а):
Вам сказали что максимум не 32К, а меньше. Я дал точное значение максимума (16896 ).


По порядку величины я даже не соврал...
Сообщение Добавлено: Пт июл 29, 2011 21:40
  Заголовок сообщения:  Re: поиск последовательностей битов в ячеке  Ответить с цитатой
chess писал(а):
Взято всего лишь по максимуму...

Вам сказали что максимум не 32К, а меньше. Я дал точное значение максимума (16896 ).
Сообщение Добавлено: Пт июл 29, 2011 20:59
  Заголовок сообщения:  Re: поиск последовательностей битов в ячеке  Ответить с цитатой
вопрос писал(а):
Это ещё почему? если маска шире 1 бита то она не может быть 32 раза, а 32 - ширина


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

Ясен пень, что не все смещения маски/битов должны обсчитываться
Сообщение Добавлено: Пт июл 29, 2011 20:55
  Заголовок сообщения:  Re: поиск последовательностей битов в ячеке  Ответить с цитатой
WingLion писал(а):
32 маски x 32 положения маски x 32 проверки

на самом деле 1 32 + 32 * 2/ 32 * ( 16896 )
Сообщение Добавлено: Пт июл 29, 2011 20:54
  Заголовок сообщения:  Re: поиск последовательностей битов в ячеке  Ответить с цитатой
Цитата:
32 маски x 32 положения маски x 32 проверки

Это ещё почему? если маска шире 1 бита то она не может быть 32 раза, а 32 - ширина
Сообщение Добавлено: Пт июл 29, 2011 20:42
  Заголовок сообщения:  Re: поиск последовательностей битов в ячеке  Ответить с цитатой
В данном случае, как мне кажется, надо "последовательности" определять вот так:

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

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

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

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

короче, пока неясно зачем сей изврат нужен, интерса кодить и нету...
Сообщение Добавлено: Пт июл 29, 2011 20:24
  Заголовок сообщения:  Re: поиск последовательностей битов в ячеке  Ответить с цитатой
Появилось замечание по поводу последовательностей из единиц и нулей.
Хотя последовательность вроде является числом, но оказалось что это не так.
Последовательность не сводится к одному числу. Она сводится к двум числам.
Первое число это количественная характеристика последовательности.
Например последовательность 0101 сводится к числу 101. Последовательность 101 сводится к тому же числу 101.
Но последовательности разные. Второе число для последовательности длина( можно еще взять количество начальных нулей что
будет короче).
То есть 0101 это 101 100 в виде чисел, а 101 это 101 11. То есть для хранения последовательности нужны две ячейки.
Название 'последовательность' неудобное. Возможно существует какой-то другой термин для последовательностей, но я что-то его
не обнаружил.
Сообщение Добавлено: Пт июл 29, 2011 16:37
  Заголовок сообщения:  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. А то меня уже сомнение посетило насчет способов сжатия информации без потерь.
А про самое главное то я и забыл - за основу сжатия берется структура самой исходной информации.
Сообщение Добавлено: Чт июл 28, 2011 15:28
  Заголовок сообщения:  Re: поиск последовательностей битов в ячеке  Ответить с цитатой
Поскольку необходимы повторяющиеся последовательности, из самого 4-байта достаточно брать повторяющиеся. Нужно, видимо, манипулировать исключающим ИЛИ

Сдвигая ячейку, сравнивать её побитно с собственной копией (несдвинутой)
Сообщение Добавлено: Чт июл 28, 2011 14:46
  Заголовок сообщения:  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 13:03

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


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