<bgdev />^free

Нали се сещаш, че по добре клюкарка, отколкото сериен посерко. Буквално няма техническа тема дето да не си се осрал, което реално е ок, едва ли някои има очаквания конкретно към теб освен ти самият ;)

gat3way

То подхода не е лош като цяло, абе аз като писах трошачката за хешове върху GPU, за някои алгоритми имаше голяма файда от това, примерно при MD5, 32 бита от крайната хеш сума ги имаш малко по-рано (конкретно за MD5 има още по-яки фокуси, но да оставим това настрана, защото дори и при яките фокуси, пак намазваш от същото). Та 32 бита от крайната хеш сума ги имаш няколко стъпки преди края. Там примерно ранна проверка работи наистина добре защото....ами вероятността примерно от 64 workitem-а един да му се падне да уцели баш правилната стойност е колко там....64/2^32, което означава статистически погледнато почти винаги имаме early exit. Абе като цяло това е забавно, GPGPU програмирането не е чак толкова скучно, някои неща са неинтуитивни на първо четене и забавни :)

Да, забавно е. Трябва да си поизчистя кода, да го направя да работи на много GPU-та и да видя за колко време ще се изпълни цялото нещо на две тесли.

Гледам, че франкенклъстъра има 20-ина нода с по 8 TITAN карти, но това е малко прекалено за тестване. :)

synergie

Нали се сещаш, че по добре клюкарка, отколкото сериен посерко.

Според кого е по-добре клюкарка? Според клюкарката? :)

synergie

Буквално няма техническа тема дето да не си се осрал, което реално е ок, едва ли някои има очаквания конкретно към теб освен ти самият ;)

Я, осралия всички технически теми, квичи отново. :)

Айде Пипончо, със здраве от мен, до другата ти техническа тема в която неминуемо пак ще се осереш на базови СS концепции. Имай поне честта да се извиниш на Жони, той води доста културен и премерен разговор с теб.

synergie

Айде Пипончо, със здраве от мен, до другата ти техническа тема в която неминуемо пак ще се осереш на базови СS концепции. Имай поне честта да се извиниш на Жони, той води доста културен и премерен разговор с теб.

Я, клюкарката пак изквича нещо нечленоразделно. :)

synergie

Имай поне честта да се извиниш на Жони, той води доста културен и премерен разговор с теб.

Е, не държа чак толкова. Както се казва, "да разбереш, значи да простиш". Пайпа е ясен - живее в САЩ, а там бият през пръстите даже за намек за агресия и нетолерантност. Така че, там иска, не иска, а трябва да говори учтиво и да се подмазва на всички. Е, а в резултат, намира отдушник във форумите - иначе ще изперка съвсем за нула време и ще трябва като повечето американци да седи на антидепресанти... (Ако вече не е).

Евлампи

|

Е няма как да сравняваш "дърво" като релационните данни, и особено идиотщина като SQL с език за програмиране, от колкото и да е високо ниво. Това наистина е все едно да използваш чук за да завиеш болт.

SQL е примордиален DSL с ниско качество като абстракция и съответно куп грозотии отгоре и особености при имплементациите ама това е положението, Еволюцията бачка така, очевидно няма време за ПРАВИЛЕН grand design щом джаваскрипт и C царуват :)

Абе зависи, аз съм игнорирал цял софт с УИ, дето смяташе някакви неща и ги експортваше в некви справки. С 2 SQL заявки. едната зареждаше данните, другата имаше имаше вложени селекти, групирания, джойнове(даже и един малък джойнт) и там каквото и изплюваше резултата за под 10 секунди в един csv. И това беше много несериозно и грубо от моя страна, защото друго си е цяла специализирана програма със всички салтанати там, bells and whistles и закачена една лелка да цъка по цял ден и да и изскачат прозорци със сложни таблици на екрана пред смаяния поглед на всички невежи, включая шефчето. Демек, ползваме софтуерен продукт и вършим тежка изчислителна и много важна работа от която никой друг не разбира освен въпросния ценен бабишкер.

Е те лелките ако можеха да се оправят, ние за какво сме? Аре, аз съм на дистрибутирани системи Ако на системите не им се налагаше да говорят, аз за какво съм им?

Още една итерация. Оказва се, че (поне на моите компютри) колкото по-прост и кратък е кодът, толкова по-бързо си работи.

Intel Pentium N3540:

0: Dist: 4, Time: 7389 ms, Index: 97865
1: Dist: 4, Time: 6852 ms, Index: 90390
2: Dist: 4, Time: 7064 ms, Index: 91065
3: Dist: 4, Time: 228 ms, Index: 1720
4: Dist: 40, Time: 7330 ms, Index: 34233
5: Dist: 4, Time: 3890 ms, Index: 49718
6: Dist: 9, Time: 5706 ms, Index: 52634
7: Dist: 6, Time: 6852 ms, Index: 80663
8: Dist: 4, Time: 2173 ms, Index: 26926
9: Dist: 6, Time: 5830 ms, Index: 60852

Index - това е номерът на стринга в SetA (от 0), на който е намерена минималната дължина.

Отново атачвам компилираните файлове. Надявам се тоя път антивирусите да не мрънкат...

Освен това си завъдих и репозиторий, ако някой иска да се запознае с кода: Fossil repository

В кода, proc Levenstein е предишната имплементация с MMX и опит за паралелна обработка (не много ефективна при Левенщейн), а сегашният фаворит е proc Levenstein2.

Следващата стъпка ще е по аналогия - ако по-малкият код се изпълнява по-бързо, следва да се приеме, че и по-малките данни ще се изпълняват по-бързо. Следователно си струва да се опита с пакетирани данни - по 2 бита на символ. (Защото това са данни за ДНК, а при тях символите са само 4).

По-бавно е от ръстовското решение:

#RUST:

  0|> Elapsed:  3292; Distance:   4
  1|> Elapsed:  3145; Distance:   4
  2|> Elapsed:  3260; Distance:   4
  3|> Elapsed:   886; Distance:   4
  4|> Elapsed:  3242; Distance:  40

#ASM:
0: Dist: 4, Time: 5340 ms, Index: 97865
1: Dist: 4, Time: 4959 ms, Index: 90390
2: Dist: 4, Time: 5110 ms, Index: 91065
3: Dist: 4, Time: 157 ms, Index: 1720
4: Dist: 40, Time: 5316 ms, Index: 34233

Само ми е интерсно как вади 157мс за ред 3 след като другите времена са почти двойни.

Искаш ли да имплементираш моя алгоритъм ?

pub fn levenshtein<'i, I, X>(a: &'i I, b: &'i I, max_distance: usize) -> usize
    where
        &'i I: IntoIterator<Item=X>,
        X: PartialEq<X> + Copy
{

    let a_len = a.into_iter().count();
    let b_len = b.into_iter().count();

    if a_len == 0 {
        return b_len;
    }

    let mut a = a;
    let mut b = b;
    if a_len < b_len {
        swap(&mut a, &mut b);
    }

    let mut cache: Vec<usize> = (1..min(a_len, b_len) + 1).collect();
    let mut result = 0;

    for (i, a_elem) in a.into_iter().enumerate() {
        result = i + 1;
        let mut distance_b = i;
        let mut current_distance = i;

        for (j, b_elem) in b.into_iter().enumerate() {
            let distance_a = if a_elem == b_elem {
                distance_b
            } else {
                distance_b + 1
            };

            distance_b = cache[j];
            result = min(
                result + 1,
                min(distance_a, distance_b + 1),
            );
            cache[j] = result;

            if result < current_distance {
                current_distance = result;
            }
        }

        if current_distance >= max_distance {
            return max_distance;
        }
    }

    result
}

ФейкПрофил

Искаш ли да имплементираш моя алгоритъм ?

В смисъл? То разстоянието на Левенщайн се смята по точно един алгоритъм. Различават се начините на имплементация на този един алгоритъм.

Това твоето решение как да го пусна на Линукс? Интересно ми е на по-бавни процесори дали все още ще е по-бърз, или аз лошо поддържам съвременните процесори?

ами само пускаш изпълнимия файл:

./playground

На твоя компютър не знам дали ще тръгне, защото е компилирано за моя, ако не тръгне или може да си го компилираш сам:

1. За да си свалиш ръст:

curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | sh

2. След което в папката със cargo.toml файла:

cargo run --release

Или ако не искаш да си го компилираш сам мога да го прекомпилирам за generic x86

ФейкПрофил

ами само пускаш изпълнимия файл:

./playground

На твоя компютър не знам дали ще тръгне, защото е компилирано за моя, ако не тръгне или може да си го компилираш сам:

1. За да си свалиш ръст:

curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | sh

2. След което в папката със cargo.toml файла:

cargo run --release

Или ако не искаш да си го компилираш сам мога да го прекомпилирам за generic x86

Аз имам някакъв инсталиран rust, но получавам грешки:

error[E0432]: unresolved import `vec_vp_tree`
  --> src/main.rs:11:5
   |
11 | use vec_vp_tree::VpTree;
   |     ^^^^^^^^^^^ Maybe a missing `extern crate vec_vp_tree;`?

error[E0309]: the parameter type `S` may not live long enough
  --> src/main.rs:92:52
   |
92 |     struct StringToBytesAdapter<'a, S: AsRef<str>>(&'a S);
   |                                     --             ^^^^^^
   |                                     |
   |                                     help: consider adding an explicit lifetime bound `S: 'a`...
   |
note: ...so that the reference type `&'a S` does not outlive the data it points at
  --> src/main.rs:92:52
   |
92 |     struct StringToBytesAdapter<'a, S: AsRef<str>>(&'a S);
   |                                                    ^^^^^^

error: aborting due to 2 previous errors

много ти е стар ръста щом реве за extern crate, това не нужно от повече от година

rustup update stable

ПП: a tova s ВП дървото може да се изтрие - наистина прави много по-малко левенщайн операции при търсене, но за самото му конструиране отиват повече операции отколкото за брутфорса :(

ФейкПрофил

много ти е стар ръста щом реве за extern crate, това не нужно от повече от година

rustup update stable

ПП: a tova s ВП дървото може да се изтрие - наистина прави много по-малко левенщайн операции при търсене, но за самото му конструиране отиват повече операции отколкото за брутфорса :(

Това го оправи.

# RUST

  0|> Elapsed:  2411; Distance:   4
  1|> Elapsed:  2271; Distance:   4
  2|> Elapsed:  2360; Distance:   4
  3|> Elapsed:   619; Distance:   4
  4|> Elapsed:  2341; Distance:  40
  5|> Elapsed:  1557; Distance:   4
  6|> Elapsed:  1678; Distance:   9
  7|> Elapsed:  2228; Distance:   6
  8|> Elapsed:  1129; Distance:   4
  9|> Elapsed:  1822; Distance:   6
 10|> Elapsed:  2911; Distance:  58

# Go (trie)

0:  4  2506 ms
1:  4  237 ms
2:  4  962 ms
3:  4  1254 ms
4:  40 2575 ms
5:  4  369 ms
6:  9  1651 ms
7:  6  1125 ms
8:  4  774 ms
9:  6  243 ms
10: 58 3739 ms

# C

0:  4  2014.568000 ms
1:  4  1894.743000 ms
2:  4  1949.750000 ms
3:  4  559.776000 ms
4:  40 1967.738000 ms
5:  4  1311.775000 ms
6:  9  1520.449000 ms
7:  6  1984.073000 ms
8:  4  960.098000 ms
9:  6  1565.859000 ms
10: 58 2415.516000 ms

# Go (bruteforce)

0:  4  3428 ms
1:  4  3329 ms
2:  4  3456 ms
3:  4  931 ms
4:  40 3434 ms
5:  4  2326 ms
6:  9  2588 ms
7:  6  3295 ms
8:  4  1777 ms
9:  6  2689 ms
10: 58 4301 ms

ФейкПрофил

Или ако не искаш да си го компилираш сам мога да го прекомпилирам за generic x86

Оказа се, че си го имам компилаторът на rust (минус на рядкото преинсталиране - събират се странни неща на диска) и си го компилирах. (Оригиналният изпълним файл гърми при мене).

Но резултатите са различни (A4-1200 1GHz) от това, което е при тебе:

Asm:

0: Dist: 4, Time: 14014 ms, Index: 97865
1: Dist: 4, Time: 13018 ms, Index: 90390
2: Dist: 4, Time: 13439 ms, Index: 91065
3: Dist: 4, Time: 447 ms, Index: 1720
4: Dist: 40, Time: 13951 ms, Index: 34233
5: Dist: 4, Time: 7401 ms, Index: 49718
6: Dist: 9, Time: 10859 ms, Index: 52634
7: Dist: 6, Time: 13028 ms, Index: 80663
8: Dist: 4, Time: 4143 ms, Index: 26926
9: Dist: 6, Time: 11125 ms, Index: 60852

Rust:

  0|> Elapsed: 18285; Distance:   4
  1|> Elapsed: 17022; Distance:   4
  2|> Elapsed: 18076; Distance:   4
  3|> Elapsed:  4591; Distance:   4
  4|> Elapsed: 17586; Distance:  40
  5|> Elapsed: 11576; Distance:   4
  6|> Elapsed: 12557; Distance:   9
  7|> Elapsed: 16770; Distance:   6
  8|> Elapsed:  8380; Distance:   4
  9|> Elapsed: 13493; Distance:   6

@пайп, Това на какъв компютър/CPU ? (Някъде назад май го беше писал..)

Накрая да вземе някой да сумира резултатите че станах разноглед - платформи, машини, оптимизиран/неоптимизиран и т.н.

Някой да напише с думи прости - МРЕТЕ СЕЛЯНИ ПРОСТИ, ASM РУЛИРА! или С-то си е С, дядките с асемблера в recycle-bin-а!

обаче е интересно как различните компилатори генерират различно оптимален код за различните процесор - според времената от bigbugex ръста е доста по-бърз от Ц и асм, докато при | Ц е малко по-бързо, a пък при теб АСМ :Д

За ред с номер 3 пак имаш невероятно малко време - 30 пъти по-бързо от ред 0.

Delegate

@пайп, Това на какъв компютър/CPU ? (Някъде назад май го беше писал..)

Laptop: 2.4 GHz 8-Core Intel Core i9