<bgdev />free

Вход

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

0 1 2 3 4 ....17 18 19 20 21 ....32 33 34 35 36
#11143 (ツ) |
Създадено на 19.09.2020, видяно: 1565 пъти.
ФейкПрофил

Как ще го смятате, по възможност без "фактори"? :)

как :)

Чакам вие да кажете първо, за да не ви вкарвам в коловоз. Моето решение определено не е оптимално.

#11150 (ツ) bvbfan
Създадено на 20.09.2020, видяно: 1545 пъти.

SQLite, blob за полетата, Levenstein в кода и дерзаеш.

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

Грешките може да са до над 100, но да предположим че ни интересува match с до 64 грешки.

Това какво значи? Че може да се дават като решение стрингове чието растояние на Левенщайн всъщност не е най-малкото в множество А?

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

Между другото, идеята на bvbfan съвсем не е лоша. Просто трябва да се имплементира потребителска функция за растоянието на Левенщайн в sqlite и директно да се напише заявка на SQL. Резултата може да се окаже съвсем изненадващо добър. ;-)

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

Грешките може да са до над 100, но да предположим че ни интересува match с до 64 грешки.

Това какво значи? Че може да се дават като решение стрингове чието растояние на Левенщайн всъщност не е най-малкото в множество А?

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

Levenshtеin distance се смята между стрингове, които не съвпадат точно. Може да има до 100 такива разлики между стринговете. В общи линии, стринговете в колекция Б са грешни копия на стринговете е колекция А. Отделно му трябва и къде са грешките като позиция, както и какъв тип грешка е (insertion, deletion, substitution), но това са подробности и може да се сметне по-късно.

johnfound

Между другото, идеята на bvbfan съвсем не е лоша. Просто трябва да се имплементира потребителска функция за растоянието на Левенщайн в sqlite и директно да се напише заявка на SQL. Резултата може да се окаже съвсем изненадващо добър. ;-)

Наистина ли мислиш, че потребителска функция в sqlite ще е по-добра от в момента работещия мноконишков, сравнително оптимизиран код? :) Защото той отнема около седмица на машина с 48*2 ядра, при това когато стринговете от колекция А е 100К. :) А компютрите имат много памет, може да предположиш че е безкрайно много (1.5 TB).

#11192 (ツ) ФейкПрофил
Създадено на 20.09.2020, видяно: 1506 пъти.

Някакви гени/днкта ли джуркаш ?

#11193 (ツ) |
Създадено на 20.09.2020, видяно: 1503 пъти.
ФейкПрофил

Някакви гени/днкта ли джуркаш ?

Нещо такова, но по-просто.

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

Levenshtеin distance се смята между стрингове, които не съвпадат точно. Може да има до 100 такива разлики между стринговете. В общи линии, стринговете в колекция Б са грешни копия на стринговете е колекция А. Отделно му трябва и къде са грешките като позиция, както и какъв тип грешка е (insertion, deletion, substitution), но това са подробности и може да се сметне по-късно.

Тоест, си искал да кажеш че търсиш минималното разстояние, но не по-голямо от 100 (64). Понятието "грешка" в този контекст е заблуждаващо, още повече, че в предишното изречение използваш правилната дума "разстояние" в същият смисъл.

|

Наистина ли мислиш, че потребителска функция в sqlite ще е по-добра от в момента работещия мноконишков, сравнително оптимизиран код? :) Защото той отнема около седмица на машина с 48*2 ядра, при това когато стринговете от колекция А е 100К. :) А компютрите имат много памет, може да предположиш че е безкрайно много (1.5 TB).

Каква връзка имат нишките тука? SQLite също може да работи паралелно в много нишки, заявките могат ефективно да се разпаралелят, а SQLite има сериозно оптимизиран код, който със сигурност ще е по-бърз от това, което сте писали набързо.

Евентуално може да има проблеми само ако искате да изпълнявате на клъстър по мрежата, но и тогава може да се измисли нещо.

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

Каква връзка имат нишките тука? SQLite също може да работи паралелно в много нишки, заявките могат ефективно да се разпаралелят, а SQLite има сериозно оптимизиран код, който със сигурност ще е по-бърз от това, което сте писали набързо.

И какво точно ще направи този "сериозно оптимизиран код" в sqlite? :) Можеш ли да го опишеш?

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

Между другото, специално в био-информатиката се смята за по-подходящо да се използва разстоянието на Дамерау-Левенщейн в което размяната на местата на два символа е една операция, а не 2.

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

И какво точно ще направи този "сериозно оптимизиран код" в sqlite? :) Можеш ли да го опишеш?

В смисъл? Ще изпълнява SQL заявките, какво друго може да прави кода в SQL база данни?

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

Между другото, специално в био-информатиката се смята за по-подходящо да се използва разстоянието на Дамерау-Левенщайн в което размяната на местата на два символа е една операция, а не 2.

Не и в този случай.

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

И какво точно ще направи този "сериозно оптимизиран код" в sqlite? :) Можеш ли да го опишеш?

В смисъл? Ще изпълнява SQL заявките, какво друго може да прави кода в SQL база данни?

Как ТОЧНО ще изпълнява SQL заявките? Какви ще са заявките, и в какъв достъп до данните ще се транслират те?

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

Как ТОЧНО ще изпълнява 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 

А по-нататък ще видя какво и как може да се оптимизира, раздели на нишки и т.н.

#11214 (ツ) |
Създадено на 20.09.2020, видяно: 1470 пъти.
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 в този случай?

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

И какви операции ще направи sqlite в този случай?

Ами пусни я и виж. Това си е твоя задача все пак.

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

И какви операции ще направи sqlite в този случай?

Ами пусни я и виж. Това си е твоя задача все пак.

Няма нужда да го правя. Знам, че моят код е по-бърз. При това без да е оптимален.

П.П. Много е забавно когато някой фен на асемблера ми дава съвет да използвам sql за оптимален код. :)

П.П.2. Само една подсказка: това ВИНАГИ ще сравнява всяка двойка от стрингове.

#11220 (ツ) ФейкПрофил
Създадено на 20.09.2020, видяно: 1459 пъти.

Тоест твоя код не прави всяко с всяко ?

#11221 (ツ) bvbfan
Създадено на 20.09.2020, видяно: 1459 пъти.
|

Наистина ли мислиш, че потребителска функция в sqlite ще е по-добра от в момента работещия мноконишков, сравнително оптимизиран код? :) Защото той отнема около седмица на машина с 48*2 ядра, при това когато стринговете от колекция А е 100К. :) А компютрите имат много памет, може да предположиш че е безкрайно много (1.5 TB).

Ако питаш мен, аз не мисля, сигурен съм.

#11223 (ツ) |
Създадено на 20.09.2020, видяно: 1457 пъти.
ФейкПрофил

Тоест твоя код не прави всяко с всяко ?

Не

#11225 (ツ) |
Създадено на 20.09.2020, видяно: 1455 пъти.
bvbfan
|

Наистина ли мислиш, че потребителска функция в sqlite ще е по-добра от в момента работещия мноконишков, сравнително оптимизиран код? :) Защото той отнема около седмица на машина с 48*2 ядра, при това когато стринговете от колекция А е 100К. :) А компютрите имат много памет, може да предположиш че е безкрайно много (1.5 TB).

Ако питаш мен, аз не мисля, сигурен съм.

Е, като се има предвид, че беше сигурен че ARM използва gcc, OK. :)

0 1 2 3 4 ....17 18 19 20 21 ....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