Diskuze: Urychleni algoritmu.
V předchozím kvízu, Online test znalostí C++, jsme si ověřili nabyté zkušenosti z kurzu.
Člen
Zobrazeno 15 zpráv z 15.
V předchozím kvízu, Online test znalostí C++, jsme si ověřili nabyté zkušenosti z kurzu.
Zrejme to je pomale prave tym triedenim kedze tam mas v podstate 2x for po
100 000 teda dokopy 10 000 000 000. Musis ten sort urobit nejako inak a
najlepsie pouzit Vector namiesto pola. K vectoru mas uz aj rozne sort funkcie
nemusis vymyslat vlastne.
(ale to by nemalo trvat hodiny to sa mi nezda)
Skus pozret tu prave som to zacal studovat.
http://www.dreamincode.net/…or-tutorial/
neni neco takeho i proc C? ne primo c++?
btw. mas pravdu, netrva to hodiny, ale spis dny
Nemam moznost to otestovat, ale ja bych to resil takto :
int poleCisel[n];
int vysledek[rozdilMinMax];
// mezitim naplnis "poleCisel"
int i;
for(i = 0; i < n; i++){
vysledek[poleCisel[i] + Min]++;
}
// sem pridat vypis pole vysledku, pokud je vyssi nez nulated me napadlo.: nebylo by lepsi to pole nejdriv setridit podle velikosti a potom to postupne projet?
Mensi chybicka, ma tam byt :
vysledek[poleCisel[i] - Min]++;
Řešil bych to nějakým slovníkem.
Key = nějaké číslo
Value = počet výskytů
Nevím jak se ta konstrukce jmenuje v c++.
Kdybys věděl maximální počet čísla, které by se vešlo do dejme tomu 10k, tak bys mohl ještě udělat pole o takové velikosti a přidávat na takový index to číslo. Ale to už závisí na detailech.
Myslim ze to ma vyznam jen pokud se chces zbavit tech MIN a MAX nebo pokud pouzijes ten muj priklad a mas takovy rozsah ze se ti nevejde do pameti, jinak nevidim duvod to seradit
Tak moc jsem tento thread nezkoumal, slyšel jsem zmínku o C++ tak jsem poradil k němu, rozdíl je ten, že nebudeš alokovat u pole 232 kombinací, ale budeš je postupně alokovat. Když se ti budou střídat 2 čísla tak využiješ pár bytu, zatím co kdybys použil pole, tak ty asi tolik, že se ti to nevejde do paměti.
Nakolik ti to pomůže nevím, ale zrychlit se to určitě dá.
Jedná se o upravenou variantu heapsortu, která je schopná rozpoznat sekvence
stejných hodnot.
Vstup a výstup do souboru si tam můžeš doplnit sám.
#include <stdio.h>
#include <stdlib.h>
#define prohod(x, y) (x ^= y, y ^= x, x ^= y)
void zatrid(int *pole, int i, int n)
{
int k;
for (;;)
{
k = i * 2 + 1;
if (k + 1 < n && pole[k + 1] < pole[i] && pole[k + 1] < pole[k])
{
prohod(pole[i], pole[k + 1]);
i = k + 1;
}
else if (k < n && pole[k] < pole[i])
{
prohod(pole[i], pole[k]);
i = k;
}
else
{
break;
}
}
}
void najdiVyskyt(int *pole, int n)
{
int i, prvek, pocet;
if (n <= 0)
return;
for (i = (n - 1) / 2; i >= 0; i--)
zatrid(pole, i, n);
prvek = pole[0];
pocet = 0;
for (i = n - 1; i >= 0; i--)
{
if (pole[0] != prvek)
{
printf("cislo %d, vyskyt %dx\n", prvek, pocet);
prvek = pole[0];
pocet = 0;
}
pocet++;
prohod(pole[0], pole[i]);
zatrid(pole, 0, i);
}
printf("cislo %d, vyskyt %dx\n", prvek, pocet);
}
int main()
{
int n = 1000000;
int pole[n];
for (int i = 0; i < n; i++)
pole[i] = rand() % 100;
najdiVyskyt(pole, n);
return 0;
}
To je přímo učebnicový příklad na countingsort - má lineární složitost - s ním to seřadíš rychleji, než kolik času ti zabere to načíst ze souboru.
Satiku, counting sort nemá lineární složitost, ale v jednodušším případě O(n + R), kde R=max-min. V případě vyššího R pak bude složitost O(n*T + R), kde T je amortizovaná složitost započítání výskytu jednoho prvku; obvykle bude T=log(N) a ve speciálních případech pak T=1 nebo T=O(R) v závislosti na chování algoritmu a distribuci vstupních hodnot.
V tomhle případě T=1 (jen inkrementuje hodnotu v poli).
Jak moc se složitost bude blížit lineární složitosti záleží na tom, jaký bude rozsah čísel a kolik jich bude.
Zobrazeno 15 zpráv z 15.