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

...
Google Search
Forth-FAQ Spy Grafic

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




Начать новую тему Ответить на тему  [ Сообщений: 39 ]  На страницу 1, 2, 3  След.
Автор Сообщение
 Заголовок сообщения: *выборка из массива указателей
СообщениеДобавлено: Пт ноя 20, 2009 21:35 
Не в сети
Moderator
Moderator
Аватара пользователя

Зарегистрирован: Чт май 04, 2006 00:53
Сообщения: 5062
Откуда: был Крым, теперь Новосибирск
Благодарил (а): 23 раз.
Поблагодарили: 63 раз.
Имеется в памяти массив указателей (адресных ссылок) фиксированной длины: arr # , длина массива задана в байтах, и кратна длине адресной ссылки. Необходимо без изменений в исходном массиве получить другой массив, содержащий только уникальные ссылки (то есть исключить все повторы из исходного). Порядок следования адресных ссылок должен быть сохранен, исключаться должны повторения, находящиеся по старшим адресам.

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

;

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


Последний раз редактировалось mOleg Вт ноя 24, 2009 21:57, всего редактировалось 1 раз.

Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: выборка из массива указателей
СообщениеДобавлено: Пт ноя 20, 2009 22:36 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июн 25, 2009 11:12
Сообщения: 412
Благодарил (а): 41 раз.
Поблагодарили: 8 раз.
Были бы в 4те готовые хэш-таблицы, тогда и решать нечего... :?


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Пт ноя 20, 2009 22:38 
Не в сети
Аватара пользователя

Зарегистрирован: Вт мар 20, 2007 23:39
Сообщения: 1261
Благодарил (а): 3 раз.
Поблагодарили: 19 раз.
Они есть в одной из соседних тем.

_________________
Cтоимость сопровождения программного обеспечения пропорциональна квадрату творческих способностей программиста.
Роберт Д. Блисc


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Пт ноя 20, 2009 23:24 
Не в сети
Аватара пользователя

Зарегистрирован: Вт мар 20, 2007 23:39
Сообщения: 1261
Благодарил (а): 3 раз.
Поблагодарили: 19 раз.
Кварк/Спф:
Код:
: -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

_________________
Cтоимость сопровождения программного обеспечения пропорциональна квадрату творческих способностей программиста.
Роберт Д. Блисc


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Пт ноя 20, 2009 23:30 
Не в сети

Зарегистрирован: Вт май 09, 2006 12:31
Сообщения: 3438
Благодарил (а): 5 раз.
Поблагодарили: 16 раз.
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?


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Пт ноя 20, 2009 23:33 
Не в сети
Аватара пользователя

Зарегистрирован: Вт мар 20, 2007 23:39
Сообщения: 1261
Благодарил (а): 3 раз.
Поблагодарили: 19 раз.
вопрос писал(а):
что-то не пойму, ссылка (размер) всегда равно CELL?

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

_________________
Cтоимость сопровождения программного обеспечения пропорциональна квадрату творческих способностей программиста.
Роберт Д. Блисc


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Пт ноя 20, 2009 23:41 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июн 25, 2009 11:12
Сообщения: 412
Благодарил (а): 41 раз.
Поблагодарили: 8 раз.
А если мильён элементов в массиве? Алгоритм-то квадратичный :roll:


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Пт ноя 20, 2009 23:45 
Не в сети
Moderator
Moderator
Аватара пользователя

Зарегистрирован: Чт май 04, 2006 00:53
Сообщения: 5062
Откуда: был Крым, теперь Новосибирск
Благодарил (а): 23 раз.
Поблагодарили: 63 раз.
dynamic-wind писал(а):
А если мильён элементов в массиве? Алгоритм-то квадратичный

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

_________________
Мне бы только мой крошечный вклад внести,
За короткую жизнь сплести
Хотя бы ниточку шёлка.
fleur


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Пт ноя 20, 2009 23:59 
Не в сети
Аватара пользователя

Зарегистрирован: Вт мар 20, 2007 23:39
Сообщения: 1261
Благодарил (а): 3 раз.
Поблагодарили: 19 раз.
dynamic-wind писал(а):
А если мильён элементов в массиве? Алгоритм-то квадратичный

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

_________________
Cтоимость сопровождения программного обеспечения пропорциональна квадрату творческих способностей программиста.
Роберт Д. Блисc


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Сб ноя 21, 2009 00:13 
Не в сети
Аватара пользователя

Зарегистрирован: Вт мар 20, 2007 23:39
Сообщения: 1261
Благодарил (а): 3 раз.
Поблагодарили: 19 раз.
Немного ранее в чате:
Цитата:
[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

_________________
Cтоимость сопровождения программного обеспечения пропорциональна квадрату творческих способностей программиста.
Роберт Д. Блисc


Последний раз редактировалось VoidVolker Вс ноя 22, 2009 23:58, всего редактировалось 4 раз(а).

Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Сб ноя 21, 2009 11:16 
Не в сети
Moderator
Moderator
Аватара пользователя

Зарегистрирован: Чт май 04, 2006 00:53
Сообщения: 5062
Откуда: был Крым, теперь Новосибирск
Благодарил (а): 23 раз.
Поблагодарили: 63 раз.
VoidVolker писал(а):
Немного ранее в чате:
Цитата:[22:29] mOleg: а вот HERE использовать для временного хранения данных очень плохое решение
Вариант с сохранением результата в произвольной области памяти:

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

_________________
Мне бы только мой крошечный вклад внести,
За короткую жизнь сплести
Хотя бы ниточку шёлка.
fleur


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Сб ноя 21, 2009 13:10 
Не в сети
Аватара пользователя

Зарегистрирован: Вт мар 20, 2007 23:39
Сообщения: 1261
Благодарил (а): 3 раз.
Поблагодарили: 19 раз.
mOleg писал(а):
Как минимум такой подход не будет нормально работать на многопоточной системе, то есть алгоритм нереентерабелен!

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

_________________
Cтоимость сопровождения программного обеспечения пропорциональна квадрату творческих способностей программиста.
Роберт Д. Блисc


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Сб ноя 21, 2009 17:13 
Не в сети
Moderator
Moderator
Аватара пользователя

Зарегистрирован: Чт май 04, 2006 00:53
Сообщения: 5062
Откуда: был Крым, теперь Новосибирск
Благодарил (а): 23 раз.
Поблагодарили: 63 раз.
такс, мой вариант(как обычно для форка).

\ 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


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

_________________
Мне бы только мой крошечный вклад внести,
За короткую жизнь сплести
Хотя бы ниточку шёлка.
fleur


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Вс ноя 22, 2009 19:35 
Не в сети
Moderator
Moderator
Аватара пользователя

Зарегистрирован: Чт май 04, 2006 00:53
Сообщения: 5062
Откуда: был Крым, теперь Новосибирск
Благодарил (а): 23 раз.
Поблагодарили: 63 раз.
еще один мой вариант решения
\ 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


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

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

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

все

_________________
Мне бы только мой крошечный вклад внести,
За короткую жизнь сплести
Хотя бы ниточку шёлка.
fleur


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Вс ноя 22, 2009 21:12 
Не в сети
Аватара пользователя

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

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

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
;

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


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

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


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

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


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

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