Grupowanie elementów tablicy - wydajność algorytmu.

[fajfi]

Cześć
Mam posortowaną tablicę, np. 1000000 elementową. Znajdują się w niej liczby całkowite od 1 do np. 100.
I teraz chcę policzyć ile razy w tablicy występuje 0, 1, 2 itd. aż do 100.
Wymyśliłem pewien algorytm (załączony w pliku) polegający na tym:
Szukam 0, jak znajdę to wycinam znalezioną komórkę z 0 i szukam znowu, tak długo, dopóki 0 będzie znajdywane i odczytuję ile razy pętla została wykonana,
potem to samo robię z 1, 2 itd.
W zasadzie algorytm działa, ale jest niesamowicie powolny: czas działania to ponad 26 minut.
Czy istnieje bardziej wydajny sposób?
Nie mogłem znaleźć funkcji, która znajdywałaby od razu wszystkie elementy o zadanej wartości.
Pozdrawiam
Fajfi

[bartus]

Witaj,

a nie szybciej byloby i byc moze szybciej robic to rownolegle ? to znaczy raz, zeby tablice rozdzielic na pare pod-tablic i dla kazdej z tych podtablic wykonywac algorytm osobno? Zastanawiam sie jeszcze na ile wydajne jest Twoje wycinanie elementow tablicy. Moznaby tez zrobic cos takiego, ze sprawdzasz elementy wszystkie naraz. To jest Tworzysz tablice 100 elementowa - jezeli dana liczba wystepuje to element o indeske [dana_liczba] zwiekszasz o jedeni potem zajmujesz sie tylko ta tablica 100 elementowa.

[mariush]

A wbudowana funkcja sobie nie radzi z tym?

rozklad.png (4.98 KiB) Przejrzano 9325 razy

+ vi z zastosowaniem:

rozklad.vi

(8.85 KiB) Pobrany 417 razy

[jogurt_owocowy]

LV ma kilka gotowych funkcji obliczających histogram np. General Histogram.
Jeśli wolisz to zrobić samemu, to chociażby zestaw klocków Equal?, Boolean To (0,1) i Add Array Elements połączonych jeden za drugim, powinien być dużo bardziej wydajny.

[smiga]

Poniżej 2 podejścia - równoległe i kolejno (w pętli najniżej ... tam powinna być liczba 101, a nie 100 (moja pomyłka) w ilości iteracji pętli, bo inaczej zapominamy o sprawdzeniu ile razy wystąpi liczba 100)
W równoległych masz 2 opcje: z zatrzymywaniem pętli żeby nie sprawdzała wszystkich elementów tablicy lub bez ... poeksperymentuj, która opcja będzie najszybsza.
Na moim komputerze cały program widoczny na rysunku (z generacją liczb włącznie) wykonuje się ok 2s

[bartus]

Jezeli chodzi o wydajnosc, to wydaje mi sie ze dla petli for bardziej wydajne jest podpinanie "czegos" do wejscia N, a nie poleganie na auto-indeksacji, ale to szczegol.
Pozatym naszlo mnie czemu tablica jest sortowana i nie jest to potem wykorzystane -> vide mozna by jechac po tablicy w poszukiwaniu kolejnego elementu startujac od indeksu elementu poprzedzajacego, ew nie - sortowac bo to tez "troche zajmuje".

[fajfi]

Bardzo wszystkim dziękuję za błyskawiczne odpowiedzi.
Niemal tak szybkie jak wasze algorytmy
Pozwoliłem sobie porównać zaprezentowane metody dla tablicy o rozmiarze 10 mln.
Oto wyniki:
Najszybszy okazał się histogram zaproponowany przez Jogurta owocowego - pogrupowanie zajęło mu 0,314 s.
Drugie miejsce zajęła metoda Mariusha - 1,317 s.
Trzecie - metoda Smigi - 31,675 s.
Czwarte - druga metoda Jogurta - 36,779 s.
Zapewne mój prymitywny i zasobożerny algorytm liczyłby to do jutra...
Jak to dobrze poradzić się czasami kogoś mądrzejszego...
Mam jednak jedną uwagę do histogramu: otóż jeżeli nie wiem dokładnie ile różnych wartości zawiera moja tablica, to bywa, że, niektóre przedziały w histogramie okazują się być puste, co widać na załączonym obrazku. Jak podałem zbyt mało przedziałów, to bywało, że sumował niektóre z nich.
Czy ktoś wie jak temu zaradzić?
Pozdrawiam
Fajfi

[jogurt_owocowy]

Czy ktoś wie jak temu zaradzić?

chcę policzyć ile razy w tablicy występuje 0, 1, 2 itd. aż do 100.

Wtedy ustawiasz argumenty funkcji General Histogram następująco:

max: 100
min: 0
# bins: 101 (bo tyle jest różnych wartości, które chcesz zliczać).