Доброе утро, Антон! Я кое-что не понял про оценку сложности:
«В алгоритме близнецов все выделяемые куски имеют размер 2^n. Выражение помещается посередине нового куска, а справа и слева естественным образом получается запас по месту. При конкатенации, если этой дырки рядом с одним из выражений достаточно, то копируется только одно из выражений, а новая память не выделяется. Например, если выражение длины N строится дописыванием в конец/начало по одному терму, то это требует O(log N) аллокаций (амортизированная стоимость O(1)).» Но ведь стоимость аллокации для близнецового метода практически константная, зачем её считать? Имеет значение стоимость присваивания значения. Для близнецового метода и размещения куска посередине наилучший случай — размер куска, равный 2^n+1 — слева и справа дырки будут иметь длину 2^n/2 (ну, одна — 2^n/2, вторая — 2^n/2−1, не суть). Соответственно, к такому куску можно с каждой стороны приписать (2^n)/2 термов без перераспределения. Наихудший случай — кусок размером 2^n — любое приписывание 1 терма потребует реаллокации и копирования 2^n+1 термов (2^n было и ещё 1, который мы приписали). Если мы приписываем термы, например, в начало, и начинаем с наилучшего случая (2^n+1, дырка имеет длину 2^n/2), то мы сможем приписать по одному терму 2^n/2 раз до перераспределения. Перераспределение потребует 2^n/2 + 2^n + 1 операций присваивания, в новом куске обе дырки будут иметь длину уже 2^n/4. А это значит, что теперь мы сделаем только n^2/4 копирований. Продолжая в том же духе, получим, что приписывание к выражению длиной 2^n+1 термов 2^n раз по одному терму мы действительно выполним O(n) аллокаций, но с каждой из них будет сопряжено O(2^n) присваиваний. Действительно, пусть после очередной переаллокации у нас занято L ячеек, с обоих сторон имеем H=(2^n−L)/2 свободных ячеек — дырок. Тогда до следующей переаллокации мы выполним H присваиваний, сама переаллокация потребует присваивания L+H ячеек. Всего за один цикл будет выполнено L + 2×(2^n−L)/2 = 2^n присваиваний. За каждый цикл дырка уменьшается в два раза, значит, число циклов будет O(n). Таким образом, удлинение выражения длины L = 2^n+1 до L′=2^(n+1)+1 требует O(n×2^n) = O(L log L) присваиваний. Можно показать, что построение выражения длины L=2^n начиная с пустого также требует O(n×2^n) = O(L log L) присваиваний. Могу эти выкладки написать, если интересно. Для L≠2^n тоже будет O(L log L) (оценка снизу), тоже могу доказать, если кто-то мне не верит. Аллокаций, кстати, на самом деле потребуется O(log² L), логарифм в квадрате. Так что, если выражение длины N строится дописыванием в конец/начало по одному терму, то это потребует O(N log N) присваиваний (амортизированная стоимость O(log N)). Если бы дырок не было вообще, то потребовалось бы O(N) аллокаций и O(N²) присваиваний. Амортизированная стоимость — O(N). Если бы мы знали, что приписывание терма выполняется только в конец, то могли бы распределять память степенями двойки и размещать занятое место с начала. Количество аллокаций было бы O(log N), количество присваиваний O(N), амортизированная стоимость — O(1). Так что близнецовый метод (вернее, распределение памяти по степеням двойки с размещением куска посередине) существенно лучше наивного варианта без дырок, но чуть хуже идеального варианта. «P.S. Помимо списков и массивов есть ещё потенциально интересные структуры данных для представления выражений. Например, rope <https://en.wikipedia.org/wiki/Rope_(data_structure)> и Finger tree <https://en.wikipedia.org/wiki/Finger_tree> , но серьёзно для рефальского применения их никто не исследовал, насколько я знаю.» К слову, в той же задаче — построении строки длиной N путём последовательного приписывания термов по одному — обе упомянутые структуры данных потребуют O(N log N) времени, поскольку приписывание одного символа в обоих видах строк требует O(log N) времени. Я когда-то давал на курсовой проект задачу — реализовать Простой Рефал с использованием rope’ов для представления объектных выражений. Студент не осилил сделать, задача оказалась слишком сложной для курсового (я по неопытности не смог оценить объём работы). Поставили тройку и отпустили. Rope и Finger tree требуют для конкатенации двух строк логарифмическое время. Про Finger tree не знаю точную оценку, rope выполняет конкатенацию за O(|log M − log N|) времени. Интересно оценить среднее время конкатенации для массивного представления и близнецового метода, но для этого нужно знать распределение длин строк и размеров дырок. С уважением, Александр Коновалов From: Александр Коновалов a.v.konovalov87_AT_mail.ru <refal@botik.ru> Sent: Tuesday, February 12, 2019 12:19 AM To: refal@botik.ru Subject: RE: Рефал Плюс – Was: Синтаксический анализ в Рефале Добрый вечер, Антон! «В алгоритме близнецов все выделяемые куски имеют размер 2^n. Выражение помещается посередине нового куска, а справа и слева естественным образом получается запас по месту. При конкатенации, если этой дырки рядом с одним из выражений достаточно, то копируется только одно из выражений, а новая память не выделяется. Например, если выражение длины N строится дописыванием в конец/начало по одному терму, то это требует O(log N) аллокаций (амортизированная стоимость O(1)).» Снимаю шляпу! Красивейшее решение реализации дырок! Сугубо в духе ТРИЗ. А вот меня давно интересует сборка мусора для массивного представления. Ведь может оказаться, что от большого когда-то массива-объектного выражения используется только небольшой диапазон. Как в этом случае красиво и эффективно сделать сборку мусора? Я не знаю. Пример: $ENTRY Go { = <F <Select '10 000 букв Б (ВВВ) 10 000 букв Г [ДДДД] 10 000 букв Е'>>; } Select { e.X = (<Select1 e.X>) (<Select2 e.X>); } Select1 { e.L '(' e.M ')' e.R = e.M; } Select2 { e.L '[' e.M ']' e.R = e.M; } F { … } По факту в функцию F передаются строки 'ВВВ' и 'ДДДД', но они являются поддиапазонами строки длиной более 30 тыс. символов. А значит, десятки килобайт памяти будут теряться (если кому-то килобайты кажутся маленькими, я могу написать ещё несколько ноликов). Можно сказать: при вырезании поддиапазона длины k << L он будет всегда копироваться. Контрпример: $ENTRY Go { = <F <Select '1 000 000 букв Ѣ'>>; } Select { e.X , e.X : e.Prefix e.Suffix , e.Prefix : s.1 s.2 s.3 s.4 s.5 s.6 , s.X : t.First e.Tail = (e.Prefix) <Select e.Tail>; e.X = (e.X); } F { … } Здесь строится почти миллион подстрочек, состоящих из 'ѢѢѢѢѢѢ', но все они перекрываются. Если для выбора коротких поддиапазонов мы будем всегда копировать, расход памяти увеличится в 6 раз. Так что нужен алгоритм сборки мусора, который может анализировать перекрывающиеся участки. И делать это эффективно. С уважением, Александр Коновалов P.S. Поменял тему. Надеюсь, письмо повиснет на нужной ветке в архиве. From: Anton Orlov orlovan_AT_gmail.com [mailto:refal@botik.ru] Sent: Monday, February 11, 2019 9:39 PM To: refal@botik.ru <mailto:refal@botik.ru> Subject: Re: Синтаксический анализ в Рефале Добрый день! On Mon, Feb 11, 2019 at 12:50 PM Arkady Klimov arkady.klimov_AT_gmail.com <http://arkady.klimov_AT_gmail.com> <refal@botik.ru <mailto:refal@botik.ru> > wrote: Может ли кто ответить на такие вопросы по реализации Рефал+ на C++ (в статье они не обсуждается - не тот уровень абстракции): 1.Какая организована работа с памятью? Какой менеджер памяти используется? Свой или каждый новый чанк через malloc запрашивается? Сделан свой аллокатор по алгоритму близнецов, описанному Кнутом (https://en.wikipedia.org/wiki/Buddy_memory_allocation). Это делал Андрей Слепухин. 2.Используются ли счетчики ссылок? Или полная сборка мусора время от времени? Какой сборщик мусора? Используются счётчики ссылок. Полной сборки мусора нет, поэтому память может течь (например, возможны циклы через ящики). Сборка мусора была в планах, но так и не была реализована (на практике надобность в ней не ощущалась). 3.Есть ли версия конкатенации inplace (когда память для выражения взята "с запасом")? Андрей уже ответил частично. В алгоритме близнецов все выделяемые куски имеют размер 2^n. Выражение помещается посередине нового куска, а справа и слева естественным образом получается запас по месту. При конкатенации, если этой дырки рядом с одним из выражений достаточно, то копируется только одно из выражений, а новая память не выделяется. Например, если выражение длины N строится дописыванием в конец/начало по одному терму, то это требует O(log N) аллокаций (амортизированная стоимость O(1)). Антон P.S. Помимо списков и массивов есть ещё потенциально интересные структуры данных для представления выражений. Например, rope (https://en.wikipedia.org/wiki/Rope_(data_structure)) и Finger tree (https://en.wikipedia.org/wiki/Finger_tree), но серьёзно для рефальского применения их никто не исследовал, насколько я знаю. Буду благодарен за разъяснения. Аркадий пн, 11 февр. 2019 г. в 11:12, Sergei M. Abramov abram_AT_botik.ru <refal@botik.ru <mailto:refal@botik.ru> >: > Замысловатый ответ ни о чем. Так какой результат, если есть статьи, > то ссылки где?. http://www.botik.ru/PSI/RCMS/publications/publications.html А далее Гуугл "site:www.botik.ru/PSI/RCMS/publications <http://www.botik.ru/PSI/RCMS/publications> Рефал Плюс" И там сразу находим: http://www.botik.ru/PSI/RCMS/publications/publ-texts/04-Abramov-Novyj-podkhod-p-373.pdf С уважением, Абрамов С.М. ab...@botik.ru <mailto:ab...@botik.ru> мобильный: +7(903)2928308 -- _______________ С уважением, Аркадий Климов, с.н.с. ИППМ РАН, +7(499)135-32-95 +7(916)072-81-48
