Zapisanie dużej tablicy "binarnej"

Odpowiedz Nowy wątek
2006-11-14 15:19
0

Witam, mam mapkę 10000 pól x 10000 pól - w sumie 100 mega pól, chodzi mi o to żeby jak najszybciej zapisać i odczytać stan mapy - tj. w których miejscach, powiedzmy gracz, już był
gdyby każdemu polu przyznać 1 bit to zapis by zajmował ponad 10MB co odpada, zapisuję więc stan jako współrzędne prostokątów, w praktyce taki zapis zajmuje koło 60kB co też jest trochę za dużo ale już w miarę, chodzi tylko o to że zapisanie tym sposobem zajmuje jakieś 2 sekundy, a odczytanie prawie jedną, więc stanowczo zbyt długo. Dodatkowo w porywach ten zapis mógłby też wygenerować olbrzymi wynik.

Czy jest może jakiś algorytm który byłby mi pomocny w tym ? Ewentualnie czy ktoś ma jakiś pomysł na to poza "spakuj zipem" ?

Czynnikiem który mógłby pomóc przy optymilizowaniu tego wyniku myślę że mógłby być fakt że jedynki muszą być ze sobą złączone krawędzią, więc odpadają porozrzucane bity czy ukośne linie ...


Dwie zasady gwarantujące sukces:
1. Nigdy nie mów nikomu wszystkiego<span style="color: white">

Pozostało 580 znaków

2006-11-14 15:25
Luc
0

to mapa do jakiegoś RTSa?
10k x 10k pól to ogromna mapa. Te pola to są piksele, czy podzieliłeś mapę na kafle?

Pozostało 580 znaków

2006-11-14 16:32
0

Coś pochodnego BSP, albo OctTree. Dzielisz planszę wg każdej osi na połowę. Zapisujesz sobie to w postaci drzewa. Jeśli w którejś połowie nikt nie był, wskaźnik na tą połowę jest nil, jeśli był, wskaźnik na tę połowę jest wskaźnikiem na opis połówek tej połowy. itd.

Planszę 2D możesz dzielić albo na ćwiartki albo wg. dwóch drzew - po jednym do każdej osi.

TElement = array[0..3] of Pointer;

Jeśli w danej ćwiartce nikt nie był, wartość pola jest nil, jeśli był, pole wskazuje na taką samą tablicę dla mniejszego podziału.

Taka metoda jest dobra, jeśli postać nie jest w stanie zająć całej planszy. Jeśli jest, warto dodać jeszcze jedno pole - jeśli gracz był we wszystkich ćwiartkach danego obszaru, pola są ustawiane na nil (kasowanie podtablic), a zmienna jest ustawiana - cały zapełniony obszar nie wymaga więc podtablic.

Podział na podtablicę powinieneś u siebie zrobić do 14 stopnia, bo 2^14> 10000; Wtedy tablica 14 stopnia będzie dla 4 obszarów 1x1.

DOPISANE:

Załóżmy, że obszar dzielimy na ćwiartki numerowane:

1 0

2 3

Załóżmy taki obszar:
user image
Dla niego można by na przykład zrobić coś takiego:

TElement = packed record
  PodObszary: array[0..3] of Pointer;
  Zajety: boolean;
end;

Dla tej mapy wynik w pamięci może być taki (@ADRES: [PodObszar0, PodObszar1, PodObszar2, PodObszar3], Zajety):

@0: [nil, 1, 2, -1], FALSE //Cała mapa
@1: [nil, -1, nil, -1], FALSE //Podobszar1
@2: [-1, nil, nil, nil], FALSE //Podobszar2

Zauważ, że w dalszych podziałach już nie dzielisz Podobszar0, bo wg mapy głównej jest pusty (nil) - nigdy tam nie było zapisu, oraz PodObszar3, bo wg mapy głównej ma -1, w więc jest cały zajęty. Pozostałę 2 podobszary dzielisz na takiej samej zasadzie. Tutaj mapa jest 4x4 więc robisz tylko 2 podziały (2^2) - główny i ćwiartek, przy mapie 8x8 miałbyś jeszcze ćwiartki ćwiartek, itd.

Musisz też zadbać, by żaden element nie miał adresu -1 (co przy niejednobajtowym rozmiarze rekordu już samo przez się nie jest możliwe).

Jeśli ktoś dużo będzie zwiedzał pewien obszar powiedzmy w rogu lewym, górnym, pamięci w ogóle nie będzie zajmowała część prawa czy dolna (czyli oszczędzasz informacje o 3 ćwiartkach dużej mapy i iluś podpodpodziałach w lewej górnej części.

Ale zamieszałem..


<font color="red">Konto porzucone</span>

Dzięki wszystkim forumowiczom za lata wspólnych dyskusji; miłej zabawy w programowanie!
Sławomir 'Szczawik' Włodkowski

Pozostało 580 znaków

2006-11-14 18:31
0

raczej nie zamieszałeś, dzięki za odpowiedzi
to nie są pixele tylko kawałki mapy
zresztą dobrze nie wiem bo to nie dla mnie, też coś nie wierzę w taką wielkość, w każdym razie, powyższy pomysł jest w miarę jeśli ktoś łazi w miejscu
zaimplementowałem to na szybko i dość długo się to zapisuje, ale tym się akurat nie przejmuję bo chciałem tylko sprawdzić rozmiar i praktycznie kod jest niezoptymilizowany
a rozmiar też zależnie od rozmieszczenia i chyba niezbyt ciekawy, dla zapełnionej całej planszy nawet mi się nie chciało czekać na rezultat bo troszkę to trwało, a wynik dla zapełnionych 50k pól ułożonych w miarę w jednym miejscu wyszedł też koło 60kB ...


Dwie zasady gwarantujące sukces:
1. Nigdy nie mów nikomu wszystkiego<span style="color: white">

Pozostało 580 znaków

2006-11-15 12:42
0

A gdyby pamiętać ścieżkę oraz punkt startowy? Kolejny krok można wykonać w jednym z 4 kierunków, czyli 2 bity. 50k punktów to 100k bitów=12.5 k bajta.

Może nawet nie warto trzymać kwadratowej tablicy tylko tą właśnie ścieżkę?
Sprawdzenie czy punkt był już odwiedzony powinno być dość chyże, a zapis i odczyt błysk.

Pozostało 580 znaków

2006-11-15 15:18
0
Xitami napisał(a)

...

wiesz że mnie oświeciłeś
to był mój pierwszy pomysł tylko patrzałem na niego ze złej strony, próbowałem napisać algorytm który wyznaczy właśnie w ten sposób ścieżkę mając tablicę bitów, a zapomniałem że ta ścieżka jest już gotowa bo wyznacza ją user i wystarczy ją spisać
znowu gorzej jak się kręci w kółeczko, wtedy musi pamiętać wszystkie jego ruchy, więc nawet jak już odwiedził prawie całą mapę (co wydaje mi się niemożliwe) to dalej zapis jego ścieżki się powiększa w oczekiwaniu że kiedyś np wejdzie jeszcze na jedno pole na którym nie był

każda z tych metod ma swoje plusy i minusy ale niewątpliwie ta chociaż będzie najszybsza i najłatwiejsza w implementacji (praktycznie zero kodu), zapis to mikrosekunda bo można do poprzedniego zapisu zwyczajnie dopisać dwa bity, gorzej z odczytem bo żeby sprawdzić konkretny fragment to ten sposób wymaga przeanalizowania od początku do końca (co i tak powinno być szybsze od poprzednich)

ale jeśli ktoś chodzeniem zrobi piękny kwadracik 1000x1000 = 1 mega pól to w tym zapisie zajmie to w najlepszym razie 244KB, a moim pierwszym sposobem np zajmie 8 bajtów, sposobem Szczawika też niewiele więcej

trzeba by było te wszystkie sposoby sprawdzić dokładnie w praktyce, najfajniej by było napisać funkcję która wszystko upakuje na wszystkie sposoby a potem zobaczy którym najmniej wyszło - to jest rozwiązanie chyba skrajne w stronę oszczędności pamięci, a druga skrajność czyli względem szybkości to zwykłe zapisanie tablicy

jak ktoś ma jeszcze propozycję to walić śmiało ;)


Dwie zasady gwarantujące sukces:
1. Nigdy nie mów nikomu wszystkiego<span style="color: white">

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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