расширенные операторами стековые манипуляторы

Hishnik

Antender писал(а):

А в форте нет стандартной функции sort - вообще нету станщартной библиотеки, а почему?

Разве есть какие-то проблемы в написании : sort ... и т.д.?

Antender писал(а):

Когда я например говорю руби, я подразумеваю С Ruby за автороством Матцумото и ничто иное.

Замечательно. Теперь надо ждать, пока гуру Ruby решат сделать еще что-то?

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

Ethereal

Код:

\ Сортируются len>0 произвольных элементов с индексами 0..(len-1)
\ Требуется дополнительный карман для хранения одного сортируемого элемента
VECT @PUSH \ ( i -- ) \ Засунуть i-й сортируемый элемент в карман
VECT @PULL \ ( i -- ) \ Выложить содержимое кармана в i-й сортируемый элемент
VECT @COPY \ ( i j -- ) \ Скопировать j-й сортируемый элемент в i-й
VECT @LESS \ ( i -- flag ) \ Сравнить то, что в кармане с i-м сортируемым элементом,
\ вернуть TRUE если содержимое кармана меньше и FALSE в противном случае

CREATE GAP 9 C, 5 C, 3 C, 2 C, 1 C,
: SORT ( +len -- ) \ Алгоритм сортировки Шелла
  5 0 DO
    GAP I + C@ 2DUP >
    IF
      2DUP DO
        I @PUSH
        I OVER -
        BEGIN
          DUP @LESS
        WHILE
          2DUP + OVER @COPY
          OVER -
          DUP 0<
        UNTIL THEN
        OVER + @PULL
      LOOP
    THEN DROP
  LOOP DROP
;

chess

Ethereal писал(а):

CREATE GAP 9 C, 5 C, 3 C, 2 C, 1 C,

Вот кстати если учесть что сортируются числа все разные и в пределах байта, то сортировка может быть реализована гораздо проще и работать будет гораздо быстрее:

Код:

CREATE GAP 9 C, 5 C, 3 C, 2 C, 1 C,
: SORT ( +len -- ) len! 256 arr] arr 256 ERASE 0 cnt!
  GAP len + GAP DO I C@ arr + 1+! LOOP
  arr 256 + arr DO I C@ 0<> IF I arr - GAP cnt + C! cnt 1+ is cnt THEN LOOP ;

\EOF
5 SORT GAP 5 DUMP

PS. Исходное сообщение переросло в обсуждение еще и других языков, это нормально. Но речь в первую очередь о форте.
Форт-текст состоит из лексем-токенов. Транслятор собственно заточен на их обработку. Предложено расширить форт на предмет
расширения понятия токена. Токен может быть не только именем слова, именем числа, строкой но и комбинатором. Имена чисел, кстати, это тоже комбинаторы определенного вида и обрабатываются отдельным локальным транслятором. Стековые манипуляторы тоже обрабатываются отдельным локальным транслятором. Точка входа во все локальные трансляторы это NOTFOUND в теле основного транслятора INTERPRET.

вопрос

chess писал(а):

Код:

CREATE GAP 9 C, 5 C, 3 C, 2 C, 1 C,
: SORT ( +len -- ) len! 256 arr] arr 256 ERASE 0 cnt!
  GAP len + GAP DO I C@ arr + 1+! LOOP
  arr 256 + arr DO I C@ 0<> IF I arr - GAP cnt + C! cnt 1+ is cnt THEN LOOP ;

\EOF
5 SORT GAP 5 DUMP

нечитаемый текст

chess

вопрос писал(а):

нечитаемый текст

Так пойдет?

Код:

CREATE GAP 9 C, 5 C, 3 C, 2 C, 1 C,
\ упрощенный вариант реализации алгоритма RAM-сортировки байтов в массиве(байты все разные)
: SORT ( +len -- ) len!  \ создать переменную типа VALUE c лок. именем len ( длина массива GAP ) при исполнении SORT записать в нее значение со стека
  256 arr]          \ создать стат. массив размером в 256 байт с лок. именем arr
  arr 256 ERASE     \ обнулить его содержимое
  0 cnt!            \ создать переменную типа VALUE c лок. именем cnt ( счетчик числа байтов ) и обнулить ее
  GAP len + GAP     \ верхний и нижний индексы для цикла DO LOOP по массиву GAP
  DO
     I C@ arr + 1+! \ увеличить содержимое байта в массиве arr по смещению равному содержимому байта в массиве GAP
  LOOP
  arr 256 + arr     \ верхний и нижний индексы для цикла DO LOOP по массиву arr
  DO
     I C@ 0<>       \ проверка очередного байта массива arr на ненуль
     IF
        I arr - GAP cnt + C!  \ записать текущее смещение смещение адреса в массиве arr по текущему смещению адреса для массива GAP
        cnt 1+ is cnt         \ увеличить смещение для массива GAP
     THEN
  LOOP ;

\ EOF
5 SORT GAP 5 DUMP \ распечатать содержимое отсортированного массива GAP

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

Antender

Есть предложение написать для форта коллекции.
А по поводу сортировки - дело не в том, что я не могу её написать, дело в том,, что я не буду писать её заново каждый раз когда она мне понадобится. И никто не будет.
Например, у spf штук 8 реализаций строк от каждого разработчика, но зачем?

chess

Antender писал(а):

Есть предложение написать для форта коллекции.
А по поводу сортировки - дело не в том, что я не могу её написать, дело в том,, что я не буду писать её заново каждый раз когда она мне понадобится. И никто не будет.

Вы за деревьями не видите леса.
Вот математика. Она развивается уже тысячи лет.
Есть конкретная предметная область. Есть ли гарантия, что математики хватит для ее
описания, для создания практически эффективной математической модели этой области.
Как это ни странно такой гарантии в общем случае нет.
Что уж говорить о программировании, которому практически не больше сотни лет.
Основная идея форта вытекает именно из констатации того факта, что действительность гораздо
сложнее любых абстрактных представлений о ней. Чтобы реально работать в конкретной области надо сначала
изучить эту предметную область, создать модель этой области на основе минимума конкретных понятий,
которые тем не менее во всей полноте отражают сложность данной области. Если же подойти к этому на основе
общих абстрактных представлений, то сложность представления будет на порядки выше, то есть образуется излишняя сложность.
Как следствие, вероятность получения практически эффективных решений будет изначально ниже.
Форт с прицелом на это и устроен - минимальный набор средств(ядро) для быстрого развертывания языков предметных областей.
Форт возник давно, в основном ядро у него сформировано, логика развития вытекает из его назначения, поэтому
сравнивать Форт с "узкими" языками, претендующими на звание универсальных не надо. В этом нет смысла. Цели разные.
Стремление создать действительно универсальный язык - это утопия(см. выше).
У форта есть недостатки(встроенная необязательная сложность) в основном из-за недостаточного понимания психологии программизма,
но все это достаточно легко устраняемые мелочи.
Средств ядра хватает для их устранения, т.е. для изменения самого ядра
(в части манипулирования параметрами на стеке, использования контекста и т.п.)
Насчет сортировки - написать эффективную сортировку для всех типов объектов сортировки - утопия,
это же в основном справедливо и для остальных "универсальных" решений.

Antender писал(а):

Например, у spf штук 8 реализаций строк от каждого разработчика, но зачем?

Ну наверное посчитали, что кому-нибудь это будет нужно.

Ethereal

Вы все на голову сдвинулись, что-ли ?
GAP - это не сортируемый массив.
GAP - это таблица сдвигов в алгоритме сортировки Шелла.

Я привел алгоритм, который сортирует ЧТО УГОДНО !
Байты, слова, строки, записи, массивы, элементы в списке ...
Главное вектора определите на 4 операции с сортируемыми элементами :
@PUSH @PULL @COPY @COMP и мой алгоритм все отсортирует.

Для сортировки массива ячеек, можно сделать, например так :

CREATE МАССИВ 7 , 5 , -1 , 9 , 7 , 11 , -3 , 6 , 5 , 4 ,

VARIABLE КАРМАН
: #PUSH CELLS МАССИВ + @ КАРМАН ! ;
: #PULL CELLS МАССИВ + КАРМАН @ SWAP ! ;
: #COPY CELLS МАССИВ + @ SWAP CELLS МАССИВ + ! ;
: #COMP CELLS МАССИВ + @ КАРМАН @ 2DUP < >R > R> - ;
' #PUSH TO @PUSH
' #PULL TO @PULL
' #COPY TO @COPY
' #COMP TO @COMP
10 SORT

вопрос

Цитата:

Вы все на голову сдвинулись, что-ли ?
GAP - это не сортируемый массив.
GAP - это таблица сдвигов в алгоритме

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

Ethereal

Antender писал(а):

А по поводу сортировки - дело не в том, что я не могу её написать, дело в том,, что я не буду писать её заново каждый раз когда она мне понадобится. И никто не будет.

Как это никто не будет, если оптимального алгоритма сортировки НЕТ !
Нужно выбирать алгоритм сортировки для каждого конкретного случая.
Например, быстрая сортировка быстрее сортировки Шелла.
Но прежде чем её применять надо определить хватит ли стека ибо она рекурсивная.
Т.е. оценить максимальное количество сортируемых элементов и прикинуть хватит ли
стека в худшем случае. Если стека может не хватить - надо отказываться от быстрой
сортировки и выбирать более медленную. А у алгоритма Шелла в зависимости от
количеств сортируемых данных надо выбирать константы сдвигов. Ибо на малых массивах
быстрее сортируют одни константы, а на больших другие. И по всем быстрым алгоритмам
сортировки есть такие нюансы.

Впрочем, алгоритм более менее хороший для всех случаев я выше привел.

Ethereal

вопрос писал(а):

ВОт, вот оно - отсутствие общепринятых, а лучше стандартных библиотек, Ethereal
всё показал и опроверг себя - лучше не надо.

Чем я опроверг себя ?
chess просто не сообразил, что можно нарисовать алгоритм сортировки не указанного сразу массива, а сортировки абстрактных данных вообще. И поленился прочесть мои комментарии и мой текст программы в десять строчек.

А стандартной функции сортировки для библиотеки нет и не может быть ! См. выше.
Впрочем, на безрыбье и рак рыба. Поэтому более менее хороший (но не лучший, ибо
такого нет) алгоритм, пригодный для библиотеки я нарисовал за 15 минут. См. выше.

dynamic-wind

Ethereal писал(а):

Впрочем, алгоритм более менее хороший для всех случаев я выше привел.

Время сортировки Шелла в худшем случае выше O(n·log(n)), мне хочется блевать.
+ она нестабильна.

chess

Ethereal писал(а):

chess просто не сообразил, что можно нарисовать алгоритм сортировки не указанного сразу массива, а сортировки абстрактных данных вообще. И поленился прочесть мои комментарии и мой текст программы в десять строчек.

Точно я поленился. Алгоритма Шелла не знаю ни разу.
Просто более-менее универсальный алгоритм всегда проиграет алгоритму настроенному на конкретный тип данных. Но это-то правда. Вот для разных байтов доказательство.

Код:

CREATE МАССИВ 7 C, 5 C, 1 C, 9 C, 8 C, 11 C, 3 C, 6 C, 11 C, 4 C,
CREATE GAP 9 C, 5 C, 3 C, 2 C, 1 C,
: SORT ( +len -- ) \ Алгоритм сортировки Шелла
КАРМАН)
@PUSH( МАССИВ + C@ КАРМАН C! )
@PULL( МАССИВ + КАРМАН C@ SWAP C! )
@COPY( МАССИВ + C@ SWAP МАССИВ + C! )
@COMP( МАССИВ + C@ КАРМАН C@ SWAP - )
  5 0 DO
    GAP I + C@ 2DUP >
    IF
      2DUP DO
        I @PUSH
        I OVER -
        BEGIN
          DUP @COMP 0<
        WHILE
          2DUP + OVER @COPY
          OVER -
          DUP 0<
        UNTIL THEN
        OVER + @PULL
      LOOP
    THEN DROP
  LOOP DROP
;

CREATE МАССИВ1 7 C, 5 C, 1 C, 9 C, 8 C, 11 C, 3 C, 6 C, 11 C, 4 C,
: SORT1 ( +len -- ) len! 256 arr] arr 256 ERASE 0 cnt!
  МАССИВ1 len + МАССИВ1
  DO
    I C@ arr + 1+!
  LOOP
  arr 256 + arr
  DO
    I C@ 0<> IF I arr - МАССИВ1 cnt + C! cnt 1+ is cnt THEN
  LOOP ;

: test 10 SORT ;    METER test ( 5310 тиков )
: test1 10 SORT1 ;  METER test1 (2484 тиков)

PS. А претензии Вопроса не по делу.
И я по прежнему не знаю алгоритма Шелла, но к делу это не относится.

вопрос

Цитата:

А претензии Вопроса не по делу.

для такого простого алгоритма на 15 минут - может и не по делу

Ethereal

dynamic-wind писал(а):

Ethereal писал(а):

Впрочем, алгоритм более менее хороший для всех случаев я выше привел.

Время сортировки Шелла в худшем случае выше O(n·log(n)), мне хочется блевать.
+ она нестабильна.

Так назови лучший алгоритм сортировки, удовлетворяющий двум условиям :
1.) Нерекурсивный (не жрет стек). Считаем, что стека 8 ячеек.
2.) Требует дополнительной памяти максимум на один сортируемый элемент. Т.е. сортировка должна быть на месте.
Без этих двух условий сортировка не может быть включена в библиотеку ибо иначе при большом количестве сортируемых данных ей не хватит ресурсов.

расширенные операторами стековые манипуляторы

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