Jak lepiej zapisać...

[Rudy]

Witam.

 

Więc tak, piszę pewien program i natrafiłem na miejsce, gdzie muszę z dwóch zmiennych (np x, y należące do naturalnych, wszystkie mające jakąś wartość) stworzyć jedną (coś w rodzaju id punktu). Jak napisałem wcześniej każdy punkt posiada jakąś znaczącą wartość i nijak nie da sie zapisać wzoru ogólnego. No i mam dylemat... załóżmy, że x i y to liczby od 0 do 4. Który kod byłby lepszy (tzn szybszy, mniej pamięcio-czaso-żerny):

 

Kandydat 1:

unsigned char foo(unsigned char x, unsigned char y)
{
  switch (x)
  {
    case 0: switch (y)
    {
      case 0: return 2;
      case 1: return 5;
      case 2: return 0;
      case 3: return 10;
      case 4: return 3;
    }
    case 1: switch (y)
    {
      case 0: return 7;
      case 1: return 24;
...
     }
  }
}

 

Kandydat 2:

const unsigned char foo[5][5] = {{2,5,0,10,3},{7,24, ... }};

 

Na pierwszy rzut oka 2 jest lepsza, no ale pomyślmy. Tablica zajmuje obecnie 25B. Póki jest mała wszystko jest ok. A co jak o zwracanej wartości będzie decydowały 3 liczby i 7/9 liczb będzie zwracała wartość 0xFF czyli "nieinteresującą" nas? Nie wiem gdzie przesiaduje informacja o definicji funkcji ale wiem że taka tablica zabierze mi 125B w pamięci RAMu. No więc co lepsze? Czy robić po prostu wielgachne tablice, czy może funkcje... a może makra z parametrem?

[CuB3]

Jeżeli dodasz break'i to funkcja będzie lepsza bo po każdym nietrafnym zapytaniu pomija kolejne zbiory, tablice musiałbyś przeszukiwać całą żeby dostać wartość... Chyba, że Cię źle zrozumiałem :P

[Rudy]

Eee... znaczy się chodzi o coś takiego :D

 

 

Mamy sobie takie liczby posegregowane wg x i y (N to liczby, które nigdy nie będą użyte (jeśli użytkownik będzie postępował zgodnie z podanymi instrukcjami (czyli prawie nigdy :D ) ). W jedynce to wiadomo, tablica najlepsza, ale co z dwójką? Też tablica? lepiej chyba funkcja. Ale wtedy mieszamy sposoby w jednym projekcie. Więc co lepiej?

 

Dokładniej: Dostaję dwie liczby a mam wypisać jedną, takie jakby id tego zestawienia liczb. Niektóre nie będą nigdy wpisane.

[Will]

Szybsza będzie druga wersja. Poza tym zrób jednowymiarową tablice a nie jakieś wielowymiarowe cuda. Całość zależy też w sumie jak będziesz to przetwarzał i jak często będziesz się "bawił" z tymi danymi.

[CuB3]

A nie lepiej jeszcze łatwiej? Obiekt z tymi dwoma zmiennymi i tablica z obiektami?

[Rudy]

Szybsza będzie druga wersja. Poza tym zrób jednowymiarową tablice a nie jakieś wielowymiarowe cuda. Całość zależy też w sumie jak będziesz to przetwarzał i jak często będziesz się "bawił" z tymi danymi.

Właśnie chodzi o wielowymiarowe cuda, bo wartość zwracana zależy od 2 liczb i w górę. Tzn foo(0,2) != foo(0,5) (albo foo[0][2] != foo[0][5]). Co do przetwarzania - jedna seria w całym działaniu, około 30 razy.

 

 

A nie lepiej jeszcze łatwiej? Obiekt z tymi dwoma zmiennymi i tablica z obiektami?

Ehh... chyba nie rozumiesz... jeszcze inaczej.

if (a == 0 && b == 0) return 2;

if (a == 0 && b == 1) return 5;

if (a == 0 && b == 2) return 0;

itd, itd. aż wykorzysta się wszystkie możliwości. Chodzi o to, że z dwóch podanych liczb funkcja/tablica zwraca id, który identyfikuje te zestawienie liczb. Id nie są po kolei, niektóre sie powtarzają, niektóre nigdy nie będą użyte. Tylko tyle.

 

Jeszcze inaczej:

a ¤ b = c, gdzie a i b należy do {0,1,2,3,4}, a c to jakaś liczba (czyli te id).

[Will]

Właśnie chodzi o wielowymiarowe cuda, bo wartość zwracana zależy od 2 liczb i w górę. Tzn 0 i 2 != 0 i 5. Co do przetwarzania - jedna seria w całym działaniu, około 30 razy.

Dalej nie widzę sensu robienia wielowymiarowej tablicy...

 

Ehh... chyba nie rozumiesz... jeszcze inaczej.

if (a == 0 && b == 0) return 2;

if (a == 0 && b == 1) return 5;

if (a == 0 && b == 2) return 0;

itd, itd. aż wykorzysta się wszystkie możliwości.

 

If'y są bardzooo wolneeee więc jeśli rzeczywiście tylko raz całość będzie użyta i jeśli dane znane są znane w czasie kompilacji to zrobić makro, które wyliczy co trzeba. Jak danych nie da się wyliczyć i trzeba wklepać ręcznie to nie ma sensu marnować pamięci/instrukcji.

[Rudy]

If'y są wolne...

Dlatego ich nie użyję, szukałem tylko sposobu, jak najprościej przedstawić mój problem :)

 

Makro byłoby najszybsze, lecz chyba tutaj nie dałoby rady, chodzi właśnie o te dwie liczby...

 

Spróbuję jeszcze inaczej :) .

 

Wyobraź sobie kartkę w kratkę. Na tej kartce, w kratkach napisane są chaotycznie rozłożone liczby. Jak coś takiego odwzorowałbyś na komputerze?

 

Parę zmiennych pomocniczych (wielkość kartki, wielkość jednej kratki, żeby odmalować samą kartkę)... no i właśnie, co z tymi liczbami. Jakbyś je namalował wiedząc, że nie możesz wymienić tylko tych liczb na kartce (załóżmy, że użytkownik może zapytać się, co znajduje się w tej kratce, a komputer ma odpowiedzieć (jeśli nie ma tam liczby) że kratka jest pusta).

 

Odp: musisz mieć te liczby (i puste kratki) zapisane w tablicy, która pobiera do indeksów x i y. W momencie zapytania zwraca liczbę znajdującą się pod tymi indeksami, i jeśli jest to liczba nieużywana (jak np 0xFF) to pisze, że jest pusta kratka. Chyba, że masz lepszy pomysł.

[Will]

Wszystko zależy od tego czym wypełniona jest kartka. Tzn dane są losowe nie można ich wyliczyć: -trzeba wyklepać jednowymiarową tablicę i po problemie lub dodać wczytanie danych do tablicy z pliku. Jeśli wielkość kartki jest dynamiczna można użyć pamięci z alokatora(jeśli tablica jest używana raz a potem jest nie potrzebna) lub jeśli jest potrzebna podczas dłuższego czasu stworzyć tablicę z pamięci z zwykłym new.

[Rudy]

Kartka jest stała, dane to liczby mieszczące sie w jednym bajcie, są losowe.

 

Ciągle nie widzę tej jednowymiarowej tablicy, jak by ona miała działać. Mógłbyś mi to pokazać na przykładzie? Weźmy tą pierwszą tablicę z obrazka powyżej. N to pusta kratka. U mnie wyglądałoby to tak:

array[4][4] = {{5, 8, 0xFF, 11} , {10, 4, 2, 0xFF} , {0xFF, 0, 6, 9} , {3, 7, 0xFF, 1}};

i wtedy x kratki byłoby pierwszym indeksem, y kratki drugim, a podczas wyświetlania (pytania użytkownika) 0xFF traktowałby jako pustą.

 

Jeśli chcesz, możesz powiedzieć, że Ci się nie chce, trochę odeszliśmy od tematu, a faktyczny efekt to tylko zwiększenie mojej wiedzy (kosztem twojego czasu).

[Will]

array[16] = {{5, 8, 0xFF, 11,10, 4, 2, 0xFF,0xFF, 0, 6, 9,3, 7, 0xFF, 1};

+zmienna np: elemSize:int=4;

teraz: getElement(x:int,y:int)

{

return array[y*elemSize+x];

}

[Rudy]

Aha :D W sumie można i tak, chociaż rozmieszczenie liczb i szybkość będzie w obu przypadkach taka sama (albo za mało wiem o C++)

 

Zrobię to w ten sposób. Skorzystam z Twojej pomocy i zamknę to do jednego indeksu. W przypadku, gdy będzie więcej wartości niż "pustych kratek" skorzystam z tablicy. A jeśli odwrotnie - funkcja ze switch.

 

Wielkie dzięki za pomoc, już chyba któryś raz z kolei pomagasz mi w C++. :)

[baca]

If'y są bardzooo

wolneeee

Mylisz się, jak umie się je używać to wcale nie są wolne.

[Will]

Mylisz się, jak umie się je używać to wcale nie są wolne.

Uznam, że tego nie napisałeś bo nie chcę mi się znowu kłócić o tak podstawową sprawę. Poczytaj trochę.

[Kofel]

Weź Ty kiedyś na przykładzie opisz, każdy by chciał się dowiedzieć...

[Will]

Mogę napisać ale to będzie raczej mało rzetelne jako, że nie mam takiej wiedzy żeby to dobrze opisać ale jeśli chcesz..

 

Dajmy na to, że masz jakąś instrukcje dla procka. Ona cała nie może się wykonać ot tak. Przypuśćmy, że na wykonanie danej instrukcji są 4 etapy:

1. Fetching bierzemy instrukcje z pamięci

2. Decoding Dekodujemy(czy raczej procek) instrukcje żeby wiedzieć co to jest

3. Execute wykonujemy instrukcje

4. Store zapisujemy wynik instrukcji do rejestru.

 

Teraz niech każdy etap potrzebuje jeden "clock cycle" aby się wykonać. Teraz w przypadku przetwarzania instrukcji "pipelined" wykonywanie kolejnych instrukcji wygląda mniej więcej tak(bardzo mniej):

 

http://imageshack.us/photo/my-images/121/pipelined.jpg/

 

Pipelined oznacza krótko pisząc tyle, że przetwarzanie kolejnych instrukcji jest podzielone na małe etapy tak, że jak instrukcja 1 przechodzi do 2 etapu procek może wrzucić do pierwszego etapu następną co jest oczywiście znacznie szybsze niż wersja procka nonpipelined, która wygląda tak:

 

http://imageshack.us/photo/my-images/64/nonpipelined.jpg/

 

Jak widać pipelined jest znacznie szybszy. Całość można porównać do budowy samochodu w przypadku pipelined budowa auta jest podzielona na wiele oddzielnych etapów, które mogą się wykonywać niezależnie od siebie i kiedy pierwsze auto otrzyma silnik i idzie do montownia drzwi na jego miejsce do etapu montowania silnika daje się następny pojazd. W przypadku nonpipelined budowa kolejnego auta może się rozpocząć dopiero kiedy poprzednik jest w 100% ukończony.

 

Instrukcje warunkowe nie są zbyt przyjazne dla tego typu rozwiązania. Kiedy natrafimy na jakieś if'a wykonywanie instrukcji na pierwszy rzut oka musi się zatrzymać dopóki cała instrukcja nie zostanie wykonana aby zdecydować gdzie "skoczyć" ale to jest nie bardzo do przyjęcia bo "montażownia" musi działać cały czas(jeśli jakieś maszyny z konkretnych etapów "stoją" to strata energii i czasu). Dlatego procek zgaduje jaki będzie wynik instrukcji warunkowej, bazuje tu na poprzednich wyborach dotyczących tego warunku(dzięki jakiemuś tam cache dla branching'u). Jeśli procek strzeli dobrze wszystko leci dalej jak trzeba. Jednak jeśli nie trafi to pipeline jest czyszczony(instrukcje, które się wykonały z źle wybranego bloku kodu) czyli jeśli pipeline podzielony jest na 20 etapów cofamy się o 20 instrukcji w tył co oczywiście sporo kosztuje.

 

To jest bardzo uproszczone tłumaczenie i całość jest znacznie.. znacznie.. bardziej skomplikowana.

[Rudy]

Hmmm... tak gruntownej analizy o wyższości switch nad if'em nie robiłem, rozumuję to trochę inaczej. (bardziej łopatologicznie). Mamy takie dwa kawałki kodu:

if (zmienna == 5) akcja1();
else if (zmienna == 7) akcja2();
else if (zmienna == 13) akcja3();
else if (zmienna == 19) akcja4();
else if (zmienna == 23) akcja5();
else akcja6();

switch (zmienna)
{
  case 5: akcja1(); break;
  case 7: akcja2(); break;
  case 13: akcja3(); break;
  case 19: akcja4(); break;
  case 23: akcja5(); break;
  default: akcja6();
}

 

Spróbujmy przeanalizować, na jakie odpowiedzi mielibyśmy odpowiedzieć, jeśli bylibyśmy procesorem*:

Pierwszy kod:

Czy zmienna jest równa 5? (tak - wykonujemy funkcję akcja1)

Jeśli nie, to czy zmienna jest równa 7? (tak - wykonujemy funkcję akcja2)

Jeśli nie, to czy zmienna jest równa 13? (tak - wykonujemy funkcję akcja3)

Jeśli nie, to czy zmienna jest równa 19? (tak - wykonujemy funkcję akcja4)

Jeśli nie, to czy zmienna jest równa 23? (tak - wykonujemy funkcję akcja5)

Jeśli nie, wykonujemy funkcję akcja6.

Drugi kod:

Która z wartości pasuje do zmienna: 5, 7, 13, 19, 23, czy żadna z powyższych? (jeśli któraś z odpowiedzi pasuje, przenosimy się do jej "znacznika" i wykonujemy operację do końca klamry, lub napotkania break).

 

I dochodzimy do setna rozważań: gdzie jest mniej pytań? Już na pierwszy rzut oka widać, że w drugim, jest tylko jedno pytanie w przeciwieństwie do pierwszego sposobu, gdzie pytań jest aż pięć. Jednakże, ten rodzaj pytania wymusza pewne zasady, które można również zauważyć w C++:

- możemy tylko przyrównywać liczby, nie sprawdzimy zakresu liczb (nierówności), czy bardziej skomplikowanych działań.

- wartość podana w case musi być stała, to oznacza, że nie możemy wpisać tam niestałej zmiennej.

 

Przez to w niektórych przypadkach nie możemy użyć switch (można oczywiście wymienić wszystkie liczby z zakresu, o ile nie będzie on zbyt duży) i musimy posiłkować się ciągiem if ... else.

 

 

* - ten sposób rozumowania nijak się ma do sposobu Willa, który podał, jak faktycznie działa procesor. Jednak na tym przyładzie można zastosować takie porównanie.

[Will]

Teoretycznie jako, że switch akceptuje tylko stałe dla danych case'ów w przypadku ich dużej liczby switch powinien być znacznie szybszy niż if/else if. Jak dobrze pamiętam kompilator tworzy sobie dla switch'a look up table tak, że choćbyś miał 1000 case'ów będzie wymagane tylko jedno porównanie aby odnaleźć właściwie. Problem jest taki, że switch nie działa dla złożonych warunków tylko dla prostych typów liczbowych. Dla bardziej złożonych i przy małej ilość if/else if np 4-5 można ustawić całość względem częstości występowania danego targetu i też będzie śmigać. Największy problem jest taki, że to co się stanie zależy od wielu elementów np: kompilatora/sprzętu/ustawień optymalizacji i wielu innych. W przypadku kodu, który wykonuje się rzadko tego typu sprawami w sumie nie ma co się za bardzo przejmować. Znacznie więcej czasu stracisz na alokowaniu pamięci ze sterty niż na takich pierdołach gdzie aby wykonać malloc mamy najpierw context switch z user mode do kernel mode a potem po wykonaniu request'a znowu context switch co jest bardzo kosztowne. Drogie są też porównania string'ów, nie pamiętam już jakie to były produkcje ale zdarzało się, że string'i były głównym bottleneck'iem całego projektu.