crypt of decay - про редактор и деревья [entries|archive|friends|userinfo]
ketmar

[ userinfo | ljr userinfo ]
[ archive | journal archive ]

про редактор и деревья [Apr. 26th, 2017|09:10 pm]
Previous Entry Add to Memories Tell A Friend Next Entry
b+tree — хорошая структура данных. особенно хороша она становится тогда, когда из неё выкидываешь требование «быть отсортированым». в таком виде она прекрасно подходит для всовывания в страницы памяти фиксированого размера, и для быстрого поиска страницы по позиции в тексте.
Linkmeow!

Comments:
[User Picture]
From:[info]steinkrauz
Date:April 26th, 2017 - 09:48 pm
(Link)
Наверное как всегда туплю, но B+ дерево без сортировки это не будет по сути список строк на стероидах?
[User Picture]
From:[info]ketmar
Date:April 27th, 2017 - 07:40 am
(Link)
он и будет, тащемта. но оно и с сортировкой почти то же самое ведь: как было ускорение поиска путём деления большого массива на части поменьше, так и осталось. а сортировка там нужна для того, чтобы найти место, куда вставлять элемент. моё «несортированое» дерево тоже, конечно, сортировано по позиции в тексте, просто ключи хранят не саму позицию, а количество символов в ребёнке.
[User Picture]
From:[info]ketmar
Date:April 27th, 2017 - 07:47 am
(Link)
то есть, ты не тупишь, ты абсолютно прав: я просто продал немного памяти за быстродействие. сейчас у меня там кэш, в котором хранится смещение до начала строки от начала текста. поиск O(log n), но медленное обновление. и плохо ложится в выделение памяти фиксироваными страницами.

а b+ — это почти то же самое, только список получается побит на части, и с частями можно работать отдельно. поиск чуть медленней (теперь там хранятся длины, и надо прощёлкать всю страницу линейно), но зато самортизировалось обновление, да ещё и в страницы ложится как родное.

потому финальная идея такая, чтобы все выделения памяти в редакторе шли строго постранично, для всего вообще. чтобы я нахрен прекратил думать о фрагментации памяти как таковой. понятно, за это я заплачу тем, что некоторые страницы будут использоваться не полностью, но ок, меня устраивает. зато есть другие преимущества — типа того, что не нужно будет делать memcpy() на 210MB+210*2MB данных, если надо подвинуть дырку вставки из конца в начало.
[User Picture]
From:[info]ketmar
Date:April 27th, 2017 - 07:52 am
(Link)
проблема, в общем, лишь в том, что в 4КБ влазит слишком много ключей. то есть, ноды дерева слишком большие. придётся, видимо, делать субаллокатор.
From:(Anonymous)
Date:April 26th, 2017 - 10:17 pm
(Link)
Где скачать твой редактор?
[User Picture]
From:[info]ketmar
Date:April 27th, 2017 - 07:54 am
(Link)
зачем?
From:(Anonymous)
Date:April 27th, 2017 - 08:14 am
(Link)
Интересно.
[User Picture]
From:[info]ketmar
Date:April 27th, 2017 - 08:34 am
(Link)
про интересные алгоритмы я рассказываю в бложеге. а реализацию ты всё равно собрать не сможешь. а если сможешь — то не сможешь пользоваться, потому что редактор сделан ровно под одного пользователя, и все настройки захардкожены под него же.
From:(Anonymous)
Date:April 27th, 2017 - 02:06 pm
(Link)
Один файл в пять тыщ строк - свинья вы, сэр!
[User Picture]
From:[info]ketmar
Date:April 27th, 2017 - 02:12 pm
(Link)
так удобней. ну какая технически разница, сделано оно рассыпухой, или же амальгамизировано? внутри оно более-менее поделено на куски.
[User Picture]
From:[info]ketmar
Date:April 27th, 2017 - 02:13 pm
(Link)
есть, впрочем, и ещё одна причина: внутри модуля всякие private игнорируются, поэтому кое-где я для скорости могу ходить мимо геттеров/сеттеров.
From:(Anonymous)
Date:April 27th, 2017 - 04:31 pm
(Link)
Конпелятор не умеет выбрасывать тривиальные геттеры?
[User Picture]
From:[info]ketmar
Date:April 27th, 2017 - 04:35 pm
(Link)
канпелятор умеет канпелировать без оптимизаций, чтобы не ждать по пол-часа.
From:(Anonymous)
Date:April 27th, 2017 - 05:55 pm
(Link)
Мсье дебажную и релизную версию с одинаковыми ключами конпелирует? Да и какие полчаса на 5000 строчек? Чего несет, вообще охуеть.
[User Picture]
From:[info]ketmar
Date:April 27th, 2017 - 06:00 pm
(Link)
нахуй пошёл.
[User Picture]
From:[info]ketmar
Date:April 27th, 2017 - 02:14 pm
(Link)
p.s.: и я намекал, что там УЖОС. ;-)