¿Cada tipo de datos se reduce a nodos con punteros?

Una matriz o vector es solo una secuencia de valores. Seguramente se pueden implementar con una lista vinculada. Esto es solo un grupo de nodos con punteros al siguiente nodo.

Las pilas y las colas son dos tipos de datos abstractos que se enseñan comúnmente en los cursos Intro CS. En algún lugar de la clase, los estudiantes a menudo tienen que implementar pilas y colas usando una lista vinculada como la estructura de datos subyacente, lo que significa que volvemos a la misma idea de "colección de nodos".

Las colas de prioridad se pueden crear utilizando un montón. Un montón se puede considerar como un árbol con el valor mínimo en la raíz. Los árboles de todo tipo, incluidos BST, AVL, montones, pueden considerarse como una colección de nodos conectados por bordes. Estos nodos están unidos entre sí donde un nodo apunta a otro.

Parece que cada concepto de datos siempre puede reducirse a solo nodos con punteros a algún otro nodo apropiado. ¿Está bien? Si es así de simple, ¿por qué los libros de texto no explican que los datos son solo un grupo de nodos con punteros? ¿Cómo pasamos de los nodos al código binario?

Bueno, eso es básicamente a lo que se reducen todas las estructuras de datos. Datos con conexiones. Todos los nodos son artificiales, en realidad no existen físicamente. Aquí es donde entra la parte binaria. Debe crear algunas estructuras de datos en C ++ y verificar dónde aterrizan sus objetos en la memoria. Puede ser muy interesante aprender cómo se almacenan los datos en la memoria.

La razón principal de tantas estructuras diferentes es que todas se especializan en una cosa u otra. Por ejemplo, normalmente es más rápido iterar a través de un vector en lugar de una lista vinculada, debido a cómo se extraen las páginas de la memoria. Una lista vinculada es mejor para almacenar tipos de mayor tamaño porque los vectores deben asignar espacio adicional para las ranuras no utilizadas (esto es necesario en el diseño de un vector).

Como nota al margen, una estructura de datos interesante que es posible que desee ver es una tabla hash. No sigue exactamente el sistema de nodos y punteros que está describiendo.

TL; DR: Los contenedores son básicamente todos los nodos y punteros, pero tienen usos muy específicos y son mejores para algo y peores para otros.

Parece que cada concepto de datos siempre puede reducirse a solo nodos con punteros a algún otro nodo apropiado.

Oh querido no. Me estas lastimando.

Como traté de explicar en otra parte (" ¿Cuál es la diferencia entre un árbol de búsqueda binario y un montón binario? ") Incluso para una estructura de datos fija, hay varios niveles para entenderlo.

Al igual que la cola de prioridad que menciona, si solo desea usarla, es un tipo de datos abstracto. Lo usa sabiendo qué tipo de objetos almacena y qué preguntas puede hacerle. Eso es más estructuras de datos como una bolsa de artículos. En el siguiente nivel, su famosa implementación, el montón binario, puede entenderse como un árbol binario, pero el último nivel es por razones de eficiencia implementado como una matriz. No hay nodos y punteros allí.

Y también para los gráficos, por ejemplo, que ciertamente parecen nodos y punteros (bordes), tiene dos representaciones básicas, matriz de adyacencia y listas de adyacencia. No todos los punteros me imagino.

Cuando realmente intenta comprender las estructuras de datos, debe estudiar sus puntos buenos y sus debilidades. A veces, una representación usa una matriz para eficiencia (espacio o tiempo), a veces hay punteros (para flexibilidad). Esto es válido incluso cuando tiene buenas implementaciones "enlatadas" como el STL de C ++, porque allí también puede elegir a veces las representaciones subyacentes. Siempre hay una compensación allí.

$f:\mathbb{R} \rightarrow \mathbb{R}$

Nadie espera que digas todo eso solo para definir una función continua, de lo contrario, nadie podría hacer ningún trabajo. Simplemente "confiamos" en que alguien hizo el trabajo aburrido para nosotros.

Cada estructura de datos que posiblemente pueda imaginar se reduce a los objetos básicos con los que trata su modelo computacional subyacente, enteros en algún registro si usa una máquina de acceso aleatorio o símbolos en alguna cinta si usa una máquina de Turing.

Usamos abstracciones porque liberan nuestra mente de asuntos triviales, permitiéndonos hablar sobre problemas más complejos. Es perfectamente razonable simplemente "confiar" en que esas estructuras funcionan: ir en espiral a cada detalle es, a menos que tenga una razón específica para hacerlo, un ejercicio inútil que no agrega nada a su argumento.

Aquí hay un contraejemplo: en cálculo λ, cada tipo de datos se reduce a funciones. El cálculo λ no tiene nodos o punteros, lo único que tiene son funciones, por lo tanto, todo debe implementarse utilizando funciones.

Este es un ejemplo de codificación de booleanos como funciones, escrito en ECMAScript:

const T   = (thn, _  ) => thn,
      F   = (_  , els) => els,
      or  = (a  , b  ) => a(a, b),
      and = (a  , b  ) => a(b, a),
      not = a          => a(F, T),
      xor = (a  , b  ) => a(not(b), b),
      iff = (cnd, thn, els) => cnd(thn, els)();

Y esta es una lista de contras:

const cons = (hd, tl) => which => which(hd, tl),
      first  = list => list(T),
      rest   = list => list(F);

Los números naturales se pueden implementar como funciones iteradoras.

Un conjunto es lo mismo que su función característica (es decir, el containsmétodo).

Tenga en cuenta que la codificación de booleanos de la Iglesia anterior es en realidad cómo se implementan los condicionales en lenguajes OO como Smalltalk, que no tienen booleanos, condicionales o bucles como construcciones de lenguaje e implementarlos puramente como una función de biblioteca. Un ejemplo en Scala:

sealed abstract trait Boolean {
  def apply[T, U <: T, V <: T](thn: => U)(els: => V): T
  def ∧(other: => Boolean): Boolean
  def ∨(other: => Boolean): Boolean
  val ¬ : Boolean

  final val unary_! = ¬
  final def &(other: => Boolean) = ∧(other)
  final def |(other: => Boolean) = ∨(other)
}

case object True extends Boolean {
  override def apply[T, U <: T, V <: T](thn: => U)(els: => V): U = thn
  override def ∧(other: => Boolean) = other
  override def ∨(other: => Boolean): this.type = this
  override final val ¬ = False
}

case object False extends Boolean {
  override def apply[T, U <: T, V <: T](thn: => U)(els: => V): V = els
  override def ∧(other: => Boolean): this.type = this
  override def ∨(other: => Boolean) = other
  override final val ¬ = True
}

object BooleanExtension {
  import scala.language.implicitConversions
  implicit def boolean2Boolean(b: => scala.Boolean) = if (b) True else False
}

import BooleanExtension._

(2 < 3) { println("2 is less than 3") } { println("2 is greater than 3") }
// 2 is less than 3

Muchas (¿la mayoría?) Estructuras de datos están formadas por nodos y punteros. Las matrices son otro elemento crítico de algunas estructuras de datos.

En última instancia, cada estructura de datos es solo un montón de palabras en la memoria, o solo un montón de bits. Lo importante es cómo están estructurados y cómo los interpretamos y usamos.

La implementación de estructuras de datos siempre se reduce a nodos y punteros, sí.

¿Pero por qué parar allí? La implementación de nodos y punteros se reduce a bits.

La implementación de bits se reduce a señales eléctricas, almacenamiento magnético, tal vez cables de fibra óptica, etc. (en una palabra, física).

Esta es la reducción ad absurdum de la afirmación: "Todas las estructuras de datos se reducen a nodos y punteros". Es cierto, pero solo se relaciona con la implementación.

Chris Date es muy capaz de diferenciar entre implementación y modelo , aunque su ensayo está dirigido a bases de datos en particular.

Podemos ir un poco más allá si nos damos cuenta de que no hay una sola línea divisoria entre el modelo y la implementación. Esto es similar (si no idéntico) al concepto de "capas de abstracción".

En una capa de abstracción dada, las capas "debajo" de usted (las capas en las que está construyendo) son meros "detalles de implementación" para la abstracción o modelo al que se dirige.

Sin embargo, las capas inferiores de la abstracción a sí mismos tienen los detalles de implementación.

Si lees un manual para una pieza de software, estás aprendiendo acerca de la capa de abstracción "presentada" por esa pieza de software, sobre la cual puedes construir tus propias abstracciones (o simplemente realizar acciones como enviar mensajes).

Si aprende los detalles de implementación de la pieza de software, aprenderá cómo los creadores respaldaron las abstracciones que construyeron. Los "detalles de implementación" pueden incluir estructuras de datos y algoritmos, entre otras cosas.

Sin embargo, no consideraría que la medición de voltaje es parte de los "detalles de implementación" para cualquier pieza de software en particular, a pesar de que esto subyace en cómo los "bits" y "bytes" y el "almacenamiento" realmente funcionan en la computadora física.

En resumen, las estructuras de datos son una capa de abstracción para razonar e implementar algoritmos y software. El hecho de que esta capa de abstracción se base en detalles de implementación de nivel inferior, como nodos y punteros, es cierto pero irrelevante dentro de la capa de abstracción.

Una gran parte de comprender realmente un sistema es comprender cómo encajan las capas de abstracción. Por lo tanto, es importante comprender cómo se implementan las estructuras de datos . Pero el hecho de que se implementan, no quiere decir que no la abstracción de las estructuras de datos existe.

Una matriz o vector es solo una secuencia de valores. Seguramente se pueden implementar con una lista vinculada. Esto es solo un grupo de nodos con punteros al siguiente nodo.

Se puede implementar una matriz o un vector con una lista vinculada, pero casi nunca se debe implementar.

$n$$n$$\Theta(n)$$\Theta(\log n)$$\Theta(1)$(es decir, un bloque secuencial de memoria de acceso aleatorio). Además, en la CPU, acceder a la matriz real es mucho más simple de implementar y más rápido de ejecutar, y almacenarlo requiere menos memoria debido a que no tiene que desperdiciar espacio en punteros entre nodos separados.

Por supuesto, las matrices físicas reales también tienen sus desventajas: en particular, necesitan $\Theta(n)$ hora de insertar un nuevo elemento, algo que una lista vinculada puede hacer en $\Theta(1)$tiempo si ya tiene un puntero a un elemento vecino. Las inserciones al final de la matriz física se pueden amortizar hasta$\Theta(1)$en promedio, a costa de, como máximo, un factor constante de memoria adicional, simplemente redondeando el tamaño real asignado de la matriz hasta, por ejemplo, la potencia más cercana de 2. Pero si necesita hacer muchas inserciones y / o eliminaciones de elementos en el medio de su lista, una matriz física puede no ser la mejor implementación para su estructura de datos. Sin embargo, con bastante frecuencia, puede reemplazar las inserciones y extracciones con intercambios, que son baratos.

Si amplía un poco su alcance, para incluir arreglos físicos contiguos en su caja de herramientas, casi todas las estructuras de datos prácticas pueden implementarse con aquellas junto con nodos y punteros.

De hecho, no puedo pensar en ninguna estructura de datos común que necesite algo más, aunque en algunos casos se puede exprimir un poco de espacio o eficiencia de tiempo al salir de ese paradigma. Como un ejemplo ilustrativo de tal caso, considere la lista enlazada XOR , que permite implementar una lista enlazada transitable de dos vías utilizando (asintóticamente) no más espacio que una lista enlazada de una sola vía, reemplazando el nodo individual siguiente y anterior punteros por su XOR bit a bit, y también tiene algunas otras características convenientes (como un$\Theta(1)$operación de inversión). Sin embargo, en la práctica, esas características rara vez son lo suficientemente útiles como para superar sus inconvenientes, que incluyen complejidad de implementación adicional e incompatibilidad con los esquemas estándar de recolección de basura .

Si es así de simple, ¿por qué los libros de texto no explican que los datos son solo un grupo de nodos con punteros?

Porque eso no es lo que significa "datos". Estás combinando ideas abstractas con implementaciones. "Datos" es una idea muy abstracta: es solo otro nombre para "información". Un grupo de nodos vinculados con punteros (también conocido como "estructura de datos vinculados") es una idea mucho más concreta: es una forma específica de representar y organizar la información.

Algunas abstracciones de datos se prestan muy bien a implementaciones "vinculadas". No hay muchas buenas maneras de implementar la naturaleza de ramificación de un árbol completamente general sin usar nodos y punteros explícitos (o, algo de isomorfismo de nodos y punteros). Pero hay otras abstracciones que nunca implementaría usando nodos y punteros. Los números de punto flotante vienen a la mente.

Las pilas y las colas caen en algún punto intermedio. Hay momentos en que tiene mucho sentido hacer una implementación vinculada de una pila. Hay otros momentos en que tiene mucho más sentido usar una matriz y un solo "puntero de pila".