Кстати говоря

я ж говорю, никто не мешает излишки памяти вернуть. Есть shrink_to_fit

У меня тут это... Тема для обсуждения есть, очень фундаментальная. Начнём с простого. Поиск needle в haystack... Бойер Мур самый толковый буит?

А когда нужно перебрать несколько тысяч needle'ов? КА?

А когда needle по маске?

Короче ищу примеры реализаций толковых движков для перебора почти-регексов

При необходимости перевыделяй память, увеличивая капасити в 2 раза.

+, обычно так и делаю

О точно, а когда успели дотнет грохнуть?

я новый сделал

С вектором надо работать так, что сначала делаешь ресайз или резёрв до нужного размера, потом работаешь

да, я обычно ресерв делаю

У меня тут это... Тема для обсуждения есть, очень фундаментальная. Начнём с простого. Поиск needle в haystack... Бойер Мур самый толковый буит?

Если просто needle искать, то префикс функция найдёт за O(n) все вхождения.

Если просто needle искать, то префикс функция найдёт за O(n) все вхождения.

а дальше?

если мне нужнл 10 тыщ сигнатур перебрать?

бинарный поиск?

сбалансированные деревья поиска?

сбалансированные деревья поиска?

это я тоже уловил

а как лепят поиск по маске

вообще слышал ли кто про поиск регексов за константное время?

ну хотя бы какой то упрощенный, без возвратов и тп

в akelpad клевая имплементация

то есть когда скорость поиска зависит как в обычном КА, только от длины haystack

в akelpad клевая имплементация

чем?

она токенизирует регэкспы и исчет по токенам

хм.

.h-only logic

там пример есть в конце, как юзать

Спасибо. смотрю

Я вообще думал о гибриде автомата и бойера мура, чтобы высота дерева была ограничена к примеру, 128 или типа того.

Надо попробовать попилить

Толковых экспериментов чо то не особо много удалось найти...

Если же прходится пушбечит, свести это к минимуму

Гыыы ык! http://users.livejournal.com/_winnie/463176.html

лол

и?

соль в том, что push_back сам reserve'ит

обычно с коэф. от 1.5 до 2

Почему неявно квадратичный, когда явно квадратичный.

в зависимости от имплементации

и поэтому у нас получилось дно

каждый шаг мы расширяем массив на 10

апотом пинаем

а если ресерв убрать, то мы его будем расширять по мере надобности в 1,5~2 раза

Где-то на хабре было исследование на тему оптимального резерва

ага

Что, опять?

я тоже помню

нет никакого оптимального резерва.

Да не, давно было

лол.

Почему неявно квадратичный, когда явно квадратичный.

Потому что невооружённым глазом видно с трудом. "Мы ж тут соптимизировали, кагжэтаг!"

Эм...

да лошпеды, не знающие апи

так соптимизируют ?

Резёрв в даном случае всегда будет вызывать перемещение.

это сумма ряда 1 +2 +3 +..+n

что равно 1/2 *n*n+1

То есть квадратичная асимптотика

Это явно и очевидно квадратичный код.

Я б в коде вызвал 10 раз пушбек, так круче: "нам понадобилось 10 - мы 10 и добавили! Никакого оверхеда!"

В http://users.livejournal.com/_winnie/463176.html?thread=6042184#t6042184 пример лучше

Как раз про "свести пушбек к минимуму".

Не, не как раз.

Я говорил про пушбек сверх резерва.

Просто так код никто в своём уме не пишет.

Обычно мы знаем сколько нам надо элементов в массиве.

Всегда сначала делается reserve

ERROR: S client not available

если нет, то опять же константа 2 это нормально

и экспериментально ок

потому что если даже предположить, что мы кладём в вектор чары, через 20 реаллокаций мы уже будем занимать мегабайт

через 30 гигабайт

часто у вас гигабайтные строки?

Переаллоцируются еще при этом.

Так что все эти рассказы про фрагментацию памяти это очень специфичный случай.

и не нужно ни золотое сечение, ни полтора,

2 это норм

в противном случае никто не мешает вызывать самостоятельно reserve с нужными величинами

Для этого не надо даже код вектора менять

без строгой надобности это всё пустой совершенно спор.

А если хоть где-то перформанс упирается в то, что вы в цикле херачите пушбек в заранее не аллоцированный вектор — это повод задуматься о дизайне вашей программы

Те же яйца вот ещё http://sim0nsays.livejournal.com/38116.html

Просто так код никто в своём уме не пишет.

Ойвэй. Громкое заявление, я б сказал. Баги, наверное, тоже никто в трезвом уме не оставляет?

Обычно мы знаем сколько нам надо элементов в массиве.

И тут хаха. На то оно и вектор, что не знаем. Есои б знали - тупо б аллоцировали массив.

нет, вектор не на то.

Вектор на то, чтобы мы безопасно использовали его как массив.

потому что если даже предположить, что мы кладём в вектор чары, через 20 реаллокаций мы уже будем занимать мегабайт

Это значит, что у нас строка уже полметра минимум, 700 кбайт в среднем.

с типобезопасностью, мувами, и сборкой мусора

через 30 гигабайт

Полгиговые данные в строке.

2 это норм

Чувак, это ж совсем другая тема.

через 30 будет 2^31

значит гигабайт минимум

не суть, всё равно такими данными никто не ворочает в векторе

А если хоть где-то перформанс упирается в то, что вы в цикле херачите пушбек в заранее не аллоцированный вектор — это повод задуматься о дизайне вашей программы

Код в это *упираться* не будет - пушбек асимптотически и так линеен, с константой около 2.

ЛИНЕЕН?

что?

пушбек это амортизированная константа

ты о чем?

Не помните, какие требования вектор накладывает на контейнер, насколько я помню контейнер должен иметь не бросающий исключения конструктор перемещения или конструктор копирования

пушбек это амортизированная константа

Тьфу, да. Описался.