Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?

czy jest jaka kolwiek różnica wydajnościowa pomiędzy listą STL, a własną implementacją listy?

Ostatnio zmodyfikowano 2011-06-18 23:48
Autor Wiadomość
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??
P-34257
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:
C/C++
#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; //disable printing
    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.
P-34258
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
C/C++
// MSVC 2008 Release(/O2)
inty = x / x;
00401018 movecx, dwordptr[ esp + 8 ]
0040101C moveax, ecx
0040101E cdq
0040101F idiveax, ecx

// przeciętny programista
inty = x / x;
00401018 moveax, 1
P-34260
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?' :)
P-34261
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).
P-34269
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 ;) )
P-34270
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?
P-34271
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
P-34274
1 « 2 »
Poprzednia strona Strona 2 z 2