<bgdev />^free

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# вариант, да не се окаже че съм много назад заради кьопав ЛевенЩЕЙН

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.

Golden Gega

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

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

Delegate

Golden Gega

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

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

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

|

johnfound

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

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

johnfound

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

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

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

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.

BIGBUGEX

C:

4: 41 5683.074905 ms

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

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

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?

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 е малко изсмукано от пръстите, пък пайпа не иска да пуска асемблерски код на неговите числотрошачки.

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

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

Delegate

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

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

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

Delegate

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

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

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

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

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 е малко изсмукано от пръстите, пък пайпа не иска да пуска асемблерски код на неговите числотрошачки.

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

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

johnfound

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

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

Delegate

johnfound

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

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

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

johnfound

Delegate

johnfound

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

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

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

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

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

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