Kako napraviti niz od 30 miliona elemenata??

Kako napraviti niz od 30 miliona elemenata?? 02.12.2004. u 16:17 · pre 267 meseci #1

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!

SORT.CPP0.56k

Re: Kako napraviti niz od 30 miliona elemenata?? 02.12.2004. u 16:47 · pre 267 meseci #2

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.

Potpis

Play Store

Re: Kako napraviti niz od 30 miliona elemenata?? 02.12.2004. u 16:51 · pre 267 meseci #3

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

Potpis

I love the smell of copyright violations in the morning. Smells like... freedom!

Re: Kako napraviti niz od 30 miliona elemenata?? 02.12.2004. u 17:20 · pre 267 meseci #4

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

Re: Kako napraviti niz od 30 miliona elemenata?? 02.12.2004. u 17:31 · pre 267 meseci #5

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

Potpis

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

Re: Kako napraviti niz od 30 miliona elemenata?? 02.12.2004. u 17:43 · pre 267 meseci #6

'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

Potpis

I love the smell of copyright violations in the morning. Smells like... freedom!

Re: Kako napraviti niz od 30 miliona elemenata?? 02.12.2004. u 18:20 · pre 267 meseci #7

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;
     }
}

Potpis

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

Re: Kako napraviti niz od 30 miliona elemenata?? 02.12.2004. u 19:40 · pre 267 meseci #8

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.

Re: Kako napraviti niz od 30 miliona elemenata?? 03.12.2004. u 08:22 · pre 267 meseci #9

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

Re: Kako napraviti niz od 30 miliona elemenata?? 03.12.2004. u 12:24 · pre 267 meseci #10

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.

Potpis

People who think they know everything tend to irritate those of us who do.

Re: Kako napraviti niz od 30 miliona elemenata?? 04.12.2004. u 01:48 · pre 267 meseci #11

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

Potpis

Play Store

Re: Kako napraviti niz od 30 miliona elemenata?? 04.12.2004. u 04:46 · pre 267 meseci #12

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

Re: Kako napraviti niz od 30 miliona elemenata?? 04.12.2004. u 11:50 · pre 267 meseci #13

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.

Re: Kako napraviti niz od 30 miliona elemenata?? 06.12.2004. u 22:20 · pre 266 meseci #14

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.

Potpis

ISO/IEC JTC1/SC22/WG14-ISO/IEC 9899:1999

Re: Kako napraviti niz od 30 miliona elemenata?? 07.12.2004. u 10:05 · pre 266 meseci #15

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

Re: Kako napraviti niz od 30 miliona elemenata?? 07.12.2004. u 10:20 · pre 266 meseci #16

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.

Re: Kako napraviti niz od 30 miliona elemenata?? 07.12.2004. u 10:30 · pre 266 meseci #17

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

Re: Kako napraviti niz od 30 miliona elemenata?? 07.12.2004. u 10:40 · pre 266 meseci #18

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.

Re: Kako napraviti niz od 30 miliona elemenata?? 07.12.2004. u 13:19 · pre 266 meseci #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

Re: Kako napraviti niz od 30 miliona elemenata?? 07.12.2004. u 13:59 · pre 266 meseci #20

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.

Forum kao aplikacija na telefonu

Srodne teme