[C++] pitanje vezano za array

[Dejan]

Npr imam strukturu definisanu ovako

struct TStruct
{
char[255] Ime;
unsigned int Indeks;
};

I imam jedan array koji sadrzi objekte tipa TStruct.

E sad, trebam da maknem sve duplikate iz tog niza. Zna li neko neki brzi nacin? Duplikati su ona dva koja imaju isto Ime, koji god da imaju Indeks.

Trenutno to radim tako sto pozivam "strcmp" i tako uporedjujem sve postojece objekte, prije svakog dodavanja. Medjutim posto je array OGROMAN, ovo je vrlo sporo.

[db]

ima mnoogo varijanti....

evo najjednostavnije (ali ne i najefikasnije)

-kad ubacuješ člana u niz, niz i sortiraj-jer onda možeš da vidiš da li postoji taj član za malo vremena ( O(log(n) ) pomoću binarnog traženja
-kad nadješ mjesto gdje treba da se ubaci član (recimo između k i k+1 mjesta), ne moraš sve elemente da pomjeraš jedan po jedan, nego možeš da:

-napraviš novi niz dovoljne veličine

-iskopiraš prvi dio (od mjesta 0 do k) niza (pomoću memcpy()) u novi niz
-dodaš novi član u nastavku-on dođe kao novi_niz[k+1]
-iskopiraš drugi blok (od mjesta k+1 do kraja u početnom nizu) niza (pomoću memcpy()) u novi niz

-izbrišeš stari niz (da oslobodiš memoriju)-ovdje pazi da eventualni pokazivači na objekte budu NULL da ne bi došlo do "kaskadnog" brisanja (to jest ovo može samo ako struktura nema neke pokazivače ili slično što će pozvati destruktore ili slično)
-adresu novog niza staviš kao adresu starog
-adresu novog podesiš na NULL (ovo vjerovatno i ne mora la za svaki slučaj)



evo i ukratko-pokušaj objašnjenja-ako ti je lakše

stari niz:
[A][B]-A i B su blokovi iymedju kojih treba da se nadje clan (ako ne postoji-a ako postoji-duplikat je i ne dodajes ga)
novi niz:
u početku je prazan
faze:
1. [A]
2. [A],novi_clan
3. [A],novi_clan,[B]



e sad to možeš i da realizuješ pomoću drveta, ali to puno komplikuje proces (a mene muka da pišem toliko )

[Dejan]

Rijesio sam problem tako sto cu koristiti std::map. Nema duplikata, nego radi kao key : value. Key ce biti ime, value ce biti struktura. I kad dodam isto ime, ono ce samo preko starog da se upise.

std::map<char*, TStruct>

[mito61]

Npr imam strukturu definisanu ovako

struct TStruct
{
char[255] Ime;
unsigned int Indeks;
};

I imam jedan array koji sadrzi objekte tipa TStruct.

E sad, trebam da maknem sve duplikate iz tog niza. Zna li neko neki brzi nacin? Duplikati su ona dva koja imaju isto Ime, koji god da imaju Indeks.

Trenutno to radim tako sto pozivam &quot;strcmp&quot; i tako uporedjujem sve postojece objekte, prije svakog dodavanja. Medjutim posto je array OGROMAN, ovo je vrlo sporo.

Vidi, nije problem sto je array OGROMAN, vec sto je neuredjen, odnosno, nesortiran. Pretpostavka pretrazivanja jeste prethodno uradjeno sortiranje. Recimo, binarno pretrazivanje ima logaritamsku efikasnost (vec ti je db napisao: O(logN). U prevodu, trazeni clan, iz array-a od , recimo, milion clanova, a koji je sortiran (rastuce ili opadajuce) ces sigurno pronaci iz najvise 20 pokusaja (2 na 20 jednako milion), primjenom binarnog pretrazivanja. Ili, interpolaciono pretrazivanje, ima jos bolju efikasnost: O(log(logN)). Slozices se da je pretrazivanje neuredjenog array-a krajnje neefikasno ...
E sad, map upravo to i radi, to jest: sortira. Znaci, sve se indeksira preko kljuca, koji je jedinstven (map ne dozvoljava vise podataka sa istim kljucem - prevedeno kod tebe: ne dozvoljava 'duplikate'). E on to radi tako sto parove 'key-data' organizuje u neku strukturu, tipicno : binarno stablo, i to u rastucem poretku.
Zasto ovo pisem? Pa, eto, u najboljoj namjeri, bez ikakve zelje za 'soljenjem pameti', vec u zelji da pomognem i pravilno usmjerim (pretpostavljam da studiras?): osnov osnova programiranja su: STRUKTURE PODATAKA (stek, stablo: gomila, AVL stabla, crveno-crna stabla, redovi, liste, ulancane, jednostruke i dvostruke, dinamicki i staticki tipovi) i ALGORITMI (rekurzija, sortiranje, pretrazivanje, optimalni algoritmi, i slicno). Ako ti nekad dodje do ruke, procitaj: 'The art of computer programming', od Donalda Knuth-a ...

[db]

pa sad interpolaciono pretraživanje je malo teže implementirati u ovom slučaju jer bi morao da prevodi string u broj i slično (dakle dosta skupe a ako je string (ime) veliko (što je logično za očekivati)-veoma skupe (jer bi trebao da implementira i algoritam za operacije sa velikmh brojevima)-ali bi možda mogao da se napravi neki hibrid (mada je to previše komplikovanja za malo bolje performanse (jer niz nije dovoljno velik) ) ),...mislim sumnjam da mu je niz toliko velik da bi imao prednosti u odnosu na binarno traženje-čak bi bio i sporiji (ako je niz razumno velik-a ne vjerujem da je veći od 1 000 000 članova)

[Dejan]

Rijesio sam problem... Nasao sam neki HASH algoritam koji ce string da pretvori u hash i sacuvao sve to u std::map tako da je hash kljuc, a odgovarajuca struktura, podatak.

I brzo i efikasno

[db]

nije baš OK koristiti heš vrijednost kao ključ jer heš nije bijektivno preslikavanje....

u suštini heš je takav da može da dodijeli istu vrijednost za različite stringove, a to u tvom slučaju ne valja.

samo razmisli koliko imaš kombinacija stringova sa 256 karaktera (dakle sa 256 bajtova), a koliko sa integerom-32 bita (4 bajta), pa će ti biti jasno zašto ne valja heš.

dakle odnos im je ( 2^2048 )/( 2^32 )=2^2016 iliti za svaku vrijednost ključa koju daje heš imaš 2^2016 različitih mogućnosti stringa

ti istina ne koristis 256, nego 254 karaktera (jer bi trebalo da je jedan terminator), ali to ne smanjuje previ[e računicu-opet je vrlo loš odnos

u suštini ako makneš karaktere koje ne koristiš, i uzmeš da će ti većina imena biti kratka dolaziš do mnogo manjeg broja (iliti boljeg odnosa), ali SAMO ako je taj algoritam brinuo o tome!!!!

ali svakako postoji realna opasnost da ce poneki neduplikat biti odbacen!


PS. pretpostavio sam da koristiš integer i to standardni, iako sa 64-bitnim integerom možeš da (istina bezznačajno) poboljšaš odnos

[Dejan]

Da, ali ni jedan string ne prilazi ni blizu duzini MAX_SIZE, a kao Hash funkciju koristim ovu:

typedef  unsigned long  int  ub4;   /* unsigned 4-byte quantities */
typedef  unsigned       char ub1;   /* unsigned 1-byte quantities */

#define mix(a,b,c) \
{ \
  a -= b; a -= c; a ^= (c>>13); \
  b -= c; b -= a; b ^= (a<<8); \
  c -= a; c -= b; c ^= (b>>13); \
  a -= b; a -= c; a ^= (c>>12);  \
  b -= c; b -= a; b ^= (a<<16); \
  c -= a; c -= b; c ^= (b>>5); \
  a -= b; a -= c; a ^= (c>>3);  \
  b -= c; b -= a; b ^= (a<<10); \
  c -= a; c -= b; c ^= (b>>15); \
}

ub4 JenkinsHash(ub1* k, ub4 length, ub4 initval)
{
   register ub4 a,b,c,len;

   /* Set up the internal state */
   len = length;
   a = b = 0x9e3779b9;  /* the golden ratio; an arbitrary value */
   c = initval;         /* the previous hash value */

   /*---------------------------------------- handle most of the key */
   while (len >= 12)
   {
      a += (k[0] +((ub4)k[1]<<8) +((ub4)k[2]<<16) +((ub4)k[3]<<24));
      b += (k[4] +((ub4)k[5]<<8) +((ub4)k[6]<<16) +((ub4)k[7]<<24));
      c += (k[8] +((ub4)k[9]<<8) +((ub4)k[10]<<16)+((ub4)k[11]<<24));
      mix(a,b,c);
      k += 12; len -= 12;
   }

   /*------------------------------------- handle the last 11 bytes */
   c += length;
   switch(len)              /* all the case statements fall through */
   {
   case 11: c+=((ub4)k[10]<<24);
   case 10: c+=((ub4)k[9]<<16);
   case 9 : c+=((ub4)k[8]<<8);
      /* the first byte of c is reserved for the length */
   case 8 : b+=((ub4)k[7]<<24);
   case 7 : b+=((ub4)k[6]<<16);
   case 6 : b+=((ub4)k[5]<<8);
   case 5 : b+=k[4];
   case 4 : a+=((ub4)k[3]<<24);
   case 3 : a+=((ub4)k[2]<<16);
   case 2 : a+=((ub4)k[1]<<8);
   case 1 : a+=k[0];
     /* case 0: nothing left to add */
   }
   mix(a,b,c);
   /*-------------------------------------------- report the result */
   return c;
}