Delegate

johnfound

Delegate

На прав път ли съм ?

Не. Трябва на всеки Б-стринг да изчисляваш дистанцията до всеки стринг от А и да намираш минималната дистанция.

Ако това върши работа, рънва на средния ми лаптоп за 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.

15.67 секунди на стринг. В момента рекорда е 0.01 секунди на стринг. :)

Delegate

johnfound

Delegate

На прав път ли съм ?

Не. Трябва на всеки Б-стринг да изчисляваш дистанцията до всеки стринг от А и да намираш минималната дистанция.

Ако това върши работа, рънва на средния ми лаптоп за 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 минути цепи мрака

johnfound

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

Доказа точно, че НЕ пишеш бързи програми. На няколко пъти ти пусках скрийншоти на най-бавното нещо дето съм виждал - пхп. Форум с хиляди юзери те отнася кат куцо пиле - домат.

По темата не съм компетентен, ник-путка верно се усети и ми призна. Тука повечето се обаждате за неща дето не разбирате. Не съм от тях.

Гугължийницата насмотаха мелеардите точно със сърч алгоритъм. Подозирам, че не е проста SQL заявка.

ФейкПрофил

ем, брутфорс - всяко с всяко рънва за 391 секунди (6:31) еднонишково на моя лаптоп. Това 26 минути цепи мрака

Това как е написано?

Delegate

johnfound

Delegate

На прав път ли съм ?

Не. Трябва на всеки Б-стринг да изчисляваш дистанцията до всеки стринг от А и да намираш минималната дистанция.

Ако това върши работа, рънва на средния ми лаптоп за 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 на практика се обхождат пак всички елементи и няма подобрение :( Или може би просто аз съм намазал нещо

ФейкПрофил

|

ФейкПрофил

ем, брутфорс - всяко с всяко рънва за 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 секунди. Но мисля, че моят лаптоп е по-бърз от твоя. Сега ще пробвам с най-лесната имплементация на много нишки.

С много нишки е 21 секунди. 8-core Intel i9.

Golden Gega

|

Delegate

johnfound

Delegate

На прав път ли съм ?

Не. Трябва на всеки Б-стринг да изчисляваш дистанцията до всеки стринг от А и да намираш минималната дистанция.

Ако това върши работа, рънва на средния ми лаптоп за 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 да е една таблица с две колони и при зареждането им с данни да се зарежда готов джойна, например:

tbl.Astring, tbl.BString

a1, b1
a2, b1
a1, b2
a2, b2

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

Джони, не знам защо Bstring и b1, b2... станаха bold, не съм ползвал нищо за тях, да не е бъгче някакво?

|

Аз определено не съм специалист по SQL, но виждам само една таблица, а според мен трябва да са две. Та, нямам идея какво точно правиш. :)

В една таблица са, различни колони.Нали нагоре някой каза, че с sqlite ще стане бързо, ти настоя някой да се захване и тука се пробвам да докарам нещо на postgreSQL. Дайте си резултатите, на първите няколко стринга да видя дали са като мойте.

Много ясно, че неоптимизиран SQL скрипт ще е по-бавен от решение на С или Ръжда :)

Delegate

|

Аз определено не съм специалист по SQL, но виждам само една таблица, а според мен трябва да са две. Та, нямам идея какво точно правиш. :)

В една таблица са, различни колони.Нали нагоре някой каза, че с sqlite ще стане бързо, ти настоя някой да се захване и тука се пробвам да докарам нещо на postgreSQL. Дайте си резултатите, на първите няколко стринга да видя дали са като мойте.

Много ясно, че неоптимизиран SQL скрипт ще е по-бавен от решение на С или Ръжда :)

Не съм вкъщи да проверя, но мисле че първите 5 бяха 4,4,4,40,4.

Иначе според изключителните експерти johnfound и bvbfan, SQLite всъщност ще е по-бързо :). Само дето ги е срам да дадат резултати :)

Golden Gega

Джони, не знам защо 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".

Използва се highlight.js

johnfound

Golden Gega

Джони, не знам защо 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".

Използва се highlight.js

Форумът ти има изкуствен интелект? Рабин ли имаш впредвид?

|

Delegate

|

Аз определено не съм специалист по 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 диск

Golden Gega

|

Delegate

|

Аз определено не съм специалист по 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 милиона стринга от Б. :)

Golden Gega

Резултат:

2020-09-26 22:19:13.857

2020-09-26 22:19:15.723

Това за i7-9750H / 2.60 GHz и nvme диск

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

По-честно ще е да има две таблици - по една за всяка от колекциите и после join.

Отделно са там теориите за нормални форми на БД и т.н. :)

|

Golden Gega

Резултат:

2020-09-26 22:19:13.857

2020-09-26 22:19:15.723

Това за i7-9750H / 2.60 GHz и nvme диск

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

По-честно ще е да има две таблици - по една за всяка от колекциите и после join.

Отделно са там теориите за нормални форми на БД и т.н. :)

Ха-ха. Моля някой да обясни на |. Ако беше легенда като Рамбо досега да съм замерил на и7цата ми от 2012 с въртящ диск колко по бръз е sqlitea от Го.

|

Golden Gega

Резултат:

2020-09-26 22:19:13.857

2020-09-26 22:19:15.723

Това за i7-9750H / 2.60 GHz и nvme диск

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

По-честно ще е да има две таблици - по една за всяка от колекциите и после join.

Отделно са там теориите за нормални форми на БД и т.н. :)

В интерес на истината този дизайн е нечестен спрямо твоето решение, понеже се използва готова таблица, без да се налага да се прави join

synergie

Ха-ха. Моля някой да обясни на |. Ако беше легенда като Рамбо досега да съм замерил на и7цата ми от 2012 с въртящ диск колко по бръз е sqlitea от Го.

Я, synergie пак се опита да изквичи нещо. :)

Golden Gega

В интерес на истината този дизайн е нечестен спрямо твоето решение, понеже се използва готова таблица, без да се налага да се прави join

Не мисля. Особено ако вместо 10 хиляди имаме 10 милиона реда. Но, може и да греша. :)

П.П. Разбира се, ако стигнем до 2.3 трилиона реда от оригиналната задача, нещата стават особено интересни. :)