On Friday, October 10, 2014 4:01:50 PM UTC+2, bartekltg wrote:
> Też tak początkowo podejrzewałem, ale kod sugerował przetwarzanie
> pojedynczej listy.
Tak tak. Specjalnie się "czepiam", poniewaz czesto staje przed
problemem dwuznacznosci w specyfikacjach.


> Jeśli jednak trzeba te listy połączyć, można to ładnie zespolić
> z mergesortem. CHoć qsort i unique nadal może być szybsze ;-)
Duzo zalezy od implementacji listy. Ja bym zalozyl, ze te listy sa
listami tablic elementow, a nie listami elementow.


> >> BTW, chyba to nie listy, skoro mają dostęp przez indeks.
> > Moze taka moda nazewnicza? W QT do jednej z list tez jest (szybki!)
> OT?
Biblioteka QT. Szablony QList, QLinkedList, QVector, QSet, QMap, QHash, itd.

> Tego chyba nikt nie napisze nawet, jak tam będzie vector.
> Sensu za dużo nie ma;-)
O 1000zł bym się nie założył, ale o 100zł mogę się założyć, że iterowanie
po wyjętym wcześniej wskaźniku będzie dużo szybsze niż po indeksie. W QT
gwarancję że to się uda daje QVector. W Standardowej nie wiem czy można.


Pozdrawiam

do góry

On Fri, 10 Oct 2014 06:39:10 -0700 (PDT), "M.M." <m...@g...com>
wrote:

>On Sunday, October 5, 2014 10:13:08 PM UTC+2, A. L. wrote:
>
>> Jak listy sa posortowane, to powtarzajace sie elementy sa jeden za
>> drugim. Wystarczy wiec "jechac" po liscie z indeksem i, i porownywac
>> element [i] z [i+1]. Jezeli sa takie same, usunac element [i+1].
>> Reszta to szczegoy
>
>> Jezeli listy sa nieduze, moana ja konwertowac do struktury Set, ktora
>> jak wiadomo nie ma duplikatow, a potem Set z powrotem do listy jezeli
>> potzrebne jest sortowanie
>
>Ja nie wiem co to znaczy odfiltrowac duplikaty. Moze jesli napis X
>wystepuje N > 1 razy, to trzeba usnac go N razy, a nie N-1 razy?
>Jesli N razy, to chyba potrzebne sa dwa Sety.
>
>Pozdrawiam

Nie rozumiem

A.L.

do góry

On Saturday, October 11, 2014 4:27:02 PM UTC+2, A. L. wrote:
> Nie rozumiem

Mam przykladowa liste wejsciowa:
a,a,a,b,b,c,c,c,d,e

Na wyjscu mam:

1) a,b,b,c,c,c,d,e
2) d,e
3) a,b,c,d,e

We wszystkich trzech przypadkach doszlo do odfiltrowania duplikatow.

Tylko przypadek trzeci da sie (wygodnie) zaimplementowac na strukturze Set.

Pozdrawiam

do góry

On 11.10.2014 10:07, M.M. wrote:
> On Friday, October 10, 2014 4:01:50 PM UTC+2, bartekltg wrote:
>> Też tak początkowo podejrzewałem, ale kod sugerował przetwarzanie
>> pojedynczej listy.
> Tak tak. Specjalnie się "czepiam", poniewaz czesto staje przed
> problemem dwuznacznosci w specyfikacjach.


Kryształowa kula jest niezbędnym wyposażeniem.


>> Tego chyba nikt nie napisze nawet, jak tam będzie vector.
>> Sensu za dużo nie ma;-)
> O 1000zł bym się nie założył, ale o 100zł mogę się założyć, że iterowanie
> po wyjętym wcześniej wskaźniku będzie dużo szybsze niż po indeksie. W QT
> gwarancję że to się uda daje QVector. W Standardowej nie wiem czy można.

Ale po co, skoro masz iterator. On się rozwija w przypadku vector
do gołego wskaźnika, a nie trzeba uprawiać partyzantki*).

GCC przy 03 i wersję z indeksem przerabia na tak samo szybką,
na O2 widzę kilka procent narzutu.


Test, pomijając szczegóły, taki:
int test1(const vector<int> &tab)
{
int acu=0;
for (size_t i=0;i<tab.size();i++)
acu+=tab[i];
return acu;
}
int test2(const vector<int> &tab)
{
int acu=0;
for (auto it = tab.begin();it!=tab.end();++it)
acu+=*it;
return acu;

}
int test3( vector<int> &tab)
{
int acu=0;
for (int *p = &(tab[0]); p<=&(tab.back()); ++p )
acu+=*p;
return acu;
}

Czasy przy O3:
ind iter ptr
0.580365s 0.5802s 0.574878s
0.573168s 0.580003s 0.570412s
0.576243s 0.595382s 0.598803s
0.583383s 0.605905s 0.574091s
0.559924s 0.570881s 0.56386s
0.565881s 0.570138s 0.567056s
0.566698s 0.572243s 0.593708s
0.583027s 0.579597s 0.582566s
0.576352s 0.57665s 0.570913s
0.577967s 0.578482s 0.57333s

czasy przy O2:
ind iter ptr
1.01675s 0.919716s 0.918818s
0.998275s 0.914182s 0.915593s
0.989508s 0.908565s 0.911251s
0.998609s 0.90728s 0.914902s
1.0199s 0.95588s 0.894817s
1.00836s 0.914023s 0.907522s
0.995177s 0.926149s 0.920606s
0.989913s 0.904324s 0.919234s
1.00331s 0.915149s 0.913598s
0.997118s 0.913398s 0.900119s

Ogolna różnica między 2 a 3 wynika z rozwijania pętli.


pzdr
bartekltg

do góry

On Sunday, October 12, 2014 1:17:57 AM UTC+2, bartekltg wrote:
> Ale po co, skoro masz iterator. On się rozwija w przypadku vector
> do gołego wskaźnika, a nie trzeba uprawiać partyzantki*).
> GCC przy 03 i wersję z indeksem przerabia na tak samo szybką,
> na O2 widzę kilka procent narzutu.
> Test, pomijając szczegóły, taki:
> [...]
> Ogolna różnica między 2 a 3 wynika z rozwijania pętli.
U mnie na testach byl narzut wiekszy. QVector i QList dzialaly 2-3 razy
dluzej niz tablica statyczna. Tak, wiem ze tablice statyczne kompilatory
moga lepiej zopytmalizowac niz wskaznik, ale jednak nie powinny, poniewaz
wskaznik to prawie to samo co tablica. Mialem tez ciut bardziej
skomplikowane obliczenia, mniej/wiecej:
QVector< QVector<typ_prosty> >
Rozmiar wewnętrznego 30 liczb int/float
Rozmiar zewnętrznego 200tys.

Operacje mniej/wiecej takie:

for( i=0 ; i<200tys ; i++ ) {
for( j=0 ; j<30 && vector[i][j] >= min[j] && vector[i][j] >= min[j] ; j++ )
;
sum += j==30 ? 1 : -1;
}
print( sum );


Teraz nie mam kodu na tym kompie, potem wrzuce calosc.

Pozdrawiam

do góry

On Sunday, October 12, 2014 2:31:35 AM UTC+2, M.M. wrote:
> Teraz nie mam kodu na tym kompie, potem wrzuce calosc.
http://pastebin.com/sinjnRRw
Pozdrawiam

do góry

On 12.10.2014 02:31, M.M. wrote:
> On Sunday, October 12, 2014 1:17:57 AM UTC+2, bartekltg wrote:
>> Ale po co, skoro masz iterator. On się rozwija w przypadku vector
>> do gołego wskaźnika, a nie trzeba uprawiać partyzantki*).
>> GCC przy 03 i wersję z indeksem przerabia na tak samo szybką,
>> na O2 widzę kilka procent narzutu.
>> Test, pomijając szczegóły, taki:
>> [...]
>> Ogolna różnica między 2 a 3 wynika z rozwijania pętli.
> U mnie na testach byl narzut wiekszy. QVector i QList dzialaly 2-3 razy
> dluzej niz tablica statyczna.

Rzeczywiście, QVectro + indeksy coś się nie chce optymalizować.
Na O2 w tamtym teście działał w tej samej kategorii co wszyscy,
ale na O3 już prawie dwa razy wolniej. Na iteratorach
nie było problemu, biega tak samo jak vector czy goła tablica.

Jednym słowem, jeśli nie bawisz się interfejsem, używaj standardowego
vectora.

> Tak, wiem ze tablice statyczne kompilatory
> moga lepiej zopytmalizowac niz wskaznik, ale jednak nie powinny, poniewaz
> wskaznik to prawie to samo co tablica. Mialem tez ciut bardziej
> skomplikowane obliczenia, mniej/wiecej:
> QVector< QVector<typ_prosty> >
> Rozmiar wewnętrznego 30 liczb int/float
> Rozmiar zewnętrznego 200tys.
>
> Operacje mniej/wiecej takie:
>
> for( i=0 ; i<200tys ; i++ ) {
> for( j=0 ; j<30 && vector[i][j] >= min[j] && vector[i][j] >= min[j] ; j++ )
> ;
> sum += j==30 ? 1 : -1;
> }
> print( sum );

Nie kompiluje się ;-)

Jeśli zawsze i wszędzie masz 30, może array<int,30> coś poprawi.
Albo nawet adresować wszytko liniowo (skoro nie boisz się
bawić wskaźnikami, i to nie powinno być problemem.)

Poza tym,
vector[i][j] >= min[j] && vector[i][j] >= min[j]
To imho dwa razy to samo.

Czysto estetycznie, może drugiego fora zastąpić while,
(albo nawet std::find_if, w końcu szukasz pierwszego
elementu nie spełniającego pewnego kryterium), początkowo
patrząc na ten kod 'nie widziałem' tego, że for kręci pustą
instrukcją.

To się cudownie równoległa;-)

pzdr
bartekltg

do góry

On Sunday, October 12, 2014 12:53:04 PM UTC+2, bartekltg wrote:

> Jeśli zawsze i wszędzie masz 30, może array<int,30> coś poprawi.
Bedę mial jeszcze wieksza sieczke, tamto na pastebin stanowi tylko
zgrubny test. Docelowo mniej / wiecej:

struct A {
QVector<int> iv;
QVector<float> fv;
};

struct B {
QVector< A > vs;
};


B b;
for( i=0 ; i<b.vs.size() ; i++ ) {
bool all = true;
int j = 0;
while( all && j<b.vs[i].iv.size() ) {
all = b.vs[i].vi[j] >= mini[j] && b.vs[i].vi[j] <= maxi[j];
j++;
}
j = 0;
while( all && j<b.vs[i].fv.size() ) {
all = b.vs[i].vf[j] >= minf[j] && b.vs[i].vf[j] <= maxf[j];
j++;
}
if( all ) coś();
}


> Albo nawet adresować wszytko liniowo (skoro nie boisz się
> bawić wskaźnikami, i to nie powinno być problemem.)
Pewnie druga wersja bedzie na samych wskaznikach i malloc.


> Poza tym,
> vector[i][j] >= min[j] && vector[i][j] >= min[j]
> To imho dwa razy to samo.
Mialo byc
vector[i][j] >= min[j] && vector[i][j] <= max[j]
Na pastebinie jest troche lepsza wersja.

> Czysto estetycznie, może drugiego fora zastąpić while,
> (albo nawet std::find_if, w końcu szukasz pierwszego
> elementu nie spełniającego pewnego kryterium), początkowo
> patrząc na ten kod 'nie widziałem' tego, że for kręci pustą
> instrukcją.
Tak, puste instrukcje nie sa zbyt czytelne.


> To się cudownie równoległa;-)
Tak! Ale to potem.

Ciekawe czy na dlugich rejestrach by sie dalo sprawdzic kilka
warunkow w jednej iteracji. Na karcie grafiki tez powinno
niezle przyspieszyc, ale moja ksiazka do CUDA lezy od ponad
roku na polce i jeszcze do teraz smierdzi drukarnia :D

Pozdrawiam

do góry

On 12.10.2014 13:39, M.M. wrote:
> On Sunday, October 12, 2014 12:53:04 PM UTC+2, bartekltg wrote:
>


> http://pastebin.com/sinjnRRw


Trochę porównujesz inne rzeczy.

Test odpalasz 10 razy. Ale pamięć dla tablic alokujesz tylko
raz, dla kontenerów 10 razy:>

BTW,
static int data[CNT_ROWS][CNT_COLS];
Zdecydowanie nie leży na stosie ;-) Przez to static.

Znasz rozmiary statycznie, a jednak nie używasz resize.
przez co alokujesz to co trzeba, ale też polowę, ćwiartkę...


Rules jako tablica tablic możę bie być najlepsza? I tak każda
reguła jest inaczej używana, nie wsadzisz więc tego w pętlę.
Czemu nie struktura? [update, zaminiłem ma pair, przyszpieszenie
znikome]


> for( int i=0 ; i<LOOPS ; i++ ) {
> for( int i=0 ; i<CNT_ROWS ; i++ ) {

Nie rób tak ;-)


Wrzuciłem napisaną przez siebie wersję na vector.
Ciut wolniejsza, ale nie aż tak;-)

testRaw
9.14884s sum=-191116600
testRaw2
6.54265s sum=-191116600
testVectBrt
10.0932s sum=-191116600
testVect2Brt
9.03653s sum=-191116600
testQVector
38.9511s sum=-191116600
testQVector2
21.9616s sum=-191116600
testQList
41.9841s sum=-191116600
testQList2
19.1983s sum=-191116600
testQList3
19.162s sum=-191116600

long long testVector()
{
vector< vector<int> > data( CNT_ROWS, vector<int>(CNT_COLS,0) );
for( int i=0 ; i<CNT_ROWS ; i++ )
{
for(auto it = data[i].begin(); it!=data[i].end(); ++it )
*it = ( rand() % 1000 );
}
vector< vector<int> > rules(CNT_COLS, vector<int>(2,0));
for( auto it = rules.begin(); it!=rules.end();++it )
{
(*it)[0]=( rand()%100 );
(*it)[1]=( 900 + rand()%100 );
}
long long sum = 0;
for( int l=0 ; l<LOOPS ; l++ ) {
for( auto it=data.begin(); it !=data.end(); ++it ) {
int j=0;
while( j < CNT_COLS && (*it)[j] >= rules[j][0] && (*it)[j]
<= rules[j][1] )
{
j++;
}
sum += (j==CNT_COLS) ? +1 : -1;
}
}
return sum;
}



long long testVector2()
{
vector< vector<int> > data( CNT_ROWS, vector<int>(CNT_COLS,0) );
for( int i=0 ; i<CNT_ROWS ; i++ )
{
for(auto it = data[i].begin(); it!=data[i].end(); ++it )
*it = ( rand() % 1000 );
}
vector< pair<int,int> > rules(CNT_COLS);
for( auto it = rules.begin(); it!=rules.end();++it )
{
it->first=rand()%100 ;
it->second=900 + rand()%100 ;
}
long long sum = 0;
for( int l=0 ; l<LOOPS ; l++ ) {
for( auto it=data.begin(); it !=data.end(); ++it ) {
auto dit = (*it).begin();
auto rit = rules.begin();
while( rit!=rules.end() && *dit >= rit->first && *dit <=
rit->second )
{
++rit;
++dit;
}
sum += (rit-rules.begin()==CNT_COLS) ? +1 : -1;
}
}
return sum;
}



>> Jeśli zawsze i wszędzie masz 30, może array<int,30> coś poprawi.
> Bedę mial jeszcze wieksza sieczke, tamto na pastebin stanowi tylko
> zgrubny test. Docelowo mniej / wiecej:



> struct A {
> QVector<int> iv;
> QVector<float> fv;
> };

Nadal nie powiedziałeś, czemu vector z QT, a nie STL? ;-)

>
> struct B {
> QVector< A > vs;
> };

Coś w tę strukturę jeszcze kiedyś wlezie? Jeśli nie, to tylko nadgarstek
męczysz wpisywaniem kropek;-)


> B b;
> for( i=0 ; i<b.vs.size() ; i++ ) {
> bool all = true;
> int j = 0;
> while( all && j<b.vs[i].iv.size() ) {
> all = b.vs[i].vi[j] >= mini[j] && b.vs[i].vi[j] <= maxi[j];
> j++;
> }
> j = 0;
> while( all && j<b.vs[i].fv.size() ) {
> all = b.vs[i].vf[j] >= minf[j] && b.vs[i].vf[j] <= maxf[j];
> j++;
> }
> if( all ) coś();
> }

:-)


>
>
>> Albo nawet adresować wszytko liniowo (skoro nie boisz się
>> bawić wskaźnikami, i to nie powinno być problemem.)
> Pewnie druga wersja bedzie na samych wskaznikach i malloc.


>> To się cudownie równoległa;-)
> Tak! Ale to potem.
>
> Ciekawe czy na dlugich rejestrach by sie dalo sprawdzic kilka
> warunkow w jednej iteracji. Na karcie grafiki tez powinno
> niezle przyspieszyc, ale moja ksiazka do CUDA lezy od ponad
> roku na polce i jeszcze do teraz smierdzi drukarnia :D

Czytaj, czytaj, nigdy nie wiadomo, kiedy się przyda;>

pzdr
bartekltg

do góry

On Sunday, October 12, 2014 5:25:46 PM UTC+2, bartekltg wrote:
> On 12.10.2014 13:39, M.M. wrote:
> Trochę porównujesz inne rzeczy.
> Test odpalasz 10 razy. Ale pamięć dla tablic alokujesz tylko
> raz, dla kontenerów 10 razy:>
O to chodzi aby nie porownywac takich samych procedur - zart :D
Powiedzmy ze porownuje wszelka wygode programowania na szablonach z
metlikiem wskaznikow.

> BTW,
> static int data[CNT_ROWS][CNT_COLS];
> Zdecydowanie nie leży na stosie ;-) Przez to static.
Zgadzam sie.

> Znasz rozmiary statycznie, a jednak nie używasz resize.
> przez co alokujesz to co trzeba, ale też polowę, ćwiartkę...
Porownuje tez listy vs wektory. Lista powinna byc sprytniejsza.


> Rules jako tablica tablic możę bie być najlepsza? I tak każda
> reguła jest inaczej używana, nie wsadzisz więc tego w pętlę.
> Czemu nie struktura? [update, zaminiłem ma pair, przyszpieszenie
> znikome]
Hmmm moze, nie wiem.

> > for( int i=0 ; i<LOOPS ; i++ ) {
> > for( int i=0 ; i<CNT_ROWS ; i++ ) {
> Nie rób tak ;-)
Poniewaz taka sama nazwa zmiennej? Lubie tak robic, choc
przyznaje, ze czasami tez mnie to drazni. Jednak generalnie dla
programisty mniej zmiennych do analizy, a dla kompilatora... tez
mniej zmiennych do optymalizowania.

> Wrzuciłem napisaną przez siebie wersję na vector.
> Ciut wolniejsza, ale nie aż tak;-)
Dzieki wielkie!


> testRaw
> 9.14884s sum=-191116600
> testRaw2
> 6.54265s sum=-191116600
> testVectBrt
> 10.0932s sum=-191116600
> testVect2Brt
> 9.03653s sum=-191116600

Ciekawe dlaczego u Ciebie testRaw2 taki szybki wypadl. U mnie byl
ciut wolniejszy. Z powodu innego sprzetu, kompilatora, opcji
kompilacji?


> long long testVector()
>
> {
>
> vector< vector<int> > data( CNT_ROWS, vector<int>(CNT_COLS,0) );
>
> for( int i=0 ; i<CNT_ROWS ; i++ )
>
> {
>
> for(auto it = data[i].begin(); it!=data[i].end(); ++it )
>
> *it = ( rand() % 1000 );
>
> }
>
> vector< vector<int> > rules(CNT_COLS, vector<int>(2,0));
>
> for( auto it = rules.begin(); it!=rules.end();++it )
>
> {
>
> (*it)[0]=( rand()%100 );
>
> (*it)[1]=( 900 + rand()%100 );
>
> }
>
> long long sum = 0;
>
> for( int l=0 ; l<LOOPS ; l++ ) {
>
> for( auto it=data.begin(); it !=data.end(); ++it ) {
>
> int j=0;
>
> while( j < CNT_COLS && (*it)[j] >= rules[j][0] && (*it)[j]
>
> <= rules[j][1] )
>
> {
>
> j++;
>
> }
>
> sum += (j==CNT_COLS) ? +1 : -1;
>
> }
>
> }
>
> return sum;
>
> }
Musze sprawdzic, czy vector z stdliba te ma constBegin, albo metode
'at' zamiast operatora indeksowania[]. W QT metoda at jest duzo szybsza
od operatora[].


> long long testVector2()
>
> {
>
> vector< vector<int> > data( CNT_ROWS, vector<int>(CNT_COLS,0) );
>
> for( int i=0 ; i<CNT_ROWS ; i++ )
>
> {
>
> for(auto it = data[i].begin(); it!=data[i].end(); ++it )
>
> *it = ( rand() % 1000 );
>
> }
>
> vector< pair<int,int> > rules(CNT_COLS);
>
> for( auto it = rules.begin(); it!=rules.end();++it )
>
> {
>
> it->first=rand()%100 ;
>
> it->second=900 + rand()%100 ;
>
> }
>
> long long sum = 0;
>
> for( int l=0 ; l<LOOPS ; l++ ) {
>
> for( auto it=data.begin(); it !=data.end(); ++it ) {
>
> auto dit = (*it).begin();
>
> auto rit = rules.begin();
>
> while( rit!=rules.end() && *dit >= rit->first && *dit <=
>
> rit->second )
>
> {
>
> ++rit;
>
> ++dit;
>
> }
>
> sum += (rit-rules.begin()==CNT_COLS) ? +1 : -1;
>
> }
>
> }
>
> return sum;
>
> }
Hmmmm, sprytniejsze.


> Nadal nie powiedziałeś, czemu vector z QT, a nie STL? ;-)
Na razie tylko z przyzwyczajenia. Docelowo uzyje albo STL, albo
sam napisze na swoje potrzeby jakis wektor, albo bedzie rzezba
na wskaznikach.


> Coś w tę strukturę jeszcze kiedyś wlezie? Jeśli nie, to tylko nadgarstek
> męczysz wpisywaniem kropek;-)
Wlezie duzo, ale przed testowaniem regulek (chyba) mozna zostawic tylko
przedzialy min i max.

Pozdrawiam

do góry