[es] - Kako napraviti niz od 30 miliona elemenata??

dejan_su
Dejan Balazevic
Subotica

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

ICQ: 337366387

Profil

Kako napraviti niz od 30 miliona elemenata??

^{02.12.2004. u 15:17}

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!

Pozdrav od Blaze

Prikačeni fajlovi

SORT.CPP - 0.56k

^{02.12.2004. u 15:17}

Srki_82
Srdjan Tot
Me @ My Home
Ljubljana

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

ICQ: 246436949

Profil

Re: Kako napraviti niz od 30 miliona elemenata??

^{02.12.2004. u 15:47}

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.

DirectX na srpskom | GLScene na srpskom

There are only 10 types of people in this world; those who understand binary and those who don't.

^{02.12.2004. u 15:47}

Damjan S. Vujnovic
London, UK

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

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

Profil

Re: Kako napraviti niz od 30 miliona elemenata??

^{02.12.2004. u 15:51}

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!

^{02.12.2004. u 15:51}

dejan_su
Dejan Balazevic
Subotica

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

ICQ: 337366387

Profil

Re: Kako napraviti niz od 30 miliona elemenata??

^{02.12.2004. u 16:20}

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

Pozdrav od Blaze

^{02.12.2004. u 16:20}

Milos Stojanovic
Belgrade

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

ICQ: 282954730
Sajt: www.sietf.org

Profil

Re: Kako napraviti niz od 30 miliona elemenata??

^{02.12.2004. u 16:31}

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
♪♫♪

^{02.12.2004. u 16:31}

Damjan S. Vujnovic
London, UK

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

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

Profil

Re: Kako napraviti niz od 30 miliona elemenata??

^{02.12.2004. u 16:43}

'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!

^{02.12.2004. u 16:43}

Milos Stojanovic
Belgrade

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

ICQ: 282954730
Sajt: www.sietf.org

Profil

Re: Kako napraviti niz od 30 miliona elemenata??

^{02.12.2004. u 17:20}

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
♪♫♪

^{02.12.2004. u 17:20}

dejan_su
Dejan Balazevic
Subotica

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

ICQ: 337366387

Profil

Re: Kako napraviti niz od 30 miliona elemenata??

^{02.12.2004. u 18:40}

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.

Pozdrav od Blaze

^{02.12.2004. u 18:40}

rivan
Ivan Radovanović

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

ICQ: 212235650

Profil

Re: Kako napraviti niz od 30 miliona elemenata??

^{03.12.2004. u 07:22}

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

^{03.12.2004. u 07:22}

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

Član broj: 128
Poruke: 571
217.16.77.*

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

Profil

Re: Kako napraviti niz od 30 miliona elemenata??

^{03.12.2004. u 11:24}

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.

^{03.12.2004. u 11:24}

Srki_82
Srdjan Tot
Me @ My Home
Ljubljana

Član broj: 28226
Poruke: 1402
82.208.201.*

ICQ: 246436949

Profil

Re: Kako napraviti niz od 30 miliona elemenata??

^{04.12.2004. u 00:48}

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

DirectX na srpskom | GLScene na srpskom

There are only 10 types of people in this world; those who understand binary and those who don't.

^{04.12.2004. u 00:48}

dejan_su
Dejan Balazevic
Subotica

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

ICQ: 337366387

Profil

Re: Kako napraviti niz od 30 miliona elemenata??

^{04.12.2004. u 03:46}

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

Pozdrav od Blaze

^{04.12.2004. u 03:46}

goky2002

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

Profil

Re: Kako napraviti niz od 30 miliona elemenata??

^{04.12.2004. u 10:50}

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.

^{04.12.2004. u 10:50}

_Super_Ellite_Bug_
Novi Sad, konacno!!!

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

Sajt: www.searchlores.org

Profil

Re: Kako napraviti niz od 30 miliona elemenata??

^{06.12.2004. u 21:20}

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

^{06.12.2004. u 21:20}

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

Profil

Re: Kako napraviti niz od 30 miliona elemenata??

^{07.12.2004. u 09:05}

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

^{07.12.2004. u 09:05}

jablan
Mladen Jablanović
Beograd

Član broj: 8286
Poruke: 3120
*.yubc.net.

Sajt: blog.radioni.ca

Profil

Re: Kako napraviti niz od 30 miliona elemenata??

^{07.12.2004. u 09:20}

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.

_{Probajte Ruby}

^{07.12.2004. u 09:20}

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

Profil

Re: Kako napraviti niz od 30 miliona elemenata??

^{07.12.2004. u 09:30}

Citat:

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

^{07.12.2004. u 09:30}

jablan
Mladen Jablanović
Beograd

Član broj: 8286
Poruke: 3120
*.yubc.net.

Sajt: blog.radioni.ca

Profil

Re: Kako napraviti niz od 30 miliona elemenata??

^{07.12.2004. u 09:40}

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.

_{Probajte Ruby}

^{07.12.2004. u 09:40}

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

Profil

Re: Kako napraviti niz od 30 miliona elemenata??

^{07.12.2004. u 12:19}

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

^{07.12.2004. u 12:19}

jablan
Mladen Jablanović
Beograd

Član broj: 8286
Poruke: 3120
*.yubc.net.

Sajt: blog.radioni.ca

Profil

Re: Kako napraviti niz od 30 miliona elemenata??

^{07.12.2004. u 12:59}

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.

_{Probajte Ruby}

^{07.12.2004. u 12:59}