Comment fonctionne la «quatrième dimension» avec les tableaux?

30

Abstrait:

Donc, si je comprends bien (bien que ma compréhension soit très limitée), il y a trois dimensions avec lesquelles nous travaillons (généralement) physiquement:

Le 1er serait représenté par une ligne.
Le 2e serait représenté par un carré.
Le 3ème serait représenté par un cube.

Assez simple jusqu'à ce que nous arrivions au 4ème - C'est un peu difficile de dessiner dans un espace 3D, si vous voyez ce que je veux dire ... Certaines personnes disent que cela a quelque chose à voir avec le temps .

La question:

Maintenant, même si cela n'a pas beaucoup de sens, c'est très bien avec moi. Ma question n'est pas à ce sujet, ou je la poserais sur MathSO ou PhysicsSO. Ma question est: comment l'ordinateur gère-t-il cela avec des tableaux?

Je sais que vous pouvez créer des tableaux 4D, 5D, 6D, etc ... dans de nombreux langages de programmation différents, mais je veux savoir comment cela fonctionne.

Point d'interrogation
la source
66
Si 3 dimensions peuvent être visualisées comme un cube, alors 4 dimensions peuvent être visualisées comme un tas de cubes dans une ligne. 5 dimensions peuvent être visualisées comme une grille où chaque cellule de la grille contient ... un cube! Et ainsi de suite ... La "Quatrième Dimension" n'a rien à voir avec le temps (quel qu'il soit), à moins que vous ne le définissiez comme tel dans le contexte de la sémantique de votre programme.
FrustratedWithFormsDesigner
14
En général, vous pouvez surmonter cette bosse conceptuelle en essayant d'éviter de considérer les dimensions comme des constructions strictement physiques. Par exemple, certains problèmes d'apprentissage automatique peuvent avoir une dimensionnalité dans les centaines de milliers, où chaque dimension est une caractéristique de l'ensemble de données.
Steven Evers
6
Suite au commentaire de Steve Evers, pensez à un type de données commun: une couleur RVB. Cela a trois dimensions, vous pouvez donc considérer "l'espace colorimétrique" RVB. Ajoutez maintenant un composant alpha. Vous avez quatre dimensions.
Josh Caswell
25
N'oubliez pas que l'ordinateur ne se soucie pas de l'idée de dimensions géométriques - ce ne sont que des appareils pour la commodité humaine. Si vous allouez un tableau 5x5x5x5, l'ordinateur alloue simplement un tableau de 625 éléments et fait des calculs avec vos indices en conséquence.
David Zhang

Réponses:

77

Heureusement, les programmes ne sont pas limités par les contraintes physiques du monde réel. Les tableaux ne sont pas stockés dans l'espace physique, donc le nombre de dimensions du tableau n'a pas d'importance. Ils sont aplatis en mémoire linéaire. Par exemple, un tableau unidimensionnel avec deux éléments peut être présenté comme suit:

(0) (1)

Un tableau dimensionnel 2x2 pourrait alors être:

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

Un tableau tridimensionnel 2x2x2 peut être:

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

Vous pouvez, espérons-le, voir où cela va. Quatre dimensions peuvent être:

(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
la source
10
Les tableaux informatiques ne sont pas limités par la compréhension ou la visualisation humaine, mais ils sont limités par des contraintes physiques, par exemple un tableau de dimensions d chacune de longueur n prendra n ^ d, ou plus généralement avec des dimensions de longueur différentes, n1 × n2 ×… × Dakota du Nord.
acelent
6
@ColtonAllen: Je ne sais pas trop de quoi vous parlez. La définition de la dimension dit "En gros, c'est le nombre de coordonnées nécessaires pour spécifier un point sur l'objet." Un tableau déclaré en C comme int a[2][2][2];serait un tableau tridimensionnel.
Greg Hewgill
4
"Heureusement, les programmes ne sont pas limités par les contraintes physiques du monde réel" C'est pourquoi nous avons tous des processeurs à 4,5 THz, et personne ne se soucie de la hiérarchie de la mémoire, n'est-ce pas? C'est vraiment la réponse la plus drôle que j'ai lue ....
Manu343726
24
@ Manu343726 Il fait allusion au fait que nous vivons dans des dimensions (théoriquement) limitées de l'espace et du temps, mais les tableaux dans la mémoire de l'ordinateur ont des dimensions "prétendues" - tout est stocké dans un espace contigu linéairement en mémoire - donc ils ne sont pas limités à la nombre de dimensions dans lesquelles nous vivons. Don't troll> :(
Blackhawk
15
@ Manu343726: J'ai bien dit Programmes , pas Ordinateurs . C'est l'un des grands avantages des logiciels.
Greg Hewgill
49

Vous n'avez pas besoin d'imaginer dans des dimensions spatiales élevées, pensez simplement à une feuille de fougère. feuille de fougère

La tige principale est votre premier tableau, chaque branche étant un élément qu'elle stocke. Si nous regardons une branche, c'est votre deuxième dimension. Il a une structure similaire de branches plus petites venant de lui représentant ses données. Ceux-ci ont à leur tour leurs propres petites branches qui continuent jusqu'à ce que nous arrivions aux minuscules feuilles représentant les données du tableau de dimension intérieure la plus haute ou la plus haute.

Vous pouvez voir cette construction s'accumuler si vous déclarez chaque niveau avec son propre nom. Ici, je réutilise chaque niveau variable pour minimiser le code:

leaf = 2;
tinyBranch = [leaf, leaf, leaf];
middleBranch = [tinyBranch, tinyBranch, tinyBranch];
bigBranch = [middleBranch, middleBranch, middleBranch];
mainBranch = [bigBranch, bigBranch, bigBranch];
n00begon
la source
1
Cette visualisation ne représenterait-elle pas de plus près un tableau dentelé?
Matt Johnson-Pint
2
@MattJohnson Formellement oui, mais cet exemple explique / visualise également les tableaux multidimensionnels.
M.Mimpen
4
+1, ce n'est pas seulement une visualisation soignée, mais plus proche de la vérité que l'explication linéaire de nombreuses implémentations de tableaux. Que la plupart des gens ici restreignent ou non le terme «tableau» à la mémoire contiguë, « tableau multidimensionnel » est certainement le terme utilisé pour de tels arrangements dans la littérature pour de nombreuses langues.
DeveloperInDevelopment
46

Les dimensions sont ce que vous voulez être, la 4ème dimension ne doit pas nécessairement être le temps. Si vous pensez à trois dimensions comme un cube, vous pouvez penser à 4 dimensions comme une rangée de cubes. 5 dimensions, une grille de cubes, etc.

Vous pouvez également avoir une collection 3D de voxels, avec une 4ème dimension étant la couleur ou la densité ou une autre propriété.

Lorsque vous allouez la mémoire pour votre tableau multidimensionnel, il alloue simplement le produit de chaque dimension maximum pour votre type de données. Si vous avez un tableau 3D ou un «cube» de 10 éléments dans chaque dimension, vous aurez 1 000 éléments alloués. Si vous en faites un tableau 4d avec 10 éléments dans la 4e dimension, l'ordinateur allouera simplement 10 000. Augmentez-le jusqu'à 5 dimensions et il en allouera 100 000.

L'ordinateur ne se soucie d'aucune sorte de signification sur ce que représente chaque dimension. Pour sélectionner où se trouve un seul point dans la liste des éléments, il suffit de multiplier pour sélectionner une adresse mémoire.

comment s'appelle-t-il
la source
26

Imaginez faire de la R&D sur un nouveau dispositif médical, une série de capteurs que vous placez le long des bras d'un patient. Vous avez sept volontaires alignés pour le test. Chaque capteur signale des mesures basse fréquence, moyenne fréquence et haute fréquence, que vous prenez toutes les 100 ms pendant environ une minute.

Comment stocker toutes ces données en mémoire pour l'analyse et le traçage?

Un tableau, évidemment. Cela ressemblerait à ceci (en utilisant un pseudocode générique composé):

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

C'est un tableau à cinq dimensions, et il n'y a rien de délicat, mystérieux ou déroutant à ce sujet. Il n'y a aucune raison d'essayer de l'associer à l'espace euclidien à 5 dimensions. Pour obtenir une valeur de données, nous utilisons une expression comme

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

Cela revient à interroger une base de données relationnelle où vous avez un enregistrement pour chaque valeur de données, avec cinq colonnes contenant l'ID du patient, l'ID du capteur, etc., et une colonne avec la valeur. Pour obtenir un point de données, utilisez cinq termes dans WHERE: SELECT value FROM SensorData WHERE (patientid = 6) and (sensorid = 5) and (arm = "left") and (channel = "midfreq") and (sampleindex = 338 ).

Il n'y a rien de mystique dans une table de base de données avec cinq colonnes ou plus, n'est-ce pas?

(J'utilise l'indexation basée sur 1, mais dans la vie réelle, la base 0 est beaucoup plus courante.)

Notez que je suis un mauvais garçon en raison du codage en dur du nombre d'armes. Si je reçois un financement pour enquêter sur ces capteurs sur une pieuvre, je suis en difficulté!

DarenW
la source
3
+1 Excellent exemple démontrant que les dimensions peuvent être toutes les données dont vous avez besoin.
Mike prend en charge Monica le
20

Un tableau n'est qu'un bloc de mémoire continue. L'adressage de la mémoire est unidimensionnel, vous pouvez avancer ou reculer. Donc, en supposant que vous ayez un tableau à 5 éléments, 5 blocs de mémoire seront réservés. Si vous avez un tableau à 2 dimensions avec 5 éléments dans chaque dimension, 25 blocs de mémoire seront réservés.

Zillolo
la source
5
Oui, gardez cela à l'esprit lorsque vous ajoutez plus de dimensions à vos tableaux. L'utilisation de la mémoire n'est peut-être pas anodine.
davidhaskins
18

... ou je le demanderais sur MathSO ...

Eh bien, en fait, les mathématiciens n'associeraient jamais (ou du moins pas habituellement) une quatrième dimension à quelque chose comme le temps. Ils n'associeraient pas non plus les trois premiers à quelque chose comme: les mathématiciens définissent simplement la dimension comme une propriété abstraite, typiquement, d'un espace vectoriel (souvent cela sera généralisé aux variétés ou même aux espaces métriques ). Et cette définition abstraite ne se soucie pas du nombre de dimensions de l'espace physique dans lequel nous nous déplaçons. Le concept de dimensions s'applique aux espaces qui ne ressemblent même pas à l'espace physique. En fait, les mathématiciens (et même les physiciens) utilisent très souvent des dimensions infinies des espaces, tels que les espaces de Hilbert de la mécanique quantique.

Cela étant clarifié, parlons de tableaux - vous n'avez pas besoin de comprendre les espaces vectoriels, car la définition abstraite est en fait beaucoup plus simple ici.

Un tableau de taille ( 0 × 1 × 2 × ... × n −1 ) (c'est-à-dire de dimension n ) est simplement un ensemble de nombres 01 ⋅ ... ⋅ n −1 ( ou n'importe quel type d'objet remplit le tableau). La seule différence avec un tableau unidimensionnel de cette longueur est que vous avez un moyen particulièrement utile d'indexer les dimensions séparément, à savoir

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

à gauche
la source
Pour être clair, vous n'avez besoin que d'un tableau à 3 éléments pour décrire 3 dimensions, et un tableau à N éléments décrit N dimensions. Cependant, détailler chaque vecteur est une histoire différente. Souvent, cela se fait en affichant une image ( imshowen Python) - elle peut montrer deux dimensions spatiales ainsi qu'une troisième dimension de couleur.
Scott
@Scott: Je suis d'accord sur le fait que la notion de "dimension d'un tableau" est malheureuse car elle signifie quelque chose sans rapport avec la dimensionnalité d'un espace dont vous pourriez représenter les vecteurs par les tableaux. (Cependant, je pense également que ce n'est pas une bonne idée de représenter des vecteurs par des tableaux simples et non abstraits en premier lieu.) Un meilleur nom pourrait être le rang d'un tableau, par analogie avec des tenseurs .
leftaroundabout
13

En programmation, les tableaux sont assez faciles à implémenter, mais peut-être pas à comprendre.

Généralement, chaque niveau de tableaux signifie que le contenu est nplié. Cela signifie

  • int x[4]sont 4 blocs, chacun contenant un int.
  • int x[5][4]sont 5 blocs, chacun contenant un int[4].
  • int x[3][5][4]sont 3 blocs, chacun d'eux contenant un int[5][4].
  • int x[2][3][5][4]sont 2 blocs, chacun contenant un int[3][5][4].

La façon dont vous vous référez à eux dépend de vous, mais pour une meilleure compréhension, vous avez quelque chose comme

  • COLUMN pour le dernier
  • ROW pour l'avant-dernier
  • PAGE pour l'avant-dernier

Jusqu'ici, je l'ai lu quelque part. Pour rester ici, on peut aussi bien définir

  • BOOK pour l'avant-dernier
  • et peut-être SHELFpour l'avant-dernier. (Ou, si vous préférez, SHELFROWafin que nous puissions continuer.)

Cela dit, je n'ai jamais vu de tableau avec plus de 4 ou peut-être 5 dimensions dans la "vie sauvage".

De cette façon, vous pouvez définir et imaginer int x[6][2][3][5][4]comme une collection de 6 "étagères", chacune ayant 2 livres, chacune ayant 3 pages, chacune ayant 5 lignes, chacune ayant 4 colonnes.

glglgl
la source
13

Imaginez un tableau unidimensionnel comme une commode:

commode

Chaque tiroir est un index du tableau. Vous pouvez mettre ce que vous voulez dans chaque tiroir, et à de nombreuses fins, chaque tiroir ne contiendra qu'un seul élément (c'est un tableau unidimensionnel).

Cette commode est magique, elle n'est donc pas limitée par l'espace physique. Cela signifie que vous pouvez placer une autre commode à l'intérieur de chaque tiroir de la première commode. Les coffres intérieurs des tiroirs peuvent alors contenir tout ce que vous voulez. C'est un tableau à deux dimensions.

Vous pouvez donc dire quelque chose comme "ouvrez le tiroir supérieur de la première commode, sortez la commode de ce tiroir, puis ouvrez le tiroir inférieur de cette deuxième commode". Ce serait comme accéder à un index d'un tableau 2D: myArray [0] [3];

Et bien sûr, les commodes à l'intérieur de la commode la plus extérieure peuvent elles-mêmes contenir des commodes. C'est un tableau en trois dimensions.

Donc, votre question est: qu'est-ce qu'un tableau à quatre dimensions? C'est une commode à tiroirs de commodes à tiroirs de commodes à tiroirs de commodes, bien sûr!

Ce sont des tiroirs tout en bas.

Kevin Workman
la source
4
Ce sont des commodes tout le long, mec.
Thomas Eding du
8
Et dans la dernière commode? Tortues .
Kevin Workman
Être légèrement pédant. Étant donné qu'il y a 3 tiroirs dans chaque coffre (sur la base de l'image), pas 4, et que vous utilisez un index de base 0, le tiroir du bas serait 2 et non 3. Donc, au lieu de myArray[0][3]cela, ce serait le cas myArray[0][2]. Mais sinon bonne explication.
Tom Heard
@TomHeard La première commode a 3 tiroirs, mais la commode à l'intérieur du premier tiroir a 4 tiroirs. Duh! : p
Kevin Workman
1
Oh alors ça va. = D
Tom Heard
5

La plupart des aspects de cette question ont déjà été examinés, mais je pense que cela vous aidera si vous considérez la nature d'une dimension. Toutes les dimensions ne sont pas spatiales. Une dimension est un contexte de mesure. Voici quelques exemples:

  • Fréquence - couleur ou ton
  • Masse
  • Valence
  • Couleur (quark haut, quark bas, quark étrange, quark charmé, etc.)
  • Direction de rotation
  • Angle
  • Intensité
  • Hotness (de piment)

La "quatrième" dimension n'est que quatrième car il existe trois dimensions spatiales. L'espace et le temps occupent une place importante, car ils occupent une place importante. Très en face. Mais toute qualité quantifiable et mesurable peut être une dimension si vous la mesurez.

Par exemple, les soutiens-gorge ont trois dimensions: la taille de la tasse, la taille de la poitrine et l'interstitiel (je ne sais pas comment vous appelez les filles, mais je veux dire la distance entre les bonnets).

Peter
la source
1
"Toutes les dimensions ne sont pas spatiales." Pour les tableaux, toutes les dimensions sont spatiales.
Rhymoid
2
@Rhymoid: Pour les tableaux, aucune dimension n'est intrinsèquement spatiale dans notre façon de penser l'espace. : P Nous les définissons pour représenter tout ce que nous voulons.
cHao
@cHao Peut-être que si vous regardez la sémantique des données qu'ils stockent. Mais du côté représentationnel / syntaxique / implémentation, toutes les dimensions du tableau sont intrinsèquement spatiales. C'est en fait ce dont vous dépendez lorsque vous utilisez des tableaux dans le cadre d'un algorithme.
Rhymoid
@Rhymoid: C'est le même processus de réflexion qui a conduit à cette question posée en premier lieu. Une dimension énumérable ne la rend pas spatiale. Côté mise en œuvre, il n'y a pas d'espace. Il n'y a que de la mémoire, et la mémoire est unidimensionnelle pour autant qu'un programme connaisse / voit / se soucie.
cHao
@cHao: au niveau de l'implémentation, il y a de l'espace, car il y a aussi du temps. Le terme «fuite d'espace» (comme alternative à «fuite de mémoire», trouvé dans la communauté Haskell) n'est pas une coïncidence. Le fait que la mémoire soit décrite comme unidimensionnelle est un héritage de BCPL.
Rhymoid
4

En physique, nous supposons que chaque dimension spatiale est infinie, ce qui rend la recherche d'espace pour de nouvelles dimensions assez difficile.

Lorsqu'il s'agit de tableaux finis, il est facile de trouver de l'espace.

Imaginez une feuille de papier avec une grille imprimée dessus; vous pouvez écrire des informations dans chaque cellule de la grille. C'est un tableau 2D: ligne et colonne.

Mettez plusieurs de ces feuilles de papier dans un dossier de fichiers; c'est un tableau 3D: page, ligne et colonne.

Mettez plusieurs de ces dossiers dans une boîte de fichier. Tableau 4D: dossier, page, ligne, colonne.

Disposez les boîtes dans une grille rectangulaire sur une palette en bois. Tableau 6D: boîte-ligne, boîte-colonne, dossier, page, ligne, colonne.

Empilez plus de grilles de boîtes par-dessus. Tableau 7D: profondeur de boîte, ligne de boîte, colonne de boîte, dossier, page, ligne, colonne.

Commencez à entasser des palettes dans un conteneur d'expédition: matrice 9D. (En supposant que chaque pile est aussi haute que l'intérieur du conteneur, vous ne pouvez donc obtenir que 2 dimensions supplémentaires ici.)

Empilez des conteneurs d'expédition sur le pont d'un porte-conteneurs: matrice 12D.

Votre flotte de porte-conteneurs est désormais un réseau 13D.

Russell Borogove
la source
"nous supposons que chaque dimension spatiale est infinie" l'infini n'est pas le plus gros problème ici, continu est le "vrai" problème (c'est-à-dire infiniment infini, et nous avons besoin d'une cartographie homéomorphe pour qu'elle soit physiquement significative).
leftaroundabout
3

Dans le système de coordonnées cartésiennes, vous avez les axes x et y sur un plan. Vous pouvez représenter n'importe quel nombre sur le plan comme (x, y).

Dans trois «espace» (autrement connu comme un cube), vous pouvez avoir les axes x, y et z. Vous pouvez représenter n'importe quel élément du cube sous la forme (x, y, z).

Dans un espace multivarié, vous pouvez avoir les axes x, y, z et, w (où l'axe w est "imaginaire"). Vous pouvez représenter n'importe quel élément de cet espace sous la forme (x, y, z, w).

Tous ces points dans l'espace sont désignés par des vecteurs. Dans quatre espaces, vous pouvez avoir deux vecteurs, où v1 = (x1, y1, z1, w1) et v2 = (x2, y2, z2, w2). Ensuite, vous manipulez ces vecteurs comme vous le feriez avec des nombres. Par exemple, la somme des deux vecteurs, v1 + v2 serait (x1, y1, z1, w1) + (x2, y2, z2, w2). Ensuite, vous ajoutez ces vecteurs terme par terme comme vous le feriez pour les nombres, pour obtenir: (x1 + x2, y1 + y2, z1 + z2, w1 + w2).

Votre programme définira les vecteurs à l'aide de tableaux appropriés, puis effectuera des opérations arithmétiques sur eux dans l'ordre approprié.

Tom Au
la source