Jak działa „Czwarty wymiar” z tablicami?

30

Abstrakcyjny:

Tak więc, jak rozumiem (chociaż mam bardzo ograniczone rozumienie), istnieją trzy wymiary, z którymi (zwykle) pracujemy fizycznie:

Pierwszy byłby reprezentowany przez linię.
Drugi byłby reprezentowany przez kwadrat.
Trzeci byłby reprezentowany przez sześcian.

Wystarczająco proste, dopóki nie dotrzemy do czwartego - Trudno jest narysować w przestrzeni 3D, jeśli wiesz, co mam na myśli ... Niektórzy mówią, że ma to coś wspólnego z czasem .

Pytanie:

Teraz, choć to nie wszystko ma sens, to wszystko jest dla mnie świetne. Moje pytanie nie dotyczy tego, czy zadawałbym je na MathSO lub PhysicsSO. Moje pytanie brzmi: jak komputer radzi sobie z tablicami?

Wiem, że możesz tworzyć tablice 4D, 5D, 6D itp. ... w wielu różnych językach programowania, ale chcę wiedzieć, jak to działa.

Znak zapytania
źródło
66
Jeśli 3 wymiary można zwizualizować jako sześcian, wówczas 4 wymiary można zwizualizować jako wiązkę sześcianów w linii. 5 wymiarów można wizualizować jako siatkę, w której każda komórka w siatce zawiera ... sześcian! I tak dalej ... „Czwarty wymiar” nie ma nic wspólnego z czasem (cokolwiek to jest), chyba że zdefiniujesz go jako taki w kontekście semantyki twojego programu.
FrustratedWithFormsDesigner
14
Ogólnie rzecz biorąc, możesz pokonać ten konceptualny garb, starając się unikać myślenia o wymiarach jako konstrukcjach ściśle fizycznych. Na przykład niektóre problemy z uczeniem maszynowym mogą mieć wymiary w setkach tysięcy, gdzie każdy wymiar jest cechą zestawu danych.
Steven Evers
6
W nawiązaniu do komentarza Steve'a Eversa zastanów się nad typowym typem danych: kolorem RGB. Ma trzy wymiary, więc możesz rozważyć „przestrzeń kolorów” RGB. Teraz dodaj składnik alfa. Masz cztery wymiary.
Josh Caswell
25
Pamiętaj, że komputer nie dba o wymiary geometryczne - to tylko urządzenie dla wygody człowieka. Jeśli przydzielisz tablicę 5x5x5x5, komputer po prostu przydzieli tablicę 625 elementów i odpowiednio wykona matematykę z twoimi indeksami.
David Zhang

Odpowiedzi:

77

Na szczęście programy nie są ograniczone fizycznymi ograniczeniami realnego świata. Tablice nie są przechowywane w przestrzeni fizycznej, więc liczba wymiarów tablicy nie ma znaczenia. Są spłaszczone do pamięci liniowej. Na przykład tablica jednowymiarowa z dwoma elementami może być określona jako:

(0) (1)

Tablica 2x2 może wówczas wyglądać następująco:

(0,0) (0,1) (1,0) (1,1)

Trójwymiarowa tablica 2x2x2 może być:

(0,0,0) (0,0,1) (0,1,0) (0,1,1) (1,0,0) (1,0,1) (1,1,0) (1,1,1)

Miejmy nadzieję, że zobaczysz, dokąd to zmierza. Cztery wymiary mogą być:

(0,0,0,0) (0,0,0,1) (0,0,1,0) (0,0,1,1) (0,1,0,0) (0,1,0,1) (0,1,1,0) (0,1,1,1)
(1,0,0,0) (1,0,0,1) (1,0,1,0) (1,0,1,1) (1,1,0,0) (1,1,0,1) (1,1,1,0) (1,1,1,1)
Greg Hewgill
źródło
10
Macierze komputerowe nie są ograniczone ludzkim rozumieniem ani wizualizacją, ale są ograniczone przez ograniczenia fizyczne, np. Tablica wymiarów d o długości n zajmie n ^ d, lub bardziej ogólnie o różnych wymiarach długości, n1 × n2 ×… × nd.
acelent
6
@ColtonAllen: Nie jestem do końca pewien, o czym mówisz. Definicja wymiaru mówi „Ogólnie rzecz biorąc, jest to liczba potrzebnych do określenia współrzędnych punktu na obiekcie”. Tablica zadeklarowana w C jako int a[2][2][2];trójwymiarowa.
Greg Hewgill
4
„Na szczęście programy nie są ograniczone fizycznymi ograniczeniami realnego świata”. Dlatego właśnie mamy wszystkie procesory o częstotliwości 4,5THz i nikogo nie obchodzi hierarchia pamięci, prawda? To naprawdę najśmieszniejsza odpowiedź, jaką przeczytałem ...
Manu343726,
24
@ Manu343726 Odwołuje się do faktu, że żyjemy w (teoretycznie) ograniczonych wymiarach przestrzeni i czasu, ale tablice w pamięci komputera mają wymiary „udające” - wszystko to jest przechowywane w liniowo ciągłej przestrzeni w pamięci - więc nie są ograniczone do liczba wymiarów, w których żyjemy. Nie trolluj: :(
Blackhawk
15
@ Manu343726: Uważnie powiedziałem Programy , a nie Komputery . To jedna z wielkich zalet oprogramowania.
Greg Hewgill
49

Nie musisz wyobrażać sobie w dużych wymiarach przestrzennych, po prostu pomyśl o tym jak o liściu paproci. liść paproci

Główną łodygą jest twoja pierwsza tablica, w której każda gałąź jest przechowywanym przedmiotem. Jeśli spojrzymy na gałąź, jest to twój drugi wymiar. Ma podobną strukturę pochodzących z niego mniejszych gałęzi reprezentujących jego dane. Te z kolei mają własne małe gałęzie, które ciągną się do momentu, aż dotrzemy do maleńkich liści reprezentujących dane z wewnętrznej lub najwyższej tablicy wymiarów.

Możesz zobaczyć, jak się buduje, jeśli zadeklarujesz każdy poziom własną nazwą. Ponownie używam każdego poziomu zmiennej, aby zminimalizować kod:

leaf = 2;
tinyBranch = [leaf, leaf, leaf];
middleBranch = [tinyBranch, tinyBranch, tinyBranch];
bigBranch = [middleBranch, middleBranch, middleBranch];
mainBranch = [bigBranch, bigBranch, bigBranch];
n00begon
źródło
1
Czy ta wizualizacja nie odzwierciedla bardziej poszarpanej tablicy?
Matt Johnson-Pint
2
@MattJohnson Formalnie tak, ale ten przykład również wyjaśnia / wizualizuje tablice wielowymiarowe.
M.Mimpen
4
+1 to nie tylko zgrabna wizualizacja, ale bliższa prawdy niż liniowe wyjaśnienie wielu implementacji tablic. Bez względu na to, czy większość ludzi ograniczyłaby termin „tablica” do ciągłej pamięci, „ tablica wielowymiarowa ” jest z pewnością terminem używanym do takich aranżacji w literaturze dla wielu języków.
DeveloperInDevelopment
46

Wymiary są czymkolwiek chcesz, czwarty wymiar niekoniecznie musi być czasem. Jeśli myślisz o trzech wymiarach jako sześcianie, możesz pomyśleć o 4 wymiarach jako rzędzie kostek. 5 wymiarów, siatka kostek i tak dalej.

Możesz także mieć kolekcję wokseli w 3D, gdzie czwartym wymiarem jest kolor, gęstość lub inna właściwość.

Gdy przydzielasz pamięć dla tablicy wielowymiarowej, po prostu przydziela ona iloczyn maksimum każdego wymiaru dla twojego typu danych. Jeśli masz tablicę 3d lub „sześcian” 10 elementów w każdym wymiarze, przydzielonych zostanie 1000 elementów. Jeśli utworzysz tablicę 4d z 10 elementami w czwartym wymiarze, komputer po prostu przydzieli 10 000. Podbij go do 5 wymiarów, a przydzieli 100 000.

Komputer nie dba o jakiekolwiek znaczenie tego, co reprezentuje każdy wymiar. Aby wybrać, gdzie na liście elementów znajduje się pojedynczy punkt, wystarczy pomnożyć, aby wybrać adres pamięci.

Jaka jest nazwa?
źródło
26

Wyobraź sobie, że wykonujesz prace badawczo-rozwojowe na nowym urządzeniu medycznym, szeregu czujników umieszczanych wzdłuż ramion pacjenta. Masz siedmiu ochotników w kolejce do testów. Każdy czujnik zgłasza odczyty niskiej, średniej i wysokiej częstotliwości, które wykonuje się co 100 ms przez około minutę.

Jak przechowywać wszystkie te dane w pamięci do analizy i kreślenia?

Oczywiście tablica. Wyglądałoby to tak (przy użyciu gotowego pseudokodu ogólnego):

npatients = 7
nsensors = 4     // number of sensors on an arm
nchannels = 3
nsamples = 60.0 / 0.1
sensordata = Array[ npatients, nsensors, 2, nchannels, nsamples ]

To pięciowymiarowa tablica i nie ma w tym nic trudnego, tajemniczego ani zaskakującego. Nie ma powodu, aby próbować kojarzyć go z 5-wymiarową przestrzenią euklidesową. Aby uzyskać dowolną wartość danych, używamy wyrażenia podobnego

x = sensordata[6, 5, 1, 2, 338)

To tak jak odpytywanie relacyjnej bazy danych, w której masz rekord dla każdej wartości danych, z pięcioma kolumnami zawierającymi identyfikator pacjenta, identyfikator czujnika itd. Oraz kolumnę z wartością. Aby uzyskać jeden punkt danych, użyj pięciu terminów w polu GDZIE: WYBIERZ wartość z SensorData GDZIE (pacjentid = 6) i (sensorid = 5) i (arm = „left”) i (channel = „midfreq”) i (sampleindex = 338 ).

Nie ma nic mistycznego w tabeli bazy danych z pięcioma lub więcej kolumnami, prawda?

(Używam indeksowania opartego na 1, chociaż w rzeczywistości, oparte na 0 jest znacznie częstsze.)

Zauważ, że jestem złym chłopcem z powodu twardego zakodowania liczby ramion. Jeśli kiedykolwiek dostanę fundusze na zbadanie tych czujników na ośmiornicy, mam kłopoty!

DarenW
źródło
3
+1 Doskonały przykład pokazujący, że wymiarami mogą być dowolne dane, których potrzebujesz.
Mike wspiera Monikę
20

Tablica to tylko blok ciągłej pamięci. Adresowanie do pamięci jest jednowymiarowe, możesz przejść do przodu lub do tyłu. Zakładając, że masz tablicę z 5 elementami, zarezerwowanych będzie 5 bloków pamięci. Jeśli masz dwuwymiarową tablicę z 5 elementami w każdym wymiarze, zarezerwowanych zostanie 25 bloków pamięci.

Zillolo
źródło
5
Tak, pamiętaj o tym, dodając kolejne wymiary do swoich tablic. Wykorzystanie pamięci może nie być trywialne.
davidhaskins
18

... lub pytałbym o to na MathSO ...

Cóż, w rzeczywistości matematycy nigdy (lub przynajmniej nie zwykle) kojarzą czwarty wymiar z czymś takim jak czas. Nie skojarzyliby też pierwszych trzech z czymkolwiek takim jak przestrzeń: matematycy po prostu definiują wymiar jako abstrakcyjną właściwość, zwykle przestrzeni wektorowej (często będzie to uogólnione na rozmaitości, a nawet przestrzenie metryczne ). A ta abstrakcyjna definicja nie dba o to, ile wymiarów ma fizyczna przestrzeń, w której się poruszamy. Pojęcie wymiarów dotyczy przestrzeni, które nawet nie przypominają przestrzeni fizycznej. W rzeczywistości matematycy (a nawet fizycy) bardzo często używają nieskończonych wymiarów przestrzenie, takie jak przestrzenie Hilberta w mechanice kwantowej.

Po wyjaśnieniu porozmawiajmy o tablicach - nie musisz rozumieć przestrzeni wektorowych, ponieważ abstrakcyjna definicja jest tutaj znacznie prostsza.

Tablica ( 0 × 1 × 2 × ... × n −1 ) (tj. O wymiarze n ) jest po prostu zbiorem 01 ⋅ ... ⋅ n −1 liczb ( lub jakikolwiek typ obiektu wypełnia tablicę). Jedyną różnicą w stosunku do jednowymiarowej tablicy o tej długości jest to, że masz szczególnie użyteczny sposób oddzielnego indeksowania wymiarów, a mianowicie

i lin = i n −1 + n −1 ⋅ ( i n −2 + n −1 ⋅ (... 2 ⋅ ( i 1 + 1i 0 ) ...))

po lewej stronie
źródło
Żeby było jasne, potrzebujesz tylko tablicy z 3 elementami do opisania 3 wymiarów, a tablica N elementów opisuje N wymiarów. Jednak wyszczególnienie każdego wektora to inna historia. Często odbywa się to poprzez pokazanie obrazu ( imshoww Pythonie) - może pokazywać dwa wymiary przestrzenne, a także trzeci wymiar koloru.
Scott
@Scott: Zgadzam się, że pojęcie „wymiar tablicy” jest niefortunne, ponieważ oznacza coś niezwiązanego z wymiarowością przestrzeni, której wektory mogą być reprezentowane przez tablice. (Wydaje mi się jednak, że reprezentowanie wektorów zwykłymi, nieabstrakcyjnymi tablicami nie jest dobrym pomysłem.) Lepszą nazwą może być ranga tablicy, analogicznie do tensorów .
leftaroundabout
13

W programowaniu tablice są dość łatwe do wdrożenia, ale może nie do zrozumienia.

Zasadniczo każdy poziom tablic oznacza, że ​​zawartość ma nskładane. To znaczy

  • int x[4]są 4 bloki, każdy z nich zawiera int.
  • int x[5][4]jest 5 bloków, każdy z nich zawiera int[4].
  • int x[3][5][4]są 3 bloki, każdy z nich zawiera int[5][4].
  • int x[2][3][5][4]są 2 bloki, każdy z nich zawiera int[3][5][4].

To, jak się do nich odnosisz, zależy od ciebie, ale dla lepszego zrozumienia masz coś takiego

  • COLUMN dla ostatniego
  • ROW po drugie
  • PAGE po trzecie

Aż tu gdzieś to czytam. Aby tu zostać, możemy również zdefiniować

  • BOOK za czwarty ostatni
  • i może SHELFna piątą ostatnią. (Lub, jeśli wolisz, SHELFROWabyśmy mogli kontynuować.)

To powiedziawszy, nigdy nie widziałem tablicy z więcej niż 4, a może 5 wymiarami w „dzikim życiu”.

W ten sposób możesz zdefiniować i wyobrazić sobie int x[6][2][3][5][4]jako zbiór 6 „półek”, każda z 2 książkami, każda z 3 stronami, każda z 5 rzędami, każda z 4 kolumnami.

glglgl
źródło
13

Pomyśl o jednowymiarowym układzie jak komoda:

komoda

Każda szuflada jest indeksem tablicy. W każdej szufladzie możesz umieścić, co chcesz, i do wielu celów każda szuflada będzie zawierać tylko jeden element (jest to jednowymiarowy układ).

Komoda jest jednak magiczna, więc nie ogranicza jej fizyczna przestrzeń. Oznacza to, że możesz umieścić kolejną komodę w każdej szufladzie pierwszej komody. Wewnętrzne komody mogą zawierać dowolne elementy. To dwuwymiarowa tablica.

Możesz więc powiedzieć coś w stylu „otwórz górną szufladę pierwszej komody z szufladami, wyjmij komodę z tej szuflady, a następnie otwórz dolną szufladę z drugiej komody”. To byłoby jak uzyskanie dostępu do indeksu tablicy 2D: myArray [0] [3];

I oczywiście, komody wewnątrz najbardziej zewnętrznej komody mogą same zawierać komody. To trójwymiarowa tablica.

Twoje pytanie brzmi: co to jest czterowymiarowa tablica? Oczywiście jest to komoda z komodami z komodami z komodami!

Szuflady są całkowicie opuszczone.

Kevin Workman
źródło
4
To komody do końca, stary.
Thomas Eding,
8
A w ostatniej komodzie? Żółwie .
Kevin Workman
Być trochę pedantyczny. Biorąc pod uwagę, że w każdej skrzyni znajdują się 3 szuflady (na podstawie obrazu), a nie 4, a korzystasz z indeksu podstawowego 0, dolna szuflada miałaby 2, a nie 3. Tak więc zamiast myArray[0][3]tego myArray[0][2]. Ale poza tym dobre wytłumaczenie.
Tom Heard
@TomHeard Pierwsza komoda z 3 szufladami, ale komoda z pierwszej szuflady ma 4 szuflady. Hه! : p
Kevin Workman
1
Och, więc w porządku. = D
Tom Heard
5

Większość aspektów tego pytania zostało już rozważonych, ale myślę, że to pomoże, jeśli weźmiesz pod uwagę naturę wymiaru. Nie wszystkie wymiary są przestrzenne. Wymiar jest kontekstem pomiaru. Oto kilka przykładów:

  • Częstotliwość - kolor lub wysokość
  • Masa
  • Wartościowość
  • Kolor (kwark górny, kwark dolny, kwark dziwny, kwark czarujący itp.)
  • Kierunek wirowania
  • Kąt
  • Głośność
  • Hotness (chili)

„Czwarty” wymiar jest tylko czwarty, ponieważ istnieją trzy wymiary przestrzenne. Przestrzeń i czas wydają się duże, ponieważ, no cóż, wydają się duże. Bardzo prosto w twarz. Ale każda mierzalna, mierzalna jakość może być wymiarem, jeśli ją zmierzysz.

Na przykład biustonosze mają trzy wymiary: rozmiar miseczki, rozmiar klatki piersiowej i reklamy pełnoekranowe (nie wiem, jak to nazywają dziewczyny, ale mam na myśli odległość między miseczkami).

Piotr
źródło
1
„Nie wszystkie wymiary są przestrzenne”. W przypadku tablic wszystkie wymiary przestrzenne.
Rhymoid,
2
@ Rhymoid: W przypadku tablic żadne wymiary nie są z natury przestrzenne w naszym sposobie myślenia o przestrzeni. : P Definiujemy je tak, aby reprezentowały wszystko, co chcemy.
cHao
@ cHao Może jeśli spojrzysz na semantykę przechowywanych danych. Ale po stronie reprezentacyjnej / składniowej / implementacyjnej wszystkie wymiary tablicy są z natury przestrzenne. W rzeczywistości zależy od tego, kiedy używasz tablic jako części algorytmu.
Rhymoid
@ Rhymoid: To ten sam proces myślowy, który doprowadził do postawienia tego pytania. Wymierny wymiar nie czyni go przestrzennym. Implementacyjnie nie ma miejsca. Jest tylko pamięć, a pamięć jest jednowymiarowa, o ile program wie / widzi / troszczy się.
cHao
@ cHao: zgodnie z implementacją jest miejsce, ponieważ jest także czas. Termin „wyciek przestrzeni” (jako alternatywa dla „wycieku pamięci”, znaleziony w społeczności Haskell) nie jest przypadkiem. Fakt, że pamięć jest opisana jako jednowymiarowa, jest dziedzictwem BCPL.
Rhymoid
4

W fizyce zakładamy, że każdy wymiar przestrzenny jest nieskończony, co sprawia, że ​​znalezienie miejsca na nowe wymiary jest dość trudne.

W przypadku tablic skończonych łatwo jest znaleźć miejsce.

Wyobraź sobie arkusz papieru z wydrukowaną na nim siatką; możesz napisać informacje w każdej komórce siatki. To tablica 2D: wiersz i kolumna.

Umieść kilka z tych arkuszy papieru w folderze plików; to tablica 3D: strona, wiersz i kolumna.

Umieść kilka z tych folderów w polu pliku. Tablica 4D: folder, strona, wiersz, kolumna.

Ułóż pudełka w prostokątną kratkę na drewnianej palecie. Tablica 6D: pole-wiersz, pole-kolumna, folder, strona, wiersz, kolumna.

Ułóż na nich więcej siatek pól. Tablica 7D: głębokość pola, pole wiersza, pole kolumny, folder, strona, wiersz, kolumna.

Rozpocznij wbijanie palet w pojemnik transportowy: tablica 9D. (Zakładając, że każdy stos jest tak wysoki jak wnętrze pojemnika, więc możesz uzyskać tylko 2 dodatkowe wymiary tutaj.)

Układaj kontenery na pokładzie statku kontenerowego: tablica 12D.

Twoja flota kontenerowców ma teraz tablicę 13D.

Russell Borogove
źródło
„zakładamy, że każdy wymiar przestrzenny jest nieskończony” nieskończoność nie jest tutaj w rzeczywistości największym problemem, ciągłość jest „prawdziwym” problemem (tj. nadmiernie nieskończonym nieskończonością i potrzebujemy mapowania homeomorficznego, aby miało to sens fizyczny).
leftaroundabout
3

W kartezjańskim układzie współrzędnych masz osie xiy na płaszczyźnie. Możesz reprezentować dowolną liczbę na płaszczyźnie jako (x, y).

W trzy- „spacji” (znanej również jako sześcian) możesz mieć osie x, y i z. Możesz reprezentować dowolny element kostki jako (x, y, z).

W przestrzeni wielowymiarowej możesz mieć osie x, y, z i w (gdzie oś w jest „urojona”). Możesz reprezentować dowolny element tej przestrzeni jako (x, y, z, w).

Wszystkie te punkty w przestrzeni są oznaczone przez wektory. W czteroprzestrzeni możesz mieć dwa wektory, gdzie v1 = (x1, y1, z1, w1), a v2 = (x2, y2, z2, w2). Następnie manipulujesz tymi wektorami w taki sam sposób jak numery. Na przykład suma dwóch wektorów, v1 + v2 będzie (x1, y1, z1, w1) + (x2, y2, z2, w2). Następnie dodajesz te wektory termin po terminie, tak jak w liczbach, aby otrzymać: (x1 + x2, y1 + y2, z1 + z2, w1 + w2).

Twój program zdefiniuje wektory za pomocą odpowiednich tablic, a następnie wykona na nich operacje arytmetyczne w odpowiedniej kolejności.

Tom Au
źródło