0 1 2 3 4 5 ...18 19 20 21 22 ...32 33 34 35 36
Не трябва да обходя цялото дърво, а само частите които ще доведат по-малка разлика от тази която има е в момента.
Рекурсията не е задължителна, версията ми на С няма рекурсия (понеже GPU-тата не я харесват).
Кода изобщо не е много, в омента не съм вкъщи да проверя, но е под 50 реда С.
Което може и да е цялото дърво, ако минималният елемент е последният. 
А средно - половината дърво. Което, както казах не променя асимптотичната сложност на алгоритъма.
А на какъв език е написано това, което работи една седмица?
Нали вече ти казах, слабо че интересува асимптотичната сложност. Затова и съм дал брой на елементите.
Написано е на Go, скоростта е близка до С.
Тези, на които асимптотичната сложност не им е важна, би трябвало да пишат на асемблер.
Защото скоростта на Go не е "близка до C" - поне 3 пъти е по-бавен. Близки са само "асимптотично" и то условно, а ти казваш, че асимптотиката не те интересува.
Ти наистина ли ще ме учиш колко е бавен езика на който пиша? :)
За фантазиите ти как асемблера бил най-бърз вече коментирахме.
Чудех се дали да се обадя въобще по тази тема, че ще защитя пайпа сега и ще ме нападнете. Ама няма да ми е сефте :) Преди повече от 15 години, бедни студенти от ФМИ писахме биоинформатични чекии. За търсене на всички възможни подстрингове на дадени термини в ntext в mssql 2000 строяхме външни индекси базирани на tries. Проблемът е, че като ги свриализираш стават гигантски. По онея години си бяха гигабайти и отнемаше много часове да се построят. Деба някъде сигурно имам кода, на. нет 1.1 го писахме... Абе пайп ти да не си кадър на ФМИ на СУ?
Поради липса на едит пиша второ мнение. Само пайпа е в правият път. С останалите решения ще се озорите. Дали ще е подстринг или симиларити е без значение.
Магистърската ми степен е от ФМИ, разбира се. Докторската е от чужбина. :)
Греша, кода ми е около 100 реда.
Другата грешка е броят на стринговете в колекция Б: 23 милиона са.
А така, знайхми чи си от нащи!
Рамбо вие дискретнта математика учихте ли в меито? Запознат ли си с научните трудове на Татко Смърф?
Ползва lower_bound за сравнение, предполагам. Няма нужда от това да се пишат дължите на стринговете в дб, достатъчно оптимизирана е да си го зададеш в заявка и да ги филтрираш по дължина достатъчно бързо. Що се отнася до Го и сравнимостта със С е смехотворно, като го напишеш на Ръст, ще се съглася, че е същото.
Едит: Забравих да спомена, че sqlite държи резултатите в двуично дърво и реално "отдолу" имаш същото.
Учихме, ама дори не помня закво ставаше въпрос. Качил съм кашоните на тавана, дето съм снимал лекции и купувал сборници за решаване задачи. Изпадат някви много странни книги, после гледам в дипломата - абе учили сме го. Ама кво е било - ебеш ли му мамата!
Наков е прав като плюе имбецилните дядки дето на програмисти преподават якост на бетона.
Изпадат в смисъл като дууне ветър и падат отгоре, абе много е забавно. Туй беше цялата файда от следването.
Сефте чувам, че МЕИ-тата имали такава дисциплина, така маловажна спрямо металознанието. Но ако си намериш из кашоните дипломата провери за всеки случай.
Дискретни структури се казваше, ся се сещам. Не е ли същото? Няква дърта леля ни го водеше, друго не помня.
Trie е вид двучино дърво, ако не го специфицираш какъв точно е може да го обобщя като бинарно.
Като зубърче от ФМИ да питам - дефиницията на бинарно дърво е такова, което има макс 2 ноуда, което е недостатъчно да се пазят всички възможни подстрингове/близки на даден. Греша ?
0 1 2 3 4 5 ...18 19 20 21 22 ...32 33 34 35 36
