Forth и другие саморасширяющиеся системы программирования Locations of visitors to this page
Текущее время: Пт мар 29, 2024 01:56

...
Google Search
Forth-FAQ Spy Grafic

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




Начать новую тему Ответить на тему  [ Сообщений: 37 ]  На страницу Пред.  1, 2, 3  След.
Автор Сообщение
 Заголовок сообщения: Re: Найти экономную заготовку для ключа.
СообщениеДобавлено: Ср авг 24, 2011 20:42 
Не в сети
Аватара пользователя

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

Можно запускать с помощью
http://file.qip.ru/file/BABQMAcN/spf419mals1.html
Только надо сначала сделать набор замков и..
nOpkl ( l k d -- n )
где, l - адрес конкретного замка, k - адрес ключа , d - длина ключа в ячейках(4 байта), n - число операций

ps. Это же не вся программа, а только фрагмент.

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


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

Зарегистрирован: Ср фев 23, 2011 20:42
Сообщения: 600
Откуда: Карелия
Благодарил (а): 3 раз.
Поблагодарили: 24 раз.
В свете сделанных (вопросом) выше замечаний, моё решение, приведенное ещё выше, неверно.


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

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2168
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 41 раз.
Решение полным перебором с предварительной генерацией исходных данных (набора замков)
Код:
REQUIRE CHOOSE LIB\EXT\RND.F
M: CLOOP 4 +LOOP ;
: optkey ( hl dl nl -- ok dl ) nl! 4 * dl! hl! \ максимальная высота зубцов, количество позиций зубцов в ключе, количество замков
  ha( ALLOCATE THROW ) hf( FREE THROW ) 40 ha bgc! ( буфер в хипе для адресов массивов в хипе ) 0 na! ( счетчик адресов массивов в хипе )
  gd( dl * ha DUP bgc na + ! na 4 + is na )  gc( na 0 DO bgc I + @ hf CLOOP bgc hf )                   \ процедуры выделения и освобождения памяти в хипе
  nl gd l!   dl nl * 0 DO hl CHOOSE 1+ I l + ! CLOOP                                                   \ генерация набора замков
   1 gd bk!  dl 0 DO 255 nl 0 DO l I dl * + J + @ MIN LOOP I bk + ! CLOOP                              \ определение начального ключа
   1 gd ek!  dl 0 DO   0 nl 0 DO l I dl * + J + @ MAX LOOP I ek + ! CLOOP                              \ определение конечного ключа
   1 gd tk!  1 gd ok!  1 gd tl! 1 gd sk!  wa( dl MOVE )  bk tk wa  bk ok wa bk sk wa 0 c!              \ установка начальных значений текущего ключа
  nextkey( 0 is c dl 0 DO I 0= IF tk @ ek @ = IF bk @ tk ! 1 is c ELSE tk 1+! 0 is c LEAVE THEN        \ формирование следующего ключа по текущему
  ELSE c IF I tk + @ I ek + @ = IF I bk + @ I tk + ! 1 is c ELSE I tk + 1+! 0 is c THEN ELSE LEAVE THEN THEN CLOOP tk sk wa )
  0 ng! 0 n1! 0 no! 0x7FFFFFFF nm! 0 n!                                     \ начальные значения числа групповых и одиночных операций
  gop( dl 0 DO I tl + @ I sk + @ - is n n 0 > IF n ng MAX is ng THEN CLOOP dl 0 DO ng I sk + +! CLOOP  \ число операций для пары замок-ключ
       dl 0 DO I sk + @ I tl + @ - 0 > IF n1 1+ is n1 THEN CLOOP ng n1 + no + is no )
  ar=( tk dl ek dl COMPARE 0= )                                                                        \ сравнение текущего ключа с конечным ключом
  BEGIN nl 0 DO l I dl * + tl wa 0. is n1 is ng gop LOOP no nm < IF no is nm tk ok wa THEN 0 is no nextkey ar= UNTIL  \ поиск оптимального ключа
  locks.( nl 0 DO dl 0 DO l I + J dl * + @ . CLOOP CR LOOP CR ) ok.( dl 0 DO I ok + @ . CLOOP CR )     \ процедуры вывода набора замков
CR locks. nm . CR CR ok.                             \ вывод набора замков, общего числа операций для оптимальной заготовки ключа и самой заготовки
gc ;                                                 \ сбор мусора - освобождение памяти в хипе

STARTLOG 8 8 6 optkey

пример лога
Код:
3 4 6 2 3 7 8 6
5 4 8 2 6 4 8 7
5 4 3 2 6 6 1 5
4 6 8 2 2 3 3 6
2 8 1 8 3 1 6 5
3 4 4 7 7 4 5 3

36

5 7 8 7 6 7 8 7

Ok
ps.
ограничения реализации:
1. число перебираемых ключей ограничено ячейкой.
2. выводится только один лучший ключ, но их может быть и больше.

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


Последний раз редактировалось chess Пт сен 02, 2011 16:38, всего редактировалось 6 раз(а).

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

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

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


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

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

Был неправ. Нашел ошибку при сравнении текущего и конечного ключа.
Исправления внес в пост с решением.

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


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

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

Был неправ. Нашел ошибку при сравнении текущего и конечного ключа.
Исправления внес в пост с решением.

Я уже собирался постить следующую, действительно заковыристую задачку про ключ :D
Подождём решение Ethereal


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

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

Размещайте, можно и не ждать. Я если и решу, то пока постить не буду.
Кстати, о старой задаче.
Модифицировал решение об оптимальной заготовке ключа на предмет автосборки мусора.
В хипе заводится массив, в который по мере выделения памяти (по ходу программы) для массивов в хипе
укладываются адреса этих массивов, а их число считается в переменной-счетчике.
По окончании программы память по адресам в буфере освобождается и освобождается сам буфер.
Решение выложено в первый пост вместо предыдущего решения.

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


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

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

Рассмотрим варианты задачи о ключе.
В качестве вариантов условия задачи могут быть приняты различные сочетание вариантов операции удаления зубцов ключа и вариантов операции наращивания зубцов ключа.
Код:
                                   удаление    наращивание
одиночное в каждой позиции        уо-  уо+       но-   но+           
групповое во всех позициях        уг-  уг+       нг-   нг+
для групповых операций можно еще ввести кратность
для каждой разновидности операций можно ввести вес(в исходной задаче он равен 1)
ну, впрочем, можно еще дорабатывать ключ по длине :)

Минимальный набор понятий, необходимых для решения(тезаурус или по фортовски лексикон ) для всех возможных условий практически не расширится.
Решение в каждом случае будет получено перебором той или иной сложности.
Общее решение для всех вариантов может быть также получено, но оно будет проигрывать по эффективности частным решениям
и займет больше времени на программирование( форт подход, как и должно быть, тут рулит)
Где тут может появиться особая заковыристость?

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


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

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2168
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 41 раз.
Чтобы стал более понятен предыдущий пост приведено еще решение когда разрешены только операции
укорочения и доращивания в каждой позиции ключа на произвольное количество.
Тут используется общий лексикон и только переопределяются нужные части функционала решения.
Код:
REQUIRE CHOOSE LIB\EXT\RND.F
M: CLOOP 4 +LOOP ;
: gen-locks ( hl dl nl -- l dl nl 'gd 'gc ) nl! 4 * dl! hl!
  ha( ALLOCATE THROW ) hf( FREE THROW ) 40 ha bgc! 0 na!
  gd( dl * ha DUP bgc na + ! na 4 + is na )  gc( na 0 DO bgc I + @ hf CLOOP bgc hf )
  nl gd l!   dl nl * 0 DO hl CHOOSE 1+ I l + ! CLOOP
  l dl nl l' gd l' gc ;

: tesaurus-optkey ( l dl nl 'gd 'gc -- l dl nl bk ek tk ok tl sk 'gc 'wa 'nextkey 't=e '.locks '.ok  ) gc! gd! nl! dl! l!
   e( EXECUTE )
   1 gd e bk!  dl 0 DO 255 nl 0 DO l I dl * + J + @ MIN LOOP I bk + ! CLOOP
   1 gd e ek!  dl 0 DO   0 nl 0 DO l I dl * + J + @ MAX LOOP I ek + ! CLOOP
   1 gd e tk!  1 gd e ok!  1 gd e tl! 1 gd e sk! 0 c! wa( dl MOVE ) bk tk wa bk ok wa ek sk wa
  nextkey( 0 is c dl 0 DO I 0= IF tk @ ek @ = IF bk @ tk ! 1 is c ELSE tk 1+! 0 is c LEAVE THEN
  ELSE c IF I tk + @ I ek + @ = IF I bk + @ I tk + ! 1 is c ELSE I tk + 1+! 0 is c THEN ELSE LEAVE THEN THEN CLOOP tk sk wa )
  t=e( tk dl ek dl COMPARE 0= )
  .locks( nl 0 DO dl 0 DO l I + J dl * + @ . CLOOP CR LOOP CR ) .ok( dl 0 DO I ok + @ . CLOOP CR )
  l dl nl bk ek tk ok tl sk gc l' wa l' nextkey l' t=e l' .locks l' .ok  ;

: optkey_g+o- ( l dl nl bk ek tk ok tl sk 'gc 'wa 'nextkey 't=e '.locks '.ok -- ok dl )
  .ok! .locks! t=e! nextkey! wa! gc! sk! tl! ok! tk! ek! bk! nl! dl! l!
  e( EXECUTE )
  0 ng! 0 n1! 0 no! 0x7FFFFFFF nm! 0 n!
  gop( dl 0 DO I tl + @ I sk + @ - is n n 0 > IF n ng MAX is ng THEN CLOOP dl 0 DO ng I sk + +! CLOOP
       dl 0 DO I sk + @ I tl + @ - 0 > IF n1 1+ is n1 THEN CLOOP ng n1 + no + is no )
  BEGIN nl 0 DO l I dl * + tl wa e 0. is n1 is ng gop LOOP no nm < IF no is nm tk ok wa e THEN 0 is no nextkey e t=e e UNTIL
  CR .locks e nm . CR CR .ok e CR ;

: optkey_o+o- ( l dl nl bk ek tk ok tl sk 'gc 'wa 'nextkey 't=e '.locks '.ok -- ok dl )
  .ok! .locks! t=e! nextkey! wa! gc! sk! tl! ok! tk! ek! bk! nl! dl! l!
  e( EXECUTE )
  0 n1! 0 no! 0x7FFFFFFF nm!
  gop( dl 0 DO I tk + @ I tl + @ <> IF n1 1+ is n1 THEN CLOOP n1 no + is no )
  BEGIN nl 0 DO l I dl * + tl wa e 0 is n1 gop LOOP no nm < IF no is nm tk ok wa e THEN 0 is no nextkey e t=e e UNTIL
  CR .locks e nm . CR CR .ok e CR gc e ;
: SPDUP ( p*n n -- p*n p*n)                                         \ дублировать параметры на стеке
  DEPTH CELLS >R SP@ DUP R@ - R@ CMOVE> SP@ R> - SP! ;

STARTLOG
8 8 6 gen-locks
tesaurus-optkey SPDUP
optkey_g+o-     \ разрешены групповое доращивание и одинарное укорочение
optkey_o+o-     \ разрешены одинарное доращивание и одинарное укорочение

пример лога
Код:
8 2 6 3 2 1 7 6
6 7 2 6 1 5 7 1
7 8 2 6 3 3 7 4
4 3 1 8 1 8 3 1
2 1 5 8 8 2 8 4
4 3 2 5 2 6 5 8

36

8 8 6 6 6 6 7 6


8 2 6 3 2 1 7 6
6 7 2 6 1 5 7 1
7 8 2 6 3 3 7 4
4 3 1 8 1 8 3 1
2 1 5 8 8 2 8 4
4 3 2 5 2 6 5 8

31

4 3 2 6 1 1 7 1


Ok

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


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

Зарегистрирован: Вт май 09, 2006 12:31
Сообщения: 3438
Благодарил (а): 5 раз.
Поблагодарили: 16 раз.
Да, неплохо.
Из этого можно сделать часть оптимизатора :) :wink:


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

Зарегистрирован: Вт май 02, 2006 22:48
Сообщения: 7960
Благодарил (а): 25 раз.
Поблагодарили: 144 раз.
вопрос писал(а):
Из этого можно сделать часть оптимизатора

Ага. И примонтировать хэш не забываем :))


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

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


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

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

Там будет другой тезаурус, сильно зависящий от архитектуры целевого и виртуального процессора и типа базовых кодовых конструкций(например, х86, вирт. форт-машина, и например, процедурный тип кодовых структур).

Вообще переборно-поисковые задачи это всегда задачи нахождения оптимальных результатов.
Такие задачи - типовые. Только на практике все гораздо сложнее и масштабнее. Поэтому задача
повышения производительности решений встает в полный рост. По большому счету это задача номер один в конкурентном плане на самом верхнем уровне. Основной упор здесь не оптимизация трансляторов и даже не производительность железа, а оптимизация алгоритмов, а уже потом производительность железа, и в наконец, последнюю очередь, уже оптимизация транслятора.

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


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

Зарегистрирован: Вт май 02, 2006 22:48
Сообщения: 7960
Благодарил (а): 25 раз.
Поблагодарили: 144 раз.
вопрос писал(а):
А присмотреться?

Вопрос несложный. Сколько потрачено времени на технологию? Какой выигрыш она может дать? Сопоставление этих величин и позволяет классифицировать ее либо как серьезную работу, либо как хобби/игру ума.


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Найти экономную заготовку для ключа.
СообщениеДобавлено: Вт сен 06, 2011 00:56 
Не в сети

Зарегистрирован: Вт май 09, 2006 12:31
Сообщения: 3438
Благодарил (а): 5 раз.
Поблагодарили: 16 раз.
Хищник писал(а):
Сопоставление этих величин и позволяет классифицировать ее либо как серьезную работу, либо как хобби/игру ума.

viewtopic.php?f=33&t=2293


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

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


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

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


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

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