johnfound | Как каквото и да правя с функцията ще промени факта, че sqlite ще я извика за всяка двойка от стрингове?
Това, което прави trie е да сравнява всеки различен символ във ВСИЧКИ стрингове от колекцията само веднъж.
Рязането на стрингове под 90 и над 210 е нормално и вече го правя.
Сортирането не помага. Ако помислиш малко ще се сетиш защо. А trie така или иначе ги сортира автоматично.
А, когато изпълнението на кода отнема седмица, слабо ме вълнова дали О-то е същото.
Ами не, не съм убеден. Реално, за всеки стринг от B ти трябва да обходиш цялото дърво. Което като сложност е еквивалентно на обхождането на целият масив А.
Икономисваш само на изчислението на разстоянието, тъй като връщайки се назад по дървото, можеш да имаш частично изчисленото разстояние и да продължиш от текущият символ, а не да започваш отначало.
Само че, за сметка на това имаш:
1. Рекурсия, която далеч не е евтина и като време и като памет.
2. Работа с далеч по-големи структури от данни, вместо с еднобайтови символи. Които структури често ще излизат от кеша на процесора.
3. Много повече код, който трябва да се изпълнява, заради 1 и 2.
И дали ползата превишава вредата е нещо, което трябва да се докаже. Освен това, ти пак не казваш на какво си го написал? Да не се окаже, че ако се напише на нормален език без всичките тези дървета пак ще е по-бързо.
Защото аз съм се убедил, че ако не се променя О() сложността, то трябва да се избира най-простото решение, а не това, което икономисва някакви итерации за сметка на прекомерно усложняване на кода и данните.
Не трябва да обходя цялото дърво, а само частите които ще доведат по-малка разлика от тази която има е в момента.
Рекурсията не е задължителна, версията ми на С няма рекурсия (понеже GPU-тата не я харесват).
Кода изобщо не е много, в омента не съм вкъщи да проверя, но е под 50 реда С.
А средно - половината дърво. Което, както казах не променя асимптотичната сложност на алгоритъма.
