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
15.67 секунди на стринг. В момента рекорда е 0.01 секунди на стринг. :)
Значи като начало пробвай да го препишеш на 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 минути цепи мрака
Доказа точно, че НЕ пишеш бързи програми. На няколко пъти ти пусках скрийншоти на най-бавното нещо дето съм виждал - пхп. Форум с хиляди юзери те отнася кат куцо пиле - домат.
По темата не съм компетентен, ник-путка верно се усети и ми призна. Тука повечето се обаждате за неща дето не разбирате. Не съм от тях.
Гугължийницата насмотаха мелеардите точно със сърч алгоритъм. Подозирам, че не е проста SQL заявка.
Аз определено не съм специалист по SQL, но виждам само една таблица, а според мен трябва да са две. Та, нямам идея какво точно правиш. :)
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.
Джони, не знам защо Bstring и b1, b2... станаха bold, не съм ползвал нищо за тях, да не е бъгче някакво?
В една таблица са, различни колони.Нали нагоре някой каза, че с sqlite ще стане бързо, ти настоя някой да се захване и тука се пробвам да докарам нещо на postgreSQL. Дайте си резултатите, на първите няколко стринга да видя дали са като мойте.
Много ясно, че неоптимизиран SQL скрипт ще е по-бавен от решение на С или Ръжда :)
Не съм вкъщи да проверя, но мисле че първите 5 бяха 4,4,4,40,4.
Иначе според изключителните експерти johnfound и bvbfan, SQLite всъщност ще е по-бързо :). Само дето ги е срам да дадат резултати :)
Тъй като не си задал език в ;begin командата, изкуственият интелект се опитва да го разпознае какъв е и да го оцвети синтактично.
Не съм сигурен, че е точно бъг...
В момента се разпознават следните езици: css, less, scss, armasm, plaintext, javascript, x86asm, cpp, arduino, nginx, xml, markdown, ini, diff, http, sql, bash, avrasm, mipsasm
Нямам си на идея като какъв ти разпознава блока. Ако не ти харесва, можеш да използваш "plaintext".
Използва се highlight.js
Форумът ти има изкуствен интелект? Рабин ли имаш впредвид?
Вече загубих началното условие, но ми стана интересно какво ще извади 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 милиона стринга от Б. :)
Без да съм експерт по релационни бази данни, струва ми се че този дизайн е нечестен и поставя БД в по-лоша светлина отколкото трябва. Просто защото в случая с една таблица тя става огромна защото трябва да съдържа комбинацията на всеки две двойки от стрингове.
По-честно ще е да има две таблици - по една за всяка от колекциите и после join.
Отделно са там теориите за нормални форми на БД и т.н. :)
Ха-ха. Моля някой да обясни на |. Ако беше легенда като Рамбо досега да съм замерил на и7цата ми от 2012 с въртящ диск колко по бръз е sqlitea от Го.
В интерес на истината този дизайн е нечестен спрямо твоето решение, понеже се използва готова таблица, без да се налага да се прави join 
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