Jak działa for(int i=0;i<n;i++) ++pom[tab[i]-Min] ?

Question

Witam :) Jeśli miałbyś ochotę, prosiłbym o odpowiedź, a na pewno takie zapytanie Cię porządnie rozwinie :)

Postanowiłem, że pouczę się kolejnych rodzajów sortowań. Tym razem padło na sortowanie kubełkowe(liczby wkłada się do kubełków, o odpowiadającym im wartościom)

 

Tutaj znajduje się kod:

http://wklej.org/id/1858809/

 

 

Mam drobny problem ze zrozumieniem dwóch linii w tym kodzie. A dokładnie lini 20 i 23

 

Czyli:for(int i=0;i<n;i++) ++pom[tab[i]-Min];

 
int k=0; for(int i=0;i<Max-Min+1;i++)while(pom[i]--)tab[k++]=i + Min;

 
Pytanie:

 
Linia20:
W jaki sposób ++pom[tab[i]-Min]; działa ? Tzn. domyślam się, że on zlicza ilość wystąpień danej liczby,
Tylko jak w zasadzie on działa ? Zrobiłem wypisanie tego na co wskazuje ta pomocnicza tablica i wartość wynosi 1. I to jest zrozumiałe, ale jak to się dzieje, że odejmując w pomocnicznej tablicy:  tab[i]-Min, dostaje się ilość wystąpień  danego wyrażenia?

 
Linia 23:

 
Zapis: tab[k++]=i+Min jest zrozumiałe, to jest po prostu zapis kolejnych liczb k do tablicy . Jednak co oznacza zapis pom[i]-- ? Oznacza to, że do czasu, gdy pętla nie będzie miała czytać z pom[i] ? I druga kwestia, jak to jest możliwe, że w  linii 23         i          rośnie niespotykanie szybko i osiąga wartości takie jak przy odjęciu tab[i]-Min, mimo iż w pętli for jest inkrementacja(zwiekszenie o jedno) ?

Pozdrawiam :)

Answer 1

Co do 20. linii:

1. Wcześniej zadeklarowałeś tablicę, która może pomieścić wszystkie całkowite wartości z przedziału <min, max>.
2. Teraz zliczasz ilość wystąpień każdej z tych wartości:
   1. Wykonujesz iterację tyle razy, ile elementów ma Twoja tablica wejściowa.
   2. W każdej iteracji inkrementujesz ilość wystąpień danej liczby z tablicy wejściowej:
      1. W tym celu zwiększasz o jeden wartość elementu tablicy pomocniczej o indeksie równym wartości z odpowiedniej komórki tablicy wejściowej.
      2. Odejmujesz wartość minimalną, żeby zniwelować ewentualne ujemne indeksy (odjęcie ujemnej wartości powoduje jej dodanie, więc dla minimalnej wartości z tablicy wejściowej, indeks będzie równy zero).
      3. Gdybyś miał do posorotwania tylko liczby nieujemne, to nie musiałbyś odejmować (i później dodawać) wartości minimalnej. *

Co do linii 23.:

Zapis while(pom[i]--) oznacza "wykonaj, dopóki wartość tablicy pom[i] jest różna od zera, a po sprawdzeniu prawdziwości warunku dekrementuj tę wartość". Czyli jeśli będziesz miał  pom[3] = 2, to pętla wykona się dwa razy:

1. pom[3] = 2; Czy pom[3] != 0? Tak, więc zmniejszam o 1 pom[3] i wykonuję ciało pętli.
2. pom[3] = 2 - 1 = 1; Czy pom[3] != 0? Tak, więc zmniejszam o 1 pom[3] i wykonuję ciało pętli.
3. pom[3] = 1 - 1 = 0; Czy pom[3] != 0? Nie, więc zmniejszam o 1 pom[3] i nie wykonuję ciała pętli.

I druga kwestia, jak to jest możliwe, że w  linii 23         i          rośnie niespotykanie szybko (...)

Tej cześci pytania niestety nie rozumiem. Licznik i jest w każdym obiegu inkrementowany o 1, nie ma tu żadnej magii.

EDIT:

* - po krótkim namyśle, byłoby to poprawne rozwiązanie tylko pod warunkiem tworzenia tablicy pomocniczej o ilości elementów równej maksymalnej wartości tablicy wejściowej (mogącej pomieścić wartości z przedziału <0, max>), a więc nieefektywne pamięciowo.

Comments

Świetnie wytłumaczone!

Wszystko już rozumiem, za wyjątkiem tego i. Wpisałem jego wypisywanie do konsoli i takie coś ujrzałem:

http://zapodaj.net/845ce19572f83.png.html

Jak to rozumieć ?

Pozdrawiam :)

---

Przeczytaj jeszcze raz mój post, bo edytowałem fragment w międzyczasie. ;)

A co do tego, co sobie wypisałeś: czy wypisywanie zrealizowałeś w bloku while czy w bloku for? Pamiętaj, że blok while wykonuje się tylko i wyłącznie dla zawartości różnej od zera.

---

W bloku while, gdy zrobiłem to w bloku for, takie coś mi wywaliło:

http://zapodaj.net/73f03a0fb7f5a.png.html

Jak to rozumieć ?:D

PS. Naprawdę dziękuje, że poświęcasz takiemu amatorowi jak ja czas na tłumaczenie :)

---

Rozumieć to tak, jak jest wypisane. ;)

Spójrz, gdy wypisywanie zrealizujesz w bloku for, możesz zauważyć, że i zmienia się co jeden. A gdy wypisywanie umieścisz w bloku while, wtedy zobaczysz tylko te wartości i, dla których tab[i] != 0. Więc wszystko jest w porządeczku, Twój kompilator działa. ;)

PS. Naprawdę dziękuje, że poświęcasz takiemu amatorowi jak ja czas na tłumaczenie :)

Proszę bardzo, na zdrowie. :) Nikt nie rodzi się zawodowcem. ;P

Pozdrawiam. :)

---

Aaa, teraz już rozumiem ! Naprawdę wzorowe tłumaczenie :)

Mam tylko ostatnie pytanie, dotyczące czasu wykonania :)

Czy możliwe jest, że to sortowanie przypseudolosowaniu jest kilkaset razy szybsze od

quicksorta ?

Zrobiłem, test dla 100 milionów elementów i oto wyniki:

http://zapodaj.net/04077f289b10d.jpg.html

Czy to jest w ogóle możliwe, czy coś źle się dzieje ?:)

Pozdrawiam :)

---

Tutaj masz artykuł, mówiący o czasie wykonania quicksort i kubełkowego.

Ogólnie, wszystko zależy od danych wejściowych. Ale niemożliwe jest, żeby różnica była aż tak znaczna - coś tam musiałeś skopać w tym teście. :P

Pamiętaj, żeby w porównaniu przekazywać do funkcji zestaw identycznych danych, żeby test był wiarygodny.

---

Rano posprawdzam na spokojnie :)

Tymczasem wielkie dzięki za odpowiedź :) Najlepsza i dziękuje leci do Ciebie :)

Pozdrawiam i miłej nocy :)

---

Ja również dziękuję. :)

Dobrej nocy i pomyślnej nauki!

Answer 2

jakoś dziwnie pytanie zadałeś, nie za bardzo rozumiem o co ci chodzi. Ale:

++zmienna dodaje 1 do zmiennej (++zmienna dodaje 1 przed użyciem zmiennej, zmienna++ dodaje 1 po użyciu zmiennej)

zmienna-- odejmuje 1 od zmiennej (analogicznie jak wyżej przed i po --zmienna i zmienna--)

Dodatkowo jeśli nie mamy klamry za for to pętla while wykona się tyle razy co pętla for.

Zapis taki mógłby wyglądać tak:

int k=0;
for(int i=0;i<Max-Min+1;i++)
   {
   while(pom[i]--)
      {
      tab[k++]=i + Min;
      }
   }

 

EDIT:

Tu masz link odnośnie różnicy (++i, i++)

http://blog.grabowski.ostrowwlkp.pl/programowanie-2/roznica-miedzy-i-a-i

 

Comments

Dziękuje za odpowiedź ! :)

Chodzi o to, że tablica[i] przechowuje zmienne pseudolosowe i które są duże, a min przechowuje wartość najmniejszą. I jeśli odejmiemy te wartości, to powstają wartości, które przekraczają zakres zarezerwowanej tablicy.

Spójrz na to:

Stworzyłem tablicę 10-elementową, i wylosowałem pseudolosowo wartości od 0 do 1000000 i odejmując wartosc np. 64567457 od minimalnej, czyli np. 10, nigdy ta liczba nie będzie od 0 do 9, a jest w tablicy pom[tab[i]-Min]

http://zapodaj.net/fe5d726ecb83b.png.html

Więc jak to jest możliwe ?:)

Pozdrawiam :)