ФейкПрофил Как ще го смятате, по възможност без "фактори"? :)
как :)
Чакам вие да кажете първо, за да не ви вкарвам в коловоз. Моето решение определено не е оптимално.
Задача НЕ за интервю
SQLite, blob за полетата, Levenstein в кода и дерзаеш.
| Грешките може да са до над 100, но да предположим че ни интересува match с до 64 грешки.
Това какво значи? Че може да се дават като решение стрингове чието растояние на Левенщайн всъщност не е най-малкото в множество А?
Или че просто растоянието на Левенщайн трябва да се смята приблизително и някой път може да е грешно сметнато, но все пак е най-малкото сред грешно сметнатите?
Между другото, идеята на bvbfan съвсем не е лоша. Просто трябва да се имплементира потребителска функция за растоянието на Левенщайн в sqlite и директно да се напише заявка на SQL. Резултата може да се окаже съвсем изненадващо добър. 
johnfound | Грешките може да са до над 100, но да предположим че ни интересува match с до 64 грешки.
Това какво значи? Че може да се дават като решение стрингове чието растояние на Левенщайн всъщност не е най-малкото в множество А?
Или че просто растоянието на Левенщайн трябва да се смята приблизително и някой път може да е грешно сметнато, но все пак е най-малкото сред грешно сметнатите?
Levenshtеin distance се смята между стрингове, които не съвпадат точно. Може да има до 100 такива разлики между стринговете. В общи линии, стринговете в колекция Б са грешни копия на стринговете е колекция А. Отделно му трябва и къде са грешките като позиция, както и какъв тип грешка е (insertion, deletion, substitution), но това са подробности и може да се сметне по-късно.
johnfound Между другото, идеята на bvbfan съвсем не е лоша. Просто трябва да се имплементира потребителска функция за растоянието на Левенщайн в sqlite и директно да се напише заявка на SQL. Резултата може да се окаже съвсем изненадващо добър.
Наистина ли мислиш, че потребителска функция в sqlite ще е по-добра от в момента работещия мноконишков, сравнително оптимизиран код? :) Защото той отнема около седмица на машина с 48*2 ядра, при това когато стринговете от колекция А е 100К. :) А компютрите имат много памет, може да предположиш че е безкрайно много (1.5 TB).
Някакви гени/днкта ли джуркаш ?
ФейкПрофил Някакви гени/днкта ли джуркаш ?
Нещо такова, но по-просто.
| Levenshtеin distance се смята между стрингове, които не съвпадат точно. Може да има до 100 такива разлики между стринговете. В общи линии, стринговете в колекция Б са грешни копия на стринговете е колекция А. Отделно му трябва и къде са грешките като позиция, както и какъв тип грешка е (insertion, deletion, substitution), но това са подробности и може да се сметне по-късно.
Тоест, си искал да кажеш че търсиш минималното разстояние, но не по-голямо от 100 (64). Понятието "грешка" в този контекст е заблуждаващо, още повече, че в предишното изречение използваш правилната дума "разстояние" в същият смисъл.
| Наистина ли мислиш, че потребителска функция в sqlite ще е по-добра от в момента работещия мноконишков, сравнително оптимизиран код? :) Защото той отнема около седмица на машина с 48*2 ядра, при това когато стринговете от колекция А е 100К. :) А компютрите имат много памет, може да предположиш че е безкрайно много (1.5 TB).
Каква връзка имат нишките тука? SQLite също може да работи паралелно в много нишки, заявките могат ефективно да се разпаралелят, а SQLite има сериозно оптимизиран код, който със сигурност ще е по-бърз от това, което сте писали набързо.
Евентуално може да има проблеми само ако искате да изпълнявате на клъстър по мрежата, но и тогава може да се измисли нещо.
johnfound Каква връзка имат нишките тука? SQLite също може да работи паралелно в много нишки, заявките могат ефективно да се разпаралелят, а SQLite има сериозно оптимизиран код, който със сигурност ще е по-бърз от това, което сте писали набързо.
И какво точно ще направи този "сериозно оптимизиран код" в sqlite? :) Можеш ли да го опишеш?
Между другото, специално в био-информатиката се смята за по-подходящо да се използва разстоянието на Дамерау-Левенщейн в което размяната на местата на два символа е една операция, а не 2.
| И какво точно ще направи този "сериозно оптимизиран код" в sqlite? :) Можеш ли да го опишеш?
В смисъл? Ще изпълнява SQL заявките, какво друго може да прави кода в SQL база данни?
johnfound Между другото, специално в био-информатиката се смята за по-подходящо да се използва разстоянието на Дамерау-Левенщайн в което размяната на местата на два символа е една операция, а не 2.
Не и в този случай.
johnfound | И какво точно ще направи този "сериозно оптимизиран код" в sqlite? :) Можеш ли да го опишеш?
В смисъл? Ще изпълнява SQL заявките, какво друго може да прави кода в SQL база данни?
Как ТОЧНО ще изпълнява SQL заявките? Какви ще са заявките, и в какъв достъп до данните ще се транслират те?
| Как ТОЧНО ще изпълнява SQL заявките? Какви ще са заявките, и в какъв достъп до данните ще се транслират те?
Е, ти сега искаш да ти реша задачата на SQL ли?
Във всеки случай, бих започнал с нещо такова:
create table setA(strA text);
create table setB(strB text);
select
min(LsDist(strB, strA))
from
setB left join setA
group by
strB
А по-нататък ще видя какво и как може да се оптимизира, раздели на нишки и т.н.
johnfound | Как ТОЧНО ще изпълнява SQL заявките? Какви ще са заявките, и в какъв достъп до данните ще се транслират те?
Е, ти сега искаш да ти реша задачата на SQL ли?
Във всеки случай, бих започнал с нещо такова:
create table setA(strA text); create table setB(strB text); select min(LsDist(strB, strA)) from setB left join setA group by strBА по-нататък ще видя какво и как може да се оптимизира, раздели на нишки и т.н.
И какви операции ще направи sqlite в този случай?
| И какви операции ще направи sqlite в този случай?
Ами пусни я и виж. Това си е твоя задача все пак.
johnfound | И какви операции ще направи sqlite в този случай?
Ами пусни я и виж. Това си е твоя задача все пак.
Няма нужда да го правя. Знам, че моят код е по-бърз. При това без да е оптимален.
П.П. Много е забавно когато някой фен на асемблера ми дава съвет да използвам sql за оптимален код. :)
П.П.2. Само една подсказка: това ВИНАГИ ще сравнява всяка двойка от стрингове.
Тоест твоя код не прави всяко с всяко ?
| Наистина ли мислиш, че потребителска функция в sqlite ще е по-добра от в момента работещия мноконишков, сравнително оптимизиран код? :) Защото той отнема около седмица на машина с 48*2 ядра, при това когато стринговете от колекция А е 100К. :) А компютрите имат много памет, може да предположиш че е безкрайно много (1.5 TB).
Ако питаш мен, аз не мисля, сигурен съм.
ФейкПрофил Тоест твоя код не прави всяко с всяко ?
Не
bvbfan | Наистина ли мислиш, че потребителска функция в sqlite ще е по-добра от в момента работещия мноконишков, сравнително оптимизиран код? :) Защото той отнема около седмица на машина с 48*2 ядра, при това когато стринговете от колекция А е 100К. :) А компютрите имат много памет, може да предположиш че е безкрайно много (1.5 TB).
Ако питаш мен, аз не мисля, сигурен съм.
Е, като се има предвид, че беше сигурен че ARM използва gcc, OK. :)