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 ] |
Заголовок сообщения: | |
А если мильён элементов в массиве? Алгоритм-то квадратичный |
Автор: | mOleg [ Пт ноя 20, 2009 23:45 ] |
Заголовок сообщения: | |
dynamic-wind писал(а): А если мильён элементов в массиве? Алгоритм-то квадратичный
тогда предлагайте свой вариант благо решать задачу можно большим количеством методов |
Автор: | 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 пример: CREATE zzz 0x123123 , 0x234234 , 0x345345 , 0x345345 , 0x123123 , вобщем, идея в том, что вместо повторов сначала записываются нули, а потом "дырявый" массив сжимается (нули убираются). |
Автор: | mOleg [ Вс ноя 22, 2009 19:35 ] |
Заголовок сообщения: | |
еще один мой вариант решения \ 22.11.2009 ~mOleg алгоритм следующий: создается два массива в хипе с длиной равной исходному массиву (потому что там может повторов не быть вообще) один буфер используется для хранения отсортированного массива, другой для массива, сохраняющего порядок значений исходного массива для каждого следующего элемента исходного буфера ищется следующее значение в отсортированном буфере ЕСЛИ значение отсутствует, добавляем его в оба буфера в один в порядке сортировки, в другой в порядке следования все |
Автор: | 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/ |