Diskuze: Urychleni algoritmu.

honza.b4

Člen

honza.b4:19.2.2014 20:41

Zdravim vsechny. Nenapada vas zpusob, jak podstatne urychlit tento algoritmus?
The algoritmus ma nejdrive nacist ze souboru cislo p indikujici pocet ostatnich cisel. A potom to ma rozradit, resp. zjistit, kolik je kterych cisel. Rozradit 100 000 cisel mu trva hodiny. Nenapada vas zpusob, jak to urychlit? Predem moc diky za pomoc.

#include <stdio.h>
#include <stdlib.h>
#define NAZEV "vstup.txt"
#define TYP "r"
#define NAZEV2 "help"
#define TYP2 "a+"
#define MIN_INT -1000000000
#define MAX_INT 1000000000
/*--------------------------------------------------------------------------------------------------*/
FILE *s;
FILE *pomocnySoubor;
int n;
int poleCisel[100001];

/*------------------------------------------------------------------------------------------------*/
void nactiVstup(){
    s = fopen(NAZEV, TYP);
    fscanf(s, "%d\n", &n);
    int i;
    for(i=0; i < n;i++){
        fscanf(s, "%d\n", &poleCisel[i]);
    }
puts("nascanoval sem ze souboru");
    fclose(s);
}
/* Druha metoda ------------------------------------------------------------------------------ */
void najdiVyskyt(){
    pomocnySoubor = fopen(NAZEV2, TYP2);
    int i,j,tmp=0;
    int vysledek;

        int aktualni_cislo;
        puts("zacinam tridit");
        for(j=MIN_INT; j < MAX_INT; j++){
            vysledek=0;
            aktualni_cislo =j;
            if(j == MIN_INT/2){
                puts("jsem v pulce");
            }
            if(j == MIN_INT/4){
                puts("jsem ve ctvrtine");
        }
                if(j == MIN_INT/1000){
                puts("jsem v jedne tisicine");
}
        for(i=0; i < n; i++){
            if(poleCisel[i] == aktualni_cislo){
            vysledek++;

        }

        }
        if(vysledek > 0){
            fprintf(pomocnySoubor, "%d %d\n", aktualni_cislo, vysledek);
            printf("%d %d\n", aktualni_cislo, vysledek);
        }
        }



        printf("dotridil sem\n");



    fclose(pomocnySoubor);
}

/*Hlavni funkce ------------------------------------------------------------------------------------- */
int main(void){
    nactiVstup();
    najdiVyskyt();
    printf("\n");
    return EXIT_SUCCESS;
}

btw. mozna tam jsou nejake nepouzite promenne. Kdyz sem to poprve napsal, tak to nefungovalo a tak jsem to komplet prepisoval. >> proto tam jsou mozna nejake prebytecne.

Odpovědět

19.2.2014 20:41

Viktor Bednarik (WickyPayne)

Tvůrce

Viktor Bednarik (WickyPayne):19.2.2014 21:14

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/

http://www.dreamincode.net/…tutorial-ii/

http://www.dreamincode.net/…-using-sort/

Nahoru Odpovědět

19.2.2014 21:14

honza.b4

Člen

honza.b4:19.2.2014 21:22

neni neco takeho i proc C? ne primo c++?

btw. mas pravdu, netrva to hodiny, ale spis dny

Nahoru Odpovědět

19.2.2014 21:22

tomisoka

Tvůrce

tomisoka:19.2.2014 21:23

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 nula

Nahoru Odpovědět

19.2.2014 21:23

honza.b4

Člen

honza.b4:19.2.2014 21:35

ted me napadlo.: nebylo by lepsi to pole nejdriv setridit podle velikosti a potom to postupne projet?

Nahoru Odpovědět

19.2.2014 21:35

tomisoka

Tvůrce

tomisoka:19.2.2014 21:36

Mensi chybicka, ma tam byt :

vysledek[poleCisel[i] - Min]++;

Nahoru Odpovědět

19.2.2014 21:36

Jan Vargovský

Tvůrce

Jan Vargovský:19.2.2014 22:17

Ř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.

Nahoru Odpovědět

19.2.2014 22:17

tomisoka

Tvůrce

tomisoka:19.2.2014 22:18

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

Nahoru Odpovědět

19.2.2014 22:18

tomisoka

Tvůrce

tomisoka:19.2.2014 22:42

co jsem pochopil tak se tu bavime jen o C, kde asi zadne slovniky nejsou. Navic trochu nevim jaky rozdil by byl mezi polem a slovnikem kdyz se stejne pristupuje pres cislo
to pole o zname velikosti (rozdil MAX a MIN) tam vsak vyuzivam ( "vysledek")

Nahoru Odpovědět

19.2.2014 22:42

Jan Vargovský

Tvůrce

Jan Vargovský:19.2.2014 23:05

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 2³² 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.

Nahoru Odpovědět

19.2.2014 23:05

coells

Tvůrce

coells:20.2.2014 12:20

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;
}

Nahoru Odpovědět

20.2.2014 12:20

Luboš Běhounek Satik

Tvůrce

Luboš Běhounek Satik:20.2.2014 12:35

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.

Nahoru Odpovědět

20.2.2014 12:35

https://www.facebook.com/peasantsandcastles/

coells

Tvůrce

coells:20.2.2014 15:01

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.

Nahoru Odpovědět

20.2.2014 15:01

Libor Šimo (libcosenior)

Tvůrce

Libor Šimo (libcosenior):20.2.2014 16:00

Najviac sa mi páči to makro.

Nahoru Odpovědět

20.2.2014 16:00

Aj tisícmíľová cesta musí začať jednoduchým krokom.

Luboš Běhounek Satik

Tvůrce

Luboš Běhounek Satik:20.2.2014 16:01

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.

Nahoru Odpovědět

20.2.2014 16:01

https://www.facebook.com/peasantsandcastles/