Prefix trie всяко листо се разклонява на общ префикс, Radix trie имаш power of 2 листа, Ternary Search - ляв, равен и десен и т.н.
Какво да стане с функцията, тя е левенщайн, приемаш 2 стринга и връщаш близостта.
Задача НЕ за интервю
0 1 2 3 4 ...14 15 16 17 18 ...30 31 32 33 34 35 36
Prefix trie. Казах ти, най-простото.
Kak ще я направиш бърза на GPU?
db.define("LEVENSTEIN", [](std::string_view s1, std::string_view s2) -> int {
const auto m = s1.size();
const auto n = s2.size();
if(m == 0) return n;
if(n == 0) return m;
std::vector<size_t> costs;
costs.resize(n + 1);
for (auto i = 0u; i < n + 1; ++i)
costs[i] = i + 1;
for (auto i = 0u; i < m; ++i) {
costs[0] = i + 1;
std::size_t corner = i;
for (auto j = 0u; j < n; ++j) {
auto upper = costs[j + 1];
if(s1[i] == s2[j]) {
costs[j + 1] = corner;
} else {
auto t = std::min(upper, corner);
costs[j + 1] = std::min(costs[j], t) + 1;
}
corner = upper;
}
}
return costs[n];
});
auto levenstein = db << "SELECT r.word as rw, MIN(LEVENSTEIN(?, r.word)) FROM right r";
db << "SELECT l.word FROM left l ORDER BY l.word"
>> [&](std::string_view v) {
levenstein << v >> [v](std::string_view s1, int leve) {
std::cout << v << " : " << s1 << " : " << leve << '\n';
};
levenstein++;
};
db << "SELECT l.word, r.word, MIN(LEVENSTEIN(l.word, r.word)) as l "
"FROM left l JOIN right r GROUP BY l.word HAVING l < 60"
>> [&](std::string_view s1, std::string_view s2, int leve) {
std::cout << s1 << " : " << s2 << " : " << leve << '\n';
};
Разбито на заявки е по-бързо от една заявка, някой по-добър да обясни?
g++ -Wall -std=c++17 -O3 -march=native main.cpp -o leve -lsqlite3
Може да се добави sqlite amalgamation за да се компилира и той с - O3, че стандартните са с - O2.
Интересно решение. При мене работи не много бързо, но не свръх бавно: примерно 10 секунди на ред.
Две забележки - добре е да качиш и базата данни с тестовите данни, защото не е ясно кое е left и кое right на пръв поглед. (В left отиват редовете от файла t2.csv, а в right от Dataset.csv).
Също добре е да извеждаш rowid-то на left защото резултатите излизат разбъркани и е трудно да се следят за коректност. Обратно - самите стрингове с данни можеш да не ги извеждаш, защото са много малко информативни.
Освен това имаш грешка в този ред:
db << "CREATE TABLE IF NOT EXISTS right (word BLOB NOT NULL PRIMARI KEY);";
Но ако сложиш и създадената база в архива, то тези редове можеш и въобще да ги махнеш.
Най-накрая успях да фиксна Windows версията, така че прикачам файл с компилираните програми с използване на SSE2, ако някой иска да тества на Windows с последната версия.
Проблема се оказа в това, че HeapAlloc на Windows алокира паметта подравнена на 8 байта, а аз си мислех, че е на 16. (Но WINE версията подравнява на 16, което прави програмата да работи във WINE, но не и във Windows! 
)
В резултат се наложи да се модифицира FreshLib слоя за Win32 - защото програмите трябва да се държат еднакво при прекомпилиране на различните операционни системи.
Така че, който иска да компилира от сорс, ще трябва да си ъпдейтне и версията на FreshLibDev от репозиторито.
Чакай сега, нали sqlite щеше да е по-бързо от моят C код, понеже го бил писал някакъв C гуру? :)
Да, векторизацията доведе до по-лош резултат. Да не говорим, че кода стана доста по-неразбираем и сложен.
И аз да се включа с avx2 решение на асемблер. 61мс средно на низ дава при мен. Това как се дебъгва под wine не е истина.
Ами да, малко странен стил на кода - засукан. А защо трябваше да е за Windows?
За съжаление не работи на Pentium P3540 – няма AVX. Ще го пробвам на AMD-то по-късно днес.
Windows има по-добрата конвенция на извикване в 64 битов режим.
При мен, разбито на заявки е под 3 сек. на ред, с една заявка поне 2 пъти по-бавно. left е t2.csv (сета от думи, на които се търсят най-близките в дясно), right e Dataset.csv (по-големият сет, в който се търсят съвпаденията).
По подразбиране в повечето дистрибуции не се прилагат големи оптимизации при компилиранe и линкване, има и изключения - Open Mandriva използват - O3 и LTO, което е достатъчно оптимизирано. Освен това, статичното линкване и O3 ще ти даде нужното ускорение, все пак за нас е критично да имаме бързодействие, O2 съвсем не дава това.
Едва ли някой е казал подобно нещо, колкото повече се тества и оптимизира даден код - толкова по-бърз и добър става. SQLite е доста по-добре и повече тестван от твоят, както вече споменах дървото трябва да се верифицира, защото много лесно може да чупиш листата си при добавяне.
М-м-м-м, много спорно. Още повече пък относно точно тази програма. Конвенциите за викане касаят само системните функции, които тука не играят никаква роля. А в твоя код можеш да си правиш каквото си искаш на която и да е операционна система.
За съжаление AVX2 не се поддържа и на AMD процесора ми. 
Програмата гърми със illegal instruction на адрес 4010f9h.
Компилирането със clang и - O3 на sqlite бутна времето с още секунда надолу, около 2 сек. на ред.
gcc version 9.3.0
clang version 10.0.1
По този повод, може да си поиграеш и със PRAGMA threads - Не съм много сигурен как точно SQLite използва допълнителни нишки (документацията е много лаконична в това отношение), но някои от операциите в базата и индексите по принцип могат да се паралелят добре. По подразбиране това е изключено въобще.
Няма келепир от нишки, аз в момента отварям базата без мутекс-и, прекалено синхронно се случват нещата.
SELECT l.word FROM left l WHERE l.ROWID < 50 ORDER BY l.word
SELECT l.word FROM left l WHERE l.ROWID >= 50 ORDER BY l.word
Реално като захване едната нишка - работи само тя, по някоя време захваща другата т.е. напълно синхронно и реално не работят една върху друга.
Аз имах предвид вътрешната заявка:
SELECT r.word as rw, MIN(LEVENSTEIN(?, r.word)) FROM right r
Агрегатните функции като MIN() вероятно могат да се ускоряват с паралелна обработка.
BIGBUGEX, ако обичаш, можеш ли да тестваш това в атачмънта колко е бързо на AMD процесор?
Сега направих една промяна, която ускори програмата 3 пъти (!) на моят А4-1200, но само с 10% на интелски процесор. Интересно дали на други АМД процесори ще се получи такова ускорение...
В архива има два изпълними файла за Линукс: LevenshteinOld и LevenshteinNew - съответно без промяната и със промяната.
Времената на А4-1200 изглеждат така:
; Преди:
0: Dist: 4, Time: 1894 ms
1: Dist: 4, Time: 1776 ms
2: Dist: 4, Time: 1844 ms
3: Dist: 4, Time: 60 ms
4: Dist: 40, Time: 1888 ms
5: Dist: 4, Time: 1032 ms
6: Dist: 9, Time: 1598 ms
7: Dist: 6, Time: 1895 ms
8: Dist: 4, Time: 574 ms
9: Dist: 6, Time: 1697 ms
; Сега:
0: Dist: 4, Time: 665 ms
1: Dist: 4, Time: 622 ms
2: Dist: 4, Time: 647 ms
3: Dist: 4, Time: 26 ms
4: Dist: 40, Time: 660 ms
5: Dist: 4, Time: 365 ms
6: Dist: 9, Time: 562 ms
7: Dist: 6, Time: 670 ms
8: Dist: 4, Time: 206 ms
9: Dist: 6, Time: 598 ms
0 1 2 3 4 ...14 15 16 17 18 ...30 31 32 33 34 35 36