• 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 13 grudnia 2020 przez adrian17 Ekspert (344,100 p.)

2 rodzajach typów: mutowalnych i niemutowalnych. Nieco inaczej działa dla każdego z nich zliczanie referencji

Nie, nie ma czegoś takiego. Nie wiem skąd to wziąłeś.

 

komentarz 13 grudnia 2020 przez mokrowski Mędrzec (155,460 p.)
Ale czego nie ma? Typów mutowalnych i niemutowalnych? Zliczanie referencji jest takie samo ale np. przy funkcjach widać konsekwencje mutowalności. Ergo.. uściślij z czym się pomyliłem.
komentarz 13 grudnia 2020 przez mokrowski Mędrzec (155,460 p.)
edycja 13 grudnia 2020 przez mokrowski

W uzupełnieniu....:

#!/usr/bin/env python3

def fun1(val = 12):
    val += 1
    print("In fun1(), val =", val)

def fun2(lst = []):
    lst.append(1)
    print("In fun2(), lst =", lst)

if __name__ == '__main__':
    print("Mut/not mut")

    a = 100
    fun1(a)
    print("In main, a =", a)
    lst = [1, 2, 3]
    fun2(lst)
    print("In main, lst =", lst)

    print("default args in fun")
    fun1()
    fun1() 
    fun1() 
    fun2()
    fun2() # !!
    fun2()
    fun2([100])
    fun2() # ?!!!!

I wyjaśnienie dla dociekliwych:

#!/usr/bin/env python3

class X:
    def __init__(self):
        print("X construct")

def no_calling_function(x = X()):
    pass

if __name__ == '__main__':
    pass
#!/usr/bin/env python3

import sys

class X:
    def __init__(self):
        print("refcount to x =", sys.getrefcount(self))

def non_call_fun(x = X()):
    pass

if __name__ == '__main__':
    pass

https://docs.python.org/2/library/sys.html#sys.getrefcount

Czyli -1. Tak więc 2. Stąd wynika różnica w obsłudze.

komentarz 13 grudnia 2020 przez adrian17 Ekspert (344,100 p.)

Nie ma w Pythonie konceptu twardego podziału na "typy mutowalne i niemutowalne". Typy są traktowane tak samo (nie "działa inaczej zliczanie referencji"). Tak się składa że niektóre mają metody mutujące, a inne nie - to prawda - ale nie ma w języku (ani interpreterze) takiego fundamentalnego podziału.

przy funkcjach widać konsekwencje mutowalności

To znaczy? (Jeśli masz na myśli domyślne argumenty, to nie ma związku z mutowalnością, tylko z tym że inaczej niż w innych językach zaimplementowali domyślne argumenty)

komentarz 13 grudnia 2020 przez adrian17 Ekspert (344,100 p.)

W uzupełnieniu....:

To nie jest przykład mutowalności, tylko tego że robisz różne rzeczy.

W takim przykładzie kod zachowuje się dokładnie tak samo:

def fun1(val = 12):
    val = 1
def fun2(lst = []):
    lst = [1]

I taki kod by się zachowywał dokładnie tak samo:

def fun1(val = 12):
    val.set(6)
def fun2(lst = []):
    lst.append(6)

...gdyby nie to, że int nie ma żadnej metody mutującej - ale to nie znaczy, że język je jakkolwiek fundamentalnie inaczej traktuje :)

komentarz 13 grudnia 2020 przez mokrowski Mędrzec (155,460 p.)

Ok.. spoko. Po prostu nie zrozumieliśmy się albo ja byłem nieścisły...  Postaram się może więc dokładniej wyjaśnić o co mi chodzi.

1. Implementacja zliczania referencji w interpreterze jest jedna dla dowolnych typów (funkcjonalnie ... bo nie chcę być złapany za jej rozproszenie po kodzie interpretera lub redundancję w pewnym stopniu zawsze występującą).

2. W Pythonie jest zaimplementowana różna obsługa (czyli behawior) typów mutowalnych i niemutowalnych. Nie wynika to z "oddzielnego traktowania kategorii typów" (znów nie chodzi mi o teorię kategorii tylko mut <-> not_mut) a ze sposobu (jednego i tylko jednego) zaimplementowania zliczania referencji. Konsekwencją są niespodzianki obsługi tychże 2 rodzajów typów (oprócz argumentów domyślnych np. metody składowe wykonywane na danych mutowalnych ze zwrotem None).

3. Tak zdaję sobie sprawę że typowanie kacze (ang. Duck Typing), wszechobecne w Pythonie, w swoich zrębach ma traktowanie typu w dużym skrócie (pozwolę sobie na niego w tym miejscu) jak zbioru zachowań (choć oczywiście nie tylko...)

4. Tak zdaję sobie sprawę że wymaganie "niemutowalności" np. dla kluczy słownika ogranicza się do implementacji metody __hash__(...) lub odpowiedzi na takie wywołanie. I to wystarcza bez deklarowania "rodzaju typu" lub jego "mutowalności/nie mutowalności". Koncept mut/not-mut występuje jedynie na poziomie różnej implementacji zbioru zachowań.

Mam nadzieję że teraz wyjaśniłem nieścisłość. Okazuje się bowiem że obaj wiemy jak to działa :)

komentarz 13 grudnia 2020 przez adrian17 Ekspert (344,100 p.)

2. W Pythonie jest zaimplementowana różna obsługa (czyli behawior) typów mutowalnych i niemutowalnych. Nie wynika to z "oddzielnego traktowania kategorii typów" (znów nie chodzi mi o teorię kategorii tylko mut <-> not_mut) a ze sposobu (jednego i tylko jednego) zaimplementowania zliczania referencji. Konsekwencją są niespodzianki obsługi tychże 2 rodzajów typów (oprócz argumentów domyślnych np. metody składowe wykonywane na danych mutowalnych ze zwrotem None).

To wciąż brzmi dziwnie. W jaki sposób "jedno zliczanie referencji" implementuje "różną obsługę typów mutowalnych i niemutowalnych"?

Wciąż to nie ma związku z argumentami domyślnymi (tylko z implementacją argumentów domyślnych; gdyby np JS miał podobnie zaimplementowane argumenty domyślne, to miałby analogiczne zachowanie i wciąż nie miałoby to związku z "mutowalnością"). I tym bardziej nie rozumiem, co masz na myśli przez "metody ze zwrotem None".

komentarz 13 grudnia 2020 przez mokrowski Mędrzec (155,460 p.)
Hmm.. wiesz co... możemy tak "dłubać i dłubać", stawiać przecinki, wykazywać niejasności... . Ale dla kolegi pytającego niewiele to wnosi... Ja wiem jak to działa, Ty wiesz jak to działa a zastrzeżenia można mieć do formy przekazania myśli gdzie język naturalny zawsze będzie sprawiał niespodzianki. Na szczęście jest kod i on jest ostatecznym sędzią :)
komentarz 15 grudnia 2020 przez xorbane Użytkownik (950 p.)

@mokrowski,
 Dzięki za obszerne wyjaśnienie.

Nie chciałem używać wyłuskania ponieważ parę osób mi mówiło żeby nie używać żadnych op na pointerach w c++ bo już się tak nie robi i w sumie wydaje mi się to dość sensowne, biorąc pod uwagę ilość i rodzaj błędów jakie może to wygenerować, myślałem że może jest coś lepszego o czym nie wiem

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,453 zapytań

141,262 odpowiedzi

319,088 komentarzy

61,854 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!

...