markon Temat założony przez niniejszego użytkownika |
» 2011-06-18 17:04:27 jak zatem proponujesz reprezentować graf w C++ pod algorytm BSF/DSF
może listę listy w oparciu o STL?? |
|
DejaVu |
» 2011-06-18 17:45:13 Chciałbym zauważyć, że przytoczony przykład na podanym slajdzie jest nieprawidłowy - do listy nie masz dostępu do dowolnego elementu w czasie O(1), natomiast do vector tak. Innymi słowy zaprezentowano wyniki algorytmów, które nie są sobie równoważne. Chyba, że ich benchmark zakładał, że usuwam np. n' elementów sąsiadujących w liście po kolei i vectorze przestawnym.
/edit:
Dodam jeszcze:
#pragma once
#include <algorithm>
#include <memory/Memory.hpp> #include <tools/Time.hpp> #include <vector>
typedef tools::CTime CTimer;
template < class ContainerT > void initialize( ContainerT & c, int ile, const char * sName ) { c.clear(); CTimer t; for( int i = 0; i < ile; i++ ) c.push_back( i ); t.Update(); printf( "Initialize %s = %.4lf\n", sName, t.Get() ); }
template < class ContainerT > void print( ContainerT & c ) { return; for( ContainerT::iterator i = c.begin(); i != c.end(); ++i ) printf( "%d, ", * i ); printf( "\n" ); }
template < class ContainerT > void usunZvectora( ContainerT & c, int usun ) { c[ usun ] = c[ c.size() - 1 ]; c.pop_back(); }
void test_vector( int rozmiar, int usun, int ileUsunac ) { const char * sName = "std::vector"; typedef std::vector < int > ContainerT; { ContainerT c; initialize( c, rozmiar, sName ); CTimer t; for( int i = 0; i < ileUsunac; i++ ) usunZvectora( c, usun - i ); t.Update(); printf( "Usuwane ze srodka %s = %.4lf\n", sName, t.Get() ); print( c ); } }
void test_list( int rozmiar, int usun, int ileUsunac ) { const char * sName = "memory::List"; typedef memory::List < int, 4096 > ContainerT; { ContainerT c; initialize( c, rozmiar, sName ); ContainerT::iterator itFirst = c.begin(); for( int i = 0; i < usun; i++ ) ++itFirst; CTimer t; for( int i = 0; i < ileUsunac; i++ ) ( itFirst = c.erase( itFirst ) ) --; t.Update(); printf( "Usuwane ze srodka %s = %.4lf\n", sName, t.Get() ); print( c ); } }
int main() { const int ILE = 3000000; test_vector( ILE, ILE / 2, ILE / 3 ); test_list( ILE, ILE / 2, ILE / 3 ); return 0; }
Milion usunięć do wykresu, który jest przedstawiony na spornym slajdzie.
Initialize std::vector = 0.0434
Usuwane ze srodka std::vector = 0.0032
Initialize memory::List = 0.0513
Usuwane ze srodka memory::List = 0.0508
Dodam jeszcze, że to jest omówienie specyficznego algorytmu w którym kolejność danych nie ma znaczenia. Niemniej jednak nie są to operacje równoważne, bowiem w przypadku std::vector zostanie wywołany dodatkowo konstruktor kopiujący, który może wykonać różne dziwne operacje po drodze, a w efekcie uzyskamy efekt odwrotny do zamierzonego. |
|
dmx81 |
» 2011-06-18 18:20:14 w innym miejscu ich pracy napisali: NIE WARTO OPTYMALIZOWAĆ? Konieczne jest bezkompromisowe wykorzystanie maksimum dostępnej mocy obliczeniowej, dlatego: Używamy C++, a nie języków interpretowanych, z wirtualną maszyną czy garbagecollectorem Wyłączamy obsługę wyjątków i RTTI Piszemy własne alokatorypamięci Unikamy STL
|
z czego wynika, ze lepiej pisac wlasne alokatory pamieci, niz uzywac STL? trzeba by to chyba w calosci przeczytac i ocenic - ale tylko ktos, kto ma rownie duze doswiadczenie, dla mnie to " za wysokie progi", dlatego pozostaje mi jedynie wkleic ich zdanie jako cytat, a ocene pozostawiam "mistrzom" :) Często powtarza się, że kompilator jest lepszy w optymalizacji kodu od przeciętnego programisty Tymczasem… 82
inty = x / x; 00401018 movecx, dwordptr[ esp + 8 ] 0040101C moveax, ecx 0040101E cdq 0040101F idiveax, ecx
inty = x / x; 00401018 moveax, 1
|
|
|
DejaVu |
» 2011-06-18 18:28:56 Ja już raz zabierałem głos na temat optymalizacji na forum gamedeva - w wyniku czego wynikła mała wojenka, a sami autorzy tej prezentacji mnie na tą konferencję zapraszali. Dodam, że jeszcze warna dostałem, że się spieram z 'władzą', więc odpuściłem sobie debatowanie po przedstawieniu kilku kolejnych dowodów popierających moje tezy.
Ja wyznaję zasadę, że liczy się przede wszystkim algorytm, a nie sztuczki i kruczki, które w sumie niosą ze sobą zazwyczaj pewne ryzyko, iż zadziałają one w nieoczekiwanym momencie przeciwko nam.
/edit:
A skomentuję jeszcze posta wyżej. Obecnie wyznaje się zasadę: moc obliczeniowa jest tania, optymalizacja algorytmów jest droga - kupmy lepszy sprzęt bądź oczekujmy lepszego sprzętu od klienta - w sumie i tak obecne czasy sprowadziły je do jednego mianownika, tj. minimum 2,4GHz + 1 rdzeń, więc 'po co walczyć i płacić za to?' :) |
|
michalp |
» 2011-06-18 20:49:11 Co do kwestii optymalizacji kompilatora przedstawionej w prezentacji to się nie zgodzę. Przytoczone zostały dwa skrajne przypadki. W pierwszym kompilator ma rację (o ile zmienna x nie jest stałą znaną w czasie kompilacji) bo jak przyznali sami autorzy prezentacji w przypadku gdy x == 0 może zostać rzucony wyjątek. Po za tym jeszcze nie widziałem w kodzie takiego "stworka" jak x / x (jest w ogóle jakieś zastosowanie tego?). W drugim przypadku nie podano który kompilator wygenerował taki kod i dla jakich parametrów. (btw. g++ 4.5.1 bez włączonej optymalizacji oblicza wartości stałych w czasie kompilacji). |
|
dmx81 |
» 2011-06-18 21:16:36 ja w sumie uwazam, ze jak sie nie ma wiedzy dostatecznie duzej, to najlepiej uzywac tego, co jest powszechnie przyjete - czyli w omawianym przypadku - sam bym tez uzywal STL no i zdal sie na optymalizacje kompilatora. A jesli ktos ma odpowiednia duza wiedze, to pewnie nie bedzie sie pytal co lepsze, ale samemu sprawdzi, ktore rozwiazanie mu bardziej odpowiada. Najgorzej, jak my malutcy zapytamy o zdanie naszych mentorów - i kazdy z nich bedzie mial inne zdanie ;) jak w przytoczonym wyzej poscie (to o wojence w udowadnianiu swoich racji... troche to poczytalem i dla mnie czarna magia ;) ) |
|
markon Temat założony przez niniejszego użytkownika |
» 2011-06-18 21:26:57 ok, ale jaką metodę reprezentacji grafu proponujecie pod algorytm DSF/BSF tak aby było to efektywne? |
|
DejaVu |
» 2011-06-18 23:48:40 To pytanie ma się akurat już nijak do pytania postawionego w temacie... więc => załóż nowy temat ;p a my odpowiemy później ze stoickim spokojem "użyj google" :P |
|
1 « 2 » |