Все още не казваш какъв вид е трая, най-лесният е да си обикаляш всички низове, трая е за бързо търсене. Разбрах, че цялата се иска, но както ти писах преди това, слагаш си гпу кода за узър функция и sqlite целият код ти е 10-на ред (питон, с, го каквото искаш). Доста по-лесно от какъвто и да е трай, както и не казваш валидация имаш ли?
Задача НЕ за интервю
0 1 2 3 4 ...13 14 15 16 17 ...29 30 31 32 33 34 35 36
Какви видове tries има?
Явно нямаш абсолютно никаква идея как работят GPUs. :)
Задачата просто си се подава на паралелизация, нуждата от синхронизация между нишките е колко....никаква. Затова ще намазва добре от многонишкова имплементация. А още по-добре от гпу такава. Това не е поради нещо толкова странно, гпу-то без много фантазия може да се разглежда като цпу с хиляда, две хиляди и повече там ядра, естествено това е супер опростен поглед, но реално причината да намазва толкова оттова че се изпълнява върху гпу е тази.
Аз не бях сигурен дали memory bandwidth ще е достатъчен да "пълни" 256 нишки, но изглеждаше ОК.
То гпуто това би трябвало да му е по-голям проблем и то вероятно не толкова заради шината към паметта че няма да смогне, а заради всичките безумни малоумни индиански ритуали свързани с това, достъпа до паметта там е некаква ужасия подаваща се на сума ти черни магии, там bank, channel конфликти и всекакви такива глупотии.
Зареждането при всяко пускане не е проблем - trie-то ми го вдига за 1.3 секунди, което не е никак зле за програма, която ще се пуска точно веднъж за даден сет от данни. Единствения проблем е високата консумация на памет, но тук съм си виновен аз, щото ползвах hashmap, а при само 4 възможни букви може да се направи по-ефективно :)
Интересно е също дали може trie-to да се възползва от avx инструкции, защото както се оказа брутфорса може и това там свали времето 10 пъти.
Според мен най-лесния вариант е ако се направи да търси едновременно N стринга. Векторизирането на търсенето в дървото ми се струва трудно.
Различни видове, ти кой си написал? Видове Аз доколкото разбрах ти ползваш гпу-то за левенщайн трая си в рама. Гпу-то трябва да копира паметта, иначе работи в паралел, като не съм писал нищо, само пробвал да фиксвам.
Обаче sqlite решение все още никой не е споделил :)
Аз съм написал Trie. Ако сравняваш два стринга с GPU ще е ЗНАЧИТЕЛНО по-бавно от това да ги сравняваш с CPU. Та, как точно ще направиш юзър функция на sqlite, която сравнява стринговете с GPU?
Какво решение очакваш, имаш данни, които са в базата, имаш юзер функция за sqlite и ти трябва заявка като от първа страница.
Намира дистанцията между 2 стринга, sqlite ти ги групира / подрежда спрямо заявката. Все още не разбрах какъв е трая, поне кажи какви са ключовете на листата.
И за колко време си въобразяваш, че GPU-то ще сравни два стринга?
Помисли как ще напишеш трай да прави каквото трябва и ще си отговориш сам на въпроса за ключовете на листата.
Търси се философския камък под формата на магична юзър дифайнд функция :)
Само Гегата опита да защити честта на релационните бази, Джон ужким е в тоя лагер ама рита за отбор асемблер :)
Ебати яката тема, чей зема още пуканки, жалко че интересите ми са по-скоро в областта на програмиране с възможно най-малко церемония което малко се бие с възможно най-ефективния код въпреки че обожавам Цъ без плюсовете
Аз какво да го мисля, ти как си го направил, може да се направи по няколко начина.
Айде някой който разбира от Ц и SQLite да се престраши за да разбием мита че асемблера е най-бърз. Джони може да пише по-добре от компилатор, но дали може по-добре от sqlite ?
Кои са тези няколко начина?
Какво стана с юзър функциите в sqlite?
Иначе най-интересното от темата е, че в общи линии очевидната имплементация на който и да е език е еднакво бавна. :)
Другото интересно беше сравнителната скорост на различните процесори.
0 1 2 3 4 ...13 14 15 16 17 ...29 30 31 32 33 34 35 36