Не. Трябва на всеки Б-стринг да изчисляваш дистанцията до всеки стринг от А и да намираш минималната дистанция.
Ако това върши работа, рънва на средния ми лаптоп за 26 минути на postgreSQL 13 за 100К срещу 100 стринга без индекси, докато си слушам музичка и си браузвам.
Някой спец да избаца по-оптимален вариант да го тествам.
SELECT "Bstring", MIN("dist") FROM
(
SELECT n1."Bstring",n2."Astring", levenshtein_less_equal(n1."Bstring",n2."Astring",100) as dist
FROM (SELECT "Bstring" FROM public."Leven") n1 ,
public."Leven" n2
) n3 GROUP BY "Bstring"
Successfully run. Total query runtime: 26 min 7 secs.
101 rows affected.
Значи като начало пробвай да го препишеш на pgsql - тук имам само M$SQL - като смениш LEN с функцията за ЛевенЩЕЙН:
select * from (
select l1.astring, l2.bstring, LEN(l1.astring + l2.bstring) as l
from leven as l1, leven as l2
) r
order by l
ем, брутфорс - всяко с всяко рънва за 391 секунди (6:31) еднонишково на моя лаптоп. Това 26 минути цепи мрака
Rabin
Последно редактирано на 26.09.2020 от Rabin, видяно: 1708 пъти. #12619
Смятам, че достатъчно често съм доказвал, че пиша бързи програми. Точно сега нямам време за още един уъркшоп.
Доказа точно, че НЕ пишеш бързи програми. На няколко пъти ти пусках скрийншоти на най-бавното нещо дето съм виждал - пхп. Форум с хиляди юзери те отнася кат куцо пиле - домат.
По темата не съм компетентен, ник-путка верно се усети и ми призна. Тука повечето се обаждате за неща дето не разбирате. Не съм от тях.
Гугължийницата насмотаха мелеардите точно със сърч алгоритъм. Подозирам, че не е проста SQL заявка.
|
Създадено на 26.09.2020, видяно: 1697 пъти. #12623
ем, брутфорс - всяко с всяко рънва за 391 секунди (6:31) еднонишково на моя лаптоп. Това 26 минути цепи мрака
Това как е написано?
|
Създадено на 26.09.2020, видяно: 1696 пъти. #12625
На прав път ли съм ?
Не. Трябва на всеки Б-стринг да изчисляваш дистанцията до всеки стринг от А и да намираш минималната дистанция.
Ако това върши работа, рънва на средния ми лаптоп за 26 минути на postgreSQL 13 за 100К срещу 100 стринга без индекси, докато си слушам музичка и си браузвам.
Някой спец да избаца по-оптимален вариант да го тествам.
SELECT "Bstring", MIN("dist") FROM
(
SELECT n1."Bstring",n2."Astring", levenshtein_less_equal(n1."Bstring",n2."Astring",100) as dist
FROM (SELECT "Bstring" FROM public."Leven") n1 ,
public."Leven" n2
) n3 GROUP BY "Bstring"
Successfully run. Total query runtime: 26 min 7 secs.
101 rows affected.
Аз определено не съм специалист по SQL, но виждам само една таблица, а според мен трябва да са две. Та, нямам идея какво точно правиш. :)
ем, брутфорс - всяко с всяко рънва за 391 секунди (6:31) еднонишково на моя лаптоп. Това 26 минути цепи мрака
Това как е написано?
fn bruteforce<'a>(first: &'a [String], second: &'a [String], result: &mut HashMap<&'a str, MeasuredString<'a>>) {
for b in second.iter() {
let mut min_distance = usize::MAX;
let mut nearest = None;
for a in first.iter() {
let distance = levenshtein(b, a);
if distance < min_distance {
min_distance = distance;
nearest = Some(a);
}
}
if let Some(s) = nearest {
result.insert(b.as_str(), MeasuredString {
value: s.as_str(),
distance: min_distance,
});
}
}
}
като левенщайн функцията не съм си я писал аз ами най-безсрамно си я ползвам от външна библиотечка: https://docs.rs/strsim/0.10.0/strsim/fn.levenshtein.html
Прбвах и с BK-Tree, но поради много големия edit distance на практика се обхождат пак всички елементи и няма подобрение :( Или може би просто аз съм намазал нещо
|
Последно редактирано на 26.09.2020 от |, видяно: 1682 пъти. #12634
ем, брутфорс - всяко с всяко рънва за 391 секунди (6:31) еднонишково на моя лаптоп. Това 26 минути цепи мрака
Това как е написано?
fn bruteforce<'a>(first: &'a [String], second: &'a [String], result: &mut HashMap<&'a str, MeasuredString<'a>>) {
for b in second.iter() {
let mut min_distance = usize::MAX;
let mut nearest = None;
for a in first.iter() {
let distance = levenshtein(b, a);
if distance < min_distance {
min_distance = distance;
nearest = Some(a);
}
}
if let Some(s) = nearest {
result.insert(b.as_str(), MeasuredString {
value: s.as_str(),
distance: min_distance,
});
}
}
}
като левенщайн функцията не съм си я писал аз ами най-безсрамно си я ползвам от външна библиотечка: https://docs.rs/strsim/0.10.0/strsim/fn.levenshtein.html
Прбвах и с BK-Tree, но поради много големия edit distance на практика се обхождат пак всички елементи и няма подобрение :( Или може би просто аз съм намазал нещо
На моя лаптоп с моята си имплементация на trie на Go, с една нишка е 154 секунди. Но мисля, че моят лаптоп е по-бърз от твоя. Сега ще пробвам с най-лесната имплементация на много нишки.
Не. Трябва на всеки Б-стринг да изчисляваш дистанцията до всеки стринг от А и да намираш минималната дистанция.
Ако това върши работа, рънва на средния ми лаптоп за 26 минути на postgreSQL 13 за 100К срещу 100 стринга без индекси, докато си слушам музичка и си браузвам.
Някой спец да избаца по-оптимален вариант да го тествам.
SELECT "Bstring", MIN("dist") FROM
(
SELECT n1."Bstring",n2."Astring", levenshtein_less_equal(n1."Bstring",n2."Astring",100) as dist
FROM (SELECT "Bstring" FROM public."Leven") n1 ,
public."Leven" n2
) n3 GROUP BY "Bstring"
Successfully run. Total query runtime: 26 min 7 secs.
101 rows affected.
Аз определено не съм специалист по SQL, но виждам само една таблица, а според мен трябва да са две. Та, нямам идея какво точно правиш. :)
То и според мен малко постановката е омазана, в случая май се прави картезиански джойн на две копия от една таблица, по-добрия вариант е ако се ползва sql да е една таблица с две колони и при зареждането им с данни да се зарежда готов джойна, например:
Аз определено не съм специалист по SQL, но виждам само една таблица, а според мен трябва да са две. Та, нямам идея какво точно правиш. :)
В една таблица са, различни колони.Нали нагоре някой каза, че с sqlite ще стане бързо, ти настоя някой да се захване и тука се пробвам да докарам нещо на postgreSQL. Дайте си резултатите, на първите няколко стринга да видя дали са като мойте.
Много ясно, че неоптимизиран SQL скрипт ще е по-бавен от решение на С или Ръжда :)
|
Последно редактирано на 26.09.2020 от |, видяно: 1648 пъти. #12697
Аз определено не съм специалист по SQL, но виждам само една таблица, а според мен трябва да са две. Та, нямам идея какво точно правиш. :)
В една таблица са, различни колони.Нали нагоре някой каза, че с sqlite ще стане бързо, ти настоя някой да се захване и тука се пробвам да докарам нещо на postgreSQL. Дайте си резултатите, на първите няколко стринга да видя дали са като мойте.
Много ясно, че неоптимизиран SQL скрипт ще е по-бавен от решение на С или Ръжда :)
Не съм вкъщи да проверя, но мисле че първите 5 бяха 4,4,4,40,4.
Иначе според изключителните експерти johnfound и bvbfan, SQLite всъщност ще е по-бързо :). Само дето ги е срам да дадат резултати :)
johnfound
Създадено на 26.09.2020, видяно: 1627 пъти. #12701
Джони, не знам защо Bstring и b1, b2... станаха bold, не съм ползвал нищо за тях, да не е бъгче някакво?
Тъй като не си задал език в ;begin командата, изкуственият интелект се опитва да го разпознае какъв е и да го оцвети синтактично.
Не съм сигурен, че е точно бъг...
В момента се разпознават следните езици: css, less, scss, armasm, plaintext, javascript, x86asm, cpp, arduino, nginx, xml, markdown, ini, diff, http, sql, bash, avrasm, mipsasm
Нямам си на идея като какъв ти разпознава блока. Ако не ти харесва, можеш да използваш "plaintext".
Унуфри
Създадено на 26.09.2020, видяно: 1625 пъти. #12703
Джони, не знам защо Bstring и b1, b2... станаха bold, не съм ползвал нищо за тях, да не е бъгче някакво?
Тъй като не си задал език в ;begin командата, изкуственият интелект се опитва да го разпознае какъв е и да го оцвети синтактично.
Не съм сигурен, че е точно бъг...
В момента се разпознават следните езици: css, less, scss, armasm, plaintext, javascript, x86asm, cpp, arduino, nginx, xml, markdown, ini, diff, http, sql, bash, avrasm, mipsasm
Нямам си на идея като какъв ти разпознава блока. Ако не ти харесва, можеш да използваш "plaintext".
Аз определено не съм специалист по SQL, но виждам само една таблица, а според мен трябва да са две. Та, нямам идея какво точно правиш. :)
В една таблица са, различни колони.Нали нагоре някой каза, че с sqlite ще стане бързо, ти настоя някой да се захване и тука се пробвам да докарам нещо на postgreSQL. Дайте си резултатите, на първите няколко стринга да видя дали са като мойте.
Много ясно, че неоптимизиран SQL скрипт ще е по-бавен от решение на С или Ръжда :)
Не съм вкъщи да проверя, но мисле че първите 5 бяха 4,4,4,40,4.
Иначе според изключителните експерти johnfound и bvbfan, SQLite всъщност ще е по-бързо :). Само дето ги е срам да дадат резултати :)
Вече загубих началното условие, но ми стана интересно какво ще извади M$SQL с външна функция - понеже няма вградена. Домързя ме да вкарвам стрингове и т.н., затова теста е 10 000 еднакви стринга, т.е. 10к сравнения. Отчита се само сравнението, напълването е отделно, ползва се memory table, т.е. теоретично би трябвало да е максимално бързо за релационна база с mssql. Използва се това за Левенщайн.
Кода на t-sql
set nocount on
declare @tbl table (a varchar(150), b varchar (150))
declare @s varchar(150) = '012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789'
while (select count(*) from @tbl) < 10000
insert into @tbl (a, b) values (@s, @s)
declare @start datetime = getdate()
select dbo.Levenshtein(a, b) from @tbl
select @start
select getdate()
Резултат:
2020-09-26 22:19:13.857
2020-09-26 22:19:15.723
Това за i7-9750H / 2.60 GHz и nvme диск
|
Последно редактирано на 26.09.2020 от |, видяно: 1595 пъти. #12713
Аз определено не съм специалист по SQL, но виждам само една таблица, а според мен трябва да са две. Та, нямам идея какво точно правиш. :)
В една таблица са, различни колони.Нали нагоре някой каза, че с sqlite ще стане бързо, ти настоя някой да се захване и тука се пробвам да докарам нещо на postgreSQL. Дайте си резултатите, на първите няколко стринга да видя дали са като мойте.
Много ясно, че неоптимизиран SQL скрипт ще е по-бавен от решение на С или Ръжда :)
Не съм вкъщи да проверя, но мисле че първите 5 бяха 4,4,4,40,4.
Иначе според изключителните експерти johnfound и bvbfan, SQLite всъщност ще е по-бързо :). Само дето ги е срам да дадат резултати :)
Вече загубих началното условие, но ми стана интересно какво ще извади M$SQL с външна функция - понеже няма вградена. Домързя ме да вкарвам стрингове и т.н., затова теста е 10 000 еднакви стринга, т.е. 10к сравнения. Отчита се само сравнението, напълването е отделно, ползва се memory table, т.е. теоретично би трябвало да е максимално бързо за релационна база с mssql. Използва се това за Левенщайн.
Кода на t-sql
set nocount on
declare @tbl table (a varchar(150), b varchar (150))
declare @s varchar(150) = '012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789'
while (select count(*) from @tbl) < 10000
insert into @tbl (a, b) values (@s, @s)
declare @start datetime = getdate()
select dbo.Levenshtein(a, b) from @tbl
select @start
select getdate()
Резултат:
2020-09-26 22:19:13.857
2020-09-26 22:19:15.723
Това за i7-9750H / 2.60 GHz и nvme диск
Благодаря за тестовете.
Пробвай 100 хиляди, което е сравнението на един стринг от Б с всички стрингове от А, или 10 милиона, което е сравнението на 100 стринга от Б с всички стрингове от А.
И ако искаш да екстраполираш, сметни колко ще е с 23 милиона стринга от Б. :)
|
Последно редактирано на 26.09.2020 от |, видяно: 1589 пъти. #12714
Резултат:
2020-09-26 22:19:13.857
2020-09-26 22:19:15.723
Това за i7-9750H / 2.60 GHz и nvme диск
Без да съм експерт по релационни бази данни, струва ми се че този дизайн е нечестен и поставя БД в по-лоша светлина отколкото трябва. Просто защото в случая с една таблица тя става огромна защото трябва да съдържа комбинацията на всеки две двойки от стрингове.
По-честно ще е да има две таблици - по една за всяка от колекциите и после join.
Отделно са там теориите за нормални форми на БД и т.н. :)
synergie
Създадено на 26.09.2020, видяно: 1577 пъти. #12715
Резултат:
2020-09-26 22:19:13.857
2020-09-26 22:19:15.723
Това за i7-9750H / 2.60 GHz и nvme диск
Без да съм експерт по релационни бази данни, струва ми се че този дизайн е нечестен и поставя БД в по-лоша светлина отколкото трябва. Просто защото в случая с една таблица тя става огромна защото трябва да съдържа комбинацията на всеки две двойки от стрингове.
По-честно ще е да има две таблици - по една за всяка от колекциите и после join.
Отделно са там теориите за нормални форми на БД и т.н. :)
Ха-ха. Моля някой да обясни на |. Ако беше легенда като Рамбо досега да съм замерил на и7цата ми от 2012 с въртящ диск колко по бръз е sqlitea от Го.
Без да съм експерт по релационни бази данни, струва ми се че този дизайн е нечестен и поставя БД в по-лоша светлина отколкото трябва. Просто защото в случая с една таблица тя става огромна защото трябва да съдържа комбинацията на всеки две двойки от стрингове.
По-честно ще е да има две таблици - по една за всяка от колекциите и после join.
Отделно са там теориите за нормални форми на БД и т.н. :)
В интерес на истината този дизайн е нечестен спрямо твоето решение, понеже се използва готова таблица, без да се налага да се прави join
|
Създадено на 26.09.2020, видяно: 1575 пъти. #12717
Ха-ха. Моля някой да обясни на |. Ако беше легенда като Рамбо досега да съм замерил на и7цата ми от 2012 с въртящ диск колко по бръз е sqlitea от Го.
Я, synergie пак се опита да изквичи нещо. :)
|
Последно редактирано на 26.09.2020 от |, видяно: 1573 пъти. #12718
В интерес на истината този дизайн е нечестен спрямо твоето решение, понеже се използва готова таблица, без да се налага да се прави join
Не мисля. Особено ако вместо 10 хиляди имаме 10 милиона реда. Но, може и да греша. :)
П.П. Разбира се, ако стигнем до 2.3 трилиона реда от оригиналната задача, нещата стават особено интересни. :)