<bgdev />free

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

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

0 1 2 3 4 ....13 14 15 16 17 ....29 30 31 32 33 34 35 36
#13700 (ツ) bvbfan
Последно редактирано на 03.10.2020 от bvbfan, видяно: 1581 пъти.
|

ЦЯЛАТА информация е нужна в случая. Колко пъти още трябва да се повтори за да го схванеш?

Trie-а е най-елементарния възможен.

Все още не казваш какъв вид е трая, най-лесният е да си обикаляш всички низове, трая е за бързо търсене. Разбрах, че цялата се иска, но както ти писах преди това, слагаш си гпу кода за узър функция и sqlite целият код ти е 10-на ред (питон, с, го каквото искаш). Доста по-лесно от какъвто и да е трай, както и не казваш валидация имаш ли?

#13701 (ツ) |
Създадено на 03.10.2020, видяно: 1580 пъти.
bvbfan
|

ЦЯЛАТА информация е нужна в случая. Колко пъти още трябва да се повтори за да го схванеш?

Trie-а е най-елементарния възможен.

Все още не казваш какъв вид е трая, най-лесният е да си обикаляш всички низове, трая е за бързо търсене. Разбрах, че цялата се иска, но както ти писах преди това, слагаш си гпу кода за узър функция и sqlite целият код ти е 10-на ред (питон, с, го каквото искаш). Доста по-лесно от какъвто и да е трай, както и не казваш валидация имаш ли?

Какви видове tries има?

Явно нямаш абсолютно никаква идея как работят GPUs. :)

#13703 (ツ) gat3way
Създадено на 03.10.2020, видяно: 1575 пъти.

Задачата просто си се подава на паралелизация, нуждата от синхронизация между нишките е колко....никаква. Затова ще намазва добре от многонишкова имплементация. А още по-добре от гпу такава. Това не е поради нещо толкова странно, гпу-то без много фантазия може да се разглежда като цпу с хиляда, две хиляди и повече там ядра, естествено това е супер опростен поглед, но реално причината да намазва толкова оттова че се изпълнява върху гпу е тази.

#13704 (ツ) |
Създадено на 03.10.2020, видяно: 1573 пъти.
gat3way

Задачата просто си се подава на паралелизация, нуждата от синхронизация между нишките е колко....никаква. Затова ще намазва добре от многонишкова имплементация. А още по-добре от гпу такава. Това не е поради нещо толкова странно, гпу-то без много фантазия може да се разглежда като цпу с хиляда, две хиляди и повече там ядра, естествено това е супер опростен поглед, но реално причината да намазва толкова оттова че се изпълнява върху гпу е тази.

Аз не бях сигурен дали memory bandwidth ще е достатъчен да "пълни" 256 нишки, но изглеждаше ОК.

#13705 (ツ) gat3way
Създадено на 03.10.2020, видяно: 1569 пъти.

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

#13707 (ツ) ФейкПрофил
Създадено на 03.10.2020, видяно: 1562 пъти.
bvbfan
ФейкПрофил

Абе това trie колко памет харчи ? Аз се заиграх, но ми заема 2ГБ :(

Харчи (виж prefix/radix trie) също както и непрекъснатото зареждане при всяко пускане на програмата, но Пайп-а не иска да разисква тоя въпрос, защото компенсира със смятането на гпу и неглижира проблема.

Зареждането при всяко пускане не е проблем - trie-то ми го вдига за 1.3 секунди, което не е никак зле за програма, която ще се пуска точно веднъж за даден сет от данни. Единствения проблем е високата консумация на памет, но тук съм си виновен аз, щото ползвах hashmap, а при само 4 възможни букви може да се направи по-ефективно :)

Интересно е също дали може trie-to да се възползва от avx инструкции, защото както се оказа брутфорса може и това там свали времето 10 пъти.

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

Абе това trie колко памет харчи ? Аз се заиграх, но ми заема 2ГБ :(

Харчи (виж prefix/radix trie) също както и непрекъснатото зареждане при всяко пускане на програмата, но Пайп-а не иска да разисква тоя въпрос, защото компенсира със смятането на гпу и неглижира проблема.

Зареждането при всяко пускане не е проблем - trie-то ми го вдига за 1.3 секунди, което не е никак зле за програма, която ще се пуска точно веднъж за даден сет от данни. Единствения проблем е високата консумация на памет, но тук съм си виновен аз, щото ползвах hashmap, а при само 4 възможни букви може да се направи по-ефективно :)

Интересно е също дали може trie-to да се възползва от avx инструкции, защото както се оказа брутфорса може и това там свали времето 10 пъти.

Според мен най-лесния вариант е ако се направи да търси едновременно N стринга. Векторизирането на търсенето в дървото ми се струва трудно.

#13712 (ツ) bvbfan
Последно редактирано на 03.10.2020 от bvbfan, видяно: 1546 пъти.
|

Какви видове tries има?

Явно нямаш абсолютно никаква идея как работят GPUs. :)

Различни видове, ти кой си написал? Видове Аз доколкото разбрах ти ползваш гпу-то за левенщайн трая си в рама. Гпу-то трябва да копира паметта, иначе работи в паралел, като не съм писал нищо, само пробвал да фиксвам.

#13713 (ツ) ФейкПрофил
Създадено на 03.10.2020, видяно: 1542 пъти.

Обаче sqlite решение все още никой не е споделил :)

#13714 (ツ) |
Създадено на 03.10.2020, видяно: 1541 пъти.
bvbfan
|

Какви видове tries има?

Явно нямаш абсолютно никаква идея как работят GPUs. :)

Различни видове, ти кой си написал? Видове Аз доколкото разбрах ти ползваш гпу-то за левенщайн трая си в рама. Гпу-то трябва да копира паметта, иначе работи в паралел, като не съм писал нищо, само пробвал да фиксвам.

Аз съм написал Trie. Ако сравняваш два стринга с GPU ще е ЗНАЧИТЕЛНО по-бавно от това да ги сравняваш с CPU. Та, как точно ще направиш юзър функция на sqlite, която сравнява стринговете с GPU?

#13717 (ツ) bvbfan
Създадено на 03.10.2020, видяно: 1540 пъти.

Какво решение очакваш, имаш данни, които са в базата, имаш юзер функция за sqlite и ти трябва заявка като от първа страница.

#13718 (ツ) |
Създадено на 03.10.2020, видяно: 1539 пъти.
bvbfan

Какво решение очакваш, имаш данни, които са в базата, имаш юзер функция за sqlite и ти трябва заявка като от първа страница.

И какво прави тази юзер функция?

#13719 (ツ) bvbfan
Последно редактирано на 03.10.2020 от bvbfan, видяно: 1537 пъти.

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

#13720 (ツ) |
Последно редактирано на 03.10.2020 от |, видяно: 1534 пъти.
bvbfan

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

И за колко време си въобразяваш, че GPU-то ще сравни два стринга?

Помисли как ще напишеш трай да прави каквото трябва и ще си отговориш сам на въпроса за ключовете на листата.

#13722 (ツ) Евлампи
Създадено на 03.10.2020, видяно: 1531 пъти.
ФейкПрофил

Обаче sqlite решение все още никой не е споделил :)

Търси се философския камък под формата на магична юзър дифайнд функция :)

Само Гегата опита да защити честта на релационните бази, Джон ужким е в тоя лагер ама рита за отбор асемблер :)

Ебати яката тема, чей зема още пуканки, жалко че интересите ми са по-скоро в областта на програмиране с възможно най-малко церемония което малко се бие с възможно най-ефективния код въпреки че обожавам Цъ без плюсовете

#13724 (ツ) bvbfan
Създадено на 03.10.2020, видяно: 1522 пъти.
|

Помисли как ще напишеш трай да прави каквото трябва и ще си отговориш сам на въпроса за ключовете на листата.

Аз какво да го мисля, ти как си го направил, може да се направи по няколко начина.

#13728 (ツ) ФейкПрофил
Създадено на 03.10.2020, видяно: 1515 пъти.

Айде някой който разбира от Ц и SQLite да се престраши за да разбием мита че асемблера е най-бърз. Джони може да пише по-добре от компилатор, но дали може по-добре от sqlite ?

#13731 (ツ) |
Създадено на 03.10.2020, видяно: 1513 пъти.
bvbfan
|

Помисли как ще напишеш трай да прави каквото трябва и ще си отговориш сам на въпроса за ключовете на листата.

Аз какво да го мисля, ти как си го направил, може да се направи по няколко начина.

Кои са тези няколко начина?

Какво стана с юзър функциите в sqlite?

#13733 (ツ) |
Създадено на 03.10.2020, видяно: 1510 пъти.

Иначе най-интересното от темата е, че в общи линии очевидната имплементация на който и да е език е еднакво бавна. :)

Другото интересно беше сравнителната скорост на различните процесори.

#13737 (ツ) Евлампи
Създадено на 03.10.2020, видяно: 1507 пъти.
ФейкПрофил

Айде някой който разбира от Ц и SQLite да се престраши за да разбием мита че асемблера е най-бърз. Джони може да пише по-добре от компилатор, но дали може по-добре от sqlite ?

За момент ми мина през акъла да напиша руби юзър функция за sqlite която генерира асемблер през FFI.

Требе да се прегледам :)

0 1 2 3 4 ....13 14 15 16 17 ....29 30 31 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