Square
Максимум перфоманса
Square
И вообще я сторонник юзать qt на замену stl
Square
Если б ещё свой аллокатор можно в шаблон отдавать как в stl - вообще б цены не было
Andrei
А я не сторонник.
Andrei
:D
Andrei
Но опустим это.
Square
Тут вообще кто нить юзает qt как замену стандартной библиотеке?
arisudesu
Лол зачем
arisudesu
Таскать за собой гигабайт зависимостей нравится?
Square
Лол потомушто он охуенен же
Square
Ну и речь не про мелкие проекты :/
Square
У нас так то крупная ids
Square
И кстати от их сикуэль драйвера я в восторге...
Square
Для оракула самостоятельно только собирать надо.
Алдар
да, у вектора есть замечательный резерв. Если знаешь сколько тебе места надо заранее, а если не знаешь, то в чём проблема выделять 2х раза?
arisudesu
Это уже получается пул
arisudesu
А не вектор
arisudesu
Кстати говоря
Andrei
я ж говорю, никто не мешает излишки памяти вернуть. Есть shrink_to_fit
Square
У меня тут это... Тема для обсуждения есть, очень фундаментальная. Начнём с простого. Поиск needle в haystack... Бойер Мур самый толковый буит?
Square
А когда нужно перебрать несколько тысяч needle'ов? КА?
Square
А когда needle по маске?
Square
Короче ищу примеры реализаций толковых движков для перебора почти-регексов
🦥Alex Fails
При необходимости перевыделяй память, увеличивая капасити в 2 раза.
+, обычно так и делаю
🦥Alex Fails
С вектором надо работать так, что сначала делаешь ресайз или резёрв до нужного размера, потом работаешь
да, я обычно ресерв делаю
Андрей
У меня тут это... Тема для обсуждения есть, очень фундаментальная. Начнём с простого. Поиск needle в haystack... Бойер Мур самый толковый буит?
Если просто needle искать, то префикс функция найдёт за O(n) все вхождения.
Square
если мне нужнл 10 тыщ сигнатур перебрать?
🦥Alex Fails
бинарный поиск?
🦥Alex Fails
сбалансированные деревья поиска?
Square
а как лепят поиск по маске
Square
вообще слышал ли кто про поиск регексов за константное время?
Square
ну хотя бы какой то упрощенный, без возвратов и тп
🦥Alex Fails
в akelpad клевая имплементация
Square
то есть когда скорость поиска зависит как в обычном КА, только от длины haystack
🦥Alex Fails
она токенизирует регэкспы и исчет по токенам
Square
хм.
🦥Alex Fails
🦥Alex Fails
🦥Alex Fails
🦥Alex Fails
.h-only logic
🦥Alex Fails
там пример есть в конце, как юзать
Square
Спасибо. смотрю
Square
Я вообще думал о гибриде автомата и бойера мура, чтобы высота дерева была ограничена к примеру, 128 или типа того.
Square
Надо попробовать попилить
Square
Толковых экспериментов чо то не особо много удалось найти...
Anatoly
Если же прходится пушбечит, свести это к минимуму
Гыыы ык!
http://users.livejournal.com/_winnie/463176.html
🦥Alex Fails
лол
Andrei
и?
🦥Alex Fails
соль в том, что push_back сам reserve'ит
🦥Alex Fails
обычно с коэф. от 1.5 до 2
Andrei
Почему неявно квадратичный, когда явно квадратичный.
🦥Alex Fails
в зависимости от имплементации
🦥Alex Fails
и поэтому у нас получилось дно
🦥Alex Fails
каждый шаг мы расширяем массив на 10
🦥Alex Fails
апотом пинаем
🦥Alex Fails
а если ресерв убрать, то мы его будем расширять по мере надобности в 1,5~2 раза
arisudesu
Где-то на хабре было исследование на тему оптимального резерва
🦥Alex Fails
ага
Andrei
Что, опять?
🦥Alex Fails
я тоже помню
Andrei
нет никакого оптимального резерва.
arisudesu
Да не, давно было
Andrei
лол.
Anatoly
Почему неявно квадратичный, когда явно квадратичный.
Потому что невооружённым глазом видно с трудом. "Мы ж тут соптимизировали, кагжэтаг!"
Andrei
Эм...
🦥Alex Fails
да лошпеды, не знающие апи
🦥Alex Fails
так соптимизируют 😂
Andrei
Резёрв в даном случае всегда будет вызывать перемещение.
Andrei
это сумма ряда 1 +2 +3 +..+n
Andrei
что равно 1/2 *n*n+1
Andrei
То есть квадратичная асимптотика
Andrei
Это явно и очевидно квадратичный код.
Anatoly
Я б в коде вызвал 10 раз пушбек, так круче: "нам понадобилось 10 - мы 10 и добавили! Никакого оверхеда!"
Anatoly
В http://users.livejournal.com/_winnie/463176.html?thread=6042184#t6042184 пример лучше
Anatoly
Как раз про "свести пушбек к минимуму".