Structure de données. Une organisation dans l’informatique pour le stockage des données digitales qui dépend des opérations individuelles sur ces données, et une fois déterminées, dépend donc du rendement théorique de l’implémentation concrète des opérations et du stockage.
L’origine des structures de données au niveau du « hardware » est toute binaire, étant donné que tous les ensembles, toutes les associations et tous les types primitifs de données sont les produits d’un codage binaire. Étant donné que le stockage de donnée est magnétique ou électronique et un support pour les 1s et 0s numériques, ces nombres binaires représentent les entiers qui représentent les caractères — si les binaires ne représentent pas de booléens dans l’espace du programme. Soit les entiers ou caractères ou booléens, tous les primitifs forment les séquences, et les séquences commencent à former les structures de donnée : les tableaux variables, les listes, les ensembles, les piles, les files d’attente, ainsi de suite. Nous ne pouvons pas les lire ou les comprendre sans algorithmes ou plans pour faire d’action sur leur donnée. Les séquences nous pouvons donc tirer dans une logique — et nous pouvons construire des expressions logiques avec code. Après tout, nous encodons les électrons sur le disque pour en utiliser — pour la résolution des problèmes du monde. Si nous sommes les physiciens se servant déjà la mathématique pour la physique quantique, nous pouvons bondir dans la virtuelle et articuler comment nos expressions logiques peuvent être crées à partir de séquences. Nos séquences auraient donc été créées de nos types de données, et nos types de données auraient été créés des 1s et 0s du support électronique.
Mais bien que Wirth et d’autres prétendent que les structures binaires étaient choisies à cause du modèle de la charge électrique, comme si l’ordinateur avec structure de donnée était descendu de la physique, d’un autre point de vue, la structure de donnée est un descendent de la mathesis leibnizienne, un characteristica universalis. En fait, Leibniz avait conçu une arithmétique qui consisterait (voilà) des 1s et 0s. Alors, l’invention de l’ordinateur qui pourrait marcher sur le code binaire, elle soit un produit ainsi des grands songes mathématiques depuis Descartes, Leibniz et Pascal. Et Von Neumann et les fondateurs de l’informatique étaient noués à cet appareil binaire du XVIIe siècle, soit réel, dans le cas de Pascal, ou théorique dans le cas de Leibniz, parce que la théorie de l’information aura paradoxalement créé un signal des séquences du code binaire comme s’il était le bruit duquel il est distingué. Selon la théorie de l’information, si nous connaissons bien ce qui est le bruit, comme résultat, nous savions qu’un signal est simplement une variation sur le bruit. Un changement subtil dans le bruit devient le signal. Nous pouvons donc articuler, en sortir de ce qui est à nous le bruit, la signification pour une machine, un langage qu’elle peut lire et que nous y créons, mais ne lisons pas.
Nous ne lisons pas de donnée, sans intermédiaire. Une structure de donnée ne peut pas être complètement articulée sans ses procédures. La donnée comme objet n’existe pas, du moins en ce moment quand nous posons la question de quoi/comment sont ces structures de données. Pour démontrer bien ce fait, nous devions prendre l’informatique en sa naissance. Ses exemples du code paraient tous bizarres dans cet âge et en même temps qu’ils ressemblent une production presque hier. Dans son livre, Algorithms + Data Structures = Programs, Niklaus Wirth décrit un buffer circulaire, un système pour accès à la donnée avec divisions pour la consomption/production qui orchestrent le partage concurrent de ressources et réutilisent un nombre fixé des bytes. Le code, en entier (1985, 2004, p. 31) :
MODULE Buffer ; IMPORT Signals ; CONST Np = 16 ; (*size of producer block*) Nc = 128 ; (*size of consumer block*) N = 1024 ; (*buffer size, common multiple of Np and Nc*) VAR ne, nf : INTEGER ; in, out : INTEGER ; nonfull : Signals.Signal ; (*ne >= 0*) nonempty : Signals.Signal ; (*nf >= 0*) buf : ARRAY N OF CHAR; PROCEDURE deposit(VAR x: ARRAY OF CHAR) ; BEGIN ne := ne — Np ; IF ne < 0 THEN Signals.Wait(nonfull) END ; FOR i := 0 TO Np-1 DO buf[in] := x[i] ; INC(in) END ; IF in = N THEN in := 0 END ; nf := nf + Np ; IF nf >= 0 THEN Signals.Send(nonempty) END END deposit; PROCEDURE fetch(VAR x: ARRAY OF CHAR) ; BEGIN nf := nf - Nc; IF nf < 0 THEN Signals.Wait(nonempty) END ; FOR i := 0 TO Nc-1 DO x[i] := buf[out] ; INC(out) END ; IF out = N THEN out := 0 END ; ne := ne + Nc ; IF ne >= 0 THEN Signals.Send(nonfull) END END fetch; BEGIN ne := N ; nf := 0 ; in := 0 ; out := 0 ; Signals.Init(nonfull); Signals.Init(nonempty) END Buffer.
Les constructions de codage de l’exemple représentent un type du buffer qui est réellement linéaire sur le support, mais son module se sert les signaux (vis-à-vis d’importation du module « Signal »), et ces indications si l’input doit être écrit au disque ou l’output doit être extrait du disque — comme si le buffer pourrait être réutilisé continuellement, en cercle. Plus complexe que les « getters » et les « setters », cet algorithme doit prendre en considération la disponibilité de ressources, et au-delà seulement le disque. La saisie et la sortie de donnée sont cachées derrière des motifs de producteur/consommateur, qui agrandissent son abstraction loin des disques, dans un règne de la théorie, sauf que cet exemple du code est arrosé aux contraints; la taille du buffer maximum est 1024 bytes, peu de stockage disponible aujourd’hui. 1024 est en revanche une quantité imaginable facilement par les humains, et elle est donc concevable comme séquence. La séquence 1024, en intersection aux régions 128 et 16, respectivement pour consommateur et producteur, elles font commencer le fait dans l’informatique qu’on doit énumérer des choses dans la science des structures de donnée. La fonction « deposit », elle fait comme ça, prenant les caractères textuels, une séquence de chaque caractère. Et elle attend le moment quand il y a de donnée au buffer vis-à-vis du module « Signal » jusqu’à cette allocation n’est pas pleine, c’est-à-dire est écrit par processus au disque. Une fois que l’allocation est vide, le module « Signal » transmise sa condition de vide. Pour la fonction inverse, « fetch », le module « Signal » attend l’allocation pleine, pour que la donnée dans le buffer de sortie puisse être prise du disque selon un processus très similaire au processus de producteur ou le buffer de saisie ci-dessus (« deposit »). Toutes majuscules dans l’exemple, les commandes de l’algorithme indiquent qu’ils sont presque les opérations sur des « bytes purs ». Et les bytes purs sont une binaire en suivant une autre, un flux d’informations non différencié en contraste de procédures. Seulement vis-à-vis de l’explication de ces procédures en prose et programme de Wirth, ce flux devient une structure de données.
Au niveau de processus mentaux des humains, alors, ce que font les programmateurs en ses moments du plan de la structure de donnée est déterminé premièrement par l’opération conceptuelle de donnée. Sa discipline théorique d’opérations conceptuelles s’appelle la théorie des types abstraits de données, bien que les implémentations individuelles, les types concrets de données contribuent à la théorie aussi.
Malgré qu’en quelque degré, le champ du code binaire est une table, les programmateurs utilisent les tables variables (arrays), qui fonctionnent en le groupement des valeurs comme sous-ensembles de la donnée d’une machine ou appareil distribué. Avec les tables variables, nous pouvons énumérer les choses représentées par les valeurs de la table variable. Sa structure conceptuelle est donc une liste. Le fait que les contenus d’une liste s’énumèrent, il correspond au fait que chaque valeur de la liste se sert un indice, et la première valeur souvent mise avec un 0 où le deuxième est indice 1, le troisième est 2, etc. Dans les implémentations communes, l’ordre des éléments suit l’ordre dans lequel les valeurs sont mises en liste. Alors que les éléments de la liste ou table variable, ils peuvent être ordonnés, en contraste d’un arbre, l’ordonnant de la table n’est pas hiérarchique. La liste plus commune est l’ensemble de résultats d’une base de données, où les contenus sont le produit d’une requête qui résulte dans une réponse, une catégorie. Il n’est pas une hiérarchie parce que chaque valeur appartient en la même manière de cette catégorie. La table variable, puis sans hiérarchie est la partie fondamentale d’énumération. C’est un champ moins différencié, comme une mer de nombres binaires. Elle met en renvois son ordre conceptuel, au XVIIIe siècle dans lequel il y avait une table seule de la donnée de tout le monde, c’est-à-dire, au moins métaphoriquement.
Dans l’ensemble de résultats, la réponse est souvent agrégée dans une partie, et le programmateur doit en utiliser, pour que le processus conceptuel qui accompagne l’énumération soit une itération. Selon la logique d’itération, le système informatique ressuscite un ordre qui a été imposé sur la collection des valeurs. Si la collection était donnée un ordre, c’est susceptible que le programmateur voudrait itérer la liste dans le même ordre, ou elle mettra de nouveau dans un ordre différent. En addition de la liste, toutes collections, on peut faire leur itération, soit un table de hachage, ensemble, arbre, ou table variable. L’itération dans l’informatique marque l’arrivé d’une notion des groupes sans une notion mandataire de quantité. Une procédure peut être écrit qui ignore — on peut dire — la quantité. Donnez-moi une collection avec quelconque nombre d’items dont j’ignore pour que j’en traverse, appliquant mes algorithmes de chaque item. Mais je ne sais quoi, le n-ième. Donnez-moi une table de hachage et j’itèrerai à travers ses clefs pour que je puisse appliquer mes algorithmes à ses valeurs pour chaque clef. Mais je ne sais quoi, le n-ième. De plus, l’itération est un processus par excellence à cause du fait qu’elle est en fin de compte, la répétition. Comment doit-on faire d’inférence sur une induction vaste d’items, la mer d’énumération ci-dessus ? Créez un processus qui exécute pour chaque item; sa définition est le tableau de toutes ses instances — tout qui se plaisait beaucoup Chancellor Bacon.
Si les structures de données permettent un niveau d’abstraction qui enlève le besoin pour savoir combien de valeurs dans cet ensemble ou une autre, cette abstraction permet aussi les programmateurs à faire des plans élaborés pour les conditions d’identité dans la donnée, soit collective, individuelle, ou indicielle. La table de hachage, par exemple, est une structure de donnée d’association, pour faire une relation entre la clef et la valeur et, comme résultat, pour permettre l’identité de la valeur d’être représentée par la clef seule. L’ensemble, bien théorique, dépend de valeurs uniques, parce qu’un nombre est une classe et le groupement des nombres démontre seulement les rapports entre chaque nombre du même niveau de la structure. La liste ordonnée dépend d’un attribue que le programmateur sélectionne, pour que quelconque section de la liste devient un ensemble d’un ordre linéaire avec sa propre indexicalité. Le multiensemble (en anglais, bag) est une agrégation des éléments dans laquelle on peut avoir des duplications, ainsi qu’une valeur dedans n’est pas une classe, mais une instance possiblement avec la même classe d’une autre instance en dedans.
La table de hachage, la structure de donnée d’association, s’appelle aussi une table variable associative. C’est essentiellement une table variable, mais plutôt que seulement les indices numériques, la table de hachage est ordonnée par des clefs qui pourraient être des caractères alphabétiques, mots, ou tous objets de programmation qui peuvent être donné une identité, être comparé, et donc être ordonné. L’identité de la table de hachage est déterminée par l’identité de sa clef, tour à tour déterminée par la computation d’un hachage numérique pour chaque membre de la clef objet, où les valeurs de la computation sont mis en appendue avec une prime, par exemple :
final int prime = 31; int résultat; résultat = prime * résultat + titre.toString().hashCode(); résultat = prime * résultat + année.toString().hashCode(); ...
Après le calcul de hachage, l’ordonnant est fait à cause de l’ordre de nombres associés avec l’item de la table. Mais, le calcul de hachage n’a pas d'importance seulement pour ordonnant, mais aussi pour la garante des clefs uniques. Sans cette garante il y aurait une perte de données en cancellation d’une valeur par une autre avec la même clef. Philosophiquement les implications sont désastreuses s’il est qu’il y a une perte de l’association en addition à la perte de données. La liaison entre la clef, souvent une pièce de texte courte et sa valeur perdue est métaphoriquement pour nous à perdre la donnée de la clef, à perdre un référent pour les mots du langage. En ce moment, nous sommes retournés aux procédures et explications linguistiques des structures de donnée, à l’illisible du code binaire sur le support de l’ordinateur précédant à toute programmation.
L’ensemble, la structure de donnée d’identité est, différemment, noué entièrement à la théorie de classes en ce moment quand le programmateur décide d’utiliser, une structure de donnée sans duplication. S’il est seulement une chose, cette chose cesse d’être une instance et devient une classe. Une fois que cette chose est devenue une classe, tout à coup, les relations entre tous autres membres deviennent mises en définition. L’ensemble devient donc un agrégé des catégories toutes sur le même niveau hiérarchique. En abstraction, un ensemble est une déclaration des constituants, un modèle d’une relation entre plusieurs catégories. Pour cette raison, nous pouvons posséder la notion de l’ensemble vide, qui est quelque chose, en même temps qu’il n’est « rien ». Puisque nous ne pouvons pas avoir rien sans une catégorie théorique qui se substitue, il est l’ensemble vide qui démontre que tous nombres dans un ensemble sont les classes ou les catégories. Tous genres de rien sont une unité. Alors, les nombres dans un ensemble fournissent une méthode pour créer un schéma parfait, sans redondance, mais sans la propriété d’une architecture au-delà d’un seul niveau hiérarchique. L’ensemble est un récipient mystérieux qui engorge ses éléments et puis annonce ceux qui peuvent exister — seulement les uniques.
Si l’ensemble est tout déterminé par la théorie de classes, la liste ordonnée reprendre les éléments uniques d’un ensemble et les met dans une particularité reconstruite comme instances. Il fait un indice, ou collection des indices dans laquelle les classes puissent être dupliquées, mais qui puissent incorporer la hiérarchie et les références multiples aux locations différents de la même classe. C’est un ensemble des listes ou une liste d’ensembles, et dans chaque sous-structure, les éléments emploient des comparateurs pour déterminer les niveaux d’importance de l’ordonnant. S’il y a une hiérarchie de filtrages du comparateur, la liste peut être réglée avec bien d’homogénéité, comme si tous les éléments sont du même niveau. Alors, les données peuvent exister sous les classifications alphabétiques, par exemple, et elles soient réglés après discrimination alphabétique, selon les indices numériques. Le comparateur est tout détaché de la donnée, mais dans son application, l’indexicalité d’items s’émerge. En ce sens les classes ont été transformées dans les instances dans la place où l’ordonnant numérique s’agrandisse sur l’ordonnant alphabétique de ses parents dans la liste.
La condition de données quand les instances sont faites d’ensembles de classes est continuée
dans le multiensemble, mais sans comparateur qui le donne un ordre
hiérarchique. Les éléments du multiensemble ne sont pas de classes sauf que si nous les
entendons d’être des classes dupliquées, ou les ensembles d’entiers naturels, qui peut avoir
des duplications. En contraste au comparateur qui opère sur les éléments d’ensemble, la
définition formelle d’un multiensemble associe plus généralement une fonction pour chaque
élément. Cette fonction est le producteur de valeur surtout si les éléments du multiensemble
sont des nombres algébriques, ou des caractères symboliques, par exemple, l’élément a
-> f(a) -> 17
. C’est comme si les bornes de multiensemble sont déterminées par
l’espace de
contenues possibles, comme s’il est une mer, mais de plus importance, comme si notre monde
est
le plus parfait multiensemble. Dans notre monde nous avons la duplication seulement de la
classe; il'y n’a pas d’objets dupliqués réels. Alors pour utiliser le multiensemble comme
formalisme, nous devions comprendre qu’il modèle les conditions de l’identité d’objets en
nature, malgré le fait que nous parlons du multiensemble dans le contexte mathématique
(toujours en nature aussi). En même temps, le multiensemble mathématique est l’homologue aux
multiensembles du monde où tous objets sont uniques. Et en fait, les structures de données
sont toutes uniques : toute donnée s’encode en adresses uniques, et reste sur les supports
de machines matérielles et réelles — bien sûr, le vrai contexte pour le problème des
structures de donnée.
Au-delà des collections, ensembles, ou tables, les arbres et les réseaux (rameau et réseau) articulent une identité plus différenciée qu’une donnée de soupe ou mer symbolique, à cause d’un ordre hiérarchique ou l’existence des arêtes et sommets. L’arbre, c’est un rameau (branch) qui représente un flux de parenté dans le sens qu’il est élément de noeuds enfants et d’une racine ultime de laquelle tous enfants descendent. Son ordre conceptuel est généalogique et presque lié complètement aux êtres vivants, comme si l’abstraction mathématique avec l’arbre est nouée irrévocablement à un vitalisme néanmoins distant. L’arbre reste vitaliste à cause de cette détermination de valeur vis-à-vis de la hiérarchie. Les parents et noeuds enfants peuvent les deux être les producteurs de valeur avec leurs responsabilités individuelles et les noeuds enfants soient toujours les inférieurs — jusqu’au moment quand l’arbre s’inverse à cause d’une rupture intérieure. Les sociétés entières et toutes leurs infrastructures dépendent des hiérarchies avant la notion du réseau. L’arbre est une grande structure qui est bâtie de noeuds et noeuds — même si les arbres sont navigues dans l’informatique sous schéma du noeud individuel. Un arbre est donc une structure hiérarchique, mais qui contient des parties qui s’invitent d’autres paradigmes, la perspective des noeuds est de bas en haut, en dedans de cette grande structure — en toute possibilité ses identités fournissent le modèle traditionnel, la manière dont le monde s’achève sa diversité et hétérogénéité, mais sans accès adéquat aux noeuds.
Le réseau est cependant un modèle des noeuds non hiérarchiques avec plus d’accès. Tous les noeuds donnent tel accès à tous autres noeuds. La mathématique de réseau donc prend tous points d’espace et trouve leurs liaisons de la forme de arrêtes et de voisins. Comme la fonction d’élément du multiensemble, ou le comparateur de la liste ordonnée, le réseau est créé des sommets seuls — les points sans liaison. La fonction mathématique ou informatique du noeud de réseau, elle construite les renvois et les liaisons entre des noeuds. Pour cette raison, les noeuds sont faits de nouveau — plusieurs temps — sans une définition ultime. C’est comme si un réseau est un arbre temporel, qui doit être refait pour exister dans le temps. Alors, le tableau des connexions est toujours partiel, et son image principale est un graphique, tous en points, mais sans tous ses points liés — pour que nous avons d’arrêtes (edges). Un chemin partiel se tisse, et le graphique du réseau est devenu un masque qui se décolle comme si le réseau est la peau d’un lépreux. Plus que les arbres, alors, les réseaux sont vraiment des noeuds de bas en haut, et ils font le codage distribué possible et la renaissance du code morte, comme les dépôts de source tels que Git. En ultime, puisque le réseau est fait plutôt que découvert, il est parfait pour l’apprentissage automatique, qui crée des liaisons pour comprendre la donnée de sa saisie.
Avec les réseaux et les arbres, nous avons les territoires, les topologies. Les procédures informatiques qui construisent ces topologies les font simplement; les créent comme objets ou surfaces. La pile se concerne cependant — en plus degré — des états durant l’exécution, où le programme marche bien, avec des couches/états qui sont tout à coup enlevés. L’une en haut est désemplie; l’autre, puis, est la prochaine, qui était entrée avant la couche en haut. Dans une manière certaine, la pile est toute liée de la pratique du film et l’animation; en ce moment quand l’état est changé, elle est l’analogue du cadre dans lequel est fait le montage. Le montage en pile informatique est une substitution de l’état courant à un nouvel état. C’est en fait un montage de bits, ou plutôt d’états discrets, mais différents que film, ses substitutions sont rendues sur la condition qu’il y a une inversion : après les états ou couches entrent la pile, ils sortent. Alors, les états sont les contenues, mais leurs changements sont divisés entre leur passage dedans et dehors. Si nous empilons un ensemble entier, souvent nous sommes les témoins de sa désemplisse. Les piles sont effectives comme structures de donnée parce que leur formalisme procédural est directement l’homologue de la machine comprise des bits ou binaires. Tous ses sous-fifres sont cordonnés dans l’ensemble éternel le plus grand, et avec une vitesse. Doit-on demande, si les premiers sur la pile sortent dernièrement; la pile, est-elle une référence bizarre à la théologie de J.C., que la pile est l’arbitre ultime et son support n’est peint pas en électrons seuls, mais dans un microcosme eschatologique ?
Non, à cause du fait que quelque d’autres structures de donnée s’agit FIFO, les premiers seront les premiers, dans le cas de la queue ou la file d’attente. La queue est un réservoir temporaire, un moment quand le calcul est appliqué aux données entrantes dedans. Elles y restent jusqu’à elles sont calculées. C’est comme s’il n’est pas même un réservoir, mais simplement une friction dans la vie de donnée, surtout parce que leur ordre ne doit pas être dérangé. FIFO se présume en pleine transparence. C’est toujours : calculez la donnée qui est ici, premièrement. La donnée de la queue est une donnée de batch; la donnée de la pile, en contraste, est un système d’exécution qui gère des données, qui retourne l’état de la machine à son début. La pile donne une naissance à l’exécution de la machine et la reprend; la queue n’offre aucune restauration ou résolution de la machine. Le processus qui travaille sur les données de queue est un état, sur la pile, les données aussi, ainsi que son contraste est entre la création et destruction de tout état du système et un processus créé, qui sert les données passagères. Pauvre théologie de FIFO : le système de simulation, c’est la pile, en homologue au monde non virtuel, et peut-être, la structure de donnée la plus importante.
En addition du plan conceptuel, l’autre détermination de la structure de donnée est le savoir des stratagèmes pour un bon rendement de la machine. Étant donné une structure de donnée comme type abstrait de donnée, puis, quoi est son degré de rendement ? Au degré que les algorithmes qui définissent les structures de donnée, ils sont noués plus près du support des binaires, ils performent bien. Et si nous avons plusieurs processeurs ou UCs, le travail du calcul sur les données devient distribué. Pour mesurer le degré auquel les structures de données marchent bien, considérons la notation asymptotique (en anglais, Big O Notation). C’est une notation pour l’expression de l’intensification de temps du calcul durant l’exécution d’un algorithme sur les données — toutes avec leurs structures qui les procédures y définissent. Si un processus s’opère en temps logarithmique, il est le meilleur de rendements — sauf le temps constant. En temps linéaire, l’algorithme exécute moins vite, mais il maintient seulement un agrandissement arithmétique — seulement l’addition du temps. Si un processus s’opère en temps exponentiel, ses additions à la quantité sont plutôt multiplications et la vitesse de son agrandissement est géométrique. Pour finir, le temps le pire est représenté avec la notation factorielle, qui va au-delà de multiplication par pouvoir, à la multiplication de tous nombres en range de zéro jusqu’à quelque facteur indiqué par n. La version binaire des types abstraits de données souvent marche mieux — les arbres binaires, le chaînage XOR, etc. Les tables de hachage, elles aussi, parce qu’elles réduisent la donnée à un hachage, les applications retiennent un bon temps de recherche ou positionnement.
C’est important de considérer la performance des structures de donnée, parce que la création en fait des ordinateurs qui marchent dans le virtuel, mais sur les supports matériaux, contribue en grand façon à la théorie des structures de donnée et la théorie des types abstraits de données. Sans en effet mettre la mathématique en conversion aux ordinateurs qui exécutent les programmes réels et matériaux, il ne serait aucune progression ou intensification des études informatiques ou — vraiment aujourd’hui — des mathématiques. En toute réalité, il y a une tournure de calcul (computational turn) en philosophie, mais aussi dans la science qui a créé les ordinateurs premièrement — à cause de ces ordinateurs. Toutes disciplines sont avancées à cause du savoir de la pratique, d’elle-même éprouvant ses théories dans l’échec de maintenir la haute théorie ou de garder une mathématique pure. Il y a de nouveaux savoirs de la machine, les nouveaux savoirs communiqués à nous, par exemple, du compilateur. Dans la naissance de l’informatique, c’était un moment de nouveau savoir en trouvant l’aide de la machine. Après cette tournure du calcul en toutes disciplines, nous avons besoin de retourner à ce moment quand en fait l’ordinateur était un outil philosophique, un outil pour tous les problèmes de l’épistémologie et l'ontologie les plus grandes.
(B) - 8 novembre 2015.