• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Jaki jest najlepszy / najwydajniejszy sposób na iteracje vectorów

Fiszki IT
Fiszki IT
+1 głos
144 wizyt
pytanie zadane 13 grudnia 2020 w C i C++ przez xorbane Nowicjusz (200 p.)

Pytam ponieważ przeglądając internety natknąłem się na bardzo wiele sugerowanych sposobów, które nawet ja mogę na pierwszy rzut oka uznać za niezbyt optymalne algorytmicznie czy wydajnościowo, np pisane w stylu:

    for (const auto X : mvr) // mvr = random vector<vector<int_fast8_t>>  
    {
        cout << "[VECTOR] @ " << &X << endl;
        for(const auto item : X)
        {
            printf("[ITEM] @ \t %p \n", &item);
        }

    }

To co mi się tutaj nie podoba to to że adresy pamięci są zawsze te same zarówno dla vectora jak i itemu w nim zawartego, czyli po prostu program tworzy nową kopie każdej zmiennej przy każdym jej użyciu no i to jest raczej b.słabe algorytmicznie, nie do końca wiem jakie są globalne wytyczne w c++ bo jeszcze mnie ta lektura przerasta, ale w np w pythonie coś takiego by nigdzie nie przeszło.

 

Jedyny sposób w jaki udało mi się zrobić to samo ale chyba już ciut wydajniej (2400 vs 3000 instrukcji cpu wg godbolt.org) to była klasyczna iteracja z C:

    for (int V = 0 ; V < mvr.size() ; V++)
    {   cout << endl;
        for (int Y = 0 ; Y < 8 ; Y++)
        {
            printf("%i\t%p\n", mvr[V][Y], &mvr[V][Y]);
        }
    };

 

Więc główne pytanie brzmi, jak najlepiej przeiterować coś takiego (vector vectorów typu int_fast8_t użyty w przykładzie) w nowoczesnym C++, nie robiąc żadnych zbędnych operacji? Czy może jest to już na tyle szybki i zoptymalizowany język że nie powinienem w ogóle się tym przejmować i zostawić to kompilatorowi?

 

 

2 odpowiedzi

+3 głosów
odpowiedź 13 grudnia 2020 przez tangarr VIP (136,520 p.)
wybrane 14 grudnia 2020 przez xorbane
 
Najlepsza

Zamiast kopii obiektu użyj referencji

for (const auto &X : mvr)

Ten kod zostanie rozwinięty do postaci

for (auto iter = mvr.begin(); iter != mvr.end(); iter++) {
    const auto &X = *iter;
    // reszta kodu
}

 

komentarz 17 grudnia 2020 przez Eriss69 Gaduła (4,050 p.)
mega przydatne @mokrowski ale czy jest często używane ? Nie lepiej użyc cppreference do  wyszukania  takich informacji?
komentarz 17 grudnia 2020 przez mokrowski VIP (145,460 p.)
Nie wszystkie takie informacje są w cppref.
+1 głos
odpowiedź 13 grudnia 2020 przez mokrowski VIP (145,460 p.)

A dlaczego zamiast tak:

for (const auto X : mvr)

... nie zrobisz tak:

for (const auto& X : mvr)

Co daje Ci referencję stałą na dane.

Z kolei robiąc tak:

for (auto& X : mvr)

Uzyskasz referencję na dane w trybie r/w. Stąd, będzie można np. zwiększyć każdy element kontenera o 3:

for (auto& X : mvr) {
    X += 3;
}

Jeśli dokonasz dokładnych pomiarów, i to z optymalizacją kompilatora, możesz dojść do wniosku że na współczesnych procesorach dane do wielkości 4-8 bajtów (32-bit vs 64-bit) można kopiować i nie ma różnicy co do wydajności z dostępem przez adres i nie. Jeśli użyjesz rozszerzeń SIMD (mmx, sse, avx ... itp), to może się okazać że ta sytuacja dalej ma miejsce nawet dla danych 16 bajtowych. Tak to optymalizuje np. gcc dla stringa. Krótki do 16 bajtów będzie mógł być kopiowany nawet jeśli prosiłeś o referencję.

Co do Python'a, to język który bazuje na referencjach i 2 rodzajach typów: mutowalnych i niemutowalnych. Nieco inaczej działa dla każdego z nich zliczanie referencji. Poza tym Python posiada odśmiecacz który potrafi obudzić się w niepożądanych miejscach. Zresztą nie bardzo można porównywać szybkość Python'a do C/C++ https://benchmarksgame-team.pages.debian.net/benchmarksgame/fastest/python3-gcc.html

komentarz 15 grudnia 2020 przez adrian17 Ekspert (297,380 p.)
Ale tutaj nie ma żadnych operacji na wskaźnikach ani wyłuskania :D Same referencje.
komentarz 15 grudnia 2020 przez mokrowski VIP (145,460 p.)
Ba.. nie pierwszy to raz pytający nie zrozumiał odpowiedzi ;-) Najśmniejszniejsze jest to że wybrana odpowiedź ma wyłuskanie;-)
komentarz 15 grudnia 2020 przez adrian17 Ekspert (297,380 p.)

Najśmniejszniejsze jest to że wybrana odpowiedź ma wyłuskanie

Nie, odpowiedź ma for-each z referencją, jak Twoja. Niżej jest tylko wyjaśnienie jak działa. (plus to nie wskaźnik, tylko iterator). Też nie przeczytałeś odpowiedzi :P

komentarz 15 grudnia 2020 przez xorbane Nowicjusz (200 p.)
& to też pointerowa operacja przecież. Rozumiem to jako polecenie aby cpu zobaczył jakie dane kryją się w kontenerze pod wskazanym pointerem. Z tego co widzę to troche działa to jak konwersja w dowolną stronę bo jeśli coś nie jest pointerem to & zwraca właśnie pointer?

Dość mocno pokręcone to zwłaszcza że jak się dużo pointerów używa w większym projekcie to szybko można naj&&&&ć pointerów do pointerów do rerefencji do dereferencji do ponterów w stylu int a = *******z i jakoś nie umiem czytać takiego kodu a nawet jak mi się uda załapać co jest co za pierwszym razem to i tak sprawdzam pojedynczo bo nie wierze że dobrze to zrozumiałem :p
komentarz 15 grudnia 2020 przez adrian17 Ekspert (297,380 p.)

Referencja to nie wskaźnik.

bo jeśli coś nie jest pointerem to & zwraca właśnie pointer

& to też pointerowa operacja przecież

Nie, nie w tym miejscu.

To jest adres obiektu:

int *x = &a;

To jest referencja na obiekt:

int &x = a;

I w funkcjach:

void f(int *a); // bierze wskaznik
void f(int &a); // bierze referencje

Ogólnie masz rację tutaj:

parę osób mi mówiło żeby nie używać żadnych op na pointerach w c++ bo już się tak nie robi

Ale referencje to zupełnie co innego, są pod wieloma względami prostsze i bezpieczniejsze i są jednym z fundamentów C++a. Rada "nie używaj wskaźników" ich nie dotyczy.

Podobne pytania

0 głosów
3 odpowiedzi 149 wizyt
pytanie zadane 13 lutego 2016 w C i C++ przez emSon Stary wyjadacz (10,500 p.)
+1 głos
2 odpowiedzi 70 wizyt
Porady nie od parady
Forum posiada swój własny serwer Discord, dzięki któremu będziesz mógł po prostu pogadać z innymi Pasjonatami lub zapytać o jakiś problem. Podstrona z chatem znajduje się w menu pod ikoną człowieka w dymku.IRC

84,745 zapytań

133,550 odpowiedzi

295,964 komentarzy

56,007 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto dwie polecane książki warte uwagi. Pełną listę znajdziesz tutaj.

...