Forth
http://fforum.winglion.ru/

*выборка из массива указателей
http://fforum.winglion.ru/viewtopic.php?f=19&t=2322
Страница 1 из 3

Автор:  mOleg [ Пт ноя 20, 2009 21:35 ]
Заголовок сообщения:  *выборка из массива указателей

Имеется в памяти массив указателей (адресных ссылок) фиксированной длины: arr # , длина массива задана в байтах, и кратна длине адресной ссылки. Необходимо без изменений в исходном массиве получить другой массив, содержащий только уникальные ссылки (то есть исключить все повторы из исходного). Порядок следования адресных ссылок должен быть сохранен, исключаться должны повторения, находящиеся по старшим адресам.

\ получить из исходного массива ссылок arr # другой массив, содержащий каждую из ссылок только по одному разу.
: clean ( arr # --> addr # )

;

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

Автор:  dynamic-wind [ Пт ноя 20, 2009 22:36 ]
Заголовок сообщения:  Re: выборка из массива указателей

Были бы в 4те готовые хэш-таблицы, тогда и решать нечего... :?

Автор:  VoidVolker [ Пт ноя 20, 2009 22:38 ]
Заголовок сообщения: 

Они есть в одной из соседних тем.

Автор:  VoidVolker [ Пт ноя 20, 2009 23:24 ]
Заголовок сообщения: 

Кварк/Спф:
Код:
: -ROT ROT ROT ;  \ Две строки для кварка
4 CONSTANT CELL

: clean \ ( arr # --> addr #1 )
  HERE -ROT   \ addr arr #  \ Сохраняем на стеке адрес нового массива
  OVER @ ,    \ Первая ссылка всегда уникальна - сразу сохраняем ее
  1 -ROT      \ addr 1 arr # \ Число сохраненных ссылок
  CELL - SWAP CELL + SWAP    \ Соответственно уменьшаем и число проходов цикла по массиву на один
  OVER + SWAP DO  \ addr #1
    0 2 PICK HERE SWAP DO
      I @ J @ = OR
    CELL +LOOP
      IF ELSE I @ , 1+ THEN
  CELL +LOOP
;

: test CELLS OVER + SWAP DO I @ . CELL +LOOP ;

CREATE arr 1 , 2 , 3 , 4 , 2 , 3 , 5 , 6 ,
arr 8 CELLS clean test  \ 1 2 3 4 5 6  Ok

Автор:  вопрос [ Пт ноя 20, 2009 23:30 ]
Заголовок сообщения: 

VoidVolker писал(а):
Кварк/Спф:
Код:

: test CELLS OVER + SWAP DO I @ . CELL +LOOP ;

CREATE arr 1 , 2 , 3 , 4 , 2 , 3 , 5 , 6 ,
arr 8 CELLS clean test  \ 1 2 3 4 5 6  Ok

что-то не пойму, ссылка (размер) всегда равно CELL?

Автор:  VoidVolker [ Пт ноя 20, 2009 23:33 ]
Заголовок сообщения: 

вопрос писал(а):
что-то не пойму, ссылка (размер) всегда равно CELL?

В данном контексте - да.

Автор:  dynamic-wind [ Пт ноя 20, 2009 23:41 ]
Заголовок сообщения: 

А если мильён элементов в массиве? Алгоритм-то квадратичный :roll:

Автор:  mOleg [ Пт ноя 20, 2009 23:45 ]
Заголовок сообщения: 

dynamic-wind писал(а):
А если мильён элементов в массиве? Алгоритм-то квадратичный

тогда предлагайте свой вариант 8) благо решать задачу можно большим количеством методов 8)

Автор:  VoidVolker [ Пт ноя 20, 2009 23:59 ]
Заголовок сообщения: 

dynamic-wind писал(а):
А если мильён элементов в массиве? Алгоритм-то квадратичный

Задача будет выполнена. А большего по условию ТЗ и не надо.

Автор:  VoidVolker [ Сб ноя 21, 2009 00:13 ]
Заголовок сообщения: 

Немного ранее в чате:
Цитата:
[22:29] mOleg: а вот HERE использовать для временного хранения данных очень плохое решение

Вариант с сохранением результата в произвольной области памяти:
Код:
: clean \ ( arr # --> addr #1 )
  DUP ALLOCATE THROW        \ arr # addr        \ Выделяем буфер;
  DUP CELL + 2SWAP          \ addr addr1 arr #  \ Сохраняем на стеке адрес нового массива;
  OVER @ 4 PICK !           \ Первая ссылка всегда уникальна - сразу сохраняем её;
  CELL - SWAP CELL + SWAP   \ Соответственно уменьшаем и число проходов цикла по массиву на один.
  \ Цикл для каждого элемента массива...
  OVER + SWAP DO    \ addr addr1 \ addr1=addr+i*cell
    \ На стеке - начальный адрес буфера и адрес в буфере для следующего сохраняемого значения.
    \ I = адрес текущего элемента массива.
    \ Цикл для каждого сохраненного элемента буфера...
    \ Т.е. просматривается не весь буфер, а только уже заполненная его часть.
    0 OVER 3 PICK DO    \ Ищем значение текущего элемента массива в буфере.
      I @ J @ = OR      \ В каждой итерации сравниваем значения из буфера и массива,
                        \ а результат(флаг) складываем с предыдущим сравнением.
    CELL +LOOP \ addr addr1 ?
    \ Если значения еще нет - копируем его в буфер и увеличиваем addr1 на размер ячейки
      IF ELSE I @ OVER ! CELL + THEN
  CELL +LOOP
  \ addr addr1 \ Начало и конец буфера
  OVER -  \ addr #1 \ И вычисляем длину буфера
;

: test   OVER + SWAP DO I @ . CELL +LOOP ;

CREATE arr 1 , 2 , 3 , 4 , 2 , 3 , 5 , 6 ,

arr 8 CELLS clean2 test CR  \ 1 2 3 4 5 6  Ok

Автор:  mOleg [ Сб ноя 21, 2009 11:16 ]
Заголовок сообщения: 

VoidVolker писал(а):
Немного ранее в чате:
Цитата:[22:29] mOleg: а вот HERE использовать для временного хранения данных очень плохое решение
Вариант с сохранением результата в произвольной области памяти:

это не спасает. Как минимум такой подход не будет нормально работать на многопоточной системе, то есть алгоритм нереентерабелен!
вторая проблема заключается в том, что DP в Форте все-же может быть очень различным образом устроен.

Автор:  VoidVolker [ Сб ноя 21, 2009 13:10 ]
Заголовок сообщения: 

mOleg писал(а):
Как минимум такой подход не будет нормально работать на многопоточной системе, то есть алгоритм нереентерабелен!

Исправил. clean2 без использования системных переменных.

Автор:  mOleg [ Сб ноя 21, 2009 17:13 ]
Заголовок сообщения: 

такс, мой вариант(как обычно для форка).

\ 21.11.2009 ~mOleg
\ Сopyright [C] 2009 mOleg mininoleg@yahoo.com
\ получение массива ссылок с указателями без повторов

\ копировать содержимое массива байт addr # в хип,
\ вернуть адрес начала и длину результирующего массива
: Copy ( addr # --> addr # )
DUP ALLOCATE THROW SWAP DDUP D>R CMOVE DR> ;

\ удалить все повторы для очередного значения
: rmCopy ( up low --> )
DUP A@ \ если нуль, пропускаем
*IF A>R
BEGIN ADDR + DDUP > WHILE
DUP A@ AR@ = IF DUP OFF THEN \ повторы стираем
REPEAT AR>
THEN TDROP ;

\ удалить все повторы
: -replica ( up low --> )
BEGIN DDUP > WHILE \ пока не конец массива
DDUP rmCopy \ удаляются повторы
ADDR +
REPEAT DDROP ;

\ сохранить n по указанному адресу,
\ увеличить адрес на величину адресной ссылки
: +> ( addr addr --> addr ) TUCK A! ADDR + ;

\ убрать все нулевые вхождения
: compress ( up low --> addr # )
TUCK DUP A>R
BEGIN DDUP > WHILE
DUP A@ *IF AR> +> A>R ELSE DROP THEN
ADDR +
REPEAT DDROP AR> OVER - ;

\ удалить все повторы
: clean ( arr # --> addr # ) Copy BOUNDS DDUP -replica compress ;


пример:
CREATE zzz 0x123123 , 0x234234 , 0x345345 , 0x345345 , 0x123123 ,
0x123123 , 0x456456 , 0x234234 , 0x123123 , 0x345345 ,

zzz 40 clean DUMP


вобщем, идея в том, что вместо повторов сначала записываются нули, а потом "дырявый" массив сжимается (нули убираются).

Автор:  mOleg [ Вс ноя 22, 2009 19:35 ]
Заголовок сообщения: 

еще один мой вариант решения
\ 22.11.2009 ~mOleg
\ Сopyright [C] 2009 mOleg mininoleg@yahoo.com
\ получение массива ссылок с указателями без повторов

memory/ fld.fts
memory/ cmove.fts

0 struct buffer
addr[] off_top \ указатель на вершину буфера
addr[] off_lim \ предельный адрес буфера
zero[] off_buf \ смещение в начало буфера
/struct

\ создать буфер
: buffer ( # --> buf )
DUP /buffer + ALLOCATE THROW
DUP >L off_buf + \ --> limit
L@ off_lim A!
L@ off_buf L@ off_top A!
L> ;

\ вернуть содержимое буфера
: buffer> ( buf --> up low ) DUP off_top A@ SWAP off_buf ;

\ увеличить размер буфера на указанное количество байт
: increase ( buf # --> )
OVER off_top A@ +
OVER off_lim A@ OVER < ABORT" пространство буфера исчерпано!"
SWAP off_top A! ;

\ добавить значение в конец буфера (неупорядоченного)
: >buffer ( n buf --> ) DUP off_top A@ SWAP ADDR increase A! ;

\ искать число n в указанном буфере buf
\ предполагается, что буфер отсортирован
: search ( n buf --> addr flag )
buffer>
ROT >L
BEGIN DDUP - *WHILE \ вообще не осталось элементов
ADDR <> WHILE \ если остался один элемент
DDUP - 2 / [ 0 ADDR - LIT, ] AND OVER + \ --> addr| |addr addr
DUP A@ L@ - *WHILE \ если найдено
-IF DROP -ROT ELSE DROP THEN NIP
REPEAT DROP NIP NIP LDROP TRUE
;THEN NIP L> OVER A@ =
;THEN NIP LDROP ;

\ если n уже есть в buf , вернуть false
\ иначе вставить значение в buf , и вернуть n
: ?insert ( n buf --> n | false )
DDUP search \ --> n buf addr flag
IF TDROP FALSE ;THEN \ вставлять нечего, значение уже есть
OVER off_top A@
ROT CELL increase
OVER -
OVER DUP ADDR + ROT CMOVE>
OVER SWAP A! ;

\ получить список уникальных адресов
: clean ( arr # --> addr # )
DUP buffer >R \ буфер для сортировки
DUP buffer >L \ буфер для сохранения результата
BOUNDS
BEGIN DDUP > WHILE
DUP A@ R@ ?insert
*IF L@ >buffer ELSE DROP THEN
ADDR +
REPEAT DDROP
R> FREE THROW
L> buffer> TUCK - ;

\EOF тестовый пример
CREATE zzz 1 , 3 , 3 , 2 , 6 ,
1 , 9 , 4 , 8 , 9 ,

zzz 40 clean .S DUMP


алгоритм следующий:

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

для каждого следующего элемента исходного буфера
ищется следующее значение в отсортированном буфере
ЕСЛИ значение отсутствует, добавляем его в оба буфера в один в порядке сортировки, в другой в порядке следования

все

Автор:  chess [ Вс ноя 22, 2009 21:12 ]
Заголовок сообщения: 

Решение имеет линейную сложность(но абсолютно не оптимизировано)
Решение с использованием лок. переменных(поэтому использованы макросы)
Алгоритм использует ячейки памяти по адресам массива указателей

Код:
\ макросы

M: A(R)  ARR IR CELLS + ;
M: P(R)  A(R) @ ;
M: A(W)  ARR IW CELLS + ;
M: P(W)  P(R) A(W) ! ;

: CLEAN { ARR LEN \ IR IW }
0 TO IR 0 TO IW
BEGIN P(R) @ 1 AND                        \ цикл разметки памяти флагами по указателям
      IF P(R) NEGATE A(R) ! THEN          \ с предварительным сохранением первого разряда ячеек памяти
      P(R) ABS @ 1 INVERT AND P(R) ABS !  \ в массиве указателей путем изменения знака указателей
      IR 1+ TO IR IR LEN >
UNTIL 0 TO IR
BEGIN P(R) ABS @ 0=                       \ цикл сжатия массива указателей на основе флагов в памяти
      IF P(W) IW 1+ TO IW THEN
      IR 1+ TO IR IR LEN >
UNTIL 0 TO IR
BEGIN P(R) 0<                             \ цикл восстановления информации памяти по указателям
      IF P(R) ABS @ 1 OR P(R) ABS ! THEN
      P(R) ABS A(R) !                     \ и восстановления знаков указателей в массиве указателей
      IR 1+ TO IR IR IW >
UNTIL ARR IW
;

Страница 1 из 3 Часовой пояс: UTC + 3 часа [ Летнее время ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/