<bgdev />free

| |  


All tags 1will 2023 2code 3for 4food 9may ai algorithm alpha amd american api argon2 arm asm asmbb assembler attachment awareness balgaria bay888 bcrypt bender beta bgdev-next bgdev-next.👍 big.data bitchnigga bitcoin bmw boi borg brexit bug bulgaria business c cad chat cloud computer-names console crossorigin deprivation desktop dna dotnet email eupl falling feature forum fp fresh fun game github google gpl gpt gpt.3.5 gypsies harvard hash improvement include investment it java javascript js kleta kleta.maqka.balg lambi language learning leftovers legend level levenshtein.dist libx license linkedlist linux ma mcafee mele microsoft minimag minimalism negro net nginx nigga not.a.bug oop paradigm parler patterns perception persuasion pipe play.station politics populi pornhub pow pro programming protonmail python reba rust sci-fi scripting seks seo server shell sleep smartbeauty soft-skills sqlite srabska sse starship sugerface syntax tablet tailwindcss telegram theme thug troll80lvl tutanota typescript uacme ui uk unix untermensch upload uptime usa utilities ux vb via viber virtual.reality vox vps vulnerable war wasm weapons-grade web windows word x86 xbox xss youtube zig ziglang Übermensch БОКЕБЪЛГАРИН БЪ БЪлгария Белезниците Били Били.Белезниците БялДонор Веган Виста Възраждане ГЛУПАК Гана Глиста ЕС Казарма Копейкин Мода.и.овча.мисъ НЕКАДЪРНИК НРБ ПО-ЗЛЕ.И.ОТ.РАБИ Подкасти Разни Румен СИК СКУМ СетенЧук Скум ТИР Туче Украйна Урсула Яначков авангард аз айфонджия алгоритми амбиции анархизъм антиваксъри армения аудио аутисти бази.данни без без.пръчове безпросвета бенчмарк биготи биомаса бира боклук борисов ботев брадва булшит бъг бъгове бял ваксина вандал век венерика викинги вицове вишу война вървежен гана ганорник гей гейщина германия герои гешев глупак говеда групировка гюбек данъкоплатец двойни.стандарти дедотия демокрация дизайн дисциплина добитък докери долар донори држава дришльо дрон ебане еврогейски.съюз езици експеримент електроника електроника.s2 емиграция ендпойнт енум ерген ергономия жалкар задача затоплизъм защита здраве златен злато игри идеали идиократ идиократи идиокрация идиот избори избори.рабин изкуство икономика имбецили имейл инвестиране инокулация инструмента интервю ипад искам.да.си.реда казах камшикодържач капитализъм карабах караница картечница кино клавиатура ковид19 колайдер колям.кур комари комплексар комунизъм консолидация конспирации космонавтика кофа кофит-19 краставица криптовалути курви кучелюбци лайно лаладжия лаптоп либерастия литература лоши.практики луд лъжеучени лъжец любов майни майтапи малоумници мафия мениджмънт месо местене метавселена метафизика механика мистика мисъл мода мода.овча.мисъл модерация морал мутра мутри наука национализъм не.it негър некадърник некадърници неон нидерландия овча овчи олигофрени организация офтопик парички партия педал пенджури пенсия пишока плюскане победа погромист поезия политика порно посредствен почивка празници прасе превод предалщина програмиране проект проста простотии против.правилата проф пръч пръч.дришльо пръчка психика психични.болести психология пустиняк путин путката путьо рабин рабин.е.шибан.пе работа радост разврат разни разработка расизъм резерват рейтинг реклама рекламен религия рест ризи ропче ропчета русия руски.език рутина самоковска сасипаха секира село селяндур сериали сериозно.програм сетен сеянин симулация скопяване скръм слушалки сортиране софия софтуер софтуни социализъм спектрометър спринтове сране стандарти стил стуйо стюи сушилня сцена съвет съм сън сървър сърничка таб ташаци телевизия тема територията терминология термояд технологии титли традиция тролинг тръмп туба туче тъпак тъпанари тъпня уиндоус украйна умнокрасивци фалит фантастика фашизъм фейк.акаунти физика филми форум форумни.проекти футбол хазарт хамали харабия хардуер хахаха хомофобия хостинг храна хумор цайко цайси целофан цензура цензурра циганин чалга чалгар чекии чернокраки честота чипове чнг чужбина чук шпация щайга юан яката яко ям 🔨 😂 🪓


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

  

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


  |  Последно редактирано на 26.09.2020 от |, видяно: 1730 пъти. #12613
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 секунди на стринг. :)



  Golden Gega  Създадено на 26.09.2020, видяно: 1725 пъти. #12614
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


  ФейкПрофил  Последно редактирано на 26.09.2020 от ФейкПрофил, видяно: 1714 пъти. #12618

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



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

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

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

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

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



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

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

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



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



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

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

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



  Golden Gega  Последно редактирано на 26.09.2020 от Golden Gega, видяно: 1679 пъти. #12639
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, не съм ползвал нищо за тях, да не е бъгче някакво?



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

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

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

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



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

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

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

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

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

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



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



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

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



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



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



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

Резултат:

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
|
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  Създадено на 26.09.2020, видяно: 1577 пъти. #12716
|
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



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

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

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



  |  Последно редактирано на 26.09.2020 от |, видяно: 1573 пъти. #12718
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


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

  



AsmBB v3.0 (check-in: bba3e7860d0627ec); SQLite v3.47.0 (check-in: 03a9703e27c44437);
©2016..2024 John Found; Licensed under EUPL; Powered by Assembly language Created with Fresh IDE