<bgdev />free

Вход

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

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

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

Не

Добре, освен правилото за "неравенството на триъгълника" не се сещам за някакво друго свойство на edit distance което да може да се ползва, не че и това ни мога по някакъв начин. Сигурен ли си, че с информацията която си дал може да се стигне до решение ? Тези стрингове имат ли някакви зависимости помежду си ?

ПП: metric tree ?

#11240 (ツ) |
Последно редактирано на 20.09.2020 от |, видяно: 1487 пъти.
ФейкПрофил
|
ФейкПрофил

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

Не

Добре, освен правилото за "неравенството на триъгълника" не се сещам за някакво друго свойство на edit distance което да може да се ползва, не че и това ни мога по някакъв начин. Сигурен ли си, че с информацията която си дал може да се стигне до решение ? Тези стрингове имат ли някакви зависимости помежду си ?

ПП: metric tree ?

Някой вече спомена: DNA.

Правя trie с елементите на една от колекциите, търся елементите от другата като давам максимално разстояние. Не е кой знае какво, но определено не сравнява всяка двойка стрингове.

#11246 (ツ) ФейкПрофил
Последно редактирано на 20.09.2020 от ФейкПрофил, видяно: 1482 пъти.

А разстоянието как го мериш в дървото ? Нали могат да се махат/добавят/сменят елементи, някак си много сложно иглежда.

http://stevehanov.ca/blog/index.php?id=130

#11248 (ツ) |
Последно редактирано на 20.09.2020 от |, видяно: 1475 пъти.
ФейкПрофил

А разстоянието как го мериш в дървото ? Нали могат да се махат/добавят/сменят елементи, някак си много сложно иглежда

Има някакъв trie search с levenshtein distance. В моят случай дървото се прави веднъж в началото и после само се търси.

K-D дърветата ги знам, разбира се, ще погледна VP trees.

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

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

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

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

Реално си бях прав, точно преди 5г. когато престанах да се занимавам с ембедед, тогава clang на връбница. Това съм го пробвал доста по-скоро.

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

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

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

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

Реално си бях прав, точно преди 5г. когато престанах да се занимавам с ембедед, тогава clang на връбница. Това съм го пробвал доста по-скоро.

Какво си пробвал по-скоро. Да търсиш минимална levenshtein distance между две колекции от стрингове? С sqlite vs. DRAM? :)

А иначе, ако си спомняш тезата ми тогва беше, че llvm изритва gcc отвсякъде. Опита отпреди 5 години няма как да има общо с реалността сега.

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

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

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

Направо на ръст :evil:

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

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

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

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

Реално си бях прав, точно преди 5г. когато престанах да се занимавам с ембедед, тогава clang на връбница. Това съм го пробвал доста по-скоро.

Какво си пробвал по-скоро. Да търсиш минимална levenshtein distance между две колекции от стрингове? С sqlite vs. DRAM? :)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Нормално, без да съм го видял. Ако си писал и на Джава - :-) Очаквай в пъти да е по-бърз sqlite. Напиши си функцията на С, и си слагай в заявки.

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

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

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

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

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

Нормално, без да съм го видял. Ако си писал и на Джава - :-) Очаквай в пъти да е по-бърз sqlite. Напиши си функцията на С, и си слагай в заявки.

Функцията я имам и на C и на Go. На C e малко дървена, понеже ще я пробвам на GPU като се наканя.

Досега не си написал абсолютно нищо, което може да ме убеди, че sqlite може да е по-бърз.

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

Не знам какво очакваш да ти напиша, levenstein е една елементарна функция, ползвах я преди години. Освен нея ти трябват заявки към базата и получаваш данните, във всякакъв ред, в зависимост от завката. Чисто и ясен код.

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

Не знам какво очакваш да ти напиша, levenstein е една елементарна функция, ползвах я преди години. Освен нея ти трябват заявки към базата и получаваш данните, във всякакъв ред, в зависимост от завката. Чисто и ясен код.

Всеки два стринга ли ще сравни? Левенщайн може да е чиста, но това не означава, че е бърза.

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

Не знам какво очакваш да ти напиша, levenstein е една елементарна функция, ползвах я преди години. Освен нея ти трябват заявки към базата и получаваш данните, във всякакъв ред, в зависимост от завката. Чисто и ясен код.

Всеки два стринга ли ще сравни? Левенщайн може да е чиста, но това не означава, че е бърза.

Ами виж сега, това, което ти правиш с това trie, реално е просто прекратяване на изчислението на дистанцията, ако е по-дълга от зададената максимална стойност (64). Но алгоритъма пак си остава О(n.m), просто защото трябва да сравниш всеки със всеки, за да знаеш кой е с минимална дистанция. И от тази сложност принципно не може да се избяга.

Но това лесно се имплементира и във функцията за пресмятане на разстоянието - просто когато стигне до 65 трябва да връща безкрайност и да не сравнява стринговете нататък.

Евентуално, ако сортираш стринговете в сет А, може да се окаже, че тези, които са със разстояние < 65 образуват някаква група и можеш да смяташ само в тази група. Но това също лесно се организира в SQLite чрез индекси и съответно параметрите във where клаузата.

Освен това, тъй като разстоянието L(s1,s2) >= ||len(s1)| - |len(s2)||, то можеш да си спестиш доста, като просто вкараш и дължините на стринговете в базата и сравняваш само тези, които също са с подходяща дължина. За това също ще ти помогнат индекси и правилните заявки. Колко печалба ще имаш, зависи от разпределението на стринговете по дължини.

#11284 (ツ) synergie
Създадено на 20.09.2020, видяно: 1408 пъти.
johnfound
|
bvbfan

Не знам какво очакваш да ти напиша, levenstein е една елементарна функция, ползвах я преди години. Освен нея ти трябват заявки към базата и получаваш данните, във всякакъв ред, в зависимост от завката. Чисто и ясен код.

Всеки два стринга ли ще сравни? Левенщайн може да е чиста, но това не означава, че е бърза.

Ами виж сега, това, което ти правиш с това trie, реално е просто прекратяване на изчислението на дистанцията, ако е по-дълга от зададената максимална стойност (64). Но алгоритъма пак си остава О(n.m), просто защото трябва да сравниш всеки със всеки, за да знаеш кой е с минимална дистанция. И от тази сложност принципно не може да се избяга.

Но това лесно се имплементира и във функцията за пресмятане на разстоянието - просто когато стигне до 65 трябва да връща безкрайност и да не сравнява стринговете нататък.

Евентуално, ако сортираш стринговете в сет А, може да се окаже, че тези, които са със разстояние < 65 образуват някаква група и можеш да смяташ само в тази група. Но това също лесно се организира в SQLite чрез индекси и съответно параметрите във where клаузата.

Освен това, тъй като разстоянието L(s1,s2) >= ||len(s1)| - |len(s2)||, то можеш да си спестиш доста, като просто вкараш и дължините на стринговете в базата и сравняваш само тези, които също са с подходяща дължина. За това също ще ти помогнат индекси и правилните заявки. Колко печалба ще имаш, зависи от разпределението на стринговете по дължини.

Видях я тая глупост с trie-то още като я пусна, но между сауните и жакузитата тука не ми остана време да пиша. Потвърждава тезата ми че пайпа не знае какво е Биг О.

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

Не знам какво очакваш да ти напиша, levenstein е една елементарна функция, ползвах я преди години. Освен нея ти трябват заявки към базата и получаваш данните, във всякакъв ред, в зависимост от завката. Чисто и ясен код.

Всеки два стринга ли ще сравни? Левенщайн може да е чиста, но това не означава, че е бърза.

Ами виж сега, това, което ти правиш с това trie, реално е просто прекратяване на изчислението на дистанцията, ако е по-дълга от зададената максимална стойност (64). Но алгоритъма пак си остава О(n.m), просто защото трябва да сравниш всеки със всеки, за да знаеш кой е с минимална дистанция. И от тази сложност принципно не може да се избяга.

Но това лесно се имплементира и във функцията за пресмятане на разстоянието - просто когато стигне до 65 трябва да връща безкрайност и да не сравнява стринговете нататък.

Евентуално, ако сортираш стринговете в сет А, може да се окаже, че тези, които са със разстояние < 65 образуват някаква група и можеш да смяташ само в тази група. Но това също лесно се организира в SQLite чрез индекси и съответно параметрите във where клаузата.

Освен това, тъй като разстоянието L(s1,s2) >= ||len(s1)| - |len(s2)||, то можеш да си спестиш доста, като просто вкараш и дължините на стринговете в базата и сравняваш само тези, които също са с подходяща дължина. За това също ще ти помогнат индекси и правилните заявки. Колко печалба ще имаш, зависи от разпределението на стринговете по дължини.

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

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

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

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

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

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

Как каквото и да правя с функцията ще промени факта, че 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

Задача НЕ за интервю
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