Forum » Programiranje » 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.
Č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.
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
č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…
- spremenil: Isotropic ()
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
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.
Isotropic ::
Najhitrejsi za to je array based heap.
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…
- spremenil: PowerShot ()
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
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…
- spremenil: Isotropic ()
Vredno ogleda ...
Tema | Ogledi | Zadnje sporočilo | |
---|---|---|---|
Tema | Ogledi | Zadnje sporočilo | |
» | Python - pomoč (strani: 1 2 3 )Oddelek: Programiranje | 18048 (8796) | black ice |
» | [php] unique randomOddelek: Izdelava spletišč | 1207 (917) | Yacked2 |
» | največkrat pojavljeni element v tabeliOddelek: Programiranje | 1951 (1326) | pac1 |
» | Nasvet - izpis najvisjega stevilaOddelek: Programiranje | 2924 (2627) | Keki |
» | [c++]UrejanjepoljaOddelek: Programiranje | 1357 (1178) | purki |