Nové výhodné předplatné namísto kreditů je tu! Více informací. Upravili jsme také naše provozní podmínky.
NOVINKA: Staň se datovým analytikem a získej jistotu práce, lepší plat a nové kariérní možnosti. Více informací:
Avatar
honza.b4
Člen
Avatar
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
Avatar
Viktor Bednarik (WickyPayne)
Tvůrce
Avatar
Odpovídá na honza.b4
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
Avatar
honza.b4
Člen
Avatar
Odpovídá na Viktor Bednarik (WickyPayne)
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
Avatar
tomisoka
Tvůrce
Avatar
Odpovídá na honza.b4
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
Avatar
honza.b4
Člen
Avatar
Odpovídá na tomisoka
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
Avatar
tomisoka
Tvůrce
Avatar
Odpovídá na tomisoka
tomisoka:19.2.2014 21:36

Mensi chybicka, ma tam byt :

vysledek[poleCisel[i] - Min]++;
 
Nahoru Odpovědět
19.2.2014 21:36
Avatar
Jan Vargovský
Tvůrce
Avatar
Odpovídá na tomisoka
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
Avatar
tomisoka
Tvůrce
Avatar
Odpovídá na honza.b4
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
Avatar
tomisoka
Tvůrce
Avatar
Odpovídá na Jan Vargovský
tomisoka:19.2.2014 22:42
  1. 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
  2. to pole o zname velikosti (rozdil MAX a MIN) tam vsak vyuzivam ( "vysledek")
 
Nahoru Odpovědět
19.2.2014 22:42
Avatar
Jan Vargovský
Tvůrce
Avatar
Odpovídá na tomisoka
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 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.

 
Nahoru Odpovědět
19.2.2014 23:05
Avatar
coells
Tvůrce
Avatar
Odpovídá na honza.b4
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
Avatar
Luboš Běhounek Satik
Tvůrce
Avatar
Odpovídá na honza.b4
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/
Avatar
coells
Tvůrce
Avatar
Odpovídá na Luboš Běhounek Satik
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
Avatar
Libor Šimo (libcosenior)
Tvůrce
Avatar
Odpovídá na coells
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.
Avatar
Luboš Běhounek Satik
Tvůrce
Avatar
Odpovídá na coells
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/
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 15 zpráv z 15.