| э-э-э, бля... |
[Apr. 27th, 2017|11:24 am] |
Правило! ты нарушил Правило! ты нарушил Правило Профилирования, и будешь за это наказан!
какое, нахуй, дерево? какое?! какое, мудак, дерево?! зачем?! ты поехавший, да?!
на вторую неделю до Умного Кэтмара дошло сделать простенький замер. и оказалось, что худшие времена для:
* линейной вставки страницы в текст (в самое начало): ~0.3 миллисекунды.
* линейного поиска позиции в тексте (с начала до textsize-1): ~0.3 миллисекунды.
примерно 53,000 страниц. 210МБ.
какое, в жопу, дерево? зачем? что оно там делает вообще? НАХУЙ ДЕРЕВО!
блядь, ну когда же я уже приучусь делать первичные замеры до того, как писать кучу кода?! |
|
|
| упд к прошлому |
[Apr. 27th, 2017|02:54 pm] |
а вот если сделать список страниц в виде сильно деградировавшего b+ (фактически, убрав нахер всё кроме листьев для тупых линейных операций; в итоге получилось что-то похожее на одноуровневый skip list), то поиск страницы по позиции в тексте для 210МБ (~54,000 текстовых страниц, ~800 страниц в индексе) занимает… ~0.01 msecs per operation (worst case). безо всяких сложных структур данных.
вставка и удаление как в текст, так и в таблицу страниц, понятно, тоже очень быстрые: всё, что надо — найти позицию, создать/удалить страницу, растусовать данные по соседним страницам более-менее равномерно (чтобы заполнение было немного сбалансированым), и починить одно- или двусвязный список.
итого, мы получаем полное отсутствие фрагментации памяти (потому что все выделения всегда одного размера), и всё ещё охуевающую скорость. при этом код почти не усложнился.
вот на этом, видимо, и остановлюсь.
upd: упс. маленько обосрался. ~3200 страниц в индексе, ~0.08 msecs на поиск. да ладно, всё равно быстрее самого быстрого поноса, хуле. |
|
|
| для дебилов и примкнувших |
[Apr. 27th, 2017|07:41 pm] |
watch your tongue. кто грубит и выёбывается не по делу — идёт нахуй и остаётся там. после этого можно не утруждаться ответами: я их практически всегда вытираю не читая.
пояснение: умных здесь любят. умничающих — нет. умный знает разницу. |
|
|