0 1 2 3 4 ...17 18 19 20 21 ...32 33 34 35 36
Добре, освен правилото за "неравенството на триъгълника" не се сещам за някакво друго свойство на edit distance което да може да се ползва, не че и това ни мога по някакъв начин. Сигурен ли си, че с информацията която си дал може да се стигне до решение ? Тези стрингове имат ли някакви зависимости помежду си ?
ПП: metric tree ?
Някой вече спомена: DNA.
Правя trie с елементите на една от колекциите, търся елементите от другата като давам максимално разстояние. Не е кой знае какво, но определено не сравнява всяка двойка стрингове.
А разстоянието как го мериш в дървото ? Нали могат да се махат/добавят/сменят елементи, някак си много сложно иглежда.
http://stevehanov.ca/blog/index.php?id=130
Има някакъв trie search с levenshtein distance. В моят случай дървото се прави веднъж в началото и после само се търси.
K-D дърветата ги знам, разбира се, ще погледна VP trees.
Реално си бях прав, точно преди 5г. когато престанах да се занимавам с ембедед, тогава clang на връбница. Това съм го пробвал доста по-скоро.
Какво си пробвал по-скоро. Да търсиш минимална levenshtein distance между две колекции от стрингове? С sqlite vs. DRAM? :)
А иначе, ако си спомняш тезата ми тогва беше, че llvm изритва gcc отвсякъде. Опита отпреди 5 години няма как да има общо с реалността сега.
Сега ми хрумна още една оптимизация, ще я пробвам по-късно. Така или иначе трябва да преписвам кода на Go, че е някаква диващина с рекурсия.
Не, big data на нишки в рама срещу sqlite, разбира се и той може всичко в рама, зависи от кеша. В интерес на истината sqlite бие всякакви nosql лайна и се доближава до напълно данните в рама, ако кеша е достатъчно голям, но печелиш, много по-малко код, кеф ти всякакви заявки.
Какъвто и да е "твоят" код, сравнявам двоични дървета, "твоят" мога да прогнозирам е някакво подобие.
Написал съм какъв е моят код. Trie.
Какво има в двоичните дървета?
Нормално, без да съм го видял. Ако си писал и на Джава - 
Очаквай в пъти да е по-бърз sqlite. Напиши си функцията на С, и си слагай в заявки.
Функцията я имам и на C и на Go. На C e малко дървена, понеже ще я пробвам на GPU като се наканя.
Досега не си написал абсолютно нищо, което може да ме убеди, че sqlite може да е по-бърз.
Не знам какво очакваш да ти напиша, levenstein е една елементарна функция, ползвах я преди години. Освен нея ти трябват заявки към базата и получаваш данните, във всякакъв ред, в зависимост от завката. Чисто и ясен код.
Всеки два стринга ли ще сравни? Левенщайн може да е чиста, но това не означава, че е бърза.
Ами виж сега, това, което ти правиш с това trie, реално е просто прекратяване на изчислението на дистанцията, ако е по-дълга от зададената максимална стойност (64). Но алгоритъма пак си остава О(n.m), просто защото трябва да сравниш всеки със всеки, за да знаеш кой е с минимална дистанция. И от тази сложност принципно не може да се избяга.
Но това лесно се имплементира и във функцията за пресмятане на разстоянието - просто когато стигне до 65 трябва да връща безкрайност и да не сравнява стринговете нататък.
Евентуално, ако сортираш стринговете в сет А, може да се окаже, че тези, които са със разстояние < 65 образуват някаква група и можеш да смяташ само в тази група. Но това също лесно се организира в SQLite чрез индекси и съответно параметрите във where клаузата.
Освен това, тъй като разстоянието L(s1,s2) >= ||len(s1)| - |len(s2)||, то можеш да си спестиш доста, като просто вкараш и дължините на стринговете в базата и сравняваш само тези, които също са с подходяща дължина. За това също ще ти помогнат индекси и правилните заявки. Колко печалба ще имаш, зависи от разпределението на стринговете по дължини.
Видях я тая глупост с trie-то още като я пусна, но между сауните и жакузитата тука не ми остана време да пиша. Потвърждава тезата ми че пайпа не знае какво е Биг О.
Как каквото и да правя с функцията ще промени факта, че sqlite ще я извика за всяка двойка от стрингове?
Това, което прави trie е да сравнява всеки различен символ във ВСИЧКИ стрингове от колекцията само веднъж.
Рязането на стрингове под 90 и над 210 е нормално и вече го правя.
Сортирането не помага. Ако помислиш малко ще се сетиш защо. А trie така или иначе ги сортира автоматично.
А, когато изпълнението на кода отнема седмица, слабо ме вълнова дали О-то е същото като това което свършва за месец. :)
Ами не, не съм убеден. Реално, за всеки стринг от B ти трябва да обходиш цялото дърво. Което като сложност е еквивалентно на обхождането на целият масив А.
Икономисваш само на изчислението на разстоянието, тъй като връщайки се назад по дървото, можеш да имаш частично изчисленото разстояние и да продължиш от текущият символ, а не да започваш отначало.
Само че, за сметка на това имаш:
1. Рекурсия, която далеч не е евтина и като време и като памет.
2. Работа с далеч по-големи структури от данни, вместо с еднобайтови символи. Които структури често ще излизат от кеша на процесора.
3. Много повече код, който трябва да се изпълнява, заради 1 и 2.
И дали ползата превишава вредата е нещо, което трябва да се докаже. Освен това, ти пак не казваш на какво си го написал? Да не се окаже, че ако се напише на нормален език без всичките тези дървета пак ще е по-бързо.
Защото аз съм се убедил, че ако не се променя О() сложността, то трябва да се избира най-простото решение, а не това, което икономисва някакви итерации за сметка на прекомерно усложняване на кода и данните.
0 1 2 3 4 ...17 18 19 20 21 ...32 33 34 35 36