<bgdev />free

Вход Регистрация

Задача НЕ за интервю
7

0 1 2 3 4 5 ....18 19 20 21 22 ....32 33 34 35 36
#11297 (ツ) |
Създадено на 20.09.2020, видяно: 1682 пъти.
johnfound
|

Как каквото и да правя с функцията ще промени факта, че sqlite ще я извика за всяка двойка от стрингове?

Това, което прави trie е да сравнява всеки различен символ във ВСИЧКИ стрингове от колекцията само веднъж.

Рязането на стрингове под 90 и над 210 е нормално и вече го правя.

Сортирането не помага. Ако помислиш малко ще се сетиш защо. А trie така или иначе ги сортира автоматично.

А, когато изпълнението на кода отнема седмица, слабо ме вълнова дали О-то е същото.

Ами не, не съм убеден. Реално, за всеки стринг от B ти трябва да обходиш цялото дърво. Което като сложност е еквивалентно на обхождането на целият масив А.

Икономисваш само на изчислението на разстоянието, тъй като връщайки се назад по дървото, можеш да имаш частично изчисленото разстояние и да продължиш от текущият символ, а не да започваш отначало.

Само че, за сметка на това имаш:

1. Рекурсия, която далеч не е евтина и като време и като памет.

2. Работа с далеч по-големи структури от данни, вместо с еднобайтови символи. Които структури често ще излизат от кеша на процесора.

3. Много повече код, който трябва да се изпълнява, заради 1 и 2.

И дали ползата превишава вредата е нещо, което трябва да се докаже. Освен това, ти пак не казваш на какво си го написал? Да не се окаже, че ако се напише на нормален език без всичките тези дървета пак ще е по-бързо.

Защото аз съм се убедил, че ако не се променя О() сложността, то трябва да се избира най-простото решение, а не това, което икономисва някакви итерации за сметка на прекомерно усложняване на кода и данните.

Не трябва да обходя цялото дърво, а само частите които ще доведат по-малка разлика от тази която има е в момента.

Рекурсията не е задължителна, версията ми на С няма рекурсия (понеже GPU-тата не я харесват).

Кода изобщо не е много, в омента не съм вкъщи да проверя, но е под 50 реда С.

#11300 (ツ) johnfound
Последно редактирано на 20.09.2020 от johnfound, видяно: 1678 пъти.
|

Не трябва да обходя цялото дърво, а само частите които ще доведат по-малка разлика от тази която има е в момента.

Което може и да е цялото дърво, ако минималният елемент е последният. ;-) А средно - половината дърво. Което, както казах не променя асимптотичната сложност на алгоритъма.

А на какъв език е написано това, което работи една седмица?

#11301 (ツ) |
Създадено на 20.09.2020, видяно: 1672 пъти.
johnfound
|

Не трябва да обходя цялото дърво, а само частите които ще доведат по-малка разлика от тази която има е в момента.

Което може и да е цялото дърво, ако минималният елемент е последният. ;-) А средно - половината дърво. Което, както казах не променя асимптотичната сложност на алгоритъма.

А на какъв език е написано това, което работи една седмица?

Нали вече ти казах, слабо че интересува асимптотичната сложност. Затова и съм дал брой на елементите.

Написано е на Go, скоростта е близка до С.

#11307 (ツ) johnfound
Създадено на 20.09.2020, видяно: 1664 пъти.
|
johnfound
|

Не трябва да обходя цялото дърво, а само частите които ще доведат по-малка разлика от тази която има е в момента.

Което може и да е цялото дърво, ако минималният елемент е последният. ;-) А средно - половината дърво. Което, както казах не променя асимптотичната сложност на алгоритъма.

А на какъв език е написано това, което работи една седмица?

Нали вече ти казах, слабо че интересува асимптотичната сложност. Затова и съм дал брой на елементите.

Написано е на Go, скоростта е близка до С.

Тези, на които асимптотичната сложност не им е важна, би трябвало да пишат на асемблер.

Защото скоростта на Go не е "близка до C" - поне 3 пъти е по-бавен. Близки са само "асимптотично" и то условно, а ти казваш, че асимптотиката не те интересува.

#11317 (ツ) |
Последно редактирано на 21.09.2020 от |, видяно: 1657 пъти.
johnfound
|
johnfound
|

Не трябва да обходя цялото дърво, а само частите които ще доведат по-малка разлика от тази която има е в момента.

Което може и да е цялото дърво, ако минималният елемент е последният. ;-) А средно - половината дърво. Което, както казах не променя асимптотичната сложност на алгоритъма.

А на какъв език е написано това, което работи една седмица?

Нали вече ти казах, слабо че интересува асимптотичната сложност. Затова и съм дал брой на елементите.

Написано е на Go, скоростта е близка до С.

Тези, на които асимптотичната сложност не им е важна, би трябвало да пишат на асемблер.

Защото скоростта на Go не е "близка до C" - поне 3 пъти е по-бавен. Близки са само "асимптотично" и то условно, а ти казваш, че асимптотиката не те интересува.

Ти наистина ли ще ме учиш колко е бавен езика на който пиша? :)

За фантазиите ти как асемблера бил най-бърз вече коментирахме.

#11327 (ツ) Унуфри
Създадено на 20.09.2020, видяно: 1647 пъти.
|
bvbfan
|
bvbfan

Не, big data на нишки в рама срещу sqlite, разбира се и той може всичко в рама, зависи от кеша. В интерес на истината sqlite бие всякакви nosql лайна и се доближава до напълно данните в рама, ако кеша е достатъчно голям, но печелиш, много по-малко код, кеф ти всякакви заявки.

Т.е. не може да се сравнява с моя код. :)

Какъвто и да е "твоят" код, сравнявам двоични дървета, "твоят" мога да прогнозирам, че не става, ако не е някакво подобие.

Написал съм какъв е моят код. Trie.

Какво има в двоичните дървета?

Чудех се дали да се обадя въобще по тази тема, че ще защитя пайпа сега и ще ме нападнете. Ама няма да ми е сефте :) Преди повече от 15 години, бедни студенти от ФМИ писахме биоинформатични чекии. За търсене на всички възможни подстрингове на дадени термини в ntext в mssql 2000 строяхме външни индекси базирани на tries. Проблемът е, че като ги свриализираш стават гигантски. По онея години си бяха гигабайти и отнемаше много часове да се построят. Деба някъде сигурно имам кода, на. нет 1.1 го писахме... Абе пайп ти да не си кадър на ФМИ на СУ?

#11329 (ツ) Унуфри
Създадено на 20.09.2020, видяно: 1645 пъти.

Поради липса на едит пиша второ мнение. Само пайпа е в правият път. С останалите решения ще се озорите. Дали ще е подстринг или симиларити е без значение.

#11334 (ツ) |
Създадено на 20.09.2020, видяно: 1638 пъти.
Унуфри

Чудех се дали да се обадя въобще по тази тема, че ще защитя пайпа сега и ще ме нападнете. Ама няма да ми е сефте :) Преди повече от 15 години, бедни студенти от ФМИ писахме биоинформатични чекии. За търсене на всички възможни подстрингове на дадени термини в ntext в mssql 2000 строяхме външни индекси базирани на tries. Проблемът е, че като ги свриализираш стават гигантски. По онея години си бяха гигабайти и отнемаше много часове да се построят. Деба някъде сигурно имам кода, на. нет 1.1 го писахме... Абе пайп ти да не си кадър на ФМИ на СУ?

Магистърската ми степен е от ФМИ, разбира се. Докторската е от чужбина. :)

#11339 (ツ) |
Последно редактирано на 21.09.2020 от |, видяно: 1632 пъти.
|

Кода изобщо не е много, в омента не съм вкъщи да проверя, но е под 50 реда С.

Греша, кода ми е около 100 реда.

Другата грешка е броят на стринговете в колекция Б: 23 милиона са.

#11346 (ツ) Унуфри
Създадено на 21.09.2020, видяно: 1603 пъти.
|
Унуфри

Чудех се дали да се обадя въобще по тази тема, че ще защитя пайпа сега и ще ме нападнете. Ама няма да ми е сефте :) Преди повече от 15 години, бедни студенти от ФМИ писахме биоинформатични чекии. За търсене на всички възможни подстрингове на дадени термини в ntext в mssql 2000 строяхме външни индекси базирани на tries. Проблемът е, че като ги свриализираш стават гигантски. По онея години си бяха гигабайти и отнемаше много часове да се построят. Деба някъде сигурно имам кода, на. нет 1.1 го писахме... Абе пайп ти да не си кадър на ФМИ на СУ?

Магистърската ми степен е от ФМИ, разбира се. Докторската е от чужбина. :)

А така, знайхми чи си от нащи!

Рамбо вие дискретнта математика учихте ли в меито? Запознат ли си с научните трудове на Татко Смърф?

#11347 (ツ) bvbfan
Последно редактирано на 21.09.2020 от bvbfan, видяно: 1598 пъти.

Ползва lower_bound за сравнение, предполагам. Няма нужда от това да се пишат дължите на стринговете в дб, достатъчно оптимизирана е да си го зададеш в заявка и да ги филтрираш по дължина достатъчно бързо. Що се отнася до Го и сравнимостта със С е смехотворно, като го напишеш на Ръст, ще се съглася, че е същото.

Едит: Забравих да спомена, че sqlite държи резултатите в двуично дърво и реално "отдолу" имаш същото.

#11350 (ツ) Унуфри
Създадено на 21.09.2020, видяно: 1593 пъти.
#11353 (ツ) Rabin
Последно редактирано на 21.09.2020 от Rabin, видяно: 1591 пъти.
Унуфри

Рамбо вие дискретнта математика учихте ли в меито?

Учихме, ама дори не помня закво ставаше въпрос. Качил съм кашоните на тавана, дето съм снимал лекции и купувал сборници за решаване задачи. Изпадат някви много странни книги, после гледам в дипломата - абе учили сме го. Ама кво е било - ебеш ли му мамата!

Наков е прав като плюе имбецилните дядки дето на програмисти преподават якост на бетона.

Изпадат в смисъл като дууне ветър и падат отгоре, абе много е забавно. Туй беше цялата файда от следването.

#11354 (ツ) bvbfan
Създадено на 21.09.2020, видяно: 1590 пъти.

Много добре знам разликата :-)

#11356 (ツ) Унуфри
Създадено на 21.09.2020, видяно: 1585 пъти.
bvbfan

Много добре знам разликата :-)

Защо тогава е "отдолу" е същото ?

#11357 (ツ) Унуфри
Създадено на 21.09.2020, видяно: 1585 пъти.
Rabin
Унуфри

Рамбо вие дискретнта математика учихте ли в меито?

Учихме, ама дори не помня закво ставаше въпрос. Качил съм кашоните на тавана, дето съм снимал лекции и купувал сборници за решаване задачи. Изпадат някви много странни книги, после гледам в дипломата - абе учили сме го. Ама кво е било - ебеш ли му мамата!

Наков е прав като плюе имбецилните дядки дето на програмисти преподават якост на бетона.

Изпадат в смисъл като дууне ветър и падат отгоре, абе много е забавно. Туй беше цялата файда от следването.

Сефте чувам, че МЕИ-тата имали такава дисциплина, така маловажна спрямо металознанието. Но ако си намериш из кашоните дипломата провери за всеки случай.

#11358 (ツ) Rabin
Създадено на 21.09.2020, видяно: 1584 пъти.
Унуфри

Сефте чувам, че МЕИ-тата имали такава дисциплина, така маловажна спрямо металознанието. Но ако си намериш из кашоните дипломата провери за всеки случай.

Дискретни структури се казваше, ся се сещам. Не е ли същото? Няква дърта леля ни го водеше, друго не помня.

#11362 (ツ) bvbfan
Създадено на 21.09.2020, видяно: 1582 пъти.
Унуфри
bvbfan

Много добре знам разликата :-)

Защо тогава е "отдолу" е същото ?

Trie е вид двучино дърво, ако не го специфицираш какъв точно е може да го обобщя като бинарно.

#11364 (ツ) Унуфри
Създадено на 21.09.2020, видяно: 1580 пъти.
bvbfan
Унуфри
bvbfan

Много добре знам разликата :-)

Защо тогава е "отдолу" е същото ?

Trie е вид двучино дърво, ако не го специфицираш какъв точно е може да го обобщя като бинарно.

Като зубърче от ФМИ да питам - дефиницията на бинарно дърво е такова, което има макс 2 ноуда, което е недостатъчно да се пазят всички възможни подстрингове/близки на даден. Греша ?

#11366 (ツ) Унуфри
Създадено на 21.09.2020, видяно: 1579 пъти.
Rabin
Унуфри

Сефте чувам, че МЕИ-тата имали такава дисциплина, така маловажна спрямо металознанието. Но ако си намериш из кашоните дипломата провери за всеки случай.

Дискретни структури се казваше, ся се сещам. Не е ли същото? Няква дърта леля ни го водеше, друго не помня.

Не грешиш, но реално са само демо. Ето Библията на Татко Смърф.

0 1 2 3 4 5 ....18 19 20 21 22 ....32 33 34 35 36

Задача НЕ за интервю
7

AsmBB v3.0 (check-in: a316dab8b98d07d9); SQLite v3.42.0 (check-in: 831d0fb2836b71c9);
©2016..2023 John Found; Licensed under EUPL. Powered by Assembly language Created with Fresh IDE