[L.....G]

Cześć,

Pytanie z #programowanie a może bardziej #algorytmy, otóż chcę wygenerować "plik"/tablicę/to niekluczowe bardzo duży.
Charakterystyka tego tych danych jest taka, że to, a jakże by inaczej, jedynka lub zero, z tym, że jedynek jest bardzo mało w stosunku do zer, chcę aby te dane zajmowały oczywiście jak najmniej pamięci.

Ok, nasuwa się oczywiste rozwiązanie, spakować to jakoś.
Super, jest tylko jeden warunek, chcę mieć jak najszybszy dostęp do danych, a przez dostęp rozumiem, że podaje index nazwijmy to bitu, i chcę mieć informację zwrotną czy tam jest jeden czy zero.

Jedynek w stosunku do zer nie jest na tyle mało, aby opłacało się po prsotu zapisać numery indeksów jedynek, gdyż ilość danych jest duża i zapisanie, aczkolwiek sprawa do rozważenia, muszę policzyć to.

Drugim z kategorii trywialnych (ale już nie szybkich) rozwiązań jest, zapisanie w stylu, po kolei, ile jest zer, jedynek, zer, jedynek itd.

Czuję, że są jakieś inne zajebiste algorytmy tylko teraz nic mi do głowy nie przychodzi.

Ma ktoś może jakiś genialny pomysł? ( ͡° ͜ʖ ͡°)

[-PPP-]

zapisanie w stylu, po kolei, ile jest zer, jedynek, zer, jedynek itd.

@LowcaG to.

[dog_meat]

@LowcaG: O ile mi wiadomo, to po skompresowaniu, dostęp zawsze będzie wolniejszy (będziesz zużywał mniej pamięci, kosztem większej pracy procesora)

[TheNewIcek]

@LowcaG: pytanie ile tych danych masz i jak bardzo chcesz skompresowac. Rozumiem, ze juz trzymasz jeden bit w jednym bicie a nie np. w "znaku"? :D

[P.....s]

@TheNewIcek: O to to. Jeżeli się do tego zastosujesz a wcześniej trzymałes jako znak o już będziesz zajmował 8x mniej miejsca na dysku ;)

[kotit]

@LowcaG: Jeżeli chcesz uzyskać jakąś konkretną odpowiedź, podaj nieco więcej informacji.

Tak jak wspomniał @TheNewIcek:
1) Ile tych danych masz ?
2) Jak bardzo chcesz skompresować ?

A dodatkowo:
3) Jaki jest przybliżony stosunek jedynek do zer ?
4) Czy w danych występują długie ciągi zer/jedynek ?
5) Chcesz mieć szybki dostęp, a czy zależy Ci też na szybkim zapisie tych danych ?

Im więcej informacji podasz, tym większe masz

[N.....n]

Możesz spróbować poszukać jak implementowane są kontenery: sparse array / list.
Tylko często mają ograniczenie na stały rozmiar tablicy.

[L.....G]

@dog_meat: nie no oczywiście nie spodziewam się poprawy szybkości ;)

@TheNewIcek: tak już jest 8 bitów w bajcie. A ile ich mam? Postawił bym pytanie inaczej mam np.X ramu i chce zmieścić jak najwięcej bez utraty możliwości odczytu konkretnego bitu.

@Philopolemus_Fronius: jak wyżej. Na to już wcześniej wpadłem ;)

@kotit:

1. Iść danych jest tak jak napisałem powyżej. Czyli jest ich bardzo bardzo bardzo dużo i wychodzę od

[kotit]

@LowcaG: Nadal podajesz mało tych danych, ale mam pewien pomysł, stwórz sobie tablicę liczb (zacznij od short unsigned int) i każda liczba w tej tablicy oznacza ilość zer albo jedynek.

Przykład:
Dane oryginalne: 0000 111 00000000 1 00000000 1 0 1 0
Dane zakodowane: 4,3,8,1,8,1,1,1,1

Zakładając, że kodujesz w ten sposób już istniejący wcześniej ciąg, złożoność zapisu i odczytu jest liniowa z ilością elementów (przy najprostszym przeszukiwaniu, ale wydaje mi się,

[kotit]

@LowcaG: Zauważyłem że to rozwiązanie wysypie się, kiedy liczba zer albo jedynej w jednym ciągu będzie większa niż ilość jaką może pomieścić zastosowany przez Ciebie typ, ale to też da się obejść stosując dodatkową flagę, niestety nie mam teraz czasu, żeby to opisać, więc dokładny opis podeślę później.

[L.....G]

@kotit: a dzieki dzięki, nie musisz opisywać, bo akurat w tę stronę na razie będę szedł, i myślę, że z tym nie będę miał większych problemów(jeśli chodzi o implementację), nawet w drugiej tablicy co jakiś czas (ekstremalnie skracając myśl) dam liczbę narastającą "bitów", co by szybko szukać odpowiednich przedziałów.

TAk, że to rozwiązanie jest bieżącym rozwiązaniem, myślałem o tym czy nie ma innych jakiś bardziej wymyślnych pomysłów.

Jak np. jakaś analiza

[L.....G]

ok, wszystko już wiem, jak to zrobię, dziękuję wszystkim za odpowiedzi.

Tak wiec... temat zamykam ( ͡° ͜ʖ ͡°)