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.
Uživatelský avatar
Eubie
Matfyz(ák|ačka) level III
Příspěvky: 295
Registrován: 8. 10. 2005 15:35
Typ studia: Informatika Bc.
Kontaktovat uživatele:

Bitove pole

Příspěvek od Eubie »

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 15:35
Typ studia: Informatika Bc.
Kontaktovat uživatele:

Příspěvek od Eubie »

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/impleme ... itVector.h
je to důležité.
Uživatelský avatar
sandius
Matfyz(ák|ačka) level II
Příspěvky: 60
Registrován: 7. 1. 2005 00:52
Typ studia: Informatika Bc.
Bydliště: Tabor / Troja
Kontaktovat uživatele:

Příspěvek od sandius »

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
Eubie
Matfyz(ák|ačka) level III
Příspěvky: 295
Registrován: 8. 10. 2005 15:35
Typ studia: Informatika Bc.
Kontaktovat uživatele:

Příspěvek od Eubie »

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
hippies
Admin(ka) level I
Příspěvky: 990
Registrován: 29. 9. 2004 12:46
Typ studia: Informatika Mgr.
Bydliště: Mladá Boleslav
Kontaktovat uživatele:

Příspěvek od hippies »

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
Eubie
Matfyz(ák|ačka) level III
Příspěvky: 295
Registrován: 8. 10. 2005 15:35
Typ studia: Informatika Bc.
Kontaktovat uživatele:

Příspěvek od Eubie »

Přístě si stačí přečíst dokumentaci, kde je explicitně řečeno, že ta reference udělat nejde:)
Uživatelský avatar
hippies
Admin(ka) level I
Příspěvky: 990
Registrován: 29. 9. 2004 12:46
Typ studia: Informatika Mgr.
Bydliště: Mladá Boleslav
Kontaktovat uživatele:

Příspěvek od hippies »

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.
ktx
Matfyz(ák|ačka) level I
Příspěvky: 27
Registrován: 20. 10. 2005 15:40
Typ studia: Matematika Mgr.

Re: Bitove pole

Příspěvek od ktx »

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
Uživatelský avatar
dr.Bik
Matfyz(ák|ačka) level II
Příspěvky: 73
Registrován: 9. 6. 2005 14:13
Typ studia: Informatika Bc.
Bydliště: Prágl
Kontaktovat uživatele:

Příspěvek od dr.Bik »

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
hippies
Admin(ka) level I
Příspěvky: 990
Registrován: 29. 9. 2004 12:46
Typ studia: Informatika Mgr.
Bydliště: Mladá Boleslav
Kontaktovat uživatele:

Příspěvek od hippies »

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:)
Odpovědět

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