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

...
Google Search
Forth-FAQ Spy Grafic

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




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

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

можете немного пояснить основную идею?
да, и не хватает указания под какую систему написано, и части подключения библиотек 8(

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


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

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

При обращении в память второй раз по одному и тому же указателю
в памяти уже есть флаг от первого обращения по этому указателю, поэтому второй указатель лишний.
Для флага нужен только один бит.
Этот бит сохраним как знак указателя на данную ячейку в массиве указателей(указатель изначально положительный)
Так понятно?

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


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

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

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

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


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

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

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

Повторы не вычисляются - они проверяются при проверке флагов в ячейкам по указателям.

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


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

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

принципиально, так как этот же массив отдается другим алгоритмам во время теста. Вообще это часть ТЗ, поэтому копирование должно присутствовать в коде, так как на его исполнение так же тратится время.

chess писал(а):
Повторы не вычисляются - они проверяются при проверке флагов в ячейкам по указателям.

простите, за тугодумство, идею понять не могу.
К примеру, у нас есть следующий массив:

1 8 3 3 4 1 3 2

как будет происходить выбор уникальных значений?
(должно получиться 1 8 3 4 2 )

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


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

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2168
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 41 раз.
mOleg писал(а):
1 8 3 3 4 1 3 2

как будет происходить выбор уникальных значений?
(должно получиться 1 8 3 4 2 )

Представьте, что у вас есть память, а значения 1 8 3 3 4 1 3 2 это адреса этой памяти.
Этот массив мы правим до 1 8 3 4 2.
Память обнулена.
Читаем из нее по первому адресу (1) - там 0, тогда пишем туда 1,
читаем по 8, там 0, тогда пишем туда 1,
читаем по 3, там 0, пишем туда 1,
читаем по 3, там 1, значит это 3 уже было и его пропускаем.
Адрес для записи очередного уникального значения остается на позиции второго 3,
а адрес для чтения уходит на следующую позицию и т.д.

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


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

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

Код:
: clean ( A U -- a u )

\ копирование исходного массива указателей в кучу

DUP CELLS ALLOCATE THROW SWAP 2DUP 2>R CELLS CMOVE

\ сохранение первого разряда ячеек памяти по указателям в самих указателях путем изменения знака указателей

2R> CELLS OVER + SWAP 2DUP 2>R
DO I @ @ 1 AND IF I @ NEGATE I ! THEN CELL +LOOP

\ обнуление первого разряда ячеек памяти по указателям

2R@
DO I @ ABS DUP @ 0xFFFFFFFE AND SWAP ! CELL +LOOP

\ сжатие массива указателей в куче

2R@ TUCK
DO I @ ABS @ 1 AND 0= IF I @ ABS DUP @ 1 OR SWAP ! DUP I @ SWAP ! CELL + THEN CELL +LOOP

\ восстановление первого разряда ячеек памяти по указателям и знаков самих указателей

DUP 2R@ NIP
DO I @ DUP 0 > IF DUP @ 0xFFFFFFFE AND SWAP ! ELSE ABS I ! THEN CELL +LOOP
2R> NIP TUCK - CELL /
;

\ TEST
STARTLOG
VARIABLE P1  0x0E P1 !
VARIABLE P2  0xFF P2 !
VARIABLE P3  0x1F P3 !
VARIABLE P4  0x22 P4 !

CREATE ARR P4 , P4 ,  P3 , P4 , P3 , P1 , P1 , P2 ,

: V. P1 @ . P2 @ . P3 @ . P4 @ . CR CR ;
: P. CELLS OVER + SWAP DO I @ . CELL +LOOP CR CR ;

V.
ARR 8 P.
ARR 8 clean P.
V.

log
Код:
E FF 1F 22

5698E0 5698E0 5698C0 5698E0 5698C0 569880 569880 5698A0

5698E0 5698C0 569880 5698A0

E FF 1F 22


Ok

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


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

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

Код:
REQUIRE { LIB\EXT\LOCALS.F

: cleanL { A U \ a u }
U CELLS DUP TO U ALLOCATE THROW TO a  A a U CMOVE
  a U + a DO I @ @ 1 AND IF I @ NEGATE I ! THEN CELL +LOOP
  a U + a DO I @ ABS DUP @ 0xFFFFFFFE AND SWAP ! CELL +LOOP
a a U + a DO I @ ABS @ 1 AND 0= IF I @ ABS DUP @ 1 OR SWAP ! DUP I @ SWAP ! CELL + THEN CELL +LOOP TO u
      u a DO I @ DUP 0 > IF DUP @ 0xFFFFFFFE AND SWAP ! ELSE ABS I ! THEN CELL +LOOP a u a - CELL / ;

\ TEST
STARTLOG

CREATE ARR
' DUP DUP , ,
' DROP DUP DUP , , ,
' SWAP ,
' NIP DUP , ,

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

ARR 8 P.
ARR 8 cleanL P.

Сравним быстродействие вариантов с лок. метками и без них

Код:
REQUIRE METER ~CHESS\TASK\METER.F

: S1 ARR 8 clean ;  METER S1
: S2 ARR 8 cleanL ; METER S2

LOG
Код:
5579564 5579564 5579620 5579620 5579620 5579808 5579936 5579936

5579564 5579620 5579808 5579936

5579564 5579564 5579620 5579620 5579620 5579808 5579936 5579936

5579564 5579620 5579808 5579936

1782 855   без лок. меток
2115 1125  с лок. метками


Лок. метки чуть проигрывают.

PS. Вообще использование памяти позволяет уменьшить сложность алгоритма.

Вот, например, сортировка

Код:
8 3 4 5 3 3 7 3 2 4 2 7


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

Код:
адр 1 2 3 4 5 6 7 8    получаем    1 2 3 4 5 6 7 8
дан 0 0 0 0 0 0 0 0                0 2 4 2 1 0 2 1

затем читаем память последовательно сначала и получаем

Код:
2 2 3 3 3 3 4 4 5 7 7 8


сортировка проведена тривиальным образом(сложность алгоритма линейная - O(n))

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


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

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

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

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


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

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

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

Многопоточность в 99% случаев достаточна для решения задач без компиляции во время исполнения. А в этом случае запретов на
использование в многопоточных программах нет.
Отрицательные адреса(в смысле отриц-х данных) для оперативной памяти на самом деле долго будут отсутствовать даже в 32 разрядной ОС. К слову я уже давно использую 64-разрядную Windows, да и Linux-64 давно есть.

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


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

Зарегистрирован: Вт май 02, 2006 13:19
Сообщения: 3565
Откуда: St.Petersburg
Благодарил (а): 4 раз.
Поблагодарили: 72 раз.
А не проще ли использовать для меток использованных указателей не адресное пространство самих указателей, а отдельный массив?

Для 32-хбитных адресных указателей нужен массив из 2<sup>32</sup> бит = 2<sup>27</sup> 32-хразрядных слов, т.е. ~512 мегабайт.
При ограничении на величину адресов объем, разумеется, уменьшится.

_________________
С уважением, WingLion
Forth-CPU . RuF09WE
Мой Форт
Отсутствие бана это не заслуга юзера, а недоработка модератора (с)


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

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

зачем нам однобайтовые "флаги", ведь достаточно знать, присутствует число или нет, то есть одного бита (экономия в 32 раза!)
Но и это не все, т.к. наверняка адреса будут раскиданы не равномерно по адресному пространству, а некими групками,
а это означает, что можно сделать таблицу двухуровневой (на первом уровне куски, к примеру размером в мегабайт),
а на следующем уровне адресация внутри мегабайта! Думая дальше понимаем, что можно вобщем-то этой фигней не заниматься, а использовать бинарные деревья, ведь поиск в них очень даже по скорости не плохой, причем, нет необходимости им быть сбалансированными, впрочем, на больших массивах АВЛ деревья будут очень даже не плохи. Еще одно достоинство у бинарных деревьев, что адреса могут группироваться как угодно!
:)) :)) :))

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


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

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

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

chess писал(а):
Многопоточность в 99% случаев достаточна для решения задач без компиляции во время исполнения. А в этом случае запретов на
использование в многопоточных программах нет.

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

chess писал(а):
Отрицательные адреса(в смысле отриц-х данных) для оперативной памяти на самом деле долго будут отсутствовать даже в 32 разрядной ОС. К слову я уже давно использую 64-разрядную Windows, да и Linux-64 давно есть.

ну, адреса АПИ функций как раз отрицательные в WINXP, так как располагаюстся с тарших 2Гб ОЗУ (раз)
а что делать, если разрядность 16 бит у микроконтроллера?

Имхо, я не спорю, решение оригинальное, но оно не применимо в общем случае, как и первый вариант VoidVolker-а, с использованием HERE.

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


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

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

Тут не надо путать адреса форт-слов входящих в определение слова clean и кодовое тело этого слова.
Это кодовое тело не имеет ссылок (сall) на входящие в него слова(инлайн подстановки).
Поэтому в этом смысле слово clean будет работать в (спф) корректно. Для других фортов можно его написать на ассме.
К слову, вот код
Код:
: S1 ( n -- n )
>R ['] R> DUP @ 0 AND SWAP ! R> ;

Вроде полностью искажаем код слова R>, ан нет - все работает, так как в кодовое тело слова S1 код (call R>) не попадет.
Остальные замечания не понял.
Что разве потоки не могут разделять общий словарь?
Адреса словарных статей для АПИ функций отрицательные?
А вобщем я воспринял эту задачу просто как задачу, а не как что-то, имеющее практический смысл.

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


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

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

тут мы сразу уходим в дебри. Инлайн подстановки - это такой трюк, их не имеет рассматривать вообще в этой теме. Лучше оставаться в рамках б\м классического шитого кода (то есть как минимум набора CALL вызовов и данных между ними).

chess писал(а):
Остальные замечания не понял.

все замечания сводятся лишь к тому, что ваш код будет работать в ограниченном количестве случаев.

chess писал(а):
Что разве потоки не могут разделять общий словарь?

они его и разделяют.

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


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

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


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

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


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

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