• 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

VPS Starter Arubacloud
+1 głos
245 wizyt
pytanie zadane 13 grudnia 2020 w C i C++ przez xorbane Użytkownik (950 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 Mędrzec (154,780 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,470 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 Mędrzec (155,460 p.)
Nie wszystkie takie informacje są w cppref.
+1 głos
odpowiedź 13 grudnia 2020 przez mokrowski Mędrzec (155,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 (344,100 p.)
Ale tutaj nie ma żadnych operacji na wskaźnikach ani wyłuskania :D Same referencje.
komentarz 15 grudnia 2020 przez mokrowski Mędrzec (155,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 (344,100 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 Użytkownik (950 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 (344,100 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
0 odpowiedzi 272 wizyt
pytanie zadane 6 kwietnia 2022 w C i C++ przez pasjonat_algorytmiki Pasjonat (19,540 p.)
0 głosów
1 odpowiedź 253 wizyt
pytanie zadane 19 marca 2022 w C i C++ przez pasjonat_algorytmiki Pasjonat (19,540 p.)

92,451 zapytań

141,261 odpowiedzi

319,073 komentarzy

61,853 pasjonatów

Motyw:

Akcja Pajacyk

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

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...