Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Kako napraviti niz od 30 miliona elemenata??

[es] :: C/C++ programiranje :: Kako napraviti niz od 30 miliona elemenata??

Strane: 1 2

[ Pregleda: 6408 | Odgovora: 30 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

dejan_su
Dejan Balazevic
Subotica

Član broj: 9453
Poruke: 483
*.suonline.net.

ICQ: 337366387


Profil

icon Kako napraviti niz od 30 miliona elemenata??02.12.2004. u 15:17 - pre 235 meseci
Pokusavam da napravim jedan programcic, ali nikako da skontam nesto. Dakle napravim da upise 30 miliona proizvoljnih elemenata u fajl, ali kako to posle da ucitam u memoriju i da sortiram?

Postovao sam i fajl, ako neko zeli da vidi...ima mozda nesto nebitno ali ajde...ako neko zna molim za pomoc!
Prikačeni fajlovi
 
Odgovor na temu

Srki_82
Srdjan Tot
Me @ My Home
Ljubljana

Član broj: 28226
Poruke: 1403
*.smin.sezampro.yu.

ICQ: 246436949


+10 Profil

icon Re: Kako napraviti niz od 30 miliona elemenata??02.12.2004. u 15:47 - pre 235 meseci
Posto su ti elementi tipa int znaci da ti za svaki element treba po 4 bajta. 30000000 elemenata = 114.44 Mb. Koliko se secam mozes da alociras oko 4Gb memorije tako da 114.44Mb ne bi trebalo da bude problem ako naravno imas dovoljno memorije. Alociras memoriju, ucitas podatke... roknes quicksort i vratis podatke u fajl. Nista tesko. Ako imas neko memorijsko ogranicenje onda... pffff... ne znam.
 
Odgovor na temu

Damjan S. Vujnovic
London, UK

Član broj: 30444
Poruke: 81
*.ceetel.co.yu.

Jabber: damjan@elitesecurity.org
ICQ: 68189289
Sajt: www.javasvet.net


Profil

icon Re: Kako napraviti niz od 30 miliona elemenata??02.12.2004. u 15:51 - pre 235 meseci
Posto su elementi manji od 65536 treba koristiti neki "linear-time" algoritam za sortiranje, tipa count sort i za to ce biti dovoljno svega 256 KB memorije...

Damjan S. Vujnovic
I love the smell of copyright violations in the morning. Smells like... freedom!
 
Odgovor na temu

dejan_su
Dejan Balazevic
Subotica

Član broj: 9453
Poruke: 483
*.suonline.net.

ICQ: 337366387


Profil

icon Re: Kako napraviti niz od 30 miliona elemenata??02.12.2004. u 16:20 - pre 235 meseci
Meni je problem sto ne znam kako iz fajla da ucitam. Moram sve preko pointera da radim posto ih ima puno, ali ne znam kako to...
 
Odgovor na temu

Milos Stojanovic
Belgrade

Član broj: 10343
Poruke: 1864
*.nat-pool.bgd.sbb.co.yu.

ICQ: 282954730
Sajt: www.sietf.org


+7 Profil

icon Re: Kako napraviti niz od 30 miliona elemenata??02.12.2004. u 16:31 - pre 235 meseci
Iz fajla? Pa lako. Jedan od načina:

Code:
#include <stdio.h>

int *niz;
long int n; // broj elemenata, long za svaki slucaj, treba nam 32 bita za 30 miliona

void ucitajNizIzFajla(char* imeFajla)
{
     FILE* in;
     int i;
     in = fopen(imeFajla, "r");
     fscanf(in, "%d", &n); // ucitava broj elemenata
     // ako je broj elemenata fiksan, onda samo stavi
     // n = brojElemenata umesto ovog

     niz = (int*)malloc(sizeof(int)*n); // alocira niz od n brojeva

     for(i=0; i<n; i++)
     {
          fscanf(in, "%d", &(niz[i])); // ucitava i-ti broj iz fajla
     }
}

ex. trooper
Oh goody... it's my Illudium PU-36 Explosive Space Modulator!
Softversko Inženjerstvo
♪♫♪
 
Odgovor na temu

Damjan S. Vujnovic
London, UK

Član broj: 30444
Poruke: 81
*.ceetel.co.yu.

Jabber: damjan@elitesecurity.org
ICQ: 68189289
Sajt: www.javasvet.net


Profil

icon Re: Kako napraviti niz od 30 miliona elemenata??02.12.2004. u 16:43 - pre 235 meseci
'Ajmo jos jednom, za one sa jeftinijim ulaznicama...

Dakle, instanciras (bilo staticki, bilo dinamicki, zavisno od okruzenja) niz od 65536 long-ova koji inicijalizujes nulama. Citas elemente fajla redom i kako koji ucitas inkrementiras element na njegovoj poziciji u instanciranom nizu longova (iliti brojis pojavljivanje svakog od 65536 mogucih int-ova). Kad procitas sve elemente, krenes lepo po napravljenom nizu, otvoris novi fajl i upisujes po onoliko elemenata koliko si prebrojao.

Nema nikakve potrebe za drzanjem svih elemenata u memoriji, quick sort-om i slicno...

Hev fan,
Damjan S. Vujnovic
I love the smell of copyright violations in the morning. Smells like... freedom!
 
Odgovor na temu

Milos Stojanovic
Belgrade

Član broj: 10343
Poruke: 1864
*.nat-pool.bgd.sbb.co.yu.

ICQ: 282954730
Sajt: www.sietf.org


+7 Profil

icon Re: Kako napraviti niz od 30 miliona elemenata??02.12.2004. u 17:20 - pre 235 meseci
my bad, nisam ni video source zakačen uz pitanje. Ako čoveku treba da učita ceo niz u memoriju, onda što mu ne bi objasnili kako da to uradi? Druga stvar, iz nekog razloga koristi strukture, možda kasnije planira da tu strukturu prošiti nekim drugim podacima. Onda count sort neće moći. Za početak, učitavanje, ako ćemo C++ (pišem napamet, moguće da ima nekih syntax errora):

Code:
NIZOVI* niz;
void izFajla()
{
     ifstream infile("sort.txt");
     niz = new NIZOVI[30000000];

     for(long int i=0; i<30000000; i++)
     {
          infile >> niz[i].x;
          cout << niz[i].x;
     }
}

ex. trooper
Oh goody... it's my Illudium PU-36 Explosive Space Modulator!
Softversko Inženjerstvo
♪♫♪
 
Odgovor na temu

dejan_su
Dejan Balazevic
Subotica

Član broj: 9453
Poruke: 483
*.suonline.net.

ICQ: 337366387


Profil

icon Re: Kako napraviti niz od 30 miliona elemenata??02.12.2004. u 18:40 - pre 235 meseci
Trooper, uradio sam kao sto si napisao ali nista se ne desava, pokrenem lepo iz command prompta i on nista, samo mi opet izbaci prompt, ko da sam enter udario. Isto je radilo i ono iz mog koda. No ajde da vidimo sa sortiranjem, mozda cemo tamo uspeti da sredimo nesto. Koje parametre predajem funkciji za sortiranje? Sta mi je niz, a sta velicina? I da li predajem "obicno" ili kao referencu ili pointer?
Ako ne uspe, onda cu da probam sa onim kodom sto si prvo napisao. Bice nesto:)

Ako je bitno, ShellSort koristim.
 
Odgovor na temu

rivan
Ivan Radovanović

Član broj: 1901
Poruke: 71
*.preco1990.com.

ICQ: 212235650


Profil

icon Re: Kako napraviti niz od 30 miliona elemenata??03.12.2004. u 07:22 - pre 235 meseci
ovakve stvari se ne resavaju tako u opstem slucaju - fora je sledeca - neka je taj tvoj fajl veliki npr preko 100K i ne mozes da ga sortiras u memoriji, ali mozes da sortiras 10K elemenata u memoriji, ti onda procitas iz fajla 10K elemenata i sortiras ih, pa to upises u novi fajl (npr f_1), pa procitas jos 10K i njih sortiras i upises u f_2 i tako dok ceo pocetni fajl ne razbijes u sortirane komadice (sekvence), onda ti samo ostaje da uradis obican merge tih sortiranih fajlova (uzimas najmanji element iz f_i fajlova i upisujes u krajnji rezultat, i pomeris se za jedno mesto u fajlu iz koga si uzeo element, dok ne pokupis sve elemente svih f_i fajlova).

P.S.
da li negde na forumu ima uputstvo za pisanje teksta - ovi tagovi sa [] me malo zezaju
 
Odgovor na temu

Riste Pejov
Team Leader/Senior Software Developer @
Ein-Sof ltd Skopje
Skopje, Macedonia

Član broj: 128
Poruke: 571
217.16.77.*

Jabber: richie@bagra.net.mk
ICQ: 154236769
Sajt: riste.softver.org.mk


Profil

icon Re: Kako napraviti niz od 30 miliona elemenata??03.12.2004. u 11:24 - pre 235 meseci
Ne vidim razloga imati sve podatke odjednom u memoriji ili citati ceo niz odjednom iz fajl u memoriji i natrag. Bolje reci koja je poenta programa ?

Ako trebas ucitati sve podatke iz jednog fajla i sortirati ih pa natrag u drugi fajl onda je bolje da koristis merge sort pa da to ide korak po korak, recimo sortiras prvih 100K pa onda drugih pa ih merge-ujes i slicno. Ako je pitanje performanse onda je drug problem ... za razlicnih ciljova programa resenje je razlicno. Ako se radi o programu koji treba pretrazivati niz, onda uzmi neku embedded bazu. Razmisli dobro o implementaciju neke DB strukture koja ce da indexira taj niz, mozda B ili Radix drva.

Ovako sa cistom informacijom da se radi 30 miliona clanova ... moguca su jedno 20-tak resenja koji ce se ponasati razlicito u razlicitim situacijama.
People who think they know everything tend to irritate those of us who do.
 
Odgovor na temu

Srki_82
Srdjan Tot
Me @ My Home
Ljubljana

Član broj: 28226
Poruke: 1403
82.208.201.*

ICQ: 246436949


+10 Profil

icon Re: Kako napraviti niz od 30 miliona elemenata??04.12.2004. u 00:48 - pre 235 meseci
E, daaaaaaa... pa baze podataka i nisu tako losa ideja. Ucitas sve podatke u bazu i samo kazes nesto kao SELECT * FROM TabelaElemenata ORDER Element (ili tako nesto) i baza ti sama vrati sve sortirano. Na tebi je da samo ispises (ili sta vec treba da radis) rezultate :)
 
Odgovor na temu

dejan_su
Dejan Balazevic
Subotica

Član broj: 9453
Poruke: 483
*.suonline.net.

ICQ: 337366387


Profil

icon Re: Kako napraviti niz od 30 miliona elemenata??04.12.2004. u 03:46 - pre 235 meseci
Delovace smesno, ali evo zasto mi treba : zelim da na velikom broju elemenata testiram najpoznatije vrste sortiranja. Dakle u svaku ubacim jedan mali "timer" i lepo izracunam koja metoda za sortiranje je najbrza.
Eto o tome se radi...
 
Odgovor na temu

goky2002

Član broj: 3848
Poruke: 191
*.ptt.yu.



Profil

icon Re: Kako napraviti niz od 30 miliona elemenata??04.12.2004. u 10:50 - pre 235 meseci
Mislim da je bolje da procitas neku knjigu o algoritmima.
Postoje drugi efikasniji metodi za procenu algoritama.
Recimo u nekim specijalnim slucajevima jedni algoritmi su brzi od drugih a u opstim nisu, tako da ako potrefis neki "bezveze" niz rezultati nece biti dobri.
 
Odgovor na temu

_Super_Ellite_Bug_
Novi Sad, konacno!!!

Član broj: 41318
Poruke: 145
*.nat-pool.nsad.sbb.co.yu.

Sajt: www.searchlores.org


Profil

icon Re: Kako napraviti niz od 30 miliona elemenata??06.12.2004. u 21:20 - pre 235 meseci
Pozdrav,
bice ti veci problem tajmer, ako zelis valjano da odradis to sto si zamislio.
Sa dobrim tajmerom(sa dobro kalibrisanim tajmerom) nema potrebe za 30 miliona elemenata, dovoljno je i naprimer 100000 elemenata niza.
ISO/IEC JTC1/SC22/WG14-ISO/IEC 9899:1999
 
Odgovor na temu

filmil
Filip Miletić
Oce Technologies B.V., inženjer
hardvera
Arcen, NL

Član broj: 243
Poruke: 2114
*.et.tudelft.nl.

Jabber: filmil@jabber.org
ICQ: 36601391


+3 Profil

icon Re: Kako napraviti niz od 30 miliona elemenata??07.12.2004. u 09:05 - pre 235 meseci
Citat:
Sa dobrim tajmerom(sa dobro kalibrisanim tajmerom) nema potrebe za 30 miliona elemenata, dovoljno je i naprimer 100000 elemenata niza.
Zapravo, dovoljno je imati (neveliki) uzorak, ali zato eksperiment ponoviti puno puta. Zatim se iskoriste statistički metodi za procenu trajanja sa odgovarajućim nivoom poverenja. Ili se lepo uzme TAOCP i tamo pročitaju asimptotska vremena izvršavanja za algoritme za sortiranje.

f
 
Odgovor na temu

jablan

Član broj: 8286
Poruke: 4541



+710 Profil

icon Re: Kako napraviti niz od 30 miliona elemenata??07.12.2004. u 09:20 - pre 235 meseci
Potpuno je različito sortirati 30 i 30 miliona elemenata. To jest, potpuno je različito sortirati stvari u memoriji i sortirati stvari na disku. I jedan i drugi problem su prilično dobro teoretski i praktično pokriveni u zadnjih par desetina godina.
 
Odgovor na temu

filmil
Filip Miletić
Oce Technologies B.V., inženjer
hardvera
Arcen, NL

Član broj: 243
Poruke: 2114
*.et.tudelft.nl.

Jabber: filmil@jabber.org
ICQ: 36601391


+3 Profil

icon Re: Kako napraviti niz od 30 miliona elemenata??07.12.2004. u 09:30 - pre 235 meseci
Citat:
Potpuno je različito sortirati 30 i 30 miliona elemenata. To jest, potpuno je različito sortirati stvari u memoriji i sortirati stvari na disku. I jedan i drugi problem su prilično dobro teoretski i praktično pokriveni u zadnjih par
U principu nije potpuno različito, pod uslovom da ili oba sortiranja budu na disku, ili oba u memoriji. Ako znaš kakvi su režijski troškovi (troškovi zauzimanja memorije, inicijalizacije i svega ostalog što traje fiksno vreme), ponavljanjem eksperimenta dovoljan broj puta možeš da isključiš njihov uticaj. Teoretski dakle čak i sa 30 elemenata se može izmeriti, jedino je uputnije uzeti veći uzorak (3e3, 3e4, 3e5 elemenata), čisto da bi konvergencija bila brža.

f
 
Odgovor na temu

jablan

Član broj: 8286
Poruke: 4541



+710 Profil

icon Re: Kako napraviti niz od 30 miliona elemenata??07.12.2004. u 09:40 - pre 235 meseci
Heh ovo me podseti na onaj vic sa sferičnim kokoškama u vakuumu. U stvarnosti, praktično se nikad ne desi da i niz sa 30 i niz sa 30 miliona elemenata budu ili samo na disku ili samo u memoriji (nešto kao ta Šredingerova mačka: nit je ima nit je nema). Primenjivanje matematičkih metoda na programiranje može da ima prilično katastrofalne posledice u praksi.
 
Odgovor na temu

filmil
Filip Miletić
Oce Technologies B.V., inženjer
hardvera
Arcen, NL

Član broj: 243
Poruke: 2114
*.et.tudelft.nl.

Jabber: filmil@jabber.org
ICQ: 36601391


+3 Profil

icon Re: Kako napraviti niz od 30 miliona elemenata??07.12.2004. u 12:19 - pre 235 meseci
Citat:
Primenjivanje matematičkih metoda na programiranje može da ima prilično katastrofalne posledice u praksi. ;)


Ne može da ima katastrofalne posledice ako se ispravno primenjuje, a rezultati tumače kako treba.

Sećam se jednog skorašnjeg primera, gde je neko pitao: „kako to, TCP je reliable delivery protokol a meni se desi greška pri povezivanju?“

f
 
Odgovor na temu

jablan

Član broj: 8286
Poruke: 4541



+710 Profil

icon Re: Kako napraviti niz od 30 miliona elemenata??07.12.2004. u 12:59 - pre 235 meseci
Ma jeste to tako, ali pitanje koliko sve možeš da aproksimiraš, ako već hoćeš da praviš matematički model. Kako se razvijaju računari, samo se gomilaju nivoi između programa i računara s jedne, i korisnika i programa sa druge strane. Nekad je bilo lako. Imao si procesor, memoriju, disk, i primitivni operativni sistem koji si mogao u prste da poznaješ. Sad između niza od 3e7 (je l' se tako beše piše?) elemenata (ili barem onoga što korisnik ili programer zamišlja kao niz) i računara postoji hard disk, keš na tom disku, dva keša na procesoru, disk keš u memoriji, RDBMS, keširani indeksi u tom RDBMSu, par nivoa između aplikacije i baze, nekoliko nivoa u samoj aplikaciji, uključujući i neki IL. Dok čovek savlada sve nivoe ne bi li koliko toliko tačno mogao da aproksimira svojim modelom, velika je verovatnoća da se nekom tamo diglo da smisli još neki ADO i da ga, s oproštenjem, ugura negde između.
 
Odgovor na temu

[es] :: C/C++ programiranje :: Kako napraviti niz od 30 miliona elemenata??

Strane: 1 2

[ Pregleda: 6408 | Odgovora: 30 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.