Оптимизация добавления в прошитое дерево

А профайлером ты прошёлся?

Кавойлером?(

Пытался потыкать некий CxxProf (нашел на вики, тут), но не осилил.

UPD: Тыкание носом в годные инструменты (с адекватной докой) приветствуются.

а что вообще хотел сделать?? (не как, а именно что..)

и пара моментов, по ходу : что за магический коммент «БЕЛИМ МРАЗБ» и почему дважды на равенство 'p' проверяется..на всяк.случай, вдруг всё-таки 'p'?

а что вообще хотел сделать?? (не как, а именно что..)

Вот то, что написано в первых пунктах + искать там слово хочу.

БЕЛИМ МРАЗБ

Выбешивает бывшая преподша по алгебре.

дважды на

Пофиксил, благодарочка.

Valgrind, не?

И что-то мне подсказывает что твою «БЕЛИМ МРАЗБ» можно заменить на что-то типа: QChar(x).isLower() && QChar(x).isLetter()

• Для стемминга взял бы ты лучше OpenFST, например, или OpenNLP, а не городил бы велосипеды.
• В зависимости от твоей задачи посмотрел бы ты лучше в сторону готовых фреймворков, которые тока допиливать надо, Stanbol, например, они в любом случае быстрее твоего кода будут работать.

Вот тут линки, если ты в гугле сам не найдешь:

• OpenFST
• OpenNLP
• Stanbol

Форматирование ужасное, пройдись clang-format-ом.

Зачем используешь смесь Qt и STL, используй что-нибудь одно, предпочтительно STL, раз GUI нет.

Зачем у тебя ручной delete, если есть std::unique_ptr? В С++14 у тебя в общем случае не должно быть ни одного сырого указателя, ни одного new и ни одного delete.

Вот тут

count += textStream.readLine().split(" ").size();

Вместо std::map лучше использовать std::unordered_map, вместо find/emplace просто emplace и смотри на результат.

Ты понимаешь, что у тебя все слова с одним хэшем сливаются в одно? Почему бы не использовать unordered_map<std::string, ...>, он сам посчитает хэши и разрулит ситуацию с повторяющимися.

В алгоритм вникать лень, запускай под oprofile да разбирайся.

профайлер
valgrind

Советы уровня lor.

Как детектировать только ru-слова?

Вот то, что написано в первых пунктах + искать там слово хочу.

по первым пунктам понятно что это wc (word count) :-)

Из мапа — в обычное бинарное дерво, но считается, насколько далеко от корня ушло слово

невообразимая операция. То есть понятно как оно работает, но не видно практического смысла - нахуа так складывать строки и учитывать их глубину...Если только это задание на лабе, но тогда в job :-)

Для компактного хранения больших коллекций слов (а-ля словари) давно придумана метода http://en.wikipedia.org/wiki/Trie , более-менее подходящие реализации на C++, включая Qt должны быть в сети.

См. callgrind.

Зачем используешь смесь Qt и STL, используй что-нибудь одно, предпочтительно STL, раз GUI нет.

Нравятся возможности Qt со строками, чтение файла оттуда же приплыло.

Зачем у тебя ручной delete, если есть std::unique_ptr? В С++14 у тебя в общем случае не должно быть ни одного сырого указателя, ни одного new и ни одного delete.

Ну да, есть варик насувать unique_ptr в дерево, кастомных деструкторов нет, так тчо будет так же быстро как с указаелями. Но процесс это не оптимизирует.

Вот тут

Функция эта там так, для примерного подсчета кол-ва слов, со своей задачей справляется, пусть хоть целых 100 мсек считает, нет, даже 300. Проблема не в этом говне.

Вместо std::map лучше использовать std::unordered_map, вместо find/emplace просто emplace и смотри на результат.

Так мне нужно считать кл-во включений слова, как тут без find? Да, unordered_map будет лучше смотреться, сортировка по хешу действительно не нужна.

Ты понимаешь, что у тебя все слова с одним хэшем сливаются в одно? Почему бы не использовать unordered_map<std::string, ...>, он сам посчитает хэши и разрулит ситуацию с повторяющимися.

Не думал, что там много пересечений хешей.

В алгоритм вникать лень, запускай под oprofile да разбирайся.

Отлично, премного балгодарен, завтра потыкаю.

cache and branch prediction profiler

Я и говорю, совет уровня lor.

затем добавляются в прошитое дерево (все, даже повторяющиеся)

Зачем?

Из дерева обходом достаются слова и пихаются в мап, вктором ключ — хеш строки. Повторяющиеся слова инкрементируют счетчик слова.

Зачем?

Из мапа — в обычное бинарное дерво, но считается, насколько далеко от корня ушло слово

Зачем?

Зачем ты описываешь то, что ты наваял - всем лень разбираться в твоём говне - пиши то, что хочешь сделать, тогда тебе, возможно, объяснять как это сделать наилучшим образом.

Практический смысл сего действа какой? Захреначить классов и обмазаться шаблонами?

Как детектировать только ru-слова?

подсказка - русские символы это U+410..U+44F и U+401,U+451 всё прочее «вражие наречья, цифирь и препинания».

Если только это задание на лабе, но тогда в job :-)

Спортивный интерес. А вообще kek2 вытек из чтения заданий по методам программирования второшей (я сам 1 курс). Они там на до-диез+дотнет ваяют интерфейсы, а в потрохах подобные задания.

Для компактного хранения больших коллекций слов

МНе не нужно как-то оптимально хранить, иначе зачем зедсь 3 (три! (sic!)) контейнера?

Мне надо оптимизировать ето.

Насколько велика разница с невключением слова при наличии в нём хоть одной не ru буквы?

Нравятся возможности Qt со строками, чтение файла оттуда же приплыло.

Ну так используй QHash, зачем map из STL тащишь.

ак мне нужно считать кл-во включений слова, как тут без find?

Посмотри на результат emplace и insert: если элемент уже есть, он возвращает итератор на него, через который его можно править. Получается один поиск по ключу вместо двух.

Не думал, что там много пересечений хешей.

Так тебе нужен работающий алгоритм или примерно работающий алгоритм?

Практический смысл сего действа какой? Захреначить классов и обмазаться шаблонами?

Да.

Зачем?

А почему нет?

Зачем ты описываешь то, что ты наваял - всем лень разбираться в твоём говне - пиши то, что хочешь сделать, тогда тебе, возможно, объяснять как это сделать наилучшим образом.

Думал, что из топика понятно. Если нет, то вот: оптимизировать обработку и добавление данных в прошитое дерево.

Посмотри на результат emplace и insert: если элемент уже есть, он возвращает итератор на него, через который его можно править. Получается один поиск по ключу вместо двух.

Благодарю.

Так тебе нужен работающий алгоритм или примерно работающий алгоритм?

Сложный вопрос, с одной стороны мне по^Wнет дела до результата (на самом деле), с другой стороны очень хочется. В любом случае замечание полезное.

Нравятся возможности Qt со строками, чтение файла оттуда же приплыло.

Эти возможности работают тогда, когда у тебя отсилы килобайты строк.

Функция эта там так, для примерного подсчета кол-ва слов, со своей задачей справляется, пусть хоть целых 100 мсек считает, нет, даже 300. Проблема не в этом говне.

Проблема какраз-таки в этом говне. Все проблема от того, что хреначишь ничего не понимания, а потом бам и всё горит и нихрена не работает.

Естественно, ведь посчитать можно гигабайт 10 слов за эти 300мсек и пока их у тебя в 10тысяч раз меньше - тебе и так норм.

В алгоритм вникать лень, запускай под oprofile да разбирайся

man perf Профайлер тебе ничего не даст, а проблемка вот она:

39 626 402 285      L1-dcache-load-misses     #   53,14% of all L1-dcache hits   [46,16%]

Это же так круто обмазываться деревьями, ведь везде написано, что они такие крутые и теоретически такие быстрее. А ведь пацанам с их килобайтами тоже казалось 300мсек на килобайт норм, а ты его заюзал на мегабайте, дак ещё и в кешец не влез, то тут сразу бида-пичаль да - 6минут.

Мне надо оптимизировать ето.

видите-ли..процесс оптимизации подразумевает наличие цели алгоритма, то есть конкретной задачи.

если цели алгоритма нет - то нечего мучаться, поставьте exit(0) первой командой.

Это же так круто обмазываться деревьями, ведь везде написано, что они такие крутые и теоретически такие быстрее. А ведь пацанам с их килобайтами тоже казалось 300мсек на килобайт норм, а ты его заюзал на мегабайте, дак ещё и в кешец не влез, то тут сразу бида-пичаль да - 6минут.

Я не фанат деревьев или еще чего-то.

Эти возможности работают тогда, когда у тебя отсилы килобайты строк.

Претензия к кутям? Т. е. переписать все на string и fstream?

Естественно, ведь посчитать можно гигабайт 10 слов за эти 300мсек и пока их у тебя в 10тысяч раз меньше - тебе и так норм.

Я удалю ради тебя эту функцию, хочешь? Тогда мы не потеряем эти 300мсек.

Проблема какраз-таки в этом говне. Все проблема от того, что хреначишь ничего не понимания, а потом бам и всё горит и нихрена не работает.

Да все работатет, на паре тысяч слов все отрабатывает за 20 милисекунд.

man perf Профайлер тебе ничего не даст, а проблемка вот она:

Так, L1 кэш, понятно. Миссы, понятно. Че делать, помогай? >_<

Я не фанат деревьев или еще чего-то.

Зачем ты их впихнул? Ты же какую-то цель преследовал?

Претензия к кутям? Т. е. переписать все на string и fstream?

Причём тут кути, тут дело не в кути. Кути намного илитней этого крестового убожества.

Есть абстракции задача которых дать тебе возможность просто взять и прочитать файл без наличия серого вещества. Они не предназначены для работы даже с мегабайтами.

Я удалю ради тебя эту функцию, хочешь? Тогда мы не потеряем эти 300мсек.

Причём тут 300мсек? Если ты что-то понимаешь в теме - 300мсек у тебя не будет - в этом штука.

Да все работатет, на паре тысяч слов все отрабатывает за 20 милисекунд.

Я тебе выше об этом же и писал. Пока у тебя килобайты данных - у тебя всё работает, а когда чуть больше - всё разбивается о реальный мир.

Естественно летенси л1 3-4такта - это миллиард разименований в секунду и на тысячу слов это всяко хватит.

Так, L1 кэш, понятно. Миссы, понятно.

Как я тебе помогу, если я не знаю что ты пытаешься сделать? Объясни задачу.

Портянку твою не спасти - объясняй практический смысл, будем писать уже думая о том как и почему мы пишем.

Зачем ты их впихнул? Ты же какую-то цель преследовал?

JFF, не будь столь серьезен.

Как я тебе помогу, если я не знаю что ты пытаешься сделать? Объясни задачу.

Хочу 200+ тысяч слов в прошитое дерево < чем за 6 минут на своей машине. Из текстового файла. Да, именно в грёбаное прошитое дерево.

П. С. Кстати, если исключить пункт с прошитым деревом, а сразу считать повторения и сувать в мап — отрабатывает за ~8 секунд.

объясняй практический смысл

Вот тоже интересно, давай параллельно разовьем вторую тему.

Практическая задача — тот самый word count. Нужно знать сколько раз какое слово в тексте встретилось и быстро рассказывать об этом.

Я бы просто сунул все в унордеред_мап и файндом отдавал бы результат.

JFF, не будь столь серьезен.

Зачем тебе прошитое дерево? Почему не что-то другое?

Да, именно в грёбаное прошитое дерево.

Понимаешь в чем штука - зачем кому-то разбираться в бесполезном говне, которое взбрело к кому-то иному в голову?

Я не увидел ни единого профита от твоего дерева, зачем мне в нём разбираться и что-то делать, какой смысл? Потратить время на бесполезное говно?

Потратить время на полезную задачу, даже которая мне не нужна - полезно. Делать херню нет.

Тебе лабу по нему задали, почему такое рвение?

Кстати, если исключить пункт с прошитым деревом

Почему именно это дерево? Почему не другое?

Зачем тебе прошитое дерево? Почему не что-то другое?

JFF

Понимаешь в чем штука - зачем кому-то разбираться в бесполезном говне, которое взбрело к кому-то иному в голову?

Извини, можешь не помогать. Прошу прощения что занял время.

Потратить время на полезную задачу, даже которая мне не нужна - полезно. Делать херню нет.

Верно.

Я не увидел ни единого профита от твоего дерева, зачем мне в нём разбираться и что-то делать, какой смысл? Потратить время на бесполезное говно?

Незачем.

Тебе лабу по нему задали, почему такое рвение?

Писал выше, что нет. А если бы и задали, думаешь тупни в универе бы не удовлетворились 6.5 минутами при таком раскладе? В моем вузе препода по ЯП даже туториалы не осиливают.

Почему именно это дерево? Почему не другое?

А че оно тормозит(99((9

А че оно тормозит(99((9

а где у вас балансировка? чё-то невидать...

Нужно знать сколько раз какое слово в тексте встретилось и быстро рассказывать об этом.

Ты спрашиваешь как я бы сделал?

Я бы просто сунул все в унордеред_мап и файндом отдавал бы результат.

Ну какбэ тупо да, а как быть с «питух» и «питухи»?

Выкати считалку слова на унордеред_мап - я запилю тебе завтра аналог.

Извини, можешь не помогать. Прошу прощения что занял время.

Да причём тут помогать/нет, дело не в этом. Почему бы просто не делать так, чтобы было всё вменяемо и всем было хорошо.

А че оно тормозит(99((9

Ну тут в основном не дерево тормазит, а реализация, а так: дерево всегда тормазит, плюс ты выбрал неудачное + вон пацан тебе пишет про балансировку, скорее всего дело в ней.

У тебя 99% времени твой add в бревно, т.е. 6.5 * 239472 words за 390секунд, т.е. 0.001628583на слово, т.е. даже если возмём 1мкс за летенси памяти, хотя там реально сотня наносекунд, то 1628 рандомных доступов к памяти на одно слово.

А должно быть 20.

а как быть с «питух» и «питухи»?

Стемминг.

< 20. ~12-15

Выкати считалку слова на унордеред_мап - я запилю тебе завтра аналог.

Как-то так:

https://github.com/RussianBruteForce/wc/blob/master/main.cpp

а где у вас балансировка? чё-то невидать...

Не осилю прошивку и балансировку, туповат.

Ну какбэ тупо да, а как быть с «питух» и «питухи»?

забить?

hash<std::string> str_hash;
unordered_map<size_t, Data> map;
map.emplace(make_pair(str_hash(buf_str), Data{buf_str}));

Вот ты поехавший, коллизии же, используй std::unordered_map<std::string, size_t>.

Не осилю прошивку и балансировку, туповат.

тогда нечего удивляться тормозам, несбалансированное дерево поиска недалеко уходит от линейного списка. Чем больше элементов - тем дольше поиск и добавление, линейно.

PS. кстате, нет смысла прошивать если каждый узел знает своего родителя. А для сбалансированных деревьев для обхода нет смысла помнить «родителя» в узле - максимальная глубина на практических задачах меньше 20, такой стек не стоит фактически ничего.

PPS. вам надо тянуть алгоритмическую матчасть, а не извраты С++ с тактодрочеством.

Забыл( Извините.

Да вертел я деревья, не думаю, что IRL мне когда-то пригодятся.