Infinite Bitmap [zamknięta]

Chciałbym zbudować bitmapę podczas uruchamiania. Mapa bitowa powinna być skalowalna ze wszystkich stron, a dostęp do pikseli powinien być cichy i wydajny.

Niektóre ilustracje http://img546.imageshack.us/img546/4995/maptm.jpg

Pomiędzy i po poleceniach pokazanych na obrazku Map.setPixel () i Map.getPixel () powinny ustawić / zwrócić dane zapisane w mapie bitowej.

Nie oczekuję, że implementacja będzie tylko koncepcją alokacji pamięci w taki sposób, że setPixel () / getPixel jest tak szybki, jak to możliwe.

Jeśli extend()operacja musi być dość szybka, Quadtree może być dobrym wyborem; w rzeczywistości nie wymagałoby to nawet jawnych operacji rozszerzania. Trzeba przyznać, że nie zapewniłoby to optymalnej wydajności losowego dostępu do poszczególnych pikseli, ale twój komentarz mówi, że twoją podstawową operacją jest iteracja nad pikselami, co poczwórne drzewo może zrobić bardzo szybko, być może prawie tak szybko, jak implementacja oparta na macierzy (i szybsza jeśli iteracja nie zawsze zachodzi w ten sam sposób, w jaki układana jest matryca).

Twoje wymagania brzmią tak, jakbyś próbował wdrożyć automat komórkowy, taki jak Game of Life. Możesz rzucić okiem na Hashlife , niezwykle wydajny sposób na wdrożenie Game of Life na nieskończonej siatce. Zauważ, że jest oparty na Quadtree, ale robi kilka bardzo inteligentnych dodatkowych optymalizacji w zależności od lokalizacji zasad gry.

@SecStone powiedział, że jest wystarczająco dużo czasu na operację rozszerzenia, więc najłatwiejszym i najskuteczniejszym sposobem przechowywania pikseli jest użycie pojedynczej płaskiej lub dwuwymiarowej tablicy, ponieważ wtedy piksele są dostępne w stałym czasie.

Ręcznie

Jeśli pamięć nie jest bardzo rzadkim zasobem, rozważam pracę w większych porcjach.
Oto pseudo-kod.

class Chunk {
    Chunk new(int size) {...}
    void setPixel(int x, int y, int value) {...}
    int getPixel(int x, int y) {...}
}

class Grid {
    Map<int, Map<Chunk>> chunks;
    Grid new(int chunkSize) {...}
    void setPixel(int x, int y, int value) {
         getChunk(x,y).setPixel(x % chunkSize, y % chunkSize, value);//actually the modulo could be right in Chunk::setPixel and getPixel for more safety
    }
    int getPixel(int x, int y) { /*along the lines of setPixel*/ }
    private Chunk getChunk(int x, int y) {
         x /= chunkSize;
         y /= chunkSize;
         Map<Chunk> row = chunks.get(y);
         if (row == null) chunks.set(y, row = new Map<Chunk>());
         Chunk ret = row.get(x);
         if (ret == null) row.set(x, ret = new Chunk(chunkSize));
         return ret;
    }
}

Ta implementacja jest dość naiwna.
Po pierwsze, tworzy porcje w getPixel (w zasadzie dobrze byłoby po prostu zwrócić 0 lub mniej, jeśli dla tej pozycji nie zdefiniowano żadnych porcji). Po drugie, opiera się na założeniu, że masz wystarczająco szybką i skalowalną implementację Map. O ile mi wiadomo, każdy przyzwoity język ma jeden.

Będziesz także musiał grać z rozmiarem porcji. W przypadku gęstych bitmap duży rozmiar fragmentu jest dobry, a dla rzadkich bitmap lepszy rozmiar mniejszego fragmentu. W rzeczywistości w przypadku bardzo rzadkich „wielkość porcji” 1 jest najlepsza, co powoduje, że same „porcje” stają się przestarzałe i redukuje strukturę danych do int mapy int mapy pikseli.

Z półki

Innym rozwiązaniem może być przeglądanie niektórych bibliotek graficznych. Są naprawdę całkiem dobrzy w rysowaniu jednego bufora 2D w innym. Oznaczałoby to, że po prostu przydzielisz większy bufor i wciągniesz do niego oryginał o odpowiednich współrzędnych.

Jako ogólna strategia: mając „dynamicznie rosnący blok pamięci”, dobrym pomysłem jest przydzielenie jego wielokrotności po zużyciu. Jest to dość obciążające pamięć, ale znacznie obniża koszty alokacji i kopiowania . Większość implementacji wektorowych przydziela dwukrotnie ich rozmiar, gdy zostanie przekroczony. Dlatego szczególnie, jeśli korzystasz z gotowego rozwiązania, nie rozszerzaj bufora tylko o 1 piksel, ponieważ zażądano tylko jednego piksela. Przydzielona pamięć jest tania. Ponowne przydzielanie, kopiowanie i wydawanie jest kosztowne.

Kilka wskazówek:

• Jeśli zaimplementujesz to jako tablicę jakiegoś integralnego typu (lub tablicę tablic ...), prawdopodobnie powinieneś zwiększyć tablicę podkładową o pewną liczbę bitów / pikseli za każdym razem, aby uniknąć konieczności przesuwania bitów podczas ich kopiowania. Wadą jest to, że zużywasz więcej miejsca, ale odsetek zmarnowanego miejsca spada, gdy bitmapa staje się większa.

• Jeśli korzystasz ze struktury danych opartej na mapie, możesz rozwiązać problem powiększania mapy bitowej, po prostu przenosząc argumenty współrzędnych x, y wywołań getPixeli setPixel.

• Jeśli korzystasz ze struktury danych opartej na mapie, potrzebujesz tylko wpisów mapy dla „jedynek”. „Zera” mogą wskazywać na brak wpisu. Oszczędza to znaczną ilość miejsca, zwłaszcza jeśli bitmapa składa się głównie z zer.

• Nie musisz używać mapy map. Możesz zakodować intparę x, y jako pojedynczy long. Analogicznego procesu można użyć do mapowania tablicy tablic na tablicę.

Wreszcie musisz zrównoważyć 3 rzeczy:

1. wydajność getPixeli setPixel,
2. wykonanie extend*operacji oraz
3. wykorzystanie przestrzeni.

Przed wypróbowaniem czegokolwiek bardziej skomplikowanego i jeśli nie jesteś w stanie utrzymać wszystkiego w pamięci, zachowaj prostotę i użyj dwuwymiarowej tablicy wraz z informacją o pochodzeniu układu współrzędnych. Aby go rozwinąć, skorzystaj z tej samej strategii, jak na przykład C ++ std :: vector: rozróżnij rzeczywisty rozmiar tablicy od pojemności tablicy i zwiększaj pojemność w porcjach, gdy limit zostanie osiągnięty. „pojemność” należy tutaj zdefiniować w kategoriach odstępów czasu (od_x, do_x), (od_y, do_y).

Może to wymagać pełnego przeniesienia pamięci od czasu do czasu, ale dopóki nie zdarza się to zbyt często, może być wystarczająco szybkie dla twojego celu (w rzeczywistości musisz spróbować / profilować to).

Absolutnie najszybszym sposobem uzyskania dostępu do pikseli jest dwuwymiarowa tablica indywidualnie adresowanych pikseli.

W przypadku rozszerzeń zacznij od prostej implementacji, która przenosi i kopiuje za każdym razem (ponieważ i tak będziesz potrzebować tego kodu). Jeśli profilowanie nie oznacza, że ​​spędzasz na nim dużo czasu, nie musisz go dalej doskonalić.

Jeśli profilowanie ujawnia potrzebę ograniczenia liczby ponownych alokacji, a nie jesteś ograniczony pamięcią, rozważ nadmiar alokacji o wartość procentową w każdym kierunku i zapisz przesunięcie względem początku. (Na przykład, jeśli rozpoczniesz nową mapę bitową na 1x1 i przydzielisz tablicę 9x9, aby ją zatrzymać, początkowa xi yoffset będzie4 .) Kompromisem jest tutaj konieczność wykonania dodatkowej matematyki podczas dostępu do pikseli, aby zastosować przesunięcie.

Jeśli rozszerzenia okażą się bardzo drogie, możesz wypróbować jedno lub oba z nich:

• Obsługuj przedłużenia pionowe i poziome w różny sposób. Rozszerzanie tablicy w pionie w dowolnym kierunku można osiągnąć poprzez przydzielenie nowego bloku i wykonanie pojedynczej kopii całej istniejącej tablicy z odpowiednim przesunięciem w nowej pamięci. Porównaj to z rozszerzeniami poziomymi, w których musisz wykonać tę operację raz na wiersz, ponieważ istniejące dane nie są ciągłe w nowym bloku.

• Śledź najczęstszą ilość i kierunek przedłużenia. Użyj tych informacji, aby wybrać nowy rozmiar i przesunięcie, co zmniejszy prawdopodobieństwo konieczności ponownego przydzielenia i skopiowania dla dowolnego rozszerzenia.

Osobiście wątpię, czy będziesz potrzebować któregoś z nich, chyba że stosunek pikseli do dostępu do rozszerzenia jest niski.

• Stała wielkość Dachówka (powiedzmy 256x256, ale z nieskończoną liczbą płytek)
• Udostępnij opakowanie bitmapy które pozwala na ujemne współrzędne pikseli (aby sprawiać wrażenie, że obraz można rozwinąć we wszystkich czterech kierunkach bez konieczności ponownego obliczania / synchronizacji odniesień do istniejących wartości współrzędnych)
  • Rzeczywista klasa bitmap (działająca pod opakowaniem) powinna jednak obsługiwać tylko bezwzględne (nieujemne) współrzędne.
• Pod opakowaniem zapewnij dostęp na poziomie kafelków (na poziomie bloku) za pomocą operacji we / wy odwzorowanych w pamięci
• Oprócz Map.setPixel()i Map.getPixel()który modyfikuje pojedynczy piksel na raz, podaj także metody kopiowania i modyfikowania jednego prostokąta pikseli na raz. Umożliwi to dzwoniącemu wybranie bardziej wydajnej formy dostępu w zależności od informacji dostępnych dla dzwoniącego.
  • Biblioteki komercyjne zapewniają również metody aktualizacji: jeden wiersz pikseli, jedna kolumna pikseli, aktualizacje rozproszenia / zbierania oraz operacje blittera arytmetyczno-logicznego w jednym kroku (aby zminimalizować kopiowanie danych).

(Nie pochwalajmy przezabawnych odpowiedzi ...)

Najbardziej elastyczną i być może niezawodną implementacją jest lista połączona ze strukturami dającymi współrzędną x, współrzędną y i wartość bitu. Najpierw zbuduję to i uruchomię.

Następnie, jeśli jest zbyt wolny i / lub duży, wypróbuj zwykłe sposoby jego przyspieszenia: tablica, macierz, mapa bitowa, kompresja, buforowanie, inwersja, przechowywanie tylko wartości „1” itp.

Łatwiej jest wykonać powolną poprawną implementację szybciej niż naprawić szybką implementację błędną. Podczas testowania „szybkiej” drugiej implementacji masz standard referncji, z którym możesz go porównać.

A kto wie, prawdopodobnie odkryjesz, że powolna wersja jest wystarczająco szybka. Tak długo, jak cała struktura mieści się w pamięci, wszystko jest już zadziwiająco szybkie.

Proponuję następującą implementację w Pythonie:

class Map(dict): pass

Ma następujące zalety:

1. Uzyskaj / Ustaw dostęp za pośrednictwem map[(1,2)]można rozważyć O(1).
2. Znika potrzeba wyraźnego rozszerzenia siatki.
3. Jest mało miejsca na błędy.
4. W razie potrzeby można go łatwo uaktualnić do 3D.

Jeśli faktycznie potrzebujesz mapy bitowej o dowolnym rozmiarze - i mam na myśli cokolwiek od 1x1 do 1000000 x 1000000 i potrzebujesz jej rozbudowy na żądanie ... jednym z możliwych sposobów jest użycie bazy danych. Na początku może się to wydawać sprzeczne z intuicją, ale tak naprawdę masz problem z pamięcią masową. Baza danych umożliwia dostęp do poszczególnych pikseli i przechowywanie praktycznie dowolnej ilości danych. Niekoniecznie mam na myśli SQL db, btw.

Czy będzie wystarczająco szybki dla twoich celów? Nie mogę odpowiedzieć, ponieważ nie ma tutaj kontekstu dotyczącego tego, co robisz z tą bitmapą. Ale jeśli jest to do wyświetlania na ekranie, należy wziąć pod uwagę, że zwykle wystarczy cofnąć dodatkowe wiersze skanowania, aby wyświetlić je podczas przewijania ekranu, a nie wszystkie dane.

Biorąc to pod uwagę, nie mogę pomóc, ale zastanawiam się, czy masz coś złego. Czy zamiast tego powinieneś użyć grafiki wektorowej i śledzić poszczególne jednostki w pamięci, a następnie renderować bitmapę tak dużą, jak potrzeba dla ekranu?

Oto kroki, aby zapewnić prawidłowe działanie:

1. użyj przekazywania z jednego interfejsu do drugiego, aby zbudować drzewo obiektów, które razem reprezentują mapę bitową
2. każde „rozszerzenie” mapy bitowej przydzieli własną pamięć i zapewni inny interfejs

3. przykładowa implementacja to:

   template<class T, class P>
   class ExtendBottom {
   public:
      ExtendBottom(T &t, int count) : t(t), count(count),k(t.XSize(), count) { }
      P &At(int x, int y) const { if (y<t.YSize()) return t.At(x,y); else return k.At(x, y-t.YSize()); }
      int XSize() const { return t.XSize(); }
      int YSize() const { return t.YSize()+count; }
   private:
      T &t;
      int count;
      MemoryBitmap k;
   };
   

Oczywiście do rzeczywistej implementacji XSize () i YSize () nie działałyby, ale potrzebujesz MinX (), MaxX (), MinY (), MaxY () lub czegoś podobnego, aby zachować spójność numerów indeksów.