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

...
Google Search
Forth-FAQ Spy Grafic

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




Ответить
Имя пользователя:
Заголовок:
Текст сообщения:
Введите текст вашего сообщения. Длина сообщения в символах не более: 60000

Размер шрифта:
Цвет шрифта
Настройки:
BBCode ВКЛЮЧЕН
[img] ВЫКЛЮЧЕН
[flash] ВЫКЛЮЧЕН
[url] ВКЛЮЧЕН
Смайлики ВЫКЛЮЧЕНЫ
Отключить в этом сообщении BBCode
Не преобразовывать адреса URL в ссылки
Вопрос
Теперь гостю придется вводить здесь пароль. Не от своей учетной записи, а ПАРОЛЬ ДЛЯ ГОСТЯ, получить который можно после регистрации на форуме через ЛС.:
Этот вопрос предназначен для выявления и предотвращения автоматических регистраций.
   

Обзор темы - *выборка из массива указателей
Автор Сообщение
  Заголовок сообщения:   Ответить с цитатой
вопрос писал(а):
Хм, я ещё раз повторю вопрос: для каких случаев могла бы понадобиться реентерабельность?

это как бы правило хорошего тона.

вопрос писал(а):
мне кажется, вполне возможно одно решение

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

то есть решение во времени будет "размазано", и тут решения с глобальными зависимостями просто в пролете.
Сообщение Добавлено: Пт ноя 27, 2009 19:54
  Заголовок сообщения:   Ответить с цитатой
Хм, я ещё раз повторю вопрос: для каких случаев могла бы понадобиться реентерабельность?

Можно было бы сформулировать задачу в виде "преобразовать один масив, оставляя его нетронутым, в другой, где элементы расположены в том же порядке, но изъяты повторы, причём должна быть учтена возможность [вот тот самый случай, где нужна реэнтерабельность] "

мне кажется, вполне возможно одно решение
Сообщение Добавлено: Пт ноя 27, 2009 19:12
  Заголовок сообщения:   Ответить с цитатой
вообще не нужно путать частные и общие решения.
Многие алгоритмы прекрасно работают в однозадачных системах, и не работают на многозадачных.
Абсолютно любое решение имеет свои достоинства и недостатки, и их важно понимать, но не нужно осуждать!
Я не занимался осуждением, а занимался обсуждением.
К примеру, на той же сортировке при ограничении значений в 256 бит (то есть на символах) вполне
быстро и красиво решается с помощью 256 ячеечной таблицы с последующей "распаковкой в простом цикле",
но на строках такой алгоритм не работает вообще.
Сообщение Добавлено: Пт ноя 27, 2009 13:26
  Заголовок сообщения:   Ответить с цитатой
WingLion писал(а):
А требование иметь при этом минимум 16Гб памяти при 32-хбитных указателях никак не смущает?

Какие еще требования? И чем они обусловлены? +1 байт на указатель - для этого нужно 16 гигабайт памяти?
Сообщение Добавлено: Пт ноя 27, 2009 11:27
  Заголовок сообщения:   Ответить с цитатой
VoidVolker писал(а):
во время работы программы можно при минимальных потерях производительности


А требование иметь при этом минимум 16Гб памяти при 32-хбитных указателях никак не смущает?
Сообщение Добавлено: Пт ноя 27, 2009 08:16
  Заголовок сообщения:   Ответить с цитатой
Алгоритм chess'а достаточно легко адаптировать под "неизменение" просто введя "промежуточные" адреса, т.е. расположить указатели в новых адресах(переменных), и упорядочивать уже массив с этими новыми адресами. Но это оптимальнее делать на более ранней стадии работы программы - при определении самих первичных указателей. Или, что еще лучше, в структуре по указателю ввести дополнительный байт для флага. Т.о. во время работы программы можно при минимальных потерях производительности достаточно быстро обрабатывать эти самые массивы указателей. А для многопоточности - можно использовать дополнительные биты в поле флага. Так что считаю это решение наиболее эффективным.
Сообщение Добавлено: Пт ноя 27, 2009 00:23
  Заголовок сообщения:   Ответить с цитатой
Если нельзя трогать изначальный массив (кстати, почему), то алгоритм может быть, кажется, только таким (или я что-то не понимаю): брать по очереди каждый элемент от начала и проверять, есть ли он же раньше в массиве, если нет - он кладётся "следующим" в новую структуру [результат-массив] , дойдя до конца, цикл прекращается. Зачем, для каких случаев нужнв реентерабельность?
Сообщение Добавлено: Чт ноя 26, 2009 23:56
  Заголовок сообщения:   Ответить с цитатой
chess писал(а):
Для меня никаких дебрей нет. Набираю SEE clean. Не вижу call-ов.
Кроме того определение можно написать на ассемблере - код будет проще и быстрее.
Кроме того можно чуть изменить формирование словарной статьи с введением доп. поля или флага.
Вообщем вариантов как всегда много.

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

chess писал(а):
Можете привести хотя бы один такой случай - если не трудно.

не будет работать на больших адресах адресах
не реентерабельно

но опять же, это не претензия.
Сообщение Добавлено: Чт ноя 26, 2009 21:59
  Заголовок сообщения:   Ответить с цитатой
mOleg писал(а):
тут мы сразу уходим в дебри.

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

Можете привести хотя бы один такой случай - если не трудно.
Сообщение Добавлено: Чт ноя 26, 2009 21:17
  Заголовок сообщения:   Ответить с цитатой
chess писал(а):
Тут не надо путать адреса форт-слов входящих в определение слова clean и кодовое тело этого слова.
Это кодовое тело не имеет ссылок (сall) на входящие в него слова(инлайн подстановки).

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

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

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

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

они его и разделяют.
Сообщение Добавлено: Чт ноя 26, 2009 18:28
  Заголовок сообщения:   Ответить с цитатой
mOleg писал(а):
они не исполняются во время работы вашего решения, я говорил о тех, которые исполняются.
к примеру, создается массив указалелей на все определения, используемые в определении слова clean (этакий вариант декомпиляции), затем этот список надо почистить от повторов.

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

Вроде полностью искажаем код слова R>, ан нет - все работает, так как в кодовое тело слова S1 код (call R>) не попадет.
Остальные замечания не понял.
Что разве потоки не могут разделять общий словарь?
Адреса словарных статей для АПИ функций отрицательные?
А вобщем я воспринял эту задачу просто как задачу, а не как что-то, имеющее практический смысл.
Сообщение Добавлено: Чт ноя 26, 2009 15:37
  Заголовок сообщения:   Ответить с цитатой
chess писал(а):
mOleg писал(а):замечательно, давайте представим, что мы взяли адреса всех исполняемых в Форт-системе слов...
Ну в последнем моем посте я уже брал несколько адресов форт-слов для примера.

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

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

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

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

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

Имхо, я не спорю, решение оригинальное, но оно не применимо в общем случае, как и первый вариант VoidVolker-а, с использованием HERE.
Сообщение Добавлено: Чт ноя 26, 2009 09:02
  Заголовок сообщения:   Ответить с цитатой
тогда уж надо идею дальше развивать!

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

Для 32-хбитных адресных указателей нужен массив из 2<sup>32</sup> бит = 2<sup>27</sup> 32-хразрядных слов, т.е. ~512 мегабайт.
При ограничении на величину адресов объем, разумеется, уменьшится.
Сообщение Добавлено: Чт ноя 26, 2009 06:27
  Заголовок сообщения:   Ответить с цитатой
mOleg писал(а):
замечательно, давайте представим, что мы взяли адреса всех исполняемых в Форт-системе слов...

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

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

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


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