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

...
Google Search
Forth-FAQ Spy Grafic

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




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

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

Обзор темы - Найти экономную заготовку для ключа.
Автор Сообщение
  Заголовок сообщения:  Re: Найти экономную заготовку для ключа.  Ответить с цитатой
Хищник писал(а):
Только вот ценой чего достигается второстепенное улучшение? Ценой синтаксиса вида:

Код:
I1l!|\l/|

Лекарство часом не тяжелее болезни получилось?


Да нет. Стековые манипуляторы тут я не применял.
Стековые манипуляторы это технологический прием, который использует другой ресурс программиста - 'видеобуфер'. Идея видеобуфера 'взята' из языка J.
Общеизвестная статистика о том, что в среднем процедуры содержат 6 параметров. Ну я на всякий случай увеличил это число до 9.
Код:
: proc ( n1 n2 n3 n4 -- 0|1) 2swap + over * swap -  > ;   
эквивалентно
Код:
: proc ( n1 n2 n3 n4 -- 0|1)  4\412+4*3-> ;
66 10 20 30 40 proc   Ok ( 66 0 )
Здесь видеобуфер это строящаяся строчка 4\412+4*3->
Применять соответсвенно нужно по случаю. Ничего в этом сложного нет. Прямой доступ к параметрам на стеке, которые укладываются в 'видеобуфер' и процесс этот тоже не использует объем внимания.
Сообщение Добавлено: Вт сен 06, 2011 16:20
  Заголовок сообщения:  Re: Найти экономную заготовку для ключа.  Ответить с цитатой
chess писал(а):
Так и я о том же. Есть ресурсы компьютера и есть ресурсы программиста. Эти ресурсы программиста надо использовать максимально. Идея локального именования позволяет эффективнее использовать такой ресурс программиста как объем оперативного внимания путем исключения оттуда всего, что непосредственно не относится к задаче. Лишним в данном случае является контекст стековых манипуляций, который присущ классическому форту.

Только вот ценой чего достигается второстепенное улучшение? Ценой синтаксиса вида:
Код:
I1l!|\l/|

Лекарство часом не тяжелее болезни получилось?
Сообщение Добавлено: Вт сен 06, 2011 15:44
  Заголовок сообщения:  Re: Найти экономную заготовку для ключа.  Ответить с цитатой
Хищник писал(а):
Вот тут я склоняюсь к необходимости очень осторожных рассуждений. Программы пишутся людьми. А в ходе прогресса вычислительных средств их возможности существенно возросли, а стоимость уменьшилась. Тогда как средняя зарплата программиста выросла. В итоге "бутылочное горлышко" при разработке программ неуклонно перемещается от максимально плотного использования ресурсов компьютера к максимально эффективной организации труда программиста. Хотя бы потому, что затраты на зарплату программиста, тщательно следящего за байтами и тактами, существенно больше стоимости этих самых байтов и тактов.

Так и я о том же. Есть ресурсы компьютера и есть ресурсы программиста. Эти ресурсы программиста надо использовать максимально. Идея локального именования позволяет эффективнее использовать такой ресурс программиста как объем оперативного внимания путем исключения оттуда всего, что непосредственно не относится к задаче. Лишним в данном случае является контекст стековых манипуляций, который присущ классическому форту.
Сообщение Добавлено: Вт сен 06, 2011 15:09
  Заголовок сообщения:  Re: Найти экономную заготовку для ключа.  Ответить с цитатой
chess писал(а):
Хищник писал(а):
А от такого кода у меня попросту в глазах рябит.

Отнесем это к субъективным впечатлениям.

Естественно.
chess писал(а):
Читабельность фактор наименьшей важности. Важна не читабельность, а корректный результат решения, который опирается на прозрачность перехода от алгоритма к его выражению в тексте программы.

Вот тут я склоняюсь к необходимости очень осторожных рассуждений. Программы пишутся людьми. А в ходе прогресса вычислительных средств их возможности существенно возросли, а стоимость уменьшилась. Тогда как средняя зарплата программиста выросла. В итоге "бутылочное горлышко" при разработке программ неуклонно перемещается от максимально плотного использования ресурсов компьютера к максимально эффективной организации труда программиста. Хотя бы потому, что затраты на зарплату программиста, тщательно следящего за байтами и тактами, существенно больше стоимости этих самых байтов и тактов.
Сообщение Добавлено: Вт сен 06, 2011 14:54
  Заголовок сообщения:  Re: Найти экономную заготовку для ключа.  Ответить с цитатой
Хищник писал(а):
Я отвечал на вопрос "не сделать ли это частью оптимизатора".

Теперь понятно.
Хищник писал(а):
Впрочем, если уж говорить о локальном именовании, то для определения затрат можно посмотреть на количество сообщений в обсуждении. Это явно не два-три дня.

Я беру мое суммарное время работы. Кроме того я выкладываю тексты реализации преследуя несколько целей:
1. Получить реакцию от форумчан на идею и скорректировать ее реализацию по их резонным замечаниям.
2. Показать как конкретную идею можно реализовать. Это может для начинающих быть полезным.
3. Показать работу реализованной идеи на примерах решения конкретных задач.
Хищник писал(а):
А от такого кода у меня попросту в глазах рябит.

Отнесем это к субъективным впечатлениям.
Хищник писал(а):
Выигрыш не в наборе кода, а во времени отладки.

Набор текста и время отладки тесно связанные понятия. От того какой текст напрямую зависит и время отладки.
При решении данной задачи время отладки было сведено к почти нулю.
Хищник писал(а):
А здесь читабельность и адаптация к предпочтениям конкретного разработчика существенно важнее возможности упихнуть в одну строчку побольше действий.

Читабельность фактор наименьшей важности. Важна не читабельность, а корректный результат решения, который опирается на прозрачность перехода от алгоритма к его выражению в тексте программы.
Вот как иллюстрация к последнему утверждению еще один вариант решения задачи о ключах, случай когда
разрешены операции одиночного наращивания и группового удаления(добавить к уже существующему тексту):
Код:
: 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 tk + @ I tl + @ - is n n 0 > IF n ng MAX is ng THEN CLOOP
       dl 0 DO I tl + @ I tk + @ - 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 gc e ;

STARTLOG
8 8 6 gen-locks
tesaurus-optkey SPDUP
optkey_g+o-     SPDUP
optkey_o+o-
optkey_g-o+

ps. Отладка свелась к двум пускам программы.
Сообщение Добавлено: Вт сен 06, 2011 14:33
  Заголовок сообщения:  Re: Найти экономную заготовку для ключа.  Ответить с цитатой
Я отвечал на вопрос "не сделать ли это частью оптимизатора". Впрочем, если уж говорить о локальном именовании, то для определения затрат можно посмотреть на количество сообщений в обсуждении. Это явно не два-три дня. А от такого кода у меня попросту в глазах рябит. Выигрыш не в наборе кода, а во времени отладки. А здесь читабельность и адаптация к предпочтениям конкретного разработчика существенно важнее возможности упихнуть в одну строчку побольше действий.
Сообщение Добавлено: Вт сен 06, 2011 13:25
  Заголовок сообщения:  Re: Найти экономную заготовку для ключа.  Ответить с цитатой
Хищник писал(а):
Вопрос несложный. Сколько потрачено времени на технологию? Какой выигрыш она может дать? Сопоставление этих величин и позволяет классифицировать ее либо как серьезную работу, либо как хобби/игру ума.

1. Какую технологию? Наверное это технология локального именования. Любая технология может быть расширена или наоборот специфицирована взависимости от задач.
2. Времени на что? Наверное на реализацию и ее доводку и возможные затраты на расширение и специализацию. (два-три дня).
3. Выигрыш в чем? Наверное это выигрыш во времени программирования по сравнению с временем программирования без использования локального именования. Сильно зависит от сложности задач. Чем сложнее задачи, тем выигрыш больше.
Цель, по которой я ввел это расширение, это удаление оперативного контекста из объема внимания за счет исключения манипуляций на стеке, которые и создают этот самый контекст.
Серьезная\несерьезная, игра\не игра - это не существенно, это как рекламный ярлык к вещи.
Сообщение Добавлено: Вт сен 06, 2011 10:03
  Заголовок сообщения:  Re: Найти экономную заготовку для ключа.  Ответить с цитатой
Хищник писал(а):
Сопоставление этих величин и позволяет классифицировать ее либо как серьезную работу, либо как хобби/игру ума.

viewtopic.php?f=33&t=2293
Сообщение Добавлено: Вт сен 06, 2011 00:56
  Заголовок сообщения:  Re: Найти экономную заготовку для ключа.  Ответить с цитатой
вопрос писал(а):
А присмотреться?

Вопрос несложный. Сколько потрачено времени на технологию? Какой выигрыш она может дать? Сопоставление этих величин и позволяет классифицировать ее либо как серьезную работу, либо как хобби/игру ума.
Сообщение Добавлено: Пн сен 05, 2011 23:45
  Заголовок сообщения:  Re: Найти экономную заготовку для ключа.  Ответить с цитатой
chess писал(а):
Из этого можно сделать часть оптимизатора

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

Вообще переборно-поисковые задачи это всегда задачи нахождения оптимальных результатов.
Такие задачи - типовые. Только на практике все гораздо сложнее и масштабнее. Поэтому задача
повышения производительности решений встает в полный рост. По большому счету это задача номер один в конкурентном плане на самом верхнем уровне. Основной упор здесь не оптимизация трансляторов и даже не производительность железа, а оптимизация алгоритмов, а уже потом производительность железа, и в наконец, последнюю очередь, уже оптимизация транслятора.
Сообщение Добавлено: Пн сен 05, 2011 22:10
  Заголовок сообщения:  Re: Найти экономную заготовку для ключа.  Ответить с цитатой
А присмотреться?
Сообщение Добавлено: Пн сен 05, 2011 21:30
  Заголовок сообщения:  Re: Найти экономную заготовку для ключа.  Ответить с цитатой
вопрос писал(а):
Из этого можно сделать часть оптимизатора

Ага. И примонтировать хэш не забываем :))
Сообщение Добавлено: Пн сен 05, 2011 20:35
  Заголовок сообщения:  Re: Найти экономную заготовку для ключа.  Ответить с цитатой
Да, неплохо.
Из этого можно сделать часть оптимизатора :) :wink:
Сообщение Добавлено: Пн сен 05, 2011 16:18
  Заголовок сообщения:  Re: Найти экономную заготовку для ключа.  Ответить с цитатой
Чтобы стал более понятен предыдущий пост приведено еще решение когда разрешены только операции
укорочения и доращивания в каждой позиции ключа на произвольное количество.
Тут используется общий лексикон и только переопределяются нужные части функционала решения.
Код:
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
Сообщение Добавлено: Пн сен 05, 2011 15:31
  Заголовок сообщения:  Re: Найти экономную заготовку для ключа.  Ответить с цитатой
вопрос писал(а):
Я уже собирался постить следующую, действительно заковыристую задачку про ключ

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

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

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


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