» »

Preverjanje števil v tabeli

Preverjanje števil v tabeli

PowerShot ::

Napisal sem algoritem v C++, ki preverja števila v tabeli in če se katero ponovi ga ponovno generira. Problem je v tem ker je pri večjih tabelah prepočasen. Zanima če lahko kdo posreduje kaj hitrejšega bi bil vesel.

HairyFotr ::

Odvisno kako velika je tabela, v kakšnem razponu so števila in od kje pridejo števila.

Če tabelo lahko v celoti sam zgeneriraš(da ubistvu ni važno kateri elementi so, dokler so različni), to lahko narediš tako, da rečeš tab[0]=naključno število, tab[i+1] = tab[i]+naključno število in na koncu elemente tabele samo premešaš med sabo. Ta je najbolj simpl in najhitrejša.

Če delaš z naravnimi števili in veš, da je razpon števil majhen, si lahko pomagaš z dodatno tabelo, kjer je vrednost v tvoji tabeli indeks druge tabele (lookup tabela)... tu greš z zanko prek svoje tabele in pogledaš vrednost lookup[tab[i]]. Če je 0 ga nastaviš na 1... če pa je 1, veš da je ta vrednost že v tabeli in zgeneriraš novo (in spet s pomočjo lookup tabele pogledaš, če si zgeneriral vrednost ki je še ni v tabeli).

Če vrstni red elementov ni važen, lahko elemente svoje tabele vstaviš v množico(set... ne vem kako je stvar implementirana v c++). Ker v množici ni podvojenih elementov, pogledaš, za koliko se število elementov tvoje tabele in nove množice razlikuje in toliko elementov zgeneriraš in dodaš v množico. Če pa vrstni red je pomemben, ali pa ne veš kako delat z množicami v c++, pa lahko narediš to sam z binarnim iskanjem ali pa hash funkcijo, ampak je dosti težje.

Isotropic ::

generiraj se en index pozicije [ [0,rand], [1,rand], [2,rand] ]
sortiraj tabelo po rand ter za vsak element preveri samo tiste vrednosti naprej, dokler ne srecas prvega vecjega elementa. potem gres na naslednjo vrednost.

phyro ::

a to ti kao dodajaš elemente noter in bi rad na hiter način izvedel, če ga že maš, če ja -> v tem primeru generiraj novega?
če je to to, pol bi lahko sortiral tabelo in pol z bisekcijo pogledal, ce ze mas to noter, ce nimas, dodas
al ti tabele ne sestaviš in jo že dobiš?
v tem primeru mogoce sortirat tabelo in primerjat med sosedi (ki jih je lahko več istih, recimo [1,2,2,2,2,4,5]) -> to je mogoce ze loki3000 omenu sam nism šteku jst tistga :D

PowerShot ::

int main()
{
    int tab[7];
    srand(time(NULL));
    for( int i=0; i<7; i++)
    {
               int stevilo=rand()%39+1;
               tab[i]=stevilo;
               int j=0;
               while(j<i)
               {
                         if(tab[j]==stevilo)
                         {
                                           i--;
                                           break;
                         }
                        j++;
               }
               cout<<tab[i]<<endl;
    }
    system("PAUSE");
    return 0;
}

To je koda samo problem je ker pri večjih tabelah zelo počasna, jaz pa bi rad da bi bila čim bolj univerzalna pa bi prosil nekoga da mi poda kaj boljšega ker sem v teh stvareh bolj začetnik.

Isotropic ::

to ja, sam da sem jaz predpostavil, da je vrstni red pomemben, zato dodaten indeks.

Zgodovina sprememb…

Mavrik ::

Ker iščeš relativno majhen obseg števil, tole rešiš z nečim podobnim Fisher-Yates shuffle algoritmu:

a) Narediš tabelo s 40 mesti, ki nosi števila 0..39 (ali karkoli je že obseg)

b) Tabelo premešaš naključno (torej narediš naključne zamenjave števil kar nekajkrat)

c) Izpišeš prvih šest celic tabele
The truth is rarely pure and never simple.

Spura ::

Najhitrejsi za to je array based heap.

Isotropic ::

Spura je izjavil:

Najhitrejsi za to je array based heap.

Mavrik je izjavil:

Ker iščeš relativno majhen obseg števil, tole rešiš z nečim podobnim Fisher-Yates shuffle algoritmu:

a) Narediš tabelo s 40 mesti, ki nosi števila 0..39 (ali karkoli je že obseg)

b) Tabelo premešaš naključno (torej narediš naključne zamenjave števil kar nekajkrat)

c) Izpišeš prvih šest celic tabele

pri katerem predmetu ste se ucili tega dvojega?
tisti podatkovne strukture al kaj je ze?

PowerShot ::

int main()
{
       int tabela[10];
       srand(time(NULL));
       int a=0;
       for(int i=0; i<10; i++)
       {   
             a=rand()%10+1;

             for(int j=0; j<i; j++)
             {
                   if(tabela[j]==a)
                   {
                          a=rand ()%10+1;
                         j=0;
                   }
              }
              
              tabela[i]=stevilo;
             cout<<tabela[i]<<endl;
       }
       system("PAUSE");
       return 0;
}    

Sem nekaj delal pa me zanima če bi bilo to kaj bolj učinkovito pri večjih tabelah

Zgodovina sprememb…

Isotropic ::

sortiraj po velikosti
primerjaj, ce je tabela[j] == a in ce je > a. v slednjem primeru lahko brez problema prekines

me pa se vedno zanima odgovor na vprasanje zgoraj

Zgodovina sprememb…



Vredno ogleda ...

TemaSporočilaOglediZadnje sporočilo
TemaSporočilaOglediZadnje sporočilo
»

Python - pomoč (strani: 1 2 3 )

Oddelek: Programiranje
10318048 (8796) black ice
»

[php] unique random

Oddelek: Izdelava spletišč
141207 (917) Yacked2
»

največkrat pojavljeni element v tabeli

Oddelek: Programiranje
181951 (1326) pac1
»

Nasvet - izpis najvisjega stevila

Oddelek: Programiranje
92924 (2627) Keki
»

[c++]Urejanjepolja

Oddelek: Programiranje
91357 (1178) purki

Več podobnih tem