Warsztat.GD

Programowanie => Matematyka i fizyka => Wątek zaczęty przez: Sarann w Wrzesień 02, 2017, 05:28:49

Tytuł: Kompresja i optymalizacja mapy
Wiadomość wysłana przez: Sarann w Wrzesień 02, 2017, 05:28:49
Sprawa wygląda tak, że mam dwuwymiarową mapę o wielkości 1m^2, lub większą. Każde pole na mapie zajmuje 1 bajt.
Jak mogę to zoptymalizować, by taka mapka 1m^2 nie zajmowała 1000 GB? Możliwe jest, iż będzie dużo więcej pustych pól niż tych wypełnionych, nawet w proporcji 100 do 1.

W RAM z tego co wiem mogę trzymać w jednej chwili fragment mapy o wielkości 100k^2, czyli około 10 GB. Jednak nawet kiedy wczytuję fragmenty tylko wtedy, kiedy są potrzebne, cała mapa zajmować będzie aż 1000 GB dysku.

Przykładowa mapka o wielkości 32^2:
(http://i.imgur.com/g5mOpFE.png)

No to czekam na geniuszy, którzy wpadną na pomysł jak skompresować takie coś.
Tytuł: Odp: Kompresja i optymalizacja mapy
Wiadomość wysłana przez: Kurak w Wrzesień 02, 2017, 06:43:59
https://en.m.wikipedia.org/wiki/Sparse_matrix

Inna sprawa to skad te dane pochodza. Rzadko sie zdarza zeby taka ilosc danych nie byla po prostu wygenerowana, i w takiej sytuacji lepiej po prostu deterministycznie generowac na zadanie.

Sa ofc przypadki gdzie faktycznie taka ilosc danych albo i wiecej jest przechowywana, wtedy optymalnym rozwiazaniem jest dokupic wiekszy dysk i troche ramu ;)
Tytuł: Odp: Kompresja i optymalizacja mapy
Wiadomość wysłana przez: Karol w Wrzesień 02, 2017, 13:34:36
Jak mogę to zoptymalizować, by taka mapka 1m^2 nie zajmowała 1000 GB? Możliwe jest, iż będzie dużo więcej pustych pól niż tych wypełnionych, nawet w proporcji 100 do 1.
Hmm, czyli jedno pole ma wielkość nanometra? ;)

No to czekam na geniuszy, którzy wpadną na pomysł jak skompresować takie coś.
Powodzenia :P
Tytuł: Odp: Kompresja i optymalizacja mapy
Wiadomość wysłana przez: wezu w Wrzesień 02, 2017, 17:07:49
Najłatwiej to zrobić mniejszą mapę.

Weźmy czarny scenariusz, że 1 punkt mapy w jakiś sposób odpowiada 1 pixelowi na ekranie i ktoś to całe ustrojstwo wyświetla na ekranie 8k. Na raz na ekranie zmieści się 7680 × 4320 punktów z twojej mapy, która ma  1000000x1000000.

Podziel swoją mapkę na 4, potem podziel każdy z każdy z kwadratów na 4, potem każdy z podzielonych kwadratów podziel jeszcze raz na 4 i zrób tak 64 razy. Potem... nie wiesz co, potem zatrzymaj sobie jeden taki fragment, wywal resztę i zastanów się jeszcze raz czy na pewno jest ci potrzeba tak wielka mapa. Co to będzie? Symulator układu słonecznego w skali?
Tytuł: Odp: Kompresja i optymalizacja mapy
Wiadomość wysłana przez: Sarann w Wrzesień 02, 2017, 19:39:16
Wiadomo, że tak wielka mapa nie zmieści się na ekranie ;)

Ale można ją przeskalować do mniejszych rozmiarów, być może tracąc przy tym nieco mało istotnych szczegółów.

Żaden symulator Układu Słonecznego, tylko automat komórkowy Mrówki Langtona :)
Z nieco zmodyfikowanymi zasadami oczywiście.

Może ten przykład z dwuwymiarową mapką o takiej wielkości jest nieco naciągany, ale identyczna wielkość będzie w przypadku czterowymiarowej mrówki o dość małym rozmiarze, bo jedynie 1000^4. Taką ilość spokojnie da się wyświetlić na większości ekranów w postaci trójwymiarowej. Mimo to także zajmować będzie 1000 GB.
W tym przypadku niemożliwe będzie wczytywanie danych z dysku na bieżąco, bo prędkość wczytywania musiałaby być większa od jakichś 15 GB/s.
Tytuł: Odp: Kompresja i optymalizacja mapy
Wiadomość wysłana przez: matheavyk w Wrzesień 02, 2017, 22:04:45
Kurak świetnie podlinkował do Sparse Matrix. A tutaj link do dwóch sposobów przechowywania: http://www.alglib.net/matrixops/sparse.php#header0

W zależności od gęstości tej mapy (czyli liczby niezerowych punktów) zyskasz (lub stracisz) więcej lub mniej.

Na pewno znajdziesz w internecie dużo materiałów naukowych np. pod hasłem "storing sparse matrices". Ale z tego, co widzę, większość formatów przechowywania tych macierzy kładzie duży nacisk na możliwość wykonywania jakichś tam operacji na skompresowanych macierzach, a nie na jak największą kompresję. Może jednak coś fajnego znajdziesz ;p
Tytuł: Odp: Kompresja i optymalizacja mapy
Wiadomość wysłana przez: wezu w Wrzesień 02, 2017, 22:35:59
Sparse Voxel Octrees:
https://pdfs.semanticscholar.org/2c9a/6d9b27c1eccd438d0685ad4c04c5a9e1d311.pdf

W 4D to chyba nie będzie octree tylko sedectree?
Tytuł: Odp: Kompresja i optymalizacja mapy
Wiadomość wysłana przez: Liosan w Wrzesień 02, 2017, 22:45:35
To wszystko co poprzednicy + proponuję poczytać https://en.wikipedia.org/wiki/Page_replacement_algorithm, przyjmując że jeden fragment drzewa to "strona" pamięci w rozumieniu tych algorytmów, żeby dobrać jakiś sensowny sposób wyboru fragmentu drzewa do usunięcia z pamięci i serializacji na dysk.

Liosan
Tytuł: Odp: Kompresja i optymalizacja mapy
Wiadomość wysłana przez: Iwan91 w Wrzesień 03, 2017, 00:03:19
Wydaje mi się, że w tym przypadku można zastosować run length encoding. Powinno to zredukować dość znacznie rozmiar.
https://en.wikipedia.org/wiki/Run-length_encoding

Znalazłem jeszcze coś takiego jak Position Aware RunLength:
https://twistedpairdevelopment.wordpress.com/2011/06/10/run-length-encoding-with-positioning-information-in-python/

edit1: Kiedyś się bawiłem kompresją danych dla gry ala minecraft i napisałem bibliotekę w javie do tego
https://github.com/Iwan91/PositionAwareRunLengthEncoding-java
Tytuł: Odp: Kompresja i optymalizacja mapy
Wiadomość wysłana przez: Sarann w Wrzesień 03, 2017, 14:11:50
Dzięki za propozycje, sprawdzę i podeślę rezultaty ;)