<bgdev />free

Вход Регистрация

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

0 1 2 3 4 5 6 7 8 9 ....12 13 14 15 16 ....23 24 25 26 27 ....32 33 34 35 36
#12613 (ツ) |
Последно редактирано на 26.09.2020 от |, видяно: 1528 пъти.
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 секунди на стринг. :)

#12614 (ツ) Golden Gega
Създадено на 26.09.2020, видяно: 1523 пъти.
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
#12618 (ツ) ФейкПрофил
Последно редактирано на 26.09.2020 от ФейкПрофил, видяно: 1512 пъти.

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

#12619 (ツ) Rabin
Последно редактирано на 26.09.2020 от Rabin, видяно: 1506 пъти.
johnfound

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

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

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

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

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

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

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

#12625 (ツ) |
Създадено на 26.09.2020, видяно: 1494 пъти.
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, но виждам само една таблица, а според мен трябва да са две. Та, нямам идея какво точно правиш. :)

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

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

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

ем, брутфорс - всяко с всяко рънва за 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.

#12639 (ツ) Golden Gega
Последно редактирано на 26.09.2020 от Golden Gega, видяно: 1477 пъти.
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

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

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

#12695 (ツ) Delegate
Последно редактирано на 26.09.2020 от Delegate, видяно: 1454 пъти.
|

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

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

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

#12697 (ツ) |
Последно редактирано на 26.09.2020 от |, видяно: 1446 пъти.
Delegate
|

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

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

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

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

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

#12701 (ツ) johnfound
Създадено на 26.09.2020, видяно: 1425 пъти.
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

#12703 (ツ) Унуфри
Създадено на 26.09.2020, видяно: 1423 пъти.
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

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

#12704 (ツ) Golden Gega
Последно редактирано на 26.09.2020 от Golden Gega, видяно: 1413 пъти.
|
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 диск

#12713 (ツ) |
Последно редактирано на 26.09.2020 от |, видяно: 1393 пъти.
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 милиона стринга от Б. :)

#12714 (ツ) |
Последно редактирано на 26.09.2020 от |, видяно: 1387 пъти.
Golden Gega

Резултат:

2020-09-26 22:19:13.857

2020-09-26 22:19:15.723

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

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

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

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

#12715 (ツ) synergie
Създадено на 26.09.2020, видяно: 1375 пъти.
|
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 от Го.

#12716 (ツ) Golden Gega
Създадено на 26.09.2020, видяно: 1375 пъти.
|
Golden Gega

Резултат:

2020-09-26 22:19:13.857

2020-09-26 22:19:15.723

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

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

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

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

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

#12717 (ツ) |
Създадено на 26.09.2020, видяно: 1373 пъти.
synergie

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

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

#12718 (ツ) |
Последно редактирано на 26.09.2020 от |, видяно: 1371 пъти.
Golden Gega

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

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

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

0 1 2 3 4 5 6 7 8 9 ....12 13 14 15 16 ....23 24 25 26 27 ....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