Kilka pytań o optymalizację

0

1)
czy jest różnica wydajnościowa między


for(int i =0; i < 1000; i++){
     //jakieś operacje
}

a


int i;
for( i = 0; i < 1000; i++){
     //jakieś operacje
}

Kiedyś na pewnym teście otrzymałem pierwszy kod z pytaniem "jak tą pętlę zoptymalizować", byłem w szoku bo nie miałem pojęcia.

2)
mam powiedzmy 2000 obiektów przetrzymywanych w vectorze vectorów (taka sobie macierz/ tablica dwuwymiarowa), jak zwał tak zwał, i w programie wykonuje się pętla while (non stop), w której są wyoknywane jakieś operacje na tych obiektach i teraz które rozwiązanie jest lepsze:
a) przetrzymywać pozycję x i y każdego z elementów (czyli zajmowanie pamięci)
b) czy może w kazdej petli while wyliczac pozycje na podstawie mnożenia dwoch liczb (mam taką możliwość)

chodzi o to co lepsze a (zajmowanie pamięci) , b (mnożenie dla każdego obiektu w każdej pętli by szukaną wartość otrzymać)

Dzięki za wszelkie sugestie.

0

te dwa kody roznia sie tylko tym ze w przypadku drugiego kodu zmienna i jest widoczna poza pętlą. w większości przypadków optymalizacje kompilatora zoptymalizują ten kod do najlepszej postaci. w przypadku wyłączonych optymalizacji, jeśli zmienna i nie jest nigdzie w kodzie używana można zrobić np tak:

int i=1000;
while (i--)
{
//jakies operacje
}

teoretycznie wpływ na szybkość ma też zapis:
i++ <==> zapamietuje wartosc i do zmiennej tymczasowej, "wrzuca" ja w wyrazenie. po zakonczeniu tej operacji inkrementuje i
++i <==> inkrementuje i, zwraca i
w przypadku takich pętli kompilator na pewno to zoptymalizuje. jeśli w jakiś operacjach używasz przykładowo:
vector<int> v;
... // tutaj mu ustawiasz rozmiar na 1000, wrzucasz jakeis elementy itd
to pętle można zapisać tak:

for (vector<int>::iterator i = v.begin(); i!=v.end(); ++i)
  {
   // jakies operacje
  }

i w tym wypadku mozesz odczuc znaczaca roznice na wykonaniu.

w przypadku tablicy np takiej którą używasz w pętli można zrobić tak:

int tab[1000];
//tutaj jakies zainicjowanie elementów
int* end = tab+1000;
for (int* i = tab; i!=end; ++i)
  {
   // jakies operacje
  }

zauważ jak ten kod wygląda podobnie do kodu z vector<int>

  1. nie wiem o co chodzi o_O
0

Kiedyś na pewnym teście otrzymałem pierwszy kod z pytaniem "jak tą pętlę zoptymalizować", byłem w szoku bo nie miałem pojęcia.

Współczuję nauczyciela/wykładowcy :( Te dwa kody być może różniły się pod względem wydajności - jakieś 20 lat temu. Teraz nie ma żadnej różnicy.

Podobnie mitem jest że for(;;++i) jest szybsze od for(;;i++) - różnica istnieje tylko w teorii, ale skoro mamy zasadę as-if to każdy kompilator to przetworzy tak samo, nawet przy wyłączonej optymalizacji.

2.

a) przetrzymywać pozycję x i y każdego z elementów (czyli zajmowanie pamięci)
b) czy może w kazdej petli while wyliczac pozycje na podstawie mnożenia dwoch liczb (mam taką możliwość)

Znaczy że chcesz zrobić wektor wektorów i tylko w niektórych miejscach znajdują się faktyczne obiekty? Lepiej byłoby przetrzymywać je w pojedynczym wektorze który zawierałby dane w rodzaju
struct s { int pozycjaX; int pozycjaY; obiekt faktycznyObiekt; } albo użyć jakiejś http://en.wikipedia.org/wiki/Sparse_array

chodzi o to co lepsze a (zajmowanie pamięci) , b (mnożenie dla każdego obiektu w każdej pętli by szukaną wartość otrzymać)

Jako że nie rozumiem do końca poprzedniego pytania (zgadywałem) to odpowiem na to oddzielnie - wybierz b.

0

1) dzięki :)
2) chodzi o to że masz np obiekt klasy
class Kwadrat{
public:
int x,y,w,h;
}
masz macierz takich obiektów
i teraz wykonujesz pętlę while, ktora sie wykonuje caly czas dzialania programu, do momentu wyjscia. W kazdym wywolaniu petli potrzebujesz zrobic cos na polu x tego obiektu.
I teraz pytanie:
a) czy w klasie powinno być tak jak teraz przetrzymywane x dla każdego z tych 2000 obiektów czy
b) nie trzymać x i y (czyli nie zajmowac pamięci) tylko przelatując przez macierz dwoma pętlami for wyliczać np

x = i*kwadrat.w;
y = j*kwadrat.h

czyli pamięć jest niezajęta do przetrzymywania x i y ale za to zeby te pola wyliczyc trzeba wykonac w kazdej petli mnozenie dla kazdego obiektu (czyli wydajnosc za pewne spada)

0

dla 2000 obiektów to nie myśl o czymś takim jak pamięć. chyba że postanowisz w środku klasy zrobić coś w stylu char pole[1000000].

lepiej mieć w tym wyopadku pamięciożerny szybki kod (jeśli pamięciożernością można nazwać zabranie 1MB ram)

0

1 MB? 2000 (obiektów) x 2 (pola) * 4 (sizeof int) = 16 kb. To się nawet spokojnie zmieści w L2 Cache. W takim razie prawdopodobnie wersja 'pamięciożerna' będzie szybsza.
Z drugiej strony mnożenie jest szybkie a ładowanie danych, nawet z cache, wolne... Zrób benchmark, sam jestem ciekawy ;)

Btw. skoro klasa nazywa się kwadrat to wysokość i szerokość każdego kwadratu jest równa? A może wszystkie kwadraty mają taką samą wysokość i szerokość? :P

1

przed chwilą zrobiłem mały eksperyment:

napisałem taki kod:


#include <stdio.h>

void bla()
{
    int i = 0;
    for( i = 0 ;i <  1000 ;i++ )
    {
        puts("Funkcja - i poza petla \n");
    }
}

void ola()
{
    for( int  i = 0 ;i <  1000 ;i++ )
    {
        puts("Funkcja - w  petli \n");
    }
}

int main()
{
    ola();
    bla();
}

po czym skompilowałem w Visual Studio w trybie Release.

Odpaliłem exeka w IDA i oto co dostałem:

int __cdecl main(int argc, const char **argv, const char **envp)
{
  signed int v3; // [email protected]
  signed int v4; // [email protected]

  v3 = 1000;
  do
  {
    _puts("Funkcja - w  petli \n");
    --v3;
  }
  while ( v3 );
  v4 = 1000;
  do
  {
    _puts("Funkcja - i poza petla \n");
    --v4;
  }
  while ( v4 );
  return 0;
}
0

przed chwilą zrobiłem mały eksperyment:

napisałem taki kod:


#include <stdio.h>

void bla()
{
    int i = 0;
    for( i = 0 ;i <  1000 ;i++ )
    {
        puts("Funkcja - i poza petla \n");
    }
}

void ola()
{
    for( int  i = 0 ;i <  1000 ;i++ )
    {
        puts("Funkcja - w  petli \n");
    }
}

int main()
{
    ola();
    bla();
}

po czym skompilowałem w Visual Studio w trybie Release.

Odpaliłem exeka w IDA i oto co dostałem:

int __cdecl main(int argc, const char **argv, const char **envp)
{
  signed int v3; // [email protected]
  signed int v4; // [email protected]

  v3 = 1000;
  do
  {
    _puts("Funkcja - w  petli \n");
    --v3;
  }
  while ( v3 );
  v4 = 1000;
  do
  {
    _puts("Funkcja - i poza petla \n");
    --v4;
  }
  while ( v4 );
  return 0;
}
0

w tym przykładzie dokładnie można zobaczyć na jakim poziomie są współczesne kompilatory.

0

Pętlarz a jesteś pewien że chodzi o taki przykład jak w pierwszym poście, a nie przypadkiem:

for (int i=0; i < lista.getKoniecListy(); i++)
{...}

i nie chodziło żeby o to żeby za każdym razem nie pobierać getKoniecListy() tylko zapamiętać tą zwracaną wartość przed pętlą?

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0