Avatar
honza.b4
Člen
Avatar
honza.b4:

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
Odpovídá na honza.b4
Viktor Bednarik (WickyPayne):

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:

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
Redaktor
Avatar
Odpovídá na honza.b4
tomisoka:

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:

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
Redaktor
Avatar
Odpovídá na tomisoka
tomisoka:

Mensi chybicka, ma tam byt :

vysledek[poleCisel[i] - Min]++;
 
Nahoru Odpovědět 19.2.2014 21:36
Avatar
Jan Vargovský
Redaktor
Avatar
Odpovídá na tomisoka
Jan Vargovský:

Ř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
Redaktor
Avatar
Odpovídá na honza.b4
tomisoka:

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
Redaktor
Avatar
Odpovídá na Jan Vargovský
tomisoka:
  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ý
Redaktor
Avatar
Odpovídá na tomisoka
Jan Vargovský:

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
Redaktor
Avatar
Odpovídá na honza.b4
coells:

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  +1 20.2.2014 12:20
Avatar
Odpovídá na honza.b4
Luboš Běhounek (Satik):

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  +1 20.2.2014 12:35
:)
Avatar
coells
Redaktor
Avatar
Odpovídá na Luboš Běhounek (Satik)
coells:

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
Odpovídá na coells
Libor Šimo (libcosenior):

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
Odpovídá na coells
Luboš Běhounek (Satik):

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
:)
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.