c++ - duże słowa bitowe

0

Witam,
Czy jest jakiś sposób, aby w c++ zadeklarować duże słowo bitowe (długość do 40000 bitów) w taki sposób, żebym naraz miał dostęp do całego słowa? std::vector odpada, no chyba że jest jakaś funkcja, która zwraca całą zawartość RAMU między vector::begin() i vector::end(). Muszę wykonywać dość dużo operacji na tymże słowie, a jeśli deklaruję to przez wektor bool-ów lub int-ów, to złożoność algorytmu staje się zbyt duża. Musiałbym znaleźć sposób, by wykonywać operacje w czasie liniowym, a więc słowo musi być w jednej zmiennej. Jak to zrobić?

Pozdrawiam

0

std::vector odpada, no chyba że jest jakaś funkcja, która zwraca całą zawartość RAMU między vector::begin() i vector::end().

Generalnie jednym z założeń std::vector jest to, że wszystkie elementy są przechowywane liniowo. Znaczy to, że możesz wziąć wskaźnik do *begin() i normalnie go iterować aż do *end(). Natomiast tutaj ważna uwaga - wyjątkiem jest specjalizacja std::vector<bool>, która tego założenia spełniać nie musi (i najczęściej NIE spełnia).
Z std::vector<int> możesz w ten sposób skorzystać. std::bitset ma z kolei stały rozmiar.

0

niestety, operacje na owym szablonie bazują na pętlach, wiec złożoność nie ulega poprawie, a dodatkowo zużywa więcej RAMu

0

śmiem zaproponować tablicę bajtów albo intów

0

dokładnie tak mam - tablicę int-ów, ale mimo wszystko złożoność jest zbyt duża

0

Ale jaka złożoność, o co ci chodzi?

0

szybciej niż tablica nie da rady - dostęp O(1).

0

dostęp do całej tablicy to złożoność 0(n)- n elementów * 0(1)

0

I w przypadku wektora jest ona większa?

0

@kajak4Cpp, nie wiem czy dobrze cie rozumiem, szukasz sposobu na przejrzenie N elementów w czasie mniejszym niż O(n) ?

0

W przypadku std::bitset operacje są znacznie wolniejsze (łącznie z resztą operacji złożoność programu jest 0(x*n^2) ), a RAMu żre prawie 3 razy więcej, więc raczej jest większa

@_13th_Dragon: Szukam sposobu, żeby móc traktować całą tablicę w operacjach tak jak pojedynczą zmienną / słowo bitowe

0

Nie da się. Na jeden raz możesz operować maksymalnie tylko na tym, co wejdzie w rejestr. (Procesory >=Sandy Bridge/Bulldozer - 256 bitów) Każda inna operacja "na jeden raz" to ukryte wykonanie w pętli. Nie unikniesz tego.

Napisz to sobie na GPU, wtedy wykonasz te wiele operacji równolegle. :-P

0
kajak4Cpp napisał(a):

Szukam sposobu, żeby móc traktować całą tablicę w operacjach tak jak pojedynczą zmienną / słowo bitowe

Całości nie możesz zaś możesz kawałkami po np 32 bity.
jak potrzebujesz X bitów to tworzysz tablice:
uint32 tb[(X+31)>>5]; // Ceil(X/32), uint32 odpowiedni 32 bitowy typ.
i możesz operować fragmentami po 32 bity na raz.
Możesz też zrobić typ generyczny:

template <size_t Size> struct BITY { uint32 B[Size]; };

BITY<((X+31)>>5)> A,B;
A=B;
0

@kajak4Cpp: Prawdopodobnie chodzi Ci o coś o nazwie "bitmap index".

Opis na wiki: http://en.wikipedia.org/wiki/Bitmap_index
Pierwsza znaleziona biblioteka: http://code.google.com/p/lemurbitmapindex/

To może też być pomocne (kompresja): http://wiki.postgresql.org/wiki/Bitmap_Indexes

1 użytkowników online, w tym zalogowanych: 0, gości: 1