Здравствуйте, Klapaucius, Вы писали:
K>Нет, я говорю о том, что для того, чтобы язык был максимально пригодным для решения задач и минимально неудобным для пользователя он должен быть формализован "в угоду" решаемым проблемам
А должен ли он вообще быть предельно формализован? Это совсем не очевидно, однако. Он должен быть удобен, все остальное это следствия и компромиссы.
K>Все дело в том, что для кресла удобство задницы — основная задача.
А для языка — основная задача это удобство разработчика. В этом его единственный смысл существования. А никак не в формализации мышления разработчика.
K> В чем удобство для человека в близости к железу мне не понятно
Мне тоже непонятно, при чем тут вообще близость к железу. Я везде речь вел лишь про близость к другой стороне, к мышлению.
Здравствуйте, hattab, Вы писали:
H>Вообще-то речь шла не о SL, а всего лишь о: H>
Сделать приложегние на С++ чтобы в нем было тесктовое поле ввода, которое крутится вокруг своей оси и в него можно вбивать текст. А в фоне этого поля ввода крутился какой-нибудь видеоролик.
H>Если у тебя есть варианты других юзкейсов (кроме презентационной пыли в глаза пионерок) этой хни -- в студию.
Не-не-не, коллега! Все началось с фразы H>Очевидно презентация это единственный юзкейс для подобной хни
По сути я докапываюсь до того, что ты так безоговорочно опустил нормальную технологию. Почитай про .Net Ria Services, например. Конкретно я использую SL для написания веб-частей, FieldTypes для MOSS 2007, то есть в корпоративном сегменте. Нормальный юзкейс?
Здравствуйте, Farsight, Вы писали:
H>>Вообще-то речь шла не о SL, а всего лишь о: H>>
Сделать приложегние на С++ чтобы в нем было тесктовое поле ввода, которое крутится вокруг своей оси и в него можно вбивать текст. А в фоне этого поля ввода крутился какой-нибудь видеоролик.
H>>Если у тебя есть варианты других юзкейсов (кроме презентационной пыли в глаза пионерок) этой хни -- в студию.
F>Не-не-не, коллега! Все началось с фразы H>>Очевидно презентация это единственный юзкейс для подобной хни
Еще раз: под "подобной хней" тут подразумевается не SL вообще, а вполне конкретный пример возможностей.
F>По сути я докапываюсь до того, что ты так безоговорочно опустил нормальную технологию.
Здравствуйте, Ночной Смотрящий, Вы писали:
K>>Нет, я говорю о том, что для того, чтобы язык был максимально пригодным для решения задач и минимально неудобным для пользователя он должен быть формализован "в угоду" решаемым проблемам НС>А должен ли он вообще быть предельно формализован?
Что значит "предельно формализован"? Любой язык — это формализм. Это задача может быть не формализована — заказчик делает в воздухе таинственные пассы руками и мычит. Может быть полностью формализована — написана программа, которая решает задачу. Процесс программирования — это процесс формализации задачи. После того, как задача формализована полностью — можно запустить компилятор и получить автомат, который эту задачу решает.
НС>Это совсем не очевидно, однако. Он должен быть удобен, все остальное это следствия и компромиссы.
Еще раз — удобен для решения задачи. например плюшевый молоток — он удобен, мягок, легок, безопасен. Но для работы не пригоден. Молоток металлический — пригоден для работы. А чтобы он был при этом более-менее удобен — ему делают ухватистую рукоятку, например. Так вот, языки не должны быть плюшевыми молотками. Они должны быть молотками металлическими. После этой иллюстрации моя мысль ясна?
K>>Все дело в том, что для кресла удобство задницы — основная задача. НС>А для языка — основная задача это удобство разработчика.
Для языка основная задача — написание понятных, хорошо поддерживаемых программ. Это может потребовать некоторых усилий на этапе изучения. потому, что простой язык приводит к написанию сложных программ. (сложный, по крайней мере, может приводить к написанию и простых и сложных) Например, брейнфак очень прост — его можно за минуту освоить. Но написать что-то на нем (про поддержку я уже и не говорю) — серьезный челлендж. Простой язык — это плюшевый молоток. Для работы он неудобен. Не нужно забывать о работе.
НС>В этом его единственный смысл существования. А никак не в формализации мышления разработчика.
Единственный смысл существования языка программирования высокого уровня — формализация мышления разработчика. Без этого он ни решить проблему не сможет — ни понять другого разработчика.
K>> В чем удобство для человека в близости к железу мне не понятно НС>Мне тоже непонятно, при чем тут вообще близость к железу. Я везде речь вел лишь про близость к другой стороне, к мышлению.
Ну да, все правильно. Как человек решает проблемы? Нужно ему, например посчитать площадь пола в комнате. Он возьмет формулу — S = a*b, потом подставит результаты измерений — 3*5 и применит умножение — 15. Этому в начальной школе учат.
Я сильно сомневаюсь, что он присвоит a ссылку на синглетон 3, b — ссылку на синглетон 5, а потом пошлет a сообщение {*,b}, присвоив результат переменной S.
... << RSDN@Home 1.2.0 alpha 4 rev. 1228>>
'You may call it "nonsense" if you like, but I'VE heard nonsense, compared with which that would be as sensible as a dictionary!' (c) Lewis Carroll
Здравствуйте, Klapaucius, Вы писали:
K>Что значит "предельно формализован"? Любой язык — это формализм. Это задача может быть не формализована — заказчик делает в воздухе таинственные пассы руками и мычит. Может быть полностью формализована — написана программа, которая решает задачу. Процесс программирования — это процесс формализации задачи. После того, как задача формализована полностью — можно запустить компилятор и получить автомат, который эту задачу решает.
Это очень узкий взгляд на разработку софта. Дело далеко не только в формализации, иначе бы полностью формальные задачи решались бы в полностью автоматическом режиме, а это далеко не так. У тебя за кадром остается, к примеру, борьба со сложностью и масса механизмов в том числе и в языках для этого.
Но суть даже не в этом. То, о чем я пытался сказать, это то, что формализация может быть в разных терминах, и вот уже набор этих терминов может быть сколь угодно близок или далек от тех терминов, в которых человек мыслит.
НС>>Это совсем не очевидно, однако. Он должен быть удобен, все остальное это следствия и компромиссы.
K>Еще раз — удобен для решения задачи.
Именно. Остается только понять, что чем меньше навыков и перестроек сознания требует язык, тем он удобнее.
K> например плюшевый молоток — он удобен, мягок, легок, безопасен. Но для работы не пригоден. Молоток металлический — пригоден для работы. А чтобы он был при этом более-менее удобен — ему делают ухватистую рукоятку, например. Так вот, языки не должны быть плюшевыми молотками. Они должны быть молотками металлическими. После этой иллюстрации моя мысль ясна?
Нет. Я не понимаю, как эта иллюстрация поясняет, почему язык должен навязывать какой то формализм, вместо того чтобы подстраиваться под мозги разработчика. Ты правильно сказал — рукоятку делают ухватистой, а не руку хирургическим путем перекраивают под молоток. Точно так же и язык должен минимальным образом требовать перестройки мозгов, а вместо этого сам под мозги перестраиваться.
K>Для языка основная задача — написание понятных, хорошо поддерживаемых программ.
Да нет. Это как раз таки задача разработчика. А задача языка — быть максимально удобным инструментом. Ключевое слово — удобным.
K> Это может потребовать некоторых усилий на этапе изучения.
И чем больше этих усилий, тем менее совершенен язык. В качестве иллюстрации — большая часть прогресса в системах управления автомобилях сосредоточена как раз таки в снижении требований к специфическим умениям водителя — АКПП, ABS, ESP, Tracking Control, Brake Assist, системы помощи при спуске и подъеме, парктроники и автоматические парковщики и т.п. Вот точно такой же прогресс нужен и в ЯВУ для промышленного применения, а не достижение рекордных характеристик в узком диапазоне любой ценой, навроде болидов Ф1.
K> потому, что простой язык приводит к написанию сложных программ
Тут сразу два заявления, нуждающихся в доказательствах. Во-первых, то, что удобный язык должен быть простым (C# удобнее С++ и проще в изучении, но сложнее). Во-вторых что простой язык приводит к написанию сложных программ.
K>. (сложный, по крайней мере, может приводить к написанию и простых и сложных) Например, брейнфак очень прост — его можно за минуту освоить.
Освоение языка, это не освоение его синтаксиса. Это наработка навыков по решению практических задач на нем. И с этой стороны брейнфак — очень сложный язык. И еще раз — не подменяй понятия. Я нигде не говорил про простой язык, я везде писал про удобный.
K>Единственный смысл существования языка программирования высокого уровня — формализация мышления разработчика. Без этого он ни решить проблему не сможет — ни понять другого разработчика.
Доказательства будут?
НС>>Мне тоже непонятно, при чем тут вообще близость к железу. Я везде речь вел лишь про близость к другой стороне, к мышлению.
K>Ну да, все правильно. Как человек решает проблемы? Нужно ему, например посчитать площадь пола в комнате. Он возьмет формулу — S = a*b, потом подставит результаты измерений — 3*5 и применит умножение — 15. Этому в начальной школе учат.
Это если у него инструмента нет. А если есть — включит какой нибудь лазерный измеритель и он ему посчитает сразу и площадь и объем. И это в реальном мире, где инструменты штука очень дорогая. В разработке софта инструмент обходится намного дешевле и имеет на много порядков большую сложность. Это, конечно, не только языка касается, но и языка в том числе.
А вот это 3*5, это уже навязанный способ решения задачи, не очень удобный для мозга, так как считает даже простую арифметику мозг очень медленно, со скоростью раненой черепахи.
Здравствуйте, WolfHound, Вы писали:
V>>Дерево — да, но дерево лишь абстракция. WH>Блин! Ты опять как тетерев токуешь. WH>Тут разговор про 2-3 дерево которое является частным случаем B дерева. Раньше в компиляторе было красно-черное дерево но он несколько медленней.
WH>И это конкретная структура данных, а никакая не абстракция.
Я просто делюсь своим (и не только) опытом по организации контейнера символов для нужд компиляции. Однородное общее дерево на все символы — неэффективно, хоть оно конкретно (с) красно-черное, хоть бинарное или 2-3. Тем более что разница м/у крсно-черным и двоичным (или 2-3) для этих нужд не должна быть так уж заметна, разве что различаться могут сами реализации по эффективности.
Нам же не просто символ найти надо, обычно есть несколько одноименных символов, но выбрать в текущем scope надо только один, вот и идет речь о том, чтобы операцию поиска символа объединить с выбором "правильного" его варианта. Тут еще есть такой интересный момент, что символы с более локальных по вложенности scope встречаются в коде чаще, т.е. для поиска нужного символа при такой организации обычно просматривается меньший объем данных.
И как уже говорил, учитывая обычно не очень большой объем символов в каждом конкретном scope, при моей схеме контейнера не принципиальна реализация хранилища символов для каждого отдельного scope.
Здравствуйте, vdimas, Вы писали:
V>Я просто делюсь своим (и не только) опытом по организации контейнера символов для нужд компиляции.
Странный у тебя опыт.
V>Однородное общее дерево на все символы — неэффективно,
Откуда дровишки? Или ты опять "прочитал" какую то умною статью?
V>Нам же не просто символ найти надо, обычно есть несколько одноименных символов, но выбрать в текущем scope надо только один, вот и идет речь о том, чтобы операцию поиска символа объединить с выбором "правильного" его варианта.
И в чем проблема?
V>Тут еще есть такой интересный момент, что символы с более локальных по вложенности scope встречаются в коде чаще, т.е. для поиска нужного символа при такой организации обычно просматривается меньший объем данных.
Понятие алгоритмический сложности знакомо?
Что такое время поиска Log(N) понимаешь?
Это значит что на миллион символов нам нужно 20 сравнений.
А столько никогда не бывает.
V>И как уже говорил, учитывая обычно не очень большой объем символов в каждом конкретном scope, при моей схеме контейнера не принципиальна реализация хранилища символов для каждого отдельного scope.
А давай ты посчитаешь сколько сравнений в среднем нужно для поиска символа в твоей схеме.
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
V>>Однородное общее дерево на все символы — неэффективно, WH>Откуда дровишки? Или ты опять "прочитал" какую то умною статью?
Изучал десятки исходников и ставил эксперименты на скорость. Разница где-то раза в 4 в среднем была. В самом худшем случае (когда в основном в коде используются глобальные символы) практически такая же эффективность как и в общем контейнере.
WH>Понятие алгоритмический сложности знакомо? Что такое время поиска Log(N) понимаешь? Это значит что на миллион символов нам нужно 20 сравнений. А столько никогда не бывает. WH>А давай ты посчитаешь сколько сравнений в среднем нужно для поиска символа в твоей схеме.
Начнем с того, что насчет логарифмической сложности ты не совсем прав. Для деревьев сложность колеблется от логарифмической для "идеального" распределения входных данных, до практически линейной при наихудшей сбалансированности построенного дерева. Строить и балансировать одновременно — опять же накладные расходы. И насчет миллионов символов... Это в твоей программе миллиона не будет, а во всех подключенных модулях современных библиотек под сотню тысяч уже набегает.
Эффект быстродействия в моем варианте уже объяснял — чаще всего в коде встречаются символы из более локальных scope, поэтому чем больше общее кол-во символов и чем "лучше" структурирована программа, тем сравнительно эффективней эта схема. Даже в наихудшем варианте, когда встречается символ из глобальной области видимости, я оперирую на порядки меньшим множеством символов — лишь теми, что видны из текущего scope и далее вверх по вложенности.
Здравствуйте, vdimas, Вы писали:
V>Изучал десятки исходников и ставил эксперименты на скорость. Разница где-то раза в 4 в среднем была. В самом худшем случае (когда в основном в коде используются глобальные символы) практически такая же эффективность как и в общем контейнере.
Покажи парочку.
Хочу посмотреть на то что они там делают.
А то у меня есть чувство что ты опять не разобрался о чем разговор.
V>Начнем с того, что насчет логарифмической сложности ты не совсем прав.
Я совсем прав.
Ибо я писал реализацию и знаю о чем говорю.
V>Строить и балансировать одновременно — опять же накладные расходы.
Вообще говоря вставка в несбалансированное дерево дороже.
А если это дерево еще и неизменяемое то вообще тушите свет.
V>И насчет миллионов символов... Это в твоей программе миллиона не будет, а во всех подключенных модулях современных библиотек под сотню тысяч уже набегает.
В любом случае 20 сравнений максимум.
V>Эффект быстродействия в моем варианте уже объяснял — чаще всего в коде встречаются символы из более локальных scope, поэтому чем больше общее кол-во символов и чем "лучше" структурирована программа, тем сравнительно эффективней эта схема.
Сколько сравнений в среднем. На вопрос ответь.
V>Даже в наихудшем варианте, когда встречается символ из глобальной области видимости, я оперирую на порядки меньшим множеством символов — лишь теми, что видны из текущего scope и далее вверх по вложенности.
Ты блин не поверишь.
Я тоже.
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, Ночной Смотрящий, Вы писали:
НС>Это очень узкий взгляд на разработку софта. Дело далеко не только в формализации, иначе бы полностью формальные задачи решались бы в полностью автоматическом режиме, а это далеко не так.
Вообще-то это именно так и есть, за некоторыми исключениями. Просто автоматическое решение часто требует неприемлимых затрат.
НС>У тебя за кадром остается, к примеру, борьба со сложностью.
Я именно о борьбе со сложностью и говорю. Борьба сложностью ведется с помощью добавления в язык средств абстракции и декомпозиции — т.е. за счет некоторого увеличения сложности языка.
Так со сложностью борятся не только в программировании, но и в физике, например, с помощью разработки и использования более мощных формальных языков. Разве есть какие-то другие способы борьбы со сложностью?
НС>Но суть даже не в этом. То, о чем я пытался сказать, это то, что формализация может быть в разных терминах, и вот уже набор этих терминов может быть сколь угодно близок или далек от тех терминов, в которых человек мыслит.
Человек или знает язык и тогда он мыслит на этом языке, терминами этого языка, или терминами языка не мыслит — и языка не знает. Человек вообще-то учится мыслить и изучает разные языки.
НС>Именно. Остается только понять, что чем меньше навыков и перестроек сознания требует язык, тем он удобнее.
Еще раз повторяю, изучается что-то для дальнейшего использования. И дальнейшее использование следует, по этой причине, из виду не упускать. Поэтому я и повторяю в который уже раз, что нужен минимакс. Легче всего — вообще ничего не учить, но тогда лубая задача — бесконечно сложна.
С другой стороны, изучение любого языка требует перестройки сознания. Для изучения ФП после тех формальных языков, которые человек осваивает в школе (и в ВУЗе, естественно) требуется меньшая перестройка сознания, чем для изучения ООП. Но, учитывая, что сознание большинства программистов уже соответствующим образом перестроено продвижение ФП связано с понятными сложностями. Я сразу и говорил, что большое число мыслящих категориями ООП программистов — серьезное преимущество ООП на данном этапе.
НС>Нет. Я не понимаю, как эта иллюстрация поясняет, почему язык должен навязывать какой то формализм, вместо того чтобы подстраиваться под мозги разработчика.
Чтобы мозги стали мозгами разработчика им уже пришлось основательно подстроится. И да, я согласен, чтоновая подстройка, да еще в возрасте, который на подстройки уже не очень рассчитан — это проблема. Но без подстройки мозгов не возможно ни развитие конкретного человека, ни общий прогресс. И профессию человек осваивает не с целью сберечь свои мозги девственными и неподстроенными, но с целью научиться решать определенный класс проблем.
НС>Ты правильно сказал — рукоятку делают ухватистой, а не руку хирургическим путем перекраивают под молоток.
Это неверная аналогия. Изменения не являются функцией руки, но являются функцией мозга одной из основных. Понятно, поэтому, желание сберечь руку от хирургического изменения, но желание сберечь мозг от выполнения его основной функции — непонятно. Т.е. вы предлагаете делатьтакие молотки, которыми не нужно учиться работать.
НС>Да нет. Это как раз таки задача разработчика. А задача языка — быть максимально удобным инструментом. Ключевое слово — удобным.
Ключевое здесь — удобным, для решения задач разработчика.
НС>И чем больше этих усилий, тем менее совершенен язык.
Т.е. все языки заведомо менее совершенны, чем брейнфак? Чудес не бывает. Конечно, язык должен быть прост, но не в ущерб эффективности и простоте решения задачи. Станок с ЧПУ требует большей квалификации, чем олдовайский каменный скребок — это неизбежная плата за производительность.
НС>Тут сразу два заявления, нуждающихся в доказательствах. Во-первых, то, что удобный язык должен быть простым (C# удобнее С++ и проще в изучении, но сложнее).
Говоря "простой", я подразумеваю "простой в изучении". А то, что "удобный" означает "простой в изучении" я посчитал вашей точкой зрения. Вывел из заявлений о минимизации подстраивания мозгов (т.е. обучения)
НС>Во-вторых что простой язык приводит к написанию сложных программ.
Я это обосновываю тем, что единственный способ борьбы со сложностью — внедрение в язык средств абстракции и декомпозиции, неизбежно усложняющих изучение языка. Да, мы таким образом перераспределяем сложность, но как показывает практика всех наук, использующих формальные языки, вполне приемлимым и выгодным для нас образом. В брейнфаке ситуация со средствами абстракции и декомпозиции совсем плохая — с соответствующими последствиями подтверждающими мои утверждения.
НС>Освоение языка, это не освоение его синтаксиса.
Ну разумеется это освоение его синтаксиса! Но не только. Это еще и освоение его семантики — что намного важнее.
НС>Это наработка навыков по решению практических задач на нем.
Это навыки, котрые имеют весьма небольшую языковую специфику. Поэтому можно научиться программировать вообще, а не на каком-то конкретном языке.
И практические задачи вы все-таки считаете имеющими значение? Я думал у нас спор "думать некогда — трясти надо" против "лучше день потерять — потом за пять минут долететь".
НС>Я нигде не говорил про простой язык, я везде писал про удобный.
Вы зато писали, что удобный — означает требующий наименьшей подстройки мозга. Из чего я сделал выводы изложенные выше.
K>>Единственный смысл существования языка программирования высокого уровня — формализация мышления разработчика. Без этого он ни решить проблему не сможет — ни понять другого разработчика. НС>Доказательства будут?
Ну, это практически — по определению. Языки программирования относятся к формальным языкам. То, что пока задача полностью не формализована программа не заработает — тоже довольно очевидно. Если бы можно было компилировать неформальные спецификации — программисты (те, кто спецификации формализуют) остались бы без работы. Да и проблемы с коммуникациями на неформальном языке хорошо демонстрируют почти все ветки на этом форуме не исключая и этой.
НС>Это если у него инструмента нет. А если есть — включит какой нибудь лазерный измеритель и он ему посчитает сразу и площадь и объем.
В качестве иллюстрации нужно приводить обязательно задачу, решение которой пока не найдено, что ли?
Инструмента этого когда-то вообще не было.
НС>В разработке софта инструмент обходится намного дешевле
Да я бы не сказал. Массовое тиражирование разработанного инструмента да, дешевле.
НС>А вот это 3*5, это уже навязанный способ решения задачи, не очень удобный для мозга, так как считает даже простую арифметику мозг очень медленно, со скоростью раненой черепахи.
Конечно навязанный. Отсутствием другого способа решения. Или считаете, что пример решения этой задачи в уме в ООП-стиле удобнее? Умножает человек, естественно, плохо. А вот подставляет и применяет вполне сносно. Лучше, чем пускает в уме стековую машину, например.
ДП вообще происходит от обычного способа решения формализованных проблем человеком с помощью ума, пера и бумаги. И придумано раньше, чем ИП. Просто на протяжении долгого времени для решения задач на машинах не годилось. Вот и пришлось мозгам программистов подстраиваться под триггеры. Всех остальных людей это, впрочем, совершенно не коснулось.
... << RSDN@Home 1.2.0 alpha 4 rev. 1228>>
'You may call it "nonsense" if you like, but I'VE heard nonsense, compared with which that would be as sensible as a dictionary!' (c) Lewis Carroll
Здравствуйте, vdimas, Вы писали:
V>Начнем с того, что насчет логарифмической сложности ты не совсем прав. Для деревьев сложность колеблется от логарифмической для "идеального" распределения входных данных, до практически линейной при наихудшей сбалансированности построенного дерева. Строить и балансировать одновременно — опять же накладные расходы.
Вообще-то не балансируемые автоматически деревья на практике не применяют, чтобы ключи строить.
V>И насчет миллионов символов... Это в твоей программе миллиона не будет, а во всех подключенных модулях современных библиотек под сотню тысяч уже набегает.
А ты, что все символы помещаешь всюду?
В таблице хранится только информация о контексете: "Какие пространства имен открыты?", "Какое пространство имен текущее?", "Какой тип текущий?". Остальное вычисляется "на ходу".
V>Эффект быстродействия в моем варианте уже объяснял — чаще всего в коде встречаются символы из более локальных scope, поэтому чем больше общее кол-во символов и чем "лучше" структурирована программа, тем сравнительно эффективней эта схема. Даже в наихудшем варианте, когда встречается символ из глобальной области видимости, я оперирую на порядки меньшим множеством символов — лишь теми, что видны из текущего scope и далее вверх по вложенности.
А когда ты помещаешь в этот локальный котнекст что-то, то где ты и как ты его ищешь?
Собственно, то что ты описываешь называется "оркужение". В от оно и может формироваться из деревьев. Одно дерево описывает глобальный контекст. Второе более локальный. Третье еще более локальный. Второе дерево получается из первого. Третье из второго.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, Klapaucius, Вы писали:
K>Замена персистентной структуры данных на неперсистентную в том случае, когда версионность использовалась, всегда будет связано с серьезными сложностями.
Может "версионной"?
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, vdimas, Вы писали: V>Для своего интерпретатора Схемы
Кстати, раз ваша дискуссия еще продолжается. Joe Marshall разрабатывает интерпретатор схемы (насколько я понял — клон mit scheme) для .net. И несколько его последних постов посвящено environment-ам. Не столько алгоритмическим вопросам (которыми заняты вы) сколько концептуальным — но почитать все равно интересно.
Здравствуйте, WolfHound, Вы писали:
V>>Эффект быстродействия в моем варианте уже объяснял — чаще всего в коде встречаются символы из более локальных scope, поэтому чем больше общее кол-во символов и чем "лучше" структурирована программа, тем сравнительно эффективней эта схема. WH>Сколько сравнений в среднем. На вопрос ответь.
Да понятно куда ты пытаешься клонить. Если м/у всеми отдельными деревьями (узлами у меня) количеством K поровну поделить все символы N, то будет K*log(N/K), что как бы несколько больше исходного log(N). Только вот в реальности эта формула моего случая никуда не годится, т.к. чем ближе scope, тем больше вероятность, что сивол будет именно там. Сколько в среднем зависит наверно от языка программирования, но для эффективных реализаций Лиспа и Схемы такой подход организации окружения — самый популярный (ибо вложенность замыканий обычно высока).
Могу лишь выдать некоторые соображения, попробуй прикинуть сам:
— наибольшее кол-во (N1) символов лежит в глобальном scope (для языков под дотнет к ним приравнены символы из импортируемых неймспейсов), поэтому затраты на поиск такого символа в последнем узле (наихудший случай) можно грубо рассматривать как log(N1)+K*log((N-N1)/K) (1), согласен, что при любом N1 и K это все еще больше, чем log(N).
— для языков типа C#, из этого глобальной области видимости поступали в основном типы, и использовались весьма нечасто (при объявлении символа, например). Предположу, что для тех символов, что мы ищем как член типа (через точку записали в C#) должна быть своя "таблица" поиска.
— для более локальных символов в самом худшем случа будет K*log((N-N1)/K), в самом лучшем, вернее в самом ожидаемом: log((N-N1)/K), в среднем можно было сказать, что K*log((N-N1)/K)/2, но это не так ввиду наиболее вероятного ожидаемого варианта, так что скорее где-то log(K)*log((N-N1)/K) (2)
— ну и в среднем затраты будут где-то м/у {1} и {2}, причем гораздо ближе к {2} в подавляющем большинстве участков кода.
Поэтому, чем меньше символов в каждой локальной области видимости, и чем чаще они используются относительно глобальных, тем эффективнее моя схема. Для Лиспа/Схемы — самый идеальный вариант.
Повторюсь, в этой структуре просто смешные накладные расходы на создание "версий" окружения, ибо не требуется перестраивать все дерево для каждой области видимости. Поэтому сравнивать надо не только кол-во сравнений, но и стоимость создания версий для каждой области видимости.
V>>Даже в наихудшем варианте, когда встречается символ из глобальной области видимости, я оперирую на порядки меньшим множеством символов — лишь теми, что видны из текущего scope и далее вверх по вложенности. WH>Ты блин не поверишь. WH>Я тоже.
И замерял скорость пересоздания всего дерева для каждой области видимости относительно скорости поиска? Ну вот у нас локальный if какой-нить, внутри пусть 2-3 символа вводятся и раз 6 они встречаются в вычислениях; сколько времени займет 3 пересоздания дерева относительно 6-х последующих поисков при общем кол-ве всех видимых символов в районе 10тыс? А то может ты вовсе зря про кол-во сравнений спрашиваешь.
Я уже молчу о том, что у тебя хранятся полные версии твоего дерева для каждой области видимости в стеке разбора. При динамическом исполнении Лиспа/Схемы эти деревья строятся и работают в run-time, поэтому эффективность всех операций, в т.ч. операции создания "версии" тоже играет роль и от того создание версии окружения не требует вообще никаких перевыделений.
Это у тебя в компиляторе некритично, можно полные копии плодить. Однако, уменьшив на многие порядки объем пересоздаваемых промежуточных данных ты можешь улучшить эффективность еще и коссвено, за счет меньшего напряга GC например.
Здравствуйте, VladD2, Вы писали:
VD>Собственно, то что ты описываешь называется "оркужение".
Именно об этом и говорил, предлагая посмотреть на практику хранения символов в Лиспе/Схеме. Ибо очень дешево создаются версии этого окружения.
Вот у тебя реальный код:
Здравствуйте, Klapaucius, Вы писали:
K>Здравствуйте, VladD2, Вы писали:
K>>>персистентной структуры VD>>Может "версионной"?
K>Это одно и то же.
С чего бы это? Персистентный — означает сохраняемый в некое хранилище. Версионный — поддерживающий разные версии. Свойства весьма независимые. Может быть и версионность не персистентных объектов.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, vdimas, Вы писали:
V>Именно об этом и говорил, предлагая посмотреть на практику хранения символов в Лиспе/Схеме. Ибо очень дешево создаются версии этого окружения. V>Вот у тебя реальный код:
V>
V>Две независимые переменные i в разных областях видимости, и ради каждой пересоздается полная версия таблицы символов. Не перебор ли?
Нет никакой практики лиспа. Есть неизменяемые структуры данных. В том числе не изменяемые деревья которые в лиспе реализуются на базовых типах данных. Собственно о применении неизменяемых деревьев Вольфхаунд тебе и говорил.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
