1

Temat: problem tablice

mamy tablice  3 wymiarowa kazdy wymiar max.256

nie kazdy rzad/kolumna jest zajeta np.

0|1|2|3|4|5|6....
1|x|0|x|x|x|0
2|0|x|0|x|x|0
3|x|0|x|0|0|x
4|x|x|x|x|x|0
5|x|0|x|0|0|x

trzeci wymiar w miejscu x mamy dane roznej dlugosci

tablica raz zdefiniowana nie zmienia swoich wymiarow

zalozenia sa takie, ze suma danych zromadzonch w trzecim wymiarze zmiesci sie w pamieci.

pytanie: jak zaprogramowac taka strukture zeby dostac sie do danych przez dwie wspolrzedne

najwazniejsza jest minimalny rozmiar takiej struktury a nie szybkosc dzialania

http://atari.pl/hsc/ad.php?i=1.

2

Odp: problem tablice

Chcesz się dostać do "kolumny" czy do konkretnej wartości? Naprostuj mnie jeśli źle rozumuję: chcesz strukturę 3-wymiarową indeksować za pomocą 2 współrzędnych? Jakie to mają być współrzędne? Czy chcesz mieć dostęp w jednym kroku czy można iterować? Mam pewną koncepcję, ale będzie kosztować trochę pamięci (konkretnie 256x256 skalarów).

Ostatnio edytowany przez perinoid (2020-11-05 19:10:03)

Pamięć studenta ma charakter kwantowy - student wie wszystko, ale jednocześnie nic nie pamięta.
- Kilka(naście?) pudełek z klawiszami i światełkami. I jeden Vectrex, żeby nimi wszystkimi rządzić.

3

Odp: problem tablice

tak, trzecieggo wymiaru nie musze indeksowac bo chce pobrac wszystkie dane z 3go wymiaru...

no i pamietaj... to ma sie zmiescic w pamieci atari...

http://atari.pl/hsc/ad.php?i=1.

4

Odp: problem tablice

Nie znam się na programowaniu Atari 8-bit, ale jeśli priorytetem ma być pamięć, to potrzebujesz 2 wymiarowej tablicy wskaźników do 256 elementowych wektorów. Część wskaźników będzie null. Tylko ta tablica zajmie 64 kB, nie licząc danych hmm

Ostatnio edytowany przez _tzok_ (2020-11-05 19:38:19)

Atari 1040STe (TOS 1.62/2.06 UK, 4MB RAM), Atari 1040STfm (TOS 1.04 UK, 4MB RAM, BLiTTER, Gotek HxC) + Digital Data Deicke HD64, SF314, UltraSatan, Gotek HxC, NetUSBee
Atari 800XE (SIMM EXP 1MB), Atari 800XL (RAMBO XL 256kB), Sinclair SPECTRUM+ (48kB), TIMEX Computer 2048 (48kB)
Commodore A600 (KS 1.3/3.1, 2MB CHIP RAM, 4MB FAST RAM, CF 4GB, Gotek FF)

5

Odp: problem tablice

xxl napisał/a:

tak, trzeciego wymiaru nie musze indeksowac bo chce pobrac wszystkie dane z 3go wymiaru...

A, czyli chcesz indeksować "stosiki" (załóżmy, że dwa pierwsze wymiary nazywamy "kolumna" i "wiersz", a "w pionie" mamy "stosik"). Przy strukturze z dziurami może być trudno zrobić to w wersji bezpośredniej... Proponowałbym strukturę taką:
1. Tablica wierszy (256 adresów pokazujących na kolejne wiersze).
2. Dla każdego wiersza po kolei:
a. pierwsza zajęta kolumna:
- jej numer (1 bajt)
- liczba elementów w stosiku (nie wiem ile planujesz, 1-2 bajty).
- kolejne elementy stosiku.
b. druka zajęta kolumna (1 bajt)
- liczba elementów w stosiku.
- kolejne elementy stosiku.
c. (i tak dalej).

Dostęp wymaga iteracji. Bierzesz adres wiersza z pierwszej tablicy, a potem iteracyjnie:
1. Patrzysz na numer pod wskaźnikiem
a. jeśli to co potrzebujesz to masz "stosik" i goto 2.
b. jeśli nie, to modyfikujesz wskaźnik o wartość z kolejnej komórki pamięci (przeskok o wysokość stosiku).
c. goto 1.
2 Masz poszukiwany stosik.

Niestety, jak musisz oszczędzić na miejscu to musisz zapłacić obliczeniami. Koszt dostępu do stosiku będzie rzędu liczby zajętych kolumn w wierszu. Koszt pamięciowy to tablica na adresy wierszy + 2 wartości na każdy stosik.

Taką mam koncepcję.

Pamięć studenta ma charakter kwantowy - student wie wszystko, ale jednocześnie nic nie pamięta.
- Kilka(naście?) pudełek z klawiszami i światełkami. I jeden Vectrex, żeby nimi wszystkimi rządzić.

6

Odp: problem tablice

Jesli dobrze zrozumialem:

0|1|2|3|4|5|6....
1|x|0|x|x|x|0
2|0|x|0|x|x|0
3|x|0|x|0|0|x
4|x|x|x|x|x|0
5|x|0|x|0|0|x


Wszedzie gdzie jest x stawiam sobie 1 a 0 jest zerem., i produkuje sobie ciagi bitowe np rzedami. dla podanego przykladu 5 rzedow po 6 bitow:

101110
010110
101001
111110
101001

I zwijam w 1 dlugi bitstream: 101110010110101001111110101001 (tu 30 bitow) i jest to rodzaj mapy.

Nastepnie dane z 3 wymiaru ukladam kolejno w pamieci jedne za drugim w takiej samej kolejnosci jak zrobilem sobie ciagi bitowe. (Jednak tylko te dane gdzie sa X'y)
Kazdy zestaw danych 3 wymiary ma d bajtow danych i ukladam je od adresu a

Gdy teraz potrzebuje dany z kolumny x=3 rzad y=4, obliczam sobie index:  i=x+(y-1)*6 (ilosc kolumn na rzad) = 21

101110010110101001111110101001 (wybrany bit) - przy okazji sprawdzam czy bit jest faktycznie ustawiony.
Nastepnie licze ile jest bitow ustawionych po lewej stronie od mojego bitu, tutaj o=11
Wiec szukane dane znajduja sie pod adresem DANE=a+d*o


Uzycie danych, ilosc slupkow 3d razy ich objetosc + 1 bit na kazda lokacje 2d.
W extremalnym przypadku 256*256*256 da: 65K danych + 8K "bitstream" indexow + odrobine kodu.


Zamotane troche bo mysl przelalem bezposrednio na klawiature. Jakby co pytaj wyjasnie.

"tatusiu zobacz, narysowałam tobie takie same coś jak na twojej koszulce" 
jmp $e477

7

Odp: problem tablice

Jeśli dobrze zrozumiałem XXL-a to niestety, zestawy danych są różnych rozmiarów.

Pamięć studenta ma charakter kwantowy - student wie wszystko, ale jednocześnie nic nie pamięta.
- Kilka(naście?) pudełek z klawiszami i światełkami. I jeden Vectrex, żeby nimi wszystkimi rządzić.

8

Odp: problem tablice

Ile tych różnych tablic x będziesz miał?
Jaka jest zajętość x w tablicy 256x256?
Jeśli nie za dużo, to mając współrzędne tablicy XY ustaliłbym wartości X i Y dla każdego x (taki "adres") i policzyłbym funkcję logiczną (optymalizacja np metodą Carnaugh) zwracającą true/false na początek. Potem może mając te funkcje policzone dla wszystkich x policzyłbym jedną zwracającą konkretną wartość x - 0, 1, 2, 3...
Może funkcja zajmie mniej miejsca, może funkcja korzystałaby z własnych tablic. Trudno powiedzieć cokolwiek jeśli nie ma konkretnych danych.
Czy ta Twoja tablica jest stała, czy wartości w środku mogą się zmieniać?

Ostatnio edytowany przez mono (2020-11-05 20:04:16)

hex, code and ror'n'rol!
"mężczyzna wydoił wielbłąda żoną" / "wcześniej miał na imię Heidi i był niemiecką kulomiotką" / "niewiedza buduje, wiedza rujnuje" / "błąd był tolerowany, a teraz tolerowany być nie chce"

9

Odp: problem tablice

Nie ma nic za darmo, chociaż atari tak chciało.
Trzeba przyjac jakies kompromisy, np dodatkowy bajt na dlugosc i sumowac to by wyliczyc offset, albo przyjac max dlugosc danych.

"tatusiu zobacz, narysowałam tobie takie same coś jak na twojej koszulce" 
jmp $e477

10

Odp: problem tablice

@willy: podoba mnie sie to... taka modfikacja tylko ze "d" tez jest roznej wielkosci wiec trzeba iterowac jak pisal perinoid, na poczatku danych z 3 wymiaru ilosc danych i dodawac big_smile ... no...

Ostatnio edytowany przez xxl (2020-11-05 20:07:38)

http://atari.pl/hsc/ad.php?i=1.

11

Odp: problem tablice

To możesz zrobić tak: tablica bitowa jak pisał willy, iteracja po niej zliczająca liczbę jedynek "na lewo" od twojej pozycji wyznacza pozycję w tablicy adresów, w którym trzymasz wskaźniki na kolejne stosiki.

[Edit]
Chociaż z drugiej strony taka tablica zer i jedynek to 1/8 całej pamięci będzie... Trochę szkoda. Moja pierwsza propozycja będzie lepsza przy mniejszej liczbie zajętych ztosików.

Ostatnio edytowany przez perinoid (2020-11-05 20:20:00)

Pamięć studenta ma charakter kwantowy - student wie wszystko, ale jednocześnie nic nie pamięta.
- Kilka(naście?) pudełek z klawiszami i światełkami. I jeden Vectrex, żeby nimi wszystkimi rządzić.

12

Odp: problem tablice

to je genialne... juz w pierwszym kroku mamy kontrole czy sa dane na pozycji x,y (bit 0 - brak danych)

http://atari.pl/hsc/ad.php?i=1.

13

Odp: problem tablice

Tak czy inaczej, jest to 2-wymiarowa tablica BLOBów (obiektów, wektorów - nie ma znaczenia, skoro mają być pobierane w całości), o różnych (?) rozmiarach i nie ma sensu na to patrzyć jako na tablicę 3W. Strategia na pewno zależy od tego, jaki procent komórek tej tablicy 2W jest zajęty.

Ostatnio edytowany przez _tzok_ (2020-11-05 20:55:41)

Atari 1040STe (TOS 1.62/2.06 UK, 4MB RAM), Atari 1040STfm (TOS 1.04 UK, 4MB RAM, BLiTTER, Gotek HxC) + Digital Data Deicke HD64, SF314, UltraSatan, Gotek HxC, NetUSBee
Atari 800XE (SIMM EXP 1MB), Atari 800XL (RAMBO XL 256kB), Sinclair SPECTRUM+ (48kB), TIMEX Computer 2048 (48kB)
Commodore A600 (KS 1.3/3.1, 2MB CHIP RAM, 4MB FAST RAM, CF 4GB, Gotek FF)

14

Odp: problem tablice

optmalizacja... a jesli bedziemy miec powtorzone dane w 3cim wymiarze?

w tablicy 2d trzymam adresy danych z 3go wymiaru, dostep do tablicy obliczac ze strumienia bitow. nie trzeba bedzie obliczac adresow w petli pobierajac rozmiar kolejnych danych z 3o wmiaru bo to zawsze bedzie wartosc 2. mocno wzrosla objetosc :-)

http://atari.pl/hsc/ad.php?i=1.

15

Odp: problem tablice

xxl napisał/a:

to je genialne... juz w pierwszym kroku mamy kontrole czy sa dane na pozycji x,y (bit 0 - brak danych)

Jeśli musisz sprawdzać - to tak, i to bardzo tanio.

Pamięć studenta ma charakter kwantowy - student wie wszystko, ale jednocześnie nic nie pamięta.
- Kilka(naście?) pudełek z klawiszami i światełkami. I jeden Vectrex, żeby nimi wszystkimi rządzić.

16

Odp: problem tablice

Mozna pojsc jeszcze kok dalej, i uzyc jakiegos algorytmu kompresji. Nawet zwykle kodowanie huffmana sie tu sprawdzi.
Wada - dostep do ostatnich danych w "streamie" bedzie dosyc dlugi.

"tatusiu zobacz, narysowałam tobie takie same coś jak na twojej koszulce" 
jmp $e477

17

Odp: problem tablice

brak tej wady, dane z 3-go wmiaru moga byc skompresowane LZ4 zewnetrznym slownikiem (np. ROM) przez co krotkie fragment kompresuja sie swietnie a szbkosc dekompresji jest praktcznie jak kopiowanie ;-)

wada... bedzie dzialac tylko z okreslona wersja ROM.

mozna tez pomslec zeby sam kod programu byl slownikiem ...

http://atari.pl/hsc/ad.php?i=1.

18

Odp: problem tablice

Możesz też iść siłowo z kompresją.
Masz 256 skompresowanych streamów w tablicy A indeksowanych po x (po wskaźnikach)
Rozkompresowujesz k-ty stream dostajesz 256 wskaźników indeksowanych po y
Rozkompresowujesz l-ty stream z docelową zawartością.

Metoda prosta i skuteczna oraz tania O(k+l+m), likwiduje redundancję pustych miejsc. Zakładam statyczność tablicy.

Ostatnio edytowany przez qbahusak (2020-11-08 03:32:12)

19

Odp: problem tablice

hmmm, niby tak... tylko widze tu ze potrzebny jest bufor na rozpakowana tablice x... do zrobienia jesli mamy jakis bufor ogolnego przeznaczenia ale jesli nie to bitsream jest lepszy.

---
jakby byl bufor to moznaby tez generowac w jakis sprytny sposob slownik np. fraktalem albo jakies proste drawto... tylko ze to juz by bylo bardziej szyfrowanie np. na taki obrazek bedacy slownikiem nakladamy napis z odpowiedza usera... jesli byla zla to wszystko leci w kosmos ;-) ... albo obecny obraz na ekranie, tylko jesli ktos poprawilby grafike w proramie to ten przestalby dzialac ;-) niezly pomysl ;-)

Ostatnio edytowany przez xxl (2020-11-08 14:52:18)

http://atari.pl/hsc/ad.php?i=1.

20

Odp: problem tablice

xxl napisał/a:

hmmm, niby tak... tylko widze tu ze potrzebny jest bufor na rozpakowana tablice x... do zrobienia jesli mamy jakis bufor ogolnego przeznaczenia ale jesli nie to bitsream jest lepszy.

512 bajtów na tablicę X, różnie dla tablic Y i różnie dla Z. A nie możesz czytać bajt po bajcie ze skompresowanego strumienia danych, aż znajdziesz te, co chcesz? (przeszukiwanie "w locie")

Wg mojego doświadczenia nie znajdziesz lepszej o rząd wielkości metody przy rzadkich tablicach ponad powyższe algorytmy. A jeśli masz jakiś szczególny przypadek - można wybierać/optymalizować. Metastruktury też trochę zajmą, a czym bardziej skomplikowane rozwiązanie, tym dłuższy kod, więc nie warto IMO wchodzić w zbyt skomplikowane rzeczy.

21

Odp: problem tablice

nie wiem czy dobrze Cie rozumiem... 512 na x niech y ma tez 512 tlko w kilku kolumnach to juz sie nie zmiesci w pamieci...

natomiast maksmalna objetosc 256x256 z bitstreamem zmiesci sie w 8 kb

http://atari.pl/hsc/ad.php?i=1.