Bitove pole

Samostatné vypracování náročnějšího programu v libovolném programovacím jazyce (obvykle v jazyce C++) a příslušné vývojové a uživatelské dokumentace jako završení výuky individuálního programování. Tento program se může stát základem pro individuální projekt požadovaný k bakalářské zkoušce z informatiky. Zápočet bude udělen za vypracování detailní specifikace a předvedení rozpracované verze díla.

Bitove pole

Příspěvekod Eubie » 27. 3. 2006 15:07

Dobrý den kolegové,
potřeboval bych opravdu velkou radu.
Musim si nějak uložit pole bitů (doopravdy bitů). C i C++ mají knihovnu bitset(.h), ale rozměr vektorů bitů musí bejt znám už pri kompilaci a já potřebuju aby tahle dýlka byla nastavitelná v závislosti na parametru programu. Má někdo zkušenost/nápad jak na to, aniž bych si musel dělat vlastní třídu s konvertováním na inty atp?
Díky
Uživatelský avatar
Eubie
Matfyz(ák|ačka) level III
 
Příspěvky: 295
Registrován: 8. 10. 2005 14:35

Příspěvekod Eubie » 27. 3. 2006 18:01

Odpovím si sám, pokud má ale někdo nápady, uvítám je.
Po hodince hledání jsem našel milý projekt týkající se astronomického výzkumu a zde...
http://aips2.nrao.edu/code/casa/implement/Utilities/BitVector.h
je to důležité.
Uživatelský avatar
Eubie
Matfyz(ák|ačka) level III
 
Příspěvky: 295
Registrován: 8. 10. 2005 14:35

Příspěvekod sandius » 27. 3. 2006 21:32

No, podle me neni moc co vymyslet (resp. me nic moc jineho nenapada). Reprezentoval bych to jako pole unsigned intu, kde hodnotu n-teho bitu ziskam tak, ze se podivam, do ktereho indexu toho pole to padne, tj. n / sirka_slova, a potrebny bit je na pozici n % sirka_slova. Cili cosi ala

Kód: Vybrat vše

#define WORD_WIDTH  (sizeof(int) * 8)

int get_bit(const unsigned * bitset, int n)
{
  return (bitset[n / WORD_WIDTH] & (1u << (n % WORD_WIDTH))) != 0;
}


Pro set_bit analogicky. (Slo by to teda udelat i preprocesorem, ale to je trosku prasecina.) V C++ imho staci jenom zabalit do tridy a hlidat meze toho pole. Operace jako and/or/xor dvou mask nebo negace masky jde udelat tak, ze se projdou obe ty pole a zavola se and/or/xor na vsecky prvky se stejnejma indexama, negace se provede pomoci operace ~ na kazdy prvek.

To pole muze byt samozrejme libovolne velike, pokud ho budes alokovat dynamicky.

Je to ono?
Uživatelský avatar
sandius
Matfyz(ák|ačka) level II
 
Příspěvky: 60
Registrován: 7. 1. 2005 00:52
Bydliště: Tabor / Troja

Příspěvekod Eubie » 27. 3. 2006 21:52

Super, díky za tip. Myslim, že to ono je, ale kromě toho, aby to řešilo co je potřeba bych od toho potřeboval extrémní efektivitu. V typickým případě bude moje aplikace mít zhruba 64 GB takovejchle bitovejch polí a bude je procházet a přetřiďovat a prohazovat indexy a kdesi cosi, takže bych se operace přístupu na bit způsobem několikrát << bál, jestli to není příliš pomalý. Rozhodně to má ale jednodušší implementaci, tak pouvažuju, protože do toho kódu, na kterej jsem posílal odkaz, opravdu nemam šanci proniknout.
Ještě jednou díky.

EDIT: Po konzultaci s doktorem Bednárkem se ukázalo, že autoři C++ už na tohle pomysleli a bitové pole se skrývá pod tajuplným názvem
vector<bool> (opravdu ukládá po bitech)
Uživatelský avatar
Eubie
Matfyz(ák|ačka) level III
 
Příspěvky: 295
Registrován: 8. 10. 2005 14:35

Příspěvekod hippies » 9. 5. 2006 00:07

Eubie píše:...
EDIT: Po konzultaci s doktorem Bednárkem se ukázalo, že autoři C++ už na tohle pomysleli a bitové pole se skrývá pod tajuplným názvem
vector<bool> (opravdu ukládá po bitech)


Jo tak na vector<bool> už sem taky přišel, .. konkrétně, když sem potřeboval napsat vlastní operator[] pro přístup na privátního člena třídy typu vector, pro vector<bool> prostě neuděláte v[x]=v[y], protože nejde dostat referenci na bit, která je potřeba v levé části příkazu;), dost sem se s tim natrápil, než sem na to přišel (když je to schovaný za devatero šablonami a devatero virtuálními děděními, tak se to hledá fakt blbě, proč to vlastně nejde):)
Uživatelský avatar
hippies
Admin(ka) level I
 
Příspěvky: 990
Registrován: 29. 9. 2004 11:46
Bydliště: Mladá Boleslav
Typ studia: Informatika Mgr.
Login do SIS: procj4am

Příspěvekod Eubie » 9. 5. 2006 05:56

Přístě si stačí přečíst dokumentaci, kde je explicitně řečeno, že ta reference udělat nejde:)
Uživatelský avatar
Eubie
Matfyz(ák|ačka) level III
 
Příspěvky: 295
Registrován: 8. 10. 2005 14:35

Příspěvekod hippies » 9. 5. 2006 12:24

Eubie píše:Přístě si stačí přečíst dokumentaci, kde je explicitně řečeno, že ta reference udělat nejde:)

No na to abych si uvědomil, že ta reference udělat nejde si nepotřebuju číst dokumentaci, to je naprosto jasný, problém byl v tom, že to bylo v tak složité konstrukci, že sem nevěděl, že je problém právě v tomhle.
Uživatelský avatar
hippies
Admin(ka) level I
 
Příspěvky: 990
Registrován: 29. 9. 2004 11:46
Bydliště: Mladá Boleslav
Typ studia: Informatika Mgr.
Login do SIS: procj4am

Re: Bitove pole

Příspěvekod ktx » 9. 5. 2006 19:41

Eubie píše:Dobrý den kolegové,
potřeboval bych opravdu velkou radu.
Musim si nějak uložit pole bitů (doopravdy bitů). C i C++ mají knihovnu bitset(.h), ale rozměr vektorů bitů musí bejt znám už pri kompilaci a já potřebuju aby tahle dýlka byla nastavitelná v závislosti na parametru programu. Má někdo zkušenost/nápad jak na to, aniž bych si musel dělat vlastní třídu s konvertováním na inty atp?
Díky


mne kedysi stacilo toto :)
Kód: Vybrat vše
get( n ) :
   idx = n >> 5;
   off = n & 0x1f;
   return ( a[ idx ] & ( 1 << off ) ) >> off

set( n ):
   idx = n >> 5;
   off = n & 0x1f;
   a[ idx ] |= 1 << off;


EDIT: nj, som neprecital cele forum, nejak podobne ste to vyriesili, ale pouzivat objekty na bitove polia, hmm
ktx
Matfyz(ák|ačka) level I
 
Příspěvky: 27
Registrován: 20. 10. 2005 14:40
Typ studia: Matematika Mgr.

Příspěvekod dr.Bik » 25. 5. 2006 23:56

64GB? Hodne stesti, chlape... Pak, ze nikdo nepotrebuje 64bit :-)
No ale stejne si myslim, ze se ti to ani poradne nevejde do ram+swap (nebo bych chtel mit tvou masinu)

<< bitovejch shiftu se neboj, jsou to velci kamaradi a hlavne rychli kamaradi (a nemaj radi, kdyz jim vykas)

Pouziti intu, no, nevim, nevim. Tam je trosku problem s tim, ze int snad ani nema podle specifikace C/C++ danou velikost nebo je to tam nejaky divny. Nastesti skoro vsude je to 4B. Kdyz ses straspytel jako ja, tak tam narves 16 bitu, ale potom mas pulku toho, co sis zabral v coudu, takze tomu bych nerikal super efektivni

S 64GB mas i problem s tim, jak to chces adresovat, pac to je opravdu hoooooodne dat (simulujes vesmir, nebo co?)
Jednou z hlavních příčin zániku Římského imperia bylo, že bez nuly nemohli Římané ohlásit úspěšné ukončení svých céčkových programů.
Uživatelský avatar
dr.Bik
Matfyz(ák|ačka) level II
 
Příspěvky: 73
Registrován: 9. 6. 2005 13:13
Bydliště: Prágl

Příspěvekod hippies » 26. 5. 2006 00:34

dr.Bik píše:S 64GB mas i problem s tim, jak to chces adresovat, pac to je opravdu hoooooodne dat (simulujes vesmir, nebo co?)


Muj odhad je ze dva a porovnava je:)
Uživatelský avatar
hippies
Admin(ka) level I
 
Příspěvky: 990
Registrován: 29. 9. 2004 11:46
Bydliště: Mladá Boleslav
Typ studia: Informatika Mgr.
Login do SIS: procj4am


Zpět na PRG033 Ročníkový projekt - specifikace

Kdo je online

Uživatelé procházející toto fórum: Žádní registrovaní uživatelé a 1 návštěvník