Автор |
Сообщение |
|
|
Заголовок сообщения: |
|
|
|
вопрос писал(а): Хм, я ещё раз повторю вопрос: для каких случаев могла бы понадобиться реентерабельность? это как бы правило хорошего тона. вопрос писал(а): мне кажется, вполне возможно одно решение
задачка интересна тем, что решений может быть много достаточно непохожих.
и оптимальное решение для разных условий может разным.
То есть, к примеру, если речь идет о ускорении поиска в контексте (то есть исключения повторов в контексте)
то лучше вариация моего первого решения с сохранением нуля в место повтора.
Причем, выглядело бы это следующим образом:
1) при каждом изменении в контексте все его содержимое копируется в "теневой" буфер
2) для каждого поиска в следующем словаре убираются возможные повторы, причем, возможно уже после того, как в нем не найден искомое слово
(да, возможно для vid словарей с уже убранными повторами стоит добавить битовый флаг.)
то есть решение во времени будет "размазано", и тут решения с глобальными зависимостями просто в пролете.
[quote="вопрос"]Хм, я ещё раз повторю вопрос: для каких случаев могла бы понадобиться реентерабельность?[/quote] это как бы правило хорошего тона.
[quote="вопрос"]мне кажется, вполне возможно одно решение[/quote]
задачка интересна тем, что решений может быть много достаточно непохожих.
и оптимальное решение для разных условий может разным.
То есть, к примеру, если речь идет о ускорении поиска в контексте (то есть исключения повторов в контексте)
то лучше вариация моего первого решения с сохранением нуля в место повтора.
Причем, выглядело бы это следующим образом:
1) при каждом изменении в контексте все его содержимое копируется в "теневой" буфер
2) для каждого поиска в следующем словаре убираются возможные повторы, причем, возможно уже после того, как в нем не найден искомое слово
(да, возможно для vid словарей с уже убранными повторами стоит добавить битовый флаг.)
то есть решение во времени будет "размазано", и тут решения с глобальными зависимостями просто в пролете.
|
|
|
|
Добавлено: Пт ноя 27, 2009 19:54 |
|
|
|
|
|
Заголовок сообщения: |
|
|
|
Хм, я ещё раз повторю вопрос: для каких случаев могла бы понадобиться реентерабельность?
Можно было бы сформулировать задачу в виде "преобразовать один масив, оставляя его нетронутым, в другой, где элементы расположены в том же порядке, но изъяты повторы, причём должна быть учтена возможность [вот тот самый случай, где нужна реэнтерабельность] "
мне кажется, вполне возможно одно решение
Хм, я ещё раз повторю вопрос: для каких случаев могла бы понадобиться реентерабельность?
Можно было бы сформулировать задачу в виде "преобразовать один масив, оставляя его нетронутым, в другой, где элементы расположены в том же порядке, но изъяты повторы, причём должна быть учтена возможность [вот тот самый случай, где нужна реэнтерабельность] "
мне кажется, вполне возможно одно решение
|
|
|
|
Добавлено: Пт ноя 27, 2009 19:12 |
|
|
|
|
|
Заголовок сообщения: |
|
|
|
вообще не нужно путать частные и общие решения.
Многие алгоритмы прекрасно работают в однозадачных системах, и не работают на многозадачных.
Абсолютно любое решение имеет свои достоинства и недостатки, и их важно понимать, но не нужно осуждать!
Я не занимался осуждением, а занимался обсуждением.
К примеру, на той же сортировке при ограничении значений в 256 бит (то есть на символах) вполне
быстро и красиво решается с помощью 256 ячеечной таблицы с последующей "распаковкой в простом цикле",
но на строках такой алгоритм не работает вообще.
вообще не нужно путать частные и общие решения.
Многие алгоритмы прекрасно работают в однозадачных системах, и не работают на многозадачных.
Абсолютно любое решение имеет свои достоинства и недостатки, и их важно понимать, но не нужно осуждать!
Я не занимался осуждением, а занимался обсуждением.
К примеру, на той же сортировке при ограничении значений в 256 бит (то есть на символах) вполне
быстро и красиво решается с помощью 256 ячеечной таблицы с последующей "распаковкой в простом цикле",
но на строках такой алгоритм не работает вообще.
|
|
|
|
Добавлено: Пт ноя 27, 2009 13:26 |
|
|
|
|
|
Заголовок сообщения: |
|
|
|
WingLion писал(а): А требование иметь при этом минимум 16Гб памяти при 32-хбитных указателях никак не смущает?
Какие еще требования? И чем они обусловлены? +1 байт на указатель - для этого нужно 16 гигабайт памяти?
[quote="WingLion"]А требование иметь при этом минимум 16Гб памяти при 32-хбитных указателях никак не смущает?[/quote]
Какие еще требования? И чем они обусловлены? +1 байт на указатель - для этого нужно 16 гигабайт памяти?
|
|
|
|
Добавлено: Пт ноя 27, 2009 11:27 |
|
|
|
|
|
Заголовок сообщения: |
|
|
|
VoidVolker писал(а): во время работы программы можно при минимальных потерях производительности
А требование иметь при этом минимум 16Гб памяти при 32-хбитных указателях никак не смущает?
[quote="VoidVolker"]во время работы программы можно при минимальных потерях производительности[/quote]
А требование иметь при этом минимум 16Гб памяти при 32-хбитных указателях никак не смущает?
|
|
|
|
Добавлено: Пт ноя 27, 2009 08:16 |
|
|
|
|
|
Заголовок сообщения: |
|
|
|
Алгоритм chess'а достаточно легко адаптировать под "неизменение" просто введя "промежуточные" адреса, т.е. расположить указатели в новых адресах(переменных), и упорядочивать уже массив с этими новыми адресами. Но это оптимальнее делать на более ранней стадии работы программы - при определении самих первичных указателей. Или, что еще лучше, в структуре по указателю ввести дополнительный байт для флага. Т.о. во время работы программы можно при минимальных потерях производительности достаточно быстро обрабатывать эти самые массивы указателей. А для многопоточности - можно использовать дополнительные биты в поле флага. Так что считаю это решение наиболее эффективным.
Алгоритм chess'а достаточно легко адаптировать под "неизменение" просто введя "промежуточные" адреса, т.е. расположить указатели в новых адресах(переменных), и упорядочивать уже массив с этими новыми адресами. Но это оптимальнее делать на более ранней стадии работы программы - при определении самих первичных указателей. Или, что еще лучше, в структуре по указателю ввести дополнительный байт для флага. Т.о. во время работы программы можно при минимальных потерях производительности достаточно быстро обрабатывать эти самые массивы указателей. А для многопоточности - можно использовать дополнительные биты в поле флага. Так что считаю это решение наиболее эффективным.
|
|
|
|
Добавлено: Пт ноя 27, 2009 00:23 |
|
|
|
|
|
Заголовок сообщения: |
|
|
|
Если нельзя трогать изначальный массив (кстати, почему), то алгоритм может быть, кажется, только таким (или я что-то не понимаю): брать по очереди каждый элемент от начала и проверять, есть ли он же раньше в массиве, если нет - он кладётся "следующим" в новую структуру [результат-массив] , дойдя до конца, цикл прекращается. Зачем, для каких случаев нужнв реентерабельность?
Если нельзя трогать изначальный массив (кстати, почему), то алгоритм может быть, кажется, только таким (или я что-то не понимаю): брать по очереди каждый элемент от начала и проверять, есть ли он же раньше в массиве, если нет - он кладётся "следующим" в новую структуру [результат-массив] , дойдя до конца, цикл прекращается. Зачем, для каких случаев нужнв реентерабельность?
|
|
|
|
Добавлено: Чт ноя 26, 2009 23:56 |
|
|
|
|
|
Заголовок сообщения: |
|
|
|
chess писал(а): Для меня никаких дебрей нет. Набираю SEE clean. Не вижу call-ов. Кроме того определение можно написать на ассемблере - код будет проще и быстрее. Кроме того можно чуть изменить формирование словарной статьи с введением доп. поля или флага. Вообщем вариантов как всегда много. мы вообще говорим о разном. Просто совсем без разницы что показывает SEE. важно, что трогать данные по указанным адресам нельзя(однако я просто не подумал об этом при написании ТЗ). chess писал(а): Можете привести хотя бы один такой случай - если не трудно.
не будет работать на больших адресах адресах
не реентерабельно
но опять же, это не претензия.
[quote="chess"]Для меня никаких дебрей нет. Набираю SEE clean. Не вижу call-ов. Кроме того определение можно написать на ассемблере - код будет проще и быстрее. Кроме того можно чуть изменить формирование словарной статьи с введением доп. поля или флага. Вообщем вариантов как всегда много.[/quote] мы вообще говорим о разном. Просто совсем без разницы что показывает SEE. важно, что трогать данные по указанным адресам нельзя(однако я просто не подумал об этом при написании ТЗ).
[quote="chess"]Можете привести хотя бы один такой случай - если не трудно.[/quote]
не будет работать на больших адресах адресах
не реентерабельно
но опять же, это не претензия.
|
|
|
|
Добавлено: Чт ноя 26, 2009 21:59 |
|
|
|
|
|
Заголовок сообщения: |
|
|
|
mOleg писал(а): тут мы сразу уходим в дебри. Для меня никаких дебрей нет. Набираю SEE clean. Не вижу call-ов. Кроме того определение можно написать на ассемблере - код будет проще и быстрее. Кроме того можно чуть изменить формирование словарной статьи с введением доп. поля или флага. Вообщем вариантов как всегда много. mOleg писал(а): все замечания сводятся лишь к тому, что ваш код будет работать в ограниченном количестве случаев.
Можете привести хотя бы один такой случай - если не трудно.
[quote="mOleg"]тут мы сразу уходим в дебри.[/quote] Для меня никаких дебрей нет. Набираю SEE clean. Не вижу call-ов. Кроме того определение можно написать на ассемблере - код будет проще и быстрее. Кроме того можно чуть изменить формирование словарной статьи с введением доп. поля или флага. Вообщем вариантов как всегда много. [quote="mOleg"]все замечания сводятся лишь к тому, что ваш код будет работать в ограниченном количестве случаев. [/quote]
Можете привести хотя бы один такой случай - если не трудно.
|
|
|
|
Добавлено: Чт ноя 26, 2009 21:17 |
|
|
|
|
|
Заголовок сообщения: |
|
|
|
chess писал(а): Тут не надо путать адреса форт-слов входящих в определение слова clean и кодовое тело этого слова. Это кодовое тело не имеет ссылок (сall) на входящие в него слова(инлайн подстановки). тут мы сразу уходим в дебри. Инлайн подстановки - это такой трюк, их не имеет рассматривать вообще в этой теме. Лучше оставаться в рамках б\м классического шитого кода (то есть как минимум набора CALL вызовов и данных между ними). chess писал(а): Остальные замечания не понял. все замечания сводятся лишь к тому, что ваш код будет работать в ограниченном количестве случаев. chess писал(а): Что разве потоки не могут разделять общий словарь?
они его и разделяют.
[quote="chess"]Тут не надо путать адреса форт-слов входящих в определение слова clean и кодовое тело этого слова. Это кодовое тело не имеет ссылок (сall) на входящие в него слова(инлайн подстановки).[/quote] тут мы сразу уходим в дебри. Инлайн подстановки - это такой трюк, их не имеет рассматривать вообще в этой теме. Лучше оставаться в рамках б\м классического шитого кода (то есть как минимум набора CALL вызовов и данных между ними).
[quote="chess"]Остальные замечания не понял.[/quote] все замечания сводятся лишь к тому, что ваш код будет работать в ограниченном количестве случаев.
[quote="chess"]Что разве потоки не могут разделять общий словарь?[/quote]
они его и разделяют.
|
|
|
|
Добавлено: Чт ноя 26, 2009 18:28 |
|
|
|
|
|
Заголовок сообщения: |
|
|
|
mOleg писал(а): они не исполняются во время работы вашего решения, я говорил о тех, которые исполняются. к примеру, создается массив указалелей на все определения, используемые в определении слова clean (этакий вариант декомпиляции), затем этот список надо почистить от повторов.
Тут не надо путать адреса форт-слов входящих в определение слова clean и кодовое тело этого слова.
Это кодовое тело не имеет ссылок (сall) на входящие в него слова(инлайн подстановки).
Поэтому в этом смысле слово clean будет работать в (спф) корректно. Для других фортов можно его написать на ассме.
К слову, вот код
Код: : S1 ( n -- n ) >R ['] R> DUP @ 0 AND SWAP ! R> ;
Вроде полностью искажаем код слова R>, ан нет - все работает, так как в кодовое тело слова S1 код (call R>) не попадет.
Остальные замечания не понял.
Что разве потоки не могут разделять общий словарь?
Адреса словарных статей для АПИ функций отрицательные?
А вобщем я воспринял эту задачу просто как задачу, а не как что-то, имеющее практический смысл.
[quote="mOleg"]они не исполняются во время работы вашего решения, я говорил о тех, которые исполняются. к примеру, создается массив указалелей на все определения, используемые в определении слова clean (этакий вариант декомпиляции), затем этот список надо почистить от повторов. [/quote]
Тут не надо путать адреса форт-слов входящих в определение слова [b]clean[/b] и кодовое тело этого слова.
Это кодовое тело не имеет ссылок (сall) на входящие в него слова(инлайн подстановки).
Поэтому в этом смысле слово [b]clean[/b] будет работать в (спф) корректно. Для других фортов можно его написать на ассме.
К слову, вот код
[code]: S1 ( n -- n ) >R ['] R> DUP @ 0 AND SWAP ! R> ;[/code]
Вроде полностью искажаем код слова 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.
[quote="chess"]mOleg писал(а):замечательно, давайте представим, что мы взяли адреса всех исполняемых в Форт-системе слов... Ну в последнем моем посте я уже брал несколько адресов форт-слов для примера.[/quote] они не исполняются во время работы вашего решения, я говорил о тех, которые исполняются. к примеру, создается массив указалелей на все определения, используемые в определении слова clean (этакий вариант декомпиляции), затем этот список надо почистить от повторов.
[quote="chess"]Многопоточность в 99% случаев достаточна для решения задач без компиляции во время исполнения. А в этом случае запретов на использование в многопоточных программах нет.[/quote] если используются глобальные адреса, а в нашем случае это так, то проблема та же, что с глобальными переменными. (то есть в случае работы двух clean в паралельных потоках на разных, частично перекрвающихся, наборах ссылок).
[quote="chess"]Отрицательные адреса(в смысле отриц-х данных) для оперативной памяти на самом деле долго будут отсутствовать даже в 32 разрядной ОС. К слову я уже давно использую 64-разрядную Windows, да и Linux-64 давно есть.[/quote]
ну, адреса АПИ функций как раз отрицательные в WINXP, так как располагаюстся с тарших 2Гб ОЗУ (раз)
а что делать, если разрядность 16 бит у микроконтроллера?
Имхо, я не спорю, решение оригинальное, но оно не применимо в общем случае, как и первый вариант VoidVolker-а, с использованием HERE.
|
|
|
|
Добавлено: Чт ноя 26, 2009 09:02 |
|
|
|
|
|
Заголовок сообщения: |
|
|
|
тогда уж надо идею дальше развивать!
зачем нам однобайтовые "флаги", ведь достаточно знать, присутствует число или нет, то есть одного бита (экономия в 32 раза!)
Но и это не все, т.к. наверняка адреса будут раскиданы не равномерно по адресному пространству, а некими групками,
а это означает, что можно сделать таблицу двухуровневой (на первом уровне куски, к примеру размером в мегабайт),
а на следующем уровне адресация внутри мегабайта! Думая дальше понимаем, что можно вобщем-то этой фигней не заниматься, а использовать бинарные деревья, ведь поиск в них очень даже по скорости не плохой, причем, нет необходимости им быть сбалансированными, впрочем, на больших массивах АВЛ деревья будут очень даже не плохи. Еще одно достоинство у бинарных деревьев, что адреса могут группироваться как угодно!
тогда уж надо идею дальше развивать!
зачем нам однобайтовые "флаги", ведь достаточно знать, присутствует число или нет, то есть одного бита (экономия в 32 раза!)
Но и это не все, т.к. наверняка адреса будут раскиданы не равномерно по адресному пространству, а некими групками,
а это означает, что можно сделать таблицу двухуровневой (на первом уровне куски, к примеру размером в мегабайт),
а на следующем уровне адресация внутри мегабайта! Думая дальше понимаем, что можно вобщем-то этой фигней не заниматься, а использовать бинарные деревья, ведь поиск в них очень даже по скорости не плохой, причем, нет необходимости им быть сбалансированными, впрочем, на больших массивах АВЛ деревья будут очень даже не плохи. Еще одно достоинство у бинарных деревьев, что адреса могут группироваться как угодно!
:)) :)) :))
|
|
|
|
Добавлено: Чт ноя 26, 2009 06:44 |
|
|
|
|
|
Заголовок сообщения: |
|
|
|
А не проще ли использовать для меток использованных указателей не адресное пространство самих указателей, а отдельный массив?
Для 32-хбитных адресных указателей нужен массив из 2<sup>32</sup> бит = 2<sup>27</sup> 32-хразрядных слов, т.е. ~512 мегабайт.
При ограничении на величину адресов объем, разумеется, уменьшится.
А не проще ли использовать для меток использованных указателей не адресное пространство самих указателей, а отдельный массив?
Для 32-хбитных адресных указателей нужен массив из 2<sup>32</sup> бит = 2<sup>27</sup> 32-хразрядных слов, т.е. ~512 мегабайт.
При ограничении на величину адресов объем, разумеется, уменьшится.
|
|
|
|
Добавлено: Чт ноя 26, 2009 06:27 |
|
|
|
|
|
Заголовок сообщения: |
|
|
|
mOleg писал(а): замечательно, давайте представим, что мы взяли адреса всех исполняемых в Форт-системе слов... Ну в последнем моем посте я уже брал несколько адресов форт-слов для примера. mOleg писал(а): (ваш вариант, на сколько я понимаю однопоточный и не будет работать, если адреса будут использоваться собственные, к тому же допущение о невозможности отрицательных адресов тоже плохое, имхо).
Многопоточность в 99% случаев достаточна для решения задач без компиляции во время исполнения. А в этом случае запретов на
использование в многопоточных программах нет.
Отрицательные адреса(в смысле отриц-х данных) для оперативной памяти на самом деле долго будут отсутствовать даже в 32 разрядной ОС. К слову я уже давно использую 64-разрядную Windows, да и Linux-64 давно есть.
[quote="mOleg"]замечательно, давайте представим, что мы взяли адреса всех исполняемых в Форт-системе слов... [/quote] Ну в последнем моем посте я уже брал несколько адресов форт-слов для примера. [quote="mOleg"](ваш вариант, на сколько я понимаю однопоточный и не будет работать, если адреса будут использоваться собственные, к тому же допущение о невозможности отрицательных адресов тоже плохое, имхо). [/quote]
Многопоточность в 99% случаев достаточна для решения задач без компиляции во время исполнения. А в этом случае запретов на
использование в многопоточных программах нет.
Отрицательные адреса(в смысле отриц-х данных) для оперативной памяти на самом деле долго будут отсутствовать даже в 32 разрядной ОС. К слову я уже давно использую 64-разрядную Windows, да и Linux-64 давно есть.
|
|
|
|
Добавлено: Ср ноя 25, 2009 21:19 |
|
|
|
|