<bgdev />free

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

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

0 1 2 3 4 ....9 10 11 12 13 ....20 21 22 23 24 ....27 28 29 30 31 32 33 34 35 36
#13092 (ツ) Golden Gega
Създадено на 29.09.2020, видяно: 1574 пъти.
Delegate

ФейкПрофил, и аз мисля, че му е бавен Левенщ*ейнът*. Тоя C# вариант, при мен е по-бърз от неговия.


 public static int LevenshteinDistance(string value1, string value2)
        {
            if (value1.Length == 0)
            {
                return 0;
            }

            int[] costs = new int[value1.Length];

            // Add indexing for insertion to first row
            for (int i = 0; i < costs.Length; )
            {
                costs[i] = ++i;
            }

            int minSize = value1.Length < value2.Length ? value1.Length : value2.Length;


            for (int i = 0; i < minSize; i++)
            {
                // cost of the first index
                int cost = i;
                int addationCost = i;

                // cache value for inner loop to avoid index lookup and bonds checking, profiled this is quicker
                char value2Char = value2[i];

                for (int j = 0; j < value1.Length; j++)
                {
                    int insertionCost = cost;

                    cost = addationCost;

                    // assigning this here reduces the array reads we do, improvment of the old version
                    addationCost = costs[j];

                    if (value2Char != value1[j])
                    {
                        if (insertionCost < cost)
                        {
                            cost = insertionCost;
                        }

                        if (addationCost < cost)
                        {
                            cost = addationCost;
                        }

                        ++cost;
                    }

                    costs[j] = cost;

                }


            }

            return costs[costs.Length - 1];
        }

Тоя откъде го взе, понеже и ползвах за моя пример C# вариант, да не се окаже че съм много назад заради кьопав ЛевенЩЕЙН

#13094 (ツ) Courvoisier
Последно редактирано на 29.09.2020 от Courvoisier, видяно: 1570 пъти.
Golden Gega

Това за i5-4570 3.20GHz, май е серия K ама джама не казва

Dictionary (SetA) length: 99775

0: Dist: 4, Time: 6344 ms
1: Dist: 4, Time: 5813 ms
2: Dist: 4, Time: 5875 ms
3: Dist: 4, Time: 187 ms
4: Dist: 40, Time: 6172 ms
5: Dist: 4, Time: 3250 ms
6: Dist: 9, Time: 5141 ms
7: Dist: 6, Time: 5953 ms
8: Dist: 4, Time: 1812 ms
9: Dist: 6, Time: 5422 ms

Имам почти подобно време на Ryzen 2700U, което е скопената версия на 2700X-а на Рабито. Интересно ми е Стиви ако го пусне на неговата i5-ца колко ще е времето. Привидно по- нов процесор, но разликите са до десетина милисекунди. Не е много голям бууст. Добре, накачулил съм и други програми, имам Хром с 10-на таба, 1 VS, 1 MSSMS, 1 SourceTree, Teams, една Java се търкаля, Notepad++, един WSL...

SHA сигурно ще смятам по- бързо, имам и AVX.

#13096 (ツ) Delegate
Създадено на 29.09.2020, видяно: 1566 пъти.
Golden Gega

Тоя откъде го взе, понеже и ползвах за моя пример C# вариант, да не се окаже че съм много назад заради кьопав ЛевенЩЕЙН

От тук : https://github.com/DanHarltey/Fastenshtein

#13103 (ツ) Golden Gega
Създадено на 29.09.2020, видяно: 1553 пъти.
Delegate
Golden Gega

Тоя откъде го взе, понеже и ползвах за моя пример C# вариант, да не се окаже че съм много назад заради кьопав ЛевенЩЕЙН

От тук : https://github.com/DanHarltey/Fastenshtein

Значи същия съм ползвал и аз

#13106 (ツ) |
Последно редактирано на 29.09.2020 от |, видяно: 1545 пъти.
|
johnfound

12-те секунди бяха на "бързият процесор" (N3540). А иначе, големият проблем се оказа с xchg r/mem (пък и r/r) която се оказа, че има гигантска латентност и във вътрешния цикъл скапваше времето тотално.

Никога не съм харесвал xchg, освен ако не е cmpxchg с lock префикс.

johnfound

Разликите в изпълнението са заради максималното разстояние - ако вече е намерено разстояние 4, то няма смисъл да завършваш стринговете с по-голямо разстояние.

Вярно, забравих да имплементирам това в C версията. Прикачвам нова версия... Разбира се, трябва да се компилира с О3.

Както и очаквах, на GPU-то тази оптимизация не доведе до значително подобрение. Сега 200К се сравняват за 1318 секунди вместо за 1335 секунди.

#13107 (ツ) BIGBUGEX
Създадено на 29.09.2020, видяно: 1535 пъти.

asm:

0: Dist: 4, Time: 5937 ms
1: Dist: 4, Time: 5496 ms
2: Dist: 4, Time: 5616 ms
3: Dist: 4, Time: 172 ms
4: Dist: 40, Time: 5937 ms
5: Dist: 4, Time: 3106 ms
6: Dist: 9, Time: 4919 ms
7: Dist: 6, Time: 5703 ms
8: Dist: 4, Time: 1728 ms
9: Dist: 6, Time: 5058 ms

C:

0: 4 5624.474042 ms
1: 4 5307.951031 ms
2: 4 5488.499883 ms
3: 4 1414.807889 ms
4: 41 5683.074905 ms
5: 4 3654.337485 ms
6: 9 3959.592666 ms
7: 6 5184.470029 ms
8: 4 2593.544323 ms
9: 6 4212.431926 ms

3700Х закотвен на 3.6GHz.

#13108 (ツ) johnfound
Последно редактирано на 29.09.2020 от johnfound, видяно: 1531 пъти.
BIGBUGEX

C:

4: 41 5683.074905 ms

Интересно, но C версията смята грешно - трябва да е 40 на 4-тия стринг.

#13109 (ツ) |
Създадено на 29.09.2020, видяно: 1516 пъти.
johnfound
BIGBUGEX

C:

4: 41 5683.074905 ms

Интересно, но C версията смята грешно - трябва да е 40 на 4-тия стринг.

Go версията също дава 40. Ето и разликите според нея (D=delete, I=insert, R=replace, минус=match).


------------------------------------------------------I-----------------------R---DR---DDDDR-D-D-D-R--D-D---D-RR-RR--I----D---RR----IR-I-II-RRR----RRR-R-IRR--I
#13110 (ツ) synergie
Създадено на 29.09.2020, видяно: 1513 пъти.
johnfound
0: Dist: 4, Time: 8588 ms
1: Dist: 4, Time: 7957 ms
2: Dist: 4, Time: 8223 ms
3: Dist: 4, Time: 260 ms
4: Dist: 40, Time: 8604 ms
5: Dist: 4, Time: 4499 ms
6: Dist: 9, Time: 7122 ms
7: Dist: 6, Time: 8251 ms
8: Dist: 4, Time: 2516 ms
9: Dist: 6, Time: 7319 ms

Тия времена, делени на 6 не са ли аналогични на Go версията с trie?

#13112 (ツ) johnfound
Създадено на 29.09.2020, видяно: 1508 пъти.
synergie
johnfound
0: Dist: 4, Time: 8588 ms
1: Dist: 4, Time: 7957 ms
2: Dist: 4, Time: 8223 ms
3: Dist: 4, Time: 260 ms
4: Dist: 40, Time: 8604 ms
5: Dist: 4, Time: 4499 ms
6: Dist: 9, Time: 7122 ms
7: Dist: 6, Time: 8251 ms
8: Dist: 4, Time: 2516 ms
9: Dist: 6, Time: 7319 ms

Тия времена, делени на 6 не са ли аналогични на Go версията с trie?

Who knows... Това :6 е малко изсмукано от пръстите, пък пайпа не иска да пуска асемблерски код на неговите числотрошачки. rofl

По някое време ще разчистя сорса, да може да се компилира без зависимости и ще го публикувам. В момента трябва да се инсталират доста неща, за да се компилира...

#13113 (ツ) Delegate
Създадено на 29.09.2020, видяно: 1507 пъти.

Джонка, последното ти exe го хваща Уиндоус дифендера и вика Trojan:Win32/Fuery.C!cl Онова от архива BioData не го закача, но това от AsmLeven го нарочи.

#13114 (ツ) johnfound
Създадено на 29.09.2020, видяно: 1503 пъти.
Delegate

Джонка, последното ти exe го хваща Уиндоус дифендера и вика Trojan:Win32/Fuery.C!cl Онова от архива BioData не го закача, но това от AsmLeven го нарочи.

И двете са компилирани от подобен сорс... А Линукската и Уиндоуската версия, съвсем от един. Поста ми не е редактиран от никой, така че файлът е чист и оригинален.

#13115 (ツ) Delegate
Създадено на 29.09.2020, видяно: 1499 пъти.

Исках да ти пусна най-новото ехе при мене да сравня с posgtgreSQL, понеже на моя i5 7200U постгрето ми изпълнява заявката за всички 100, всеки срещу 100К сравнение за 3 минути, което отвява C# решението ми, и идва около 5 пъти по-бързо от C#-па на моя комп. Да не би да е кеширало някъде постгрето и да ми вади зайци от ръкава..

#13116 (ツ) johnfound
Създадено на 29.09.2020, видяно: 1494 пъти.
Delegate

Исках да ти пусна най-новото ехе при мене да сравня с posgtgreSQL, понеже на моя i5 7200U постгрето ми изпълнява заявката за всички 100, всеки срещу 100К сравнение за 3 минути, което отвява C# решението ми, и идва около 5 пъти по-бързо от C#-па на моя комп. Да не би да е кеширало някъде постгрето и да ми вади зайци от ръкава..

Пускай го - exe-то е чисто. Мога да пробвам да го прекомпилирам някак си, но като не знам какво не му харесва на антивируса ти?

А това с постгре-то, със изчислянията на дистанцията ли е? Защото ако е така - отвява не само C# решението.

И да - нормално е да кешира в рам-а, но защо това да е "зайци от ръкава"? Така работят всички бази данни.

#13117 (ツ) synergie
Създадено на 29.09.2020, видяно: 1490 пъти.
johnfound
synergie
johnfound
0: Dist: 4, Time: 8588 ms
1: Dist: 4, Time: 7957 ms
2: Dist: 4, Time: 8223 ms
3: Dist: 4, Time: 260 ms
4: Dist: 40, Time: 8604 ms
5: Dist: 4, Time: 4499 ms
6: Dist: 9, Time: 7122 ms
7: Dist: 6, Time: 8251 ms
8: Dist: 4, Time: 2516 ms
9: Dist: 6, Time: 7319 ms

Тия времена, делени на 6 не са ли аналогични на Go версията с trie?

Who knows... Това :6 е малко изсмукано от пръстите, пък пайпа не иска да пуска асемблерски код на неговите числотрошачки. rofl

По някое време ще разчистя сорса, да може да се компилира без зависимости и ще го публикувам. В момента трябва да се инсталират доста неща, за да се компилира...

Хахахахах е сега го сметнах, 1055 ms average за първите 10 ръна с асм бинарито спрямо 1083 аверидж за Го версият при х6 коефициент. Пипончо, тая картинка виждал ли си я:

My picture

#13119 (ツ) Delegate
Последно редактирано на 29.09.2020 от Delegate, видяно: 1488 пъти.
johnfound

А това с постгре-то, със изчислянията на дистанцията ли е?

Ами с дистанцията, как иначе. Малко съм барнал параметъра на функцията, да търси до 62 макс, но и до 100 да го направя няй-много да скочи минута за целия сет, което пак не е зле.

My picture

Attached files:
FileSizeUploadedDownloadsMD5 hash
levenstein.png266982 bytes29.09.20201648329978ba1fdbf5a62186eaa49080a31
#13120 (ツ) johnfound
Последно редактирано на 29.09.2020 от johnfound, видяно: 1483 пъти.
Delegate
johnfound

А това с постгре-то, със изчислянията на дистанцията ли е?

Ами с дистанцията, как иначе. Малко съм барнал параметъра на функцията, да търси до 62 макс, но и до 100 да го направя няй-много да скочи секунда.

Приблизително 2300ms на стринг е определено великолепен резултат. Да не излезе накрая, че базите данни се справят по-добре от къстъм кода? rofl

#13121 (ツ) synergie
Създадено на 29.09.2020, видяно: 1475 пъти.
johnfound
Delegate
johnfound

А това с постгре-то, със изчислянията на дистанцията ли е?

Ами с дистанцията, как иначе. Малко съм барнал параметъра на функцията, да търси до 62 макс, но и до 100 да го направя няй-много да скочи секунда.

Приблизително 2300ms на стринг е определено великолепен резултат. Да не излезе накрая, че базите данни се справят по-добре от къстъм кода? rofl

В тая цялата тема има толкова много бисери колкото Рамбо не успява да изсере за половин година.

#13122 (ツ) Delegate
Създадено на 29.09.2020, видяно: 1474 пъти.

Ако имаш postgreSQL пробвай да не би да пропускам нещо. Нали щяхте на sqlite даже да пробвате.

#13123 (ツ) Унуфри
Създадено на 29.09.2020, видяно: 1474 пъти.

Абе вие работите ли нещо или сте си вземали отпуска да мерите чуровете ?

0 1 2 3 4 ....9 10 11 12 13 ....20 21 22 23 24 ....27 28 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