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