To co? Bawimy się? :D

[mariotti]

No niestety, ja też jestem wyrobnik - w zasadzie VB6 i .NET, trochę (mało) PHP i to w zasadzie wszystko...

VB6 i .NET do typowych zastosowań to bardzo dobry komplet :) Ja raczej C++, a to w
zwykłych zastosowaniach jest zbyt niskopoziomowe.

Niemniej, jak się dane wygenerują i zaimportują do bazy, to polowa za nami.
Też przyjąłem, że max 70 znaków (sprawdzone kawałki mieszczą się w 60), więc powinno być dobrze.

Dla pewności lepiej sprawdzę i potem wkleję wynik.

Jak chcesz, to po całej operacji dam Ci dostęp do gotowej bazy, żeby nie przerabiać znowu tego samego...

Dodałeś do tabeli jakieś pole auto-inc? Kolejne wiersze muszą mieć kolejny numerek :)


Pozdrawiam

[krzyszp]

Dodałeś do tabeli jakieś pole auto-inc? Kolejne wiersze muszą mieć kolejny numerek :)

Oczywiście :)
Line też mają index (unique)- wydłuży to mocno import do bazy, ale przyśpieszy SELECT podczas wyszukiwania.

Kod [Zaznacz] Rozwiń

CREATE TABLE IF NOT EXISTS `dane` (
  `ID` int(11) NOT NULL AUTO_INCREMENT,
  `Line` varchar(70) NOT NULL,
  `Repeat` int(6) NOT NULL,
  PRIMARY KEY (`ID`),
  UNIQUE KEY `Line` (`Line`)
) ENGINE=InnoDB DEFAULT CHARSET=latin1 AUTO_INCREMENT=1 ;

Nie jestem tylko pewien, czy nie trzeba było 'Line' zdefiniować jako Char(70)...

[mariotti]

Nie jestem tylko pewien, czy nie trzeba było 'Line' zdefiniować jako Char(70)...

O ile pamiętam, char różni się od varchar tylko tym, że char dokleja białe znaki
na końcu, a varchar ma znak końca linii? Jeśli pamiętam dobrze, to oba typy
w naszym przypadku będą zachowywały się bardzo podobnie.

Co do długości wiersza, to ten programik:

Kod [Zaznacz] Rozwiń


(
(
echo printLeafs 5
echo quit
) | ./perft4
) | awk ' { if ( length > x ) { x = length; y = $0 } }END{ printf "%s:lenght:%d\n",y,x }'

Daje taki wynik:
rnbqkbnr/p1p1pppp/1p1p4/8/8/1P1P1P2/P1P1P1PP/RNBQKBNR b qkQK -:lenght:62
Więc długość najdłuższego wiersza przy depth=5 wynosi 62 znaki.

Dla depth=7 jeszcze się liczy :D

Pozdrawiam

[krzyszp]

VARCHAR stores a variable number of bytes for only the space required by the content.
CHAR stores a fixed size of however many bytes you specify for your table, no matter how many characters occupy a field of this type per row

Faktycznie, w naszym przypadku różnica będzie minimalna.

[mariotti]

VARCHAR stores a variable number of bytes for only the space required by the content.
CHAR stores a fixed size of however many bytes you specify for your table, no matter how many characters occupy a field of this type per row

Mnie to zawsze myliło. Nie wiem jak Ty rozumiesz to zdanie.

Space content nie tyczy się miejsca na dysku, ale miejsca na
dane, czyli miejsca na napis. VARCHAR nie tylko nie oszczędza
miejsca na dysku (jakby mogło sugerować space required), ale wręcz
zużywa go więcej :)

Tutaj ktoś dobrze przedstawił problem:
http://www.sqlblog.pl/2012/01/optymalizacja-rozmiaru-tabel-char-vs-varchar
ale na koniec wyciągnął złe wnioski, bo jest więcej przesłanek za używaniem
char :)

Pozdrawiam

[krzyszp]

Ja rozumiem to w ten sposób, że jeśli długość ciągu się mocno/często zmienia, to opłaca się varchar, w przeciwnym wypadku char i kompresja tabeli :)

Sytuację komplikuje to, że przy stałej długości wiersza szybciej przebiega indeksowanie i przeszukiwanie tabel - ale nie mam tutaj nic na poparcie tej tezy poza moimi odczuciami z pracy, więc traktuj to z przymrużeniem oka ;)

[mariotti]

Ja rozumiem to w ten sposób, że jeśli długość ciągu się mocno/często zmienia, to opłaca się varchar, w przeciwnym wypadku char i kompresja tabeli :)
Sytuację komplikuje to, że przy stałej długości wiersza szybciej przebiega indeksowanie i przeszukiwanie tabel - ale nie mam tutaj nic na poparcie tej tezy poza moimi odczuciami z pracy, więc traktuj to z przymrużeniem oka ;)

A jak to było z porównywaniem? W char  chyba "a" jest równe "a    ", chyba zawsze dokleja spacje?

[buninek]

Najdłuższą linię można odszukać również z pomocą wc.

Kod [Zaznacz] Rozwiń

wc -L

Nie mam tych danych wejściowych, żeby to sprawdzić, czy to nie oto idzie.

Kod [Zaznacz] Rozwiń

nl dane | sort -t$'\t' -k2 | uniq -cd -f2 | sort -n -k2

Dziwię się, że operujesz na tych danych bez żadnej kompresji, te dane powinny dobrze się kompresować 7-10x, a to mogłoby przyśpieszyć wszelkie operacje dyskowe. Dane na wejściu dekompresujesz.
Ewentualnie zrobić split i operować na mniejszych porcjach (sort|uniq),  następnie połączyć i ponownie (sort|uniq).

[krzyszp]

A jak to było z porównywaniem? W char  chyba "a" jest równe "a    ", chyba zawsze dokleja spacje?

Nic o tym nie wiem :)
Może to kwestia użytego connectora?
Nigdy nie napotkałem takiego problemu...

Ps. Nie zaglądasz na IRC? Można na żywo pogadać na serwerze: irc.ircnet.pl kanał: #boinc@poland...

[mariotti]

Najdłuższą linię można odszukać również z pomocą wc.

Kod [Zaznacz] Rozwiń

wc -L

Dzięki

Nie mam tych danych wejściowych, żeby to sprawdzić, czy to nie oto idzie.

Kod [Zaznacz] Rozwiń

nl dane | sort -t$'\t' -k2 | uniq -cd -f2 | sort -n -k2

Chyba nie o to, albo ja coś źle robię:

Kod [Zaznacz] Rozwiń


(
echo printLeafs 3
echo quit
) | ./perft4 | nl | sort -t$'\t' -k2 | uniq -cd -f1 | sort -n -k2 > out.txt
wc -l out.txt #powinno dać 5362

(
echo printLeafs 4
echo quit
) | ./perft4 | nl | sort -t$'\t' -k2 | uniq -cd -f1 | sort -n -k2 > out.txt
wc -l out.txt #powinno dać 72078


Dziwię się, że operujesz na tych danych bez żadnej kompresji, te dane powinny dobrze się kompresować 7-10x, a to mogłoby przyśpieszyć wszelkie operacje dyskowe. Dane na wejściu dekompresujesz.
Ewentualnie zrobić split i operować na mniejszych porcjach (sort|uniq),  następnie połączyć i ponownie (sort|uniq).

Dane wyjściowe i tak i tak muszę mieć w formacie bez kompresji. Natomiast do danych wejściowych
jest generator, w ogóle nie trzeba ich nigdzie zapisywać ani kompresować. Wygenerować wejście
można tak:

Kod [Zaznacz] Rozwiń


(
echo printLeafs 3
echo quit
) | ./perft4


Docelowo echo printLeafs 3 ma być zastąpione echo printLeafs 7, a w wersji
ambitnej echo printLeafs 8.

Pozdrawiam

[mariotti]

A jak to było z porównywaniem? W char  chyba "a" jest równe "a    ", chyba zawsze dokleja spacje?

Nic o tym nie wiem :)
Może to kwestia użytego connectora?
Nigdy nie napotkałem takiego problemu...

Ps. Nie zaglądasz na IRC? Można na żywo pogadać na serwerze: irc.ircnet.pl kanał: #boinc@poland...

Dużo czasu poszło na rozwiązania "na kolanie" :) Przez ten czas może
bym zrobił porządny program :) Mam kupę pracy. Robię sobie dwa dni
całkowitego szlabanu na BOINCa. Potem zobaczymy co zrobił Twój
programik. Jeśli do tego czasu nie zakończy działania, to wklepię coś
w C++, bez bazy danych :)

Pozdrawiam
P.S.
A irca... nie nauczyłem się jeszcze obsługiwać pod linuxem :)

[buninek]

Uniq powinen działać od drugiego pola. Pierwsze pole to numer linii, rozdielony spacjami i tabulatorem.
W międzyczasie poprawiłem z
uniq -cd -f1
na

Kod [Zaznacz] Rozwiń

uniq -cd -f2

Przed sortem proponuje użyć

Kod [Zaznacz] Rozwiń

LC_ALL=C sort

[mariotti]

Uniq powinen działać od drugiego pola. Pierwsze pole to numer linii, rozdielony spacjami i tabulatorem.
W międzyczasie poprawiłem z
uniq -cd -f1
na
uniq -cd -f2

Zdaje się, że uniq jako fields traktuej wszystko rozdzielone białymi znakami. Wiersze
nie zawierają tabulatorów, ale zawierają spacje i chyba dlatego nie działa. W manie
nie znalazłem jak można zdefiniować separator dla uniq - a to by rozwiązało problem i to
w bardzo elegancki sposób. Inna sprawa czy byłby to też sposób wydajny :)

Pozdrawiam i dobranoc, bo jestem 20tą godzinę na nogach :)

[buninek]

Dokumentacja rozszerzona znajduje się w info coreutils.
info uniq

"Fields are sequences of non-space non-tab characters that are separated from each other by at least one space or tab."
uniq -f2 oznacza ni mniej, ni więcej - pomiń pierwsze pole, zacznij od drugiego porównywać wszystko.

To powinno dać prawidłowy wynik. Porównałem to z wu_test_perft i wynnik był identyczny.

Kod [Zaznacz] Rozwiń

nl pos.txt | LC_ALL=C sort -t$'\t' -k2 | uniq -cd -f2 | LC_ALL=C sort -n -k2

Standardowo nl, startuje z numeracją tylko 100000 linii, przy większej trzeba zwiększyć poprzez parametr -w.
Nie mam pojęcia jak sort radzi sobie z gigantycznymi porcjami danych. Warto zwrócić uwagę na możliwość kompresji tymczasowych plików poprzez
--compress-program=PROG  oraz
--parallel=N    (change the number of sorts run concurrently to N).

[krzyszp]

Zacząłem zapis do bazy danych, ale dwie rzeczy mocno spowalniają operację: zapis rekordów pojedynczo przez sieć oraz odpalenie programu w debuggerze (nie wiem jak się zachowa przy tak wielkim pliku). Niestety dziś nie mogę go w czasie dnia zostawić bez nadzoru.

Wieczorem dam znać jaki wynik.

[mariotti]

Dokumentacja rozszerzona znajduje się w info coreutils.
info uniq

"Fields are sequences of non-space non-tab characters that are separated from each other by at least one space or tab."
uniq -f2 oznacza ni mniej, ni więcej - pomiń pierwsze pole, zacznij od drugiego porównywać wszystko.

W takim razie powinno działać.

To powinno dać prawidłowy wynik. Porównałem to z wu_test_perft i wynnik był identyczny.

Kod [Zaznacz] Rozwiń

nl pos.txt | LC_ALL=C sort -t$'\t' -k2 | uniq -cd -f2 | LC_ALL=C sort -n -k2

U mnie nie działa:

Kod [Zaznacz] Rozwiń


./go.sh
72078 out1.txt # prawidłowa ilość wierszy
6799 out2.txt  # nieprawidłowa

cat go.sh
depth=4

(
echo printLeafs $depth
echo quit
) | ./perft4 | sort | uniq > out1.txt
wc -l out1.txt

(
echo printLeafs $depth
echo quit
) | ./perft4 | nl | LC_ALL=C sort -t$'\t' -k2 | uniq -cd -f2 | LC_ALL=C sort -n -k2 > out2.txt
wc -l out2.txt





Poniższy skrypt też nie działa, a realizuje tylko część zadania.

Kod [Zaznacz] Rozwiń


depth=4
(
(
(
(
echo printLeafs $depth
echo quit
) | ./perft4
) | gawk '{printf"%s;%d\n",$0,NR}'
) | sort -t$';' -k1
) | gawk -F';' '{if(field==$1) {sum++} else {printf"%s\n",$0} field=$1}' > out1.txt

wc -l out1.txt

Znajduje za dużo wierszy, bo aż 72090. Unikalnych jest tylko 72078.
Nie wiem dlaczego nie działa, to prosty skrypt. Pierwsze gawk dodaje do
każdego wiersza średnik i numer kolejny. Sort sortuje po tym co jest
przed średnikiem. Drugi gawk wyświetla wiersz, pod warunkiem że ta
część do średnika różni się od wiersza bezpośrednio nad nim.

Nie mam pojęcia jak sort radzi sobie z gigantycznymi porcjami danych. Warto zwrócić uwagę na możliwość kompresji tymczasowych plików poprzez

Sort ma możliwość wskazania plików tymczasowych. Jeszcze nie wiem co robi w tych
plikach tymczasowych, ale jeśli robi w nich merge-sort, to rozwiąże to zadanie bardzo
szybko. W połączeniu z kompresją może być jeszcze lepiej.


Pozdrawiam

[mariotti]

Zacząłem zapis do bazy danych, ale dwie rzeczy mocno spowalniają operację: zapis rekordów pojedynczo przez sieć oraz odpalenie programu w debuggerze (nie wiem jak się zachowa przy tak wielkim pliku). Niestety dziś nie mogę go w czasie dnia zostawić bez nadzoru.

Wieczorem dam znać jaki wynik.

Ciekawy jestem jak to się zachowa. Dziś i jutro mam urwanie głowy. Jak
"rozwiązania na kolanie" nie zadziałają, to w piątek/sobotę napiszę porządny
program do tego zadania.

Pozdrawiam

[mariotti]

Bym zapomniał.
Najdłuższy wiersz przy depth=7 ma 66 znaków. Sprawdzenie
tego trwało 181 minut.

Załączam skrypt który to policzył. Gdy uruchamiałem skrypt, to
jeszcze nie znałem wc -L i dlatego w awk. Mam nadzieję że nie ma bugów:

Kod [Zaznacz] Rozwiń


cat go2.sh
(
(
echo printLeafs 7
echo quit
) | ./perft4
) | awk ' { if ( length > x ) { x = length; y = $0 } }END{ printf "%s:lenght:%d\n",y,x }'
time ./go2.sh
rnbqkbnr/p1p1p1pp/1p1p1p2/8/5B2/1P1P1P2/P1P1P1PP/RN1QKBNR b qkQK -:lenght:66

real    181m5.714s
user    229m47.530s
sys     27m49.140s


Pozdrawiam

[krzyszp]

Zapomniałem wcześniej napisać - w MySQL pole nie może mieć nazwy 'Repeat' (to komenda SQL), nie wiem jak w sqlite...

Póki co rekordy dodajá sié prawidłowo (w tej chwili jest 70958).

Ps. Przy okazji przypomniałem sobie, że inkrementacja i=i+1 dla integera jest w tym wypadku złym pomysłem - stack overflow ;)

[krzyszp]

Tak sobie pomyślałem, że jeśli dl depth=7 mamy 195GB na dysku, to jednak lepiej je chyba generować bezpośrednio do bazy w przypadku depth=8...
Pytanie, ile bédzie unikalnych rekordów dla tek ilości danych? (Gdzieś to wcześniej było, ale przegapiłem)

[mariotti]

Zapomniałem wcześniej napisać - w MySQL pole nie może mieć nazwy 'Repeat' (to komenda SQL), nie wiem jak w sqlite...

Póki co rekordy dodajá sié prawidłowo (w tej chwili jest 70958).

Ps. Przy okazji przypomniałem sobie, że inkrementacja i=i+1 dla integera jest w tym wypadku złym pomysłem - stack overflow ;)

Tabelka ze wszystkimi i unikalnymi:

Kod [Zaznacz] Rozwiń


6        119.060.324        9.417.681
7      3.195.901.860       96.400.068
8     84.998.978.956      988.187.354
9  2.439.530.234.167   10.122.483.176 <-- ekstrapolowane


Więc int32 (31 bitów na dodatnie wartości) wystarczy do depth=8, jeśli
zapisuje się tylko unikalne układy.


SQLite nie burzył się na repeat - dla małych głębokości dał poprawne wyniki.


A co do optymalnego algorytmu na "dyskowym modelu obliczeń", to widzę go tak:

Definiujemy parę:
struct Pair {
short count
char row[70];
};

Tworzymy tablicę tych par, tak dużą jak pozwala pamięć RAM:
Pair pairs[SIZE];

Zapamiętujemy początek tablicy:
start = 0;

Zapamiętujemy koniec tablicy:
end = 0;

Program wczytuje kolejne wiersze ze standardowego wejścia do
zmiennej row;

Jeśli row jest mniejszy niż 70 bajtów, to dokleja zera na końcu row.

Następnie program szuka w tablicy pairs czy dany wiersz się
powtarza. Jeśli się powtarza, to inkrementuje licznik, jeśli nie
to dodaje na koncu:
pairs[end].row = row;
pairs[end].count = 1;

Następnie zwiększa zmienną end:
end = (end + 1) % SIZE;

Jeśli zmienna end równa się start, to zrzuca ostatni element do pliku
if( end == start ) {
save( file , pair[start] );
start = (start + 1) % SIZE;
}
W ten sposób otrzymamy kolejkę cykliczną.

Wąskim gardłem będzie wyszukiwanie w dużej tablicy pairs. Trzeba ją jakoś
zaindeksować. Najszybsza do tego celu będzie jakaś hash-table.

Gdy podawane rekordy na standardowe wejście wyczerpią się, to trzeba
uruchomić drugi program. Drugi program też będzie miał tablicę pairs.
Wpisze do niej układy z początku pliku. Gdy tablica się zapełni, to
będzie musiał iterować do końca pliku wczytując po jednym rekordzie.
Wczytywanie sekwencyjne jest bardzo szybkie - i to jest istotą
tego algorytmu. Każdy wczytany rekord z pliku, program będzie próbował
odszukać w tablicy pairs. Jeśli znajdzie, to na dysku oznaczy ten rekord
jako usunięty, a w tablicy piars zwiększy count. Gdy osiągnie koniec
pliku, to tablica pairs ze zmienionymi wartościami count zostanie
zapisna na dysku, "dziurka od klucza" zostanie przesunięta za ostatni
element który poprzednio był wczytany do pairs, no i do tablicy
pairs zostaną wczytane następne rekordy. Oczywiście poza tymi
rekordami, które zostały oznaczone jako usunięte.

Para będzie miała rozmiar 72 bajtów. Więc w 6GB pamięci ram zmieści
się około 100mln par. Unikalnych wierszy dla depht=8 jest 988.187.354,
oznacza to, że wystarczy przeiterować po pliku 10 razy minus to co
zostanie odrzucone pierwszym programem. Ponadto każda kolejna
iteracja będzie się zaczynała od dalszych adresów (nie każda będzie
od początku pliku).

Strzelam że koszt wykonania całego programu będzie równy czterem
całkowitym odczytom pliku z danymi. Czyli dla depht=8 może da się
policzyć w 2 dni - o ile się nie mylę :)


Pozdrawiam

P.S.
Jeszcze jest potrzebny trzeci program/procedura do fizycznego usunięcia
wszystkich logicznie oznaczonych jako usunięte :)

[krzyszp]

Cóż, mój program sié nie sprawdzi... Po kilku godzinach mam 120k rekordów (unikalnych) wiéc dla 96,4kk rekordów potrwa to... długo. Skompilowanie softu nic nie da, bo dalej rekordy dodajá sié po jednym.

Wieczorem przysiádé i przerobie na dodawanie w seriach (np. po 10k rekordów), wtedy powinna być sensowniejsza prédkość, w dodatku skompilujé też program.
Innym rozwiázaniem (chyba lepszym) by był zapis do csv i import całości jednym rzutem do bazy - może tak właśnie zrobié - zobaczé wieczorem.

[mariotti]

Cóż, mój program sié nie sprawdzi... Po kilku godzinach mam 120k rekordów (unikalnych) wiéc dla 96,4kk rekordów potrwa to... długo. Skompilowanie softu nic nie da, bo dalej rekordy dodajá sié po jednym.

Wieczorem przysiádé i przerobie na dodawanie w seriach (np. po 10k rekordów), wtedy powinna być sensowniejsza prédkość, w dodatku skompilujé też program.
Innym rozwiázaniem (chyba lepszym) by był zapis do csv i import całości jednym rzutem do bazy - może tak właśnie zrobié - zobaczé wieczorem.

Moim zdaniem transfer związany z wieloma małymi zapytaniami nie jest wąskim gardłem.
Wąskim gardłem są naprowadzenia głowicy na losowe adresy. Dyski talerzowe (w
przeciwieństwie do pamięci RAM i dysków SSD) są przystosowane do sekwencyjnego
odczytu. Potrafią np. szybko odczytać ogromny plik. Ale wyszukiwanie małych porcji
danych na dysku talerzowym jest bardzo wolne, gdyż element mechaniczny (głowica)
musi być mechanicznie pozycjonowana. Elementy mechaniczne są zawsze wolne.

W momencie gdy dajemy
select * form tabela where row = 'row';
to baza danych  (na podstawie indeksu) ustala pozycję rekordów.
Następnie głowica jest naprowadzana na tę pozycję. Oczywiście
jest cache dysku, bazy i systemu plików - ale na tak dużych
zbiorach cache szybko się wyczerpuje. Dla 988.187.354 unikalnych
rekordów powiedzmy że mamy 3kkk naprowadzeń głowicy. Jedno naprowadzenie
niech trwa np. 5ms to mam 170 dni na samo naprowadzenie głowicy.

Więc ja bym nie sprawdzał jak działa na wielu danych w jednym zapytaniu, ale
nie wiem na pewno, może coś pomyliłem :D

Pozdrawiam

[krzyszp]

Nie zapomnij, że ja wciáż mam bardzo mało rekordów, wiéc zapewne i baza i index siedzá w cache.
Natomiast przy okazji robienia bazy danych klimatycznych dla Rysia odkryłem, że najbardziej ekonomiczne (ilosc_rekordow/jednostke_czasu) jest jednoczesne dodawanie 10k rekordów.

[mariotti]

Nie zapomnij, że ja wciáż mam bardzo mało rekordów, wiéc zapewne i baza i index siedzá w cache.

Racja. W końcu cache się wyczerpie. Gdy ilość rekordów wzrośnie N razy, to czas może
wzrosnąć 10*N.

Natomiast przy okazji robienia bazy danych klimatycznych dla Rysia odkryłem, że najbardziej ekonomiczne (ilosc_rekordow/jednostke_czasu) jest jednoczesne dodawanie 10k rekordów.

To muszę o coś zapytać. Jak używasz transakcji? O ile się nie mylę, to większość
baz danych każde jedno zapytanie automatycznie obejmuje transakcją, jeśli
wcześniej tego nie zrobił użytkownik.

Czyli zapytanie:
select coś tam;

Jest równoważne trzem zapytaniom:
begin;
select coś tam;
commit;

Transakcje wymuszają przerzucenie danych z dziennika do plików, a
mało tego, wymuszają jeszcze oczekiwanie aplikacji na upewnienie się, że
system operacyjny zapisał na dysku dane. Z góry przepraszam jeśli
dobrze wiesz o tym, a ja zbędnie tłumaczę.

Natomiast jeśli nie próbowałeś optymalizować transakcji, to cały ten
program do dodawania unikalnych rekordów obejmij transakcją.
Na początku programu, zaraz po połączeniu się do bazy daj begin,
a zupełnie na końcu daj commit - mogę się mylić, ale powinno
przyspieszyć 10-100 razy - wszystko zależy od buforów. No chyba
że łącze internetowe jest naprawdę bardzo wolne, to nic nie da.

Pozdrawiam

[buninek]

U mnie nie działa:

Kod [Zaznacz] Rozwiń


./go.sh
72078 out1.txt # prawidłowa ilość wierszy
6799 out2.txt  # nieprawidłowa

cat go.sh
depth=4

(
echo printLeafs $depth
echo quit
) | ./perft4 | sort | uniq > out1.txt
wc -l out1.txt

(
echo printLeafs $depth
echo quit
) | ./perft4 | nl | LC_ALL=C sort -t$'\t' -k2 | uniq -cd -f2 | LC_ALL=C sort -n -k2 > out2.txt
wc -l out2.txt



Jesli możesz wrzuć tu ten plik dla depth=4, sprawdziłbym to jeszcze raz.
Ja tego generatora nie uruchomię z uwagi na system x86.

[mariotti]

Jesli możesz wrzuć tu ten plik dla depth=4, sprawdziłbym to jeszcze raz.
Ja tego generatora nie uruchomię z uwagi na system x86.

Nie działa. Zaczynam się bać - proste programy i skrypty nie działają. Czy ja
robię coś źle? Bałem się, że to program perft4 coś psuje, więc uruchomiłem go
w osobnym wierszu - nie pomogło.

Kod [Zaznacz] Rozwiń


head -n 13 go.sh
depth=4

(
echo printLeafs $depth
echo quit
) | ./perft4 > input.txt

cat input.txt | sort | uniq > out1.txt
wc -l out1.txt

cat input.txt | nl | LC_ALL=C sort -t$'\t' -k2 | uniq -cd -f2 | LC_ALL=C sort -n -k2 > out2.txt
wc -l out2.txt
exit

./go.sh
72078 out1.txt
6799 out2.txt


Załączam plik input.txt - ten sam który wygenerował powyższy skrypt.
Plik jest spakowany programem bzip2 - trzeba zmienić nazwę na input.txt.bz2

Załączam także moje wszystkie próby w bashu.

Pozdrawiam
[edit]
Nie można załączać plików z rozszerzeniem sh i przez pomylkę załączyłem plik
out.txt. Załączam teraz go.txt, trzeba zmienić nazwę na go.sh.

[buninek]

Kod [Zaznacz] Rozwiń

nl input | LC_ALL=C sort -t$'\t' -k2 | uniq -c -f1 | LC_ALL=C sort -n -k2 | wc -l
72078
U mnie sort, uniq jest szybsze od sqlite ok 37 razy.

Kod [Zaznacz] Rozwiń

time ( cat input | ./wu_test_perft out.db )

[mariotti]

Kod [Zaznacz] Rozwiń

nl input | LC_ALL=C sort -t$'\t' -k2 | uniq -c -f1 | LC_ALL=C sort -n -k2 | wc -l
72078

Wyjaśniło się, tym razem ja przeoczyłem poprawny wynik. Chyba
przywykłem do błędów na dobre. Hehe :)

U mnie sort, uniq jest szybsze od sqlite ok 37 razy.

Kod [Zaznacz] Rozwiń

time ( cat input | ./wu_test_perft out.db )

Zrobię benchmark od głębokości 1 do 6.

Mam wersję tego algorytmu w pamięci RAM, on ledwo daje radę
dla głębokości=6. Niemniej dzięki niemu sprawdzimy jeszcze
poprawność powtórzeń - oba algorytmy muszą dać identyczne wyniki.

Jak będzie wszystko ok, to spróbujemy policzyć dla 7. Szkoda że sort
nie ma paska postępu, nie bedziemy wiedzieli czy się zawiesiło, czy
działa.

Pozdrawiam

[buninek]

Nic nie przeoczyłeś, najzwyczajniej źle były dobrane opcje dla uniq.
Wcześniej było uniq -cd -f2, powinno być jednak uniq -c -f1.

[mariotti]

Nic nie przeoczyłeś, najzwyczajniej źle były dobrane opcje dla uniq.
Wcześniej było uniq -cd -f2, powinno być jednak uniq -c -f1.

Racja. Teraz pomieszałem z dobrym wynikiem dla gołego sort i uniq. Zadanie jest
trudne, wymaga zastanowienia, a tak z doskoku to człowiek sam nie wie co robi :)

Benchamrk trwa. Dla depth=5 zakończył, czekamy na depth=6.

Kod [Zaznacz] Rozwiń


cat ./go.sh
depth=$1
(
echo printLeafs $depth
echo quit
) | ./perft4 | nl | LC_ALL=C sort -t$'\t' -k2 | uniq -c -f1 | LC_ALL=C sort -n -k2 > out.txt
wc -l out.txt
x@biglaptop:/media/ATA1TB/tmp$ time ./go.sh 1
20 out.txt

real    0m0.042s
user    0m0.004s
sys     0m0.000s
x@biglaptop:/media/ATA1TB/tmp$ time ./go.sh 2
400 out.txt

real    0m0.016s
user    0m0.004s
sys     0m0.000s
x@biglaptop:/media/ATA1TB/tmp$ time ./go.sh 3
5362 out.txt

real    0m0.048s
user    0m0.028s
sys     0m0.028s
x@biglaptop:/media/ATA1TB/tmp$ time ./go.sh 4
72078 out.txt

real    0m0.820s
user    0m0.784s
sys     0m0.324s
x@biglaptop:/media/ATA1TB/tmp$ time ./go.sh 5
822518 out.txt

real    0m21.362s
user    0m20.549s
sys     0m7.936s
x@biglaptop:/media/ATA1TB/tmp$ time ./go.sh 6


Pozdrawiam

[buninek]

 :facepalm2:Wcześniej wspomniałem, że nie jestem pewien jak nl zachowuje się przy numeracji bardzo dużych plików.
Na szybko można sprawdzić czy poprawnie.

Kod [Zaznacz] Rozwiń

seq 1 119060324 | nl | tail -n10
seq 1 3195901860 | nl | tail -n10

Czy nie trzeba dodać

Kod [Zaznacz] Rozwiń

seq 1 119060324 | nl -w9 | tail -n10
seq 1 3195901860 | nl -w10 | tail -n10

Numerować można również cat-em.

Kod [Zaznacz] Rozwiń

man cat
man nl

Edit:
Pasek postępu moża zrobić dzięki pv są również inne rozwiązania. Choć umiejętne skorzystanie z pv w takim potoku nie jest proste.
Tak zupełnie nie dość dokładnie (wręcz bardzo kulawo), to

Kod [Zaznacz] Rozwiń

pv input | nl | LC_ALL=C sort -t$'\t' -k2 | uniq -c -f1 | LC_ALL=C sort -n -k2 > out

[mariotti]

Benchamrk trwa. Dla depth=5 zakończył, czekamy na depth=6.

Benchmark się zakończył. Zrzut z konsoli:

Kod [Zaznacz] Rozwiń


x@biglaptop:/media/ATA1TB/tmp$ cat ./go.sh
depth=$1
(
echo printLeafs $depth
echo quit
) | ./perft4 | nl | LC_ALL=C sort -t$'\t' -k2 | uniq -c -f1 | LC_ALL=C sort -n -k2 > out.txt
wc -l out.txt
x@biglaptop:/media/ATA1TB/tmp$ time ./go.sh 1
20 out.txt

real    0m0.042s
user    0m0.004s
sys     0m0.000s
x@biglaptop:/media/ATA1TB/tmp$ time ./go.sh 2
400 out.txt

real    0m0.016s
user    0m0.004s
sys     0m0.000s
x@biglaptop:/media/ATA1TB/tmp$ time ./go.sh 3
5362 out.txt

real    0m0.048s
user    0m0.028s
sys     0m0.028s
x@biglaptop:/media/ATA1TB/tmp$ time ./go.sh 4
72078 out.txt

real    0m0.820s
user    0m0.784s
sys     0m0.324s
x@biglaptop:/media/ATA1TB/tmp$ time ./go.sh 5
822518 out.txt

real    0m21.362s
user    0m20.549s
sys     0m7.936s
x@biglaptop:/media/ATA1TB/tmp$ time ./go.sh 6
9417683 out.txt

real    25m53.570s
user    9m38.424s
sys     4m7.715s


x@biglaptop:/media/ATA1TB/tmp$ ./perft4
diffLeafs 6 0
diff leafs: = 9417683
max repeat: 479
fen: rnbqkbnr/pppp1ppp/8/4p3/4P3/8/PPPP1PPP/RNBQKBNR w qkQK -
quit
x@biglaptop:/media/ATA1TB/tmp$


Jak widać, obliczenia dla depth=6 trwały 25 minut. Polecenie sort przydzieliło sobie
malutko pamięci ram, może 50MB. Czyli ogólnie pozytywnie.

Mam jakiś dokument, a w nim, że ilość węzłów unikalnych wynosi 9417681.
Tymczasem w teście wyszło 9417683. Na końcu zrzutu z konsoli widać
jeszcze jeden wynik 9417683 - to wersja która realizuje to samo zadanie, ale
w pamięci ram. Więc jeszcze muszę ustalić, czy błąd zawiera ten dokument, czy
program perft4. Ciekawe jaki może być błąd w perft4, jeśli przeszedł tak ogromną
ilość testów na poprawne zliczanie wszystkich (nie unikalnych) węzłów. Tak czy
inaczej, znowu coś dziwnego, ale wybrniemy w końcu :)

Zrobiłem aproksymację, przy założeniu że kolejne głębokości mają złożoność N*LogN, a
N rośnie tak jak ilość węzłów. Wyszło że dla depth=7 policzy w pół doby, a dla
depth=8 w 17 dni. Ciekawe ile taka aproksymacja jest warta :)

Nie zaszkodzi zostawić tego na 1-2 doby, może akurat się uda :)

Pozdrawiam

[buninek]

Może trafił jakiś komunikat, ostrzeżenie, biała linia z sort, uniq, nl.
Może jakoś zweryfikować na szybko grepem, czy nie ma tam nic niepożądanego.

grep -v '.*/.*/.*/.*/.*/.*/.*/.*' wynik

[mariotti]

Może trafił jakiś komunikat, ostrzeżenie, biała linia z sort, uniq, nl.
Może jakoś zweryfikować na szybko grepem, czy nie ma tam nic niepożądanego.
grep -v '.*/.*/.*/.*/.*/.*/.*/.*' wynik

Dobry pomysł, takie sprawdzenie nigdy nie zaszkodzi.

Jednak z dwóch innych (lecz niestety zależnych) programów jest wynik z
trójką na końcu. Wynik z trójką na końcu dał algorytm który działa
całkowicie w RAM i Twój algorytm który działa tylko na tekstowych wierszach.
Oba algorytmy korzystają z dobrze przetestowanego "trzonu" do
generowania układów. I oba algorytmy dały taki sam błąd? Może jednak
błąd jest w tym dokumencie - dziwne ale możliwe, będzie trzeba to dokładnie zbadać.

Wracając do Twojego potoku, dodałem bufory ram, a katalog tymczasowy
będzie na drugim dysku:

Kod [Zaznacz] Rozwiń


cat go.sh
depth=$1
(
echo printLeafs $depth
echo quit
) | ./perft4 | nl | LC_ALL=C sort -t$'\t' -k2 -T'./tmp' -S1000000 | uniq -c -f1 | LC_ALL=C sort -n -k2 -T'./tmp' -S1000000 > out.txt
wc -l out.txt

time ./go.sh 6
9417683 out.txt

real    13m32.642s
user    9m54.301s
sys     3m8.344s


Jak widać, nieźle przyspieszyło. Teraz przenoszę wszystko na stacjonarny, dam 6GB RAM i czekamy.

Pozdrawiam

[buninek]

Jeszcze trochę czasu zaoszczędzi się, gdy się ograniczy uniq do znaków ASCII.
Dodaj LC_ALL=C przed uniq.

Porównaj:
time grep -v '.*/.*/.*/.*/.*/.*/.*/.*' wynik
time LC_ALL=C grep -v '.*/.*/.*/.*/.*/.*/.*/.*' wynik
Różnica jest niebagatelna.

Bardzo dobrym zamiennikiem sed-a jest minised. Diabelsko szybki, na ogromnych plikach.
Identycnie jest z cgrepem.
http://www.bell-labs.com/project/wwexptools/cgrep/
Rewelacyjne narzędzie, niezwykle szybkie, duużo szybsze od GNU grepa.

Tym sortem się kiedyś bawiłem całkiem sprawny.
http://billposer.org/Software/msort.html

[krzyszp]

Natomiast jeśli nie próbowałeś optymalizować transakcji, to cały ten
program do dodawania unikalnych rekordów obejmij transakcją.

Nie da rady, zabraknie pamięci (w serwerze mam tylko ok.3GB dla bazy).
Podobnie nie ma sensu paczkować rekordów, gdyż obecnie dla każdej linii przed dodaniem leci select, aby sprawdzić, czy nie występuje...

Myślę, że rozwiązanie shellowe będzie znacznie szybsze.

Ps. Na bazie działam przez LAN 1Gb/s

[mariotti]

Jeszcze trochę czasu zaoszczędzi się, gdy się ograniczy uniq do znaków ASCII.
Dodaj LC_ALL=C przed uniq.

Porównaj:
time grep -v '.*/.*/.*/.*/.*/.*/.*/.*' wynik
time LC_ALL=C grep -v '.*/.*/.*/.*/.*/.*/.*/.*' wynik
Różnica jest niebagatelna.

Bardzo dobrym zamiennikiem sed-a jest minised. Diabelsko szybki, na ogromnych plikach.
Identycnie jest z cgrepem.
http://www.bell-labs.com/project/wwexptools/cgrep/
Rewelacyjne narzędzie, niezwykle szybkie, duużo szybsze od GNU grepa.

Tym sortem się kiedyś bawiłem całkiem sprawny.
http://billposer.org/Software/msort.html

A ja myślałem naiwnie, że najszybsze są standardowo w linuxie.
Dobrze wiedzieć że są lepsze.

Programik już odpaliłem, działa na drugim kompie. Nie zmienię teraz
w nim nic, po prostu mam masę roboty, terminy, itd. Jutro zobaczymy jaki
będzie efekt działania tego programu. Jak będzie mizerny, to cóż...
zaimplementuję w C++ ten algorytm który opisałem kilka postów
wyżej.

Niepokoi mnie jeszcze ten błąd z trójką na końcu. No ale między innymi
po to będzie testowa wersja na boinc :)

Pozdrawiam

[mariotti]

Nie da rady, zabraknie pamięci (w serwerze mam tylko ok.3GB dla bazy).

Można też dać begin commit np. co 10k rekordów. Na sqlite taka technika daje
czasami bardzo duże przyspieszenie - zależy od struktury bazy.

Podobnie nie ma sensu paczkować rekordów, gdyż obecnie dla każdej linii przed dodaniem leci select, aby sprawdzić, czy nie występuje...

Wszystko się zgadza, prawdopodobnie ten select jest wąskim gardłem całej aplikacji.

Myślę, że rozwiązanie shellowe będzie znacznie szybsze.
Ps. Na bazie działam przez LAN 1Gb/s

Shellowe dla deph=6 działa 10 minut na laptopie. Zobaczymy co będzie dla depth=7.


Pozdrawiam

[buninek]

A ja myślałem naiwnie, że najszybsze są standardowo w linuxie.
Dobrze wiedzieć że są lepsze.

Bez przesady, te standardowe narzędzia są uniwersalne i naprawdę szybkie. To są poprostu zupełnie inne narzędzia.

Przykładowo minised ma 5% możliwości seda. Tylko czasem potrzebujemy tylko tych 2% możliwości, a dużo ważniejsza jest szybkość przy przetworzenie terabajtów danych.

Cgrep to akurat unikalny programik. Tylko znowu ma pewne cechy których nie posiada GNU grep, ale również brakuje mu kilku opcji grepa.
Powstał nie byle gdzie, bo w Bell Labs, a tam pracowali naprawdę łebscy goście. Twórcy UNIXA, języka C, C++, R. Bodajże 7 pracowników tego laboratorium "talentów" zostało nagrodzonych Noblem.