algorithm - sistemas - ¿Hay O(1) estructuras de datos de acceso aleatorio que no dependen del almacenamiento contiguo?

perifericos de acceso secuencial (11)

¿Qué tal un trie donde la longitud de las claves está limitada a algún contante K (por ejemplo, 4 bytes para que pueda usar enteros de 32 bits como índices). Entonces, el tiempo de búsqueda será O (K), es decir O (1) con memoria no contigua. Me parece razonable.

Recordando nuestras clases de complejidad, no olvide que cada gran O tiene un factor constante, es decir, O (n) + C, Este enfoque sin duda tendrá una C mucho mayor que una matriz real.

EDITAR : En realidad, ahora que lo pienso, es O (K * A) donde A es del tamaño del "alfabeto". Cada nodo debe tener una lista de nodos secundarios A, que deberán ser una lista vinculada, para mantener la implementación no contigua. Pero A sigue siendo constante, por lo que sigue siendo O (1).

La estructura de datos de acceso aleatorio O (1) clásica es la matriz. Pero una matriz se basa en el lenguaje de programación que se utiliza para garantizar la asignación de memoria continua (ya que la matriz se basa en poder tomar un desplazamiento simple de la base para encontrar cualquier elemento).

Esto significa que el lenguaje debe tener una semántica con respecto a si la memoria es continua o no, en lugar de dejar esto como un detalle de implementación. Por lo tanto, podría ser deseable tener una estructura de datos que tenga O (1) acceso aleatorio, pero que no dependa del almacenamiento continuo.

¿Hay tal cosa?

Además de una tabla hash, puede tener una matriz de arreglos de dos niveles:

Almacene los primeros 10,000 elementos en la primera sub-matriz
Almacene los siguientes 10,000 elementos en la próxima sub-matriz
etc.

Aparte de las estructuras obvias anidadas a la profundidad finita observadas por otros, no estoy al tanto de una estructura de datos con las propiedades que describes. Comparto las opiniones de los demás de que con una estructura de datos logarítmicos bien diseñada, puede tener memoria no contigua con tiempos de acceso rápido a cualquier información que se ajuste a la memoria principal.

Soy consciente de una estructura de datos interesante y estrechamente relacionada:

Los cables de cedro son cadenas inmutables que proporcionan acceso logarítmico en lugar de tiempo constante, pero proporcionan una operación de concatenación de tiempo constante y una inserción eficiente de caracteres. El documento está protegido por derechos de autor, pero parece que hay una copia en la web en este momento.

Esta estructura de datos es lo suficientemente eficiente como para poder representar todo el contenido de un archivo grande que la usa, y la implementación es lo suficientemente inteligente como para mantener los bits en el disco a menos que los necesite.

En la práctica, para pequeños conjuntos de datos que usan almacenamiento contiguo no es un problema, y para grandes conjuntos de datos O (log (n)) es tan bueno como O (1); el factor constante es bastante más importante.

De hecho, para los conjuntos de datos REALMENTE grandes, el acceso aleatorio O (root3 (n)) es lo mejor que se puede obtener en un universo físico tridimensional.

Editar: Suponiendo que log10 y el algoritmo O (log (n)) sea el doble de rápido que el O (1) uno en un millón de elementos, se necesitarán un trillón de elementos para que sean pares, y un quintillón para el O (1 ) algoritmo para ser dos veces más rápido, más que incluso las bases de datos más grandes en la tierra.

Todas las tecnologías de almacenamiento actuales y previsibles requieren un cierto espacio físico (llamémoslo v) para almacenar cada elemento de datos. En un universo tridimensional, esto significa que para n elementos hay una distancia mínima de root3 (n * v * 3/4 / pi) entre al menos algunos de los elementos y el lugar que hace la búsqueda, porque ese es el radio de una esfera de volumen n * v. Y luego, la velocidad de la luz da un límite inferior físico de root3 (n * v * 3/4 / pi) / c para el tiempo de acceso a esos elementos, y eso es O (root3 (n)), sin importar qué algoritmo de fantasía tu usas.

Los mapas hash distribuidos tienen esa propiedad. Bueno, en realidad, no del todo, básicamente una función hash le dice qué cubo de almacenamiento debe buscar, allí probablemente deba confiar en los mapas hash tradicionales. No cubre por completo sus requisitos, ya que la lista que contiene las áreas / nodos de almacenamiento (en un escenario distribuido), de nuevo, suele ser un mapa hash (esencialmente convirtiéndolo en una tabla hash de tablas hash), aunque podría usar algún otro Algoritmo, por ejemplo, si se conoce el número de áreas de almacenamiento.

EDITAR:
Se olvidó de un pequeño tid-bit, es probable que desee utilizar diferentes funciones hash para los diferentes niveles, de lo contrario terminará con una gran cantidad de valores hash similares dentro de cada área de almacenamiento.

Seguramente de lo que está hablando aquí no es el almacenamiento contiguo de memoria como tal, sino más la capacidad de indexar una estructura de datos que contiene. Es común implementar internamente una matriz o lista dinámica como una matriz de punteros con el contenido real de cada elemento en otra parte de la memoria. Hay varias razones para hacerlo, y no menos importante, que permite que cada entrada tenga un tamaño diferente. Como otros han señalado, la mayoría de las implementaciones de hashtable también se basan en la indexación. No puedo pensar en una forma de implementar un algoritmo O (1) que no dependa de la indexación, pero esto implica al menos una memoria contigua para el índice.

Un poco de curiosidad: el hash trie ahorra espacio al intercalar en memoria las matrices de claves de los nodos que no colisionan. Es decir, si el nodo 1 tiene las teclas A, B, D, mientras que el nodo 2 tiene las teclas C, X, Y, Z, por ejemplo, puede usar el mismo almacenamiento contiguo para ambos nodos a la vez. Se generaliza a diferentes desplazamientos y una cantidad arbitraria de nodos; Knuth usó esto en su programa de palabras más comunes en Literate Programming .

De modo que esto le da a O (1) acceso a las claves de cualquier nodo dado, sin reservarle almacenamiento contiguo, aunque usando almacenamiento contiguo para todos los nodos colectivamente.

Por lo tanto, podría ser deseable tener una estructura de datos que tenga O (1) acceso aleatorio, pero que no dependa del almacenamiento continuo.
¿Hay tal cosa?

No no hay. Boceto de la prueba:

Si tiene un límite en su tamaño de bloque continuo, entonces obviamente tendrá que usar indirección para acceder a sus elementos de datos. La profundidad fija de direccionamiento indirecto con un tamaño de bloque limitado le proporciona solo un gráfico de tamaño fijo (aunque su tamaño crece exponencialmente con la profundidad), de modo que a medida que crece su conjunto de datos, la profundidad indirecta crecerá (solo logarítmicamente, pero no O (1) )

Es posible asignar un bloque de memoria para los datos completos, pero solo para una matriz de referencia para datos. Esto trae un ~~aumento~~ dramático en la disminución de la longitud de la memoria contigua necesaria.

Otra opción, si los elementos se pueden identificar con claves y estas claves se pueden asignar de forma única a las ubicaciones de memoria disponibles, es posible no colocar todos los objetos contiguamente, dejando espacios entre ellos. Esto requiere control sobre la asignación de memoria para que pueda distribuir la memoria libre y reubicar objetos de segundo grado en otro lugar cuando tenga que usar esa ubicación de memoria para su objeto de primera prioridad. Sin embargo, seguirían siendo contiguos en una subdivisión.

¿Puedo nombrar una estructura de datos común que responda a su pregunta? No.

Algunas respuestas pseudo O (1)

Una lista V es O (1) de acceso (en promedio), y no requiere que toda la información sea contigua, aunque sí requiere almacenamiento contiguo en bloques pequeños. Otras estructuras de datos basadas en representaciones numéricas también se amortizan O (1).

Una representación numérica aplica el mismo ''truco'' que una ordenación de radix , produciendo una estructura de acceso O (k) - si hay otro límite superior del índice, como ser un int de 64 bits, luego un árbol binario donde cada nivel corresponden a un bit en el índice toma un tiempo constante. Por supuesto, esa constante k es mayor que lnN para cualquier N que se pueda usar con la estructura, por lo que no es probable que mejore el rendimiento (la clasificación por radix puede mejorar el rendimiento si k es solo un poco mayor que lnN y la implementación de el tipo de raíz funciona mejor explota la plataforma).

Si usa la misma representación de un árbol binario que es común en las implementaciones de montón, termina en una matriz.

¿Tabla de picadillo?

Editar: Una matriz es O(1) búsqueda porque a[i] es solo azúcar sintáctica para *(a+i) . En otras palabras, para obtener O(1) , necesita un puntero directo o un puntero fácilmente calculable para cada elemento (junto con una buena sensación de que la memoria que está a punto de buscar es para su programa). En ausencia de un puntero a cada elemento, no es probable que tenga un puntero fácilmente calculado (y sepa que la memoria está reservada para usted) sin memoria contigua.

Por supuesto, es plausible (si es terrible) tener una implementación Hashtable donde la dirección de cada búsqueda es simplemente *(a + hash(i)) No se hace en una matriz, es decir, se crea dinámicamente en la ubicación de memoria especificada si tiene eso tipo de control ... el punto es que la implementación más eficiente va a ser una matriz subyacente, pero es ciertamente plausible tomar éxitos en otro lugar para hacer una implementación WTF que aún le consiga una búsqueda constante.

Edit2: mi punto es que una matriz se basa en la memoria contigua porque es azúcar sintáctica, pero una Hashtable elige una matriz porque es el mejor método de implementación, no porque sea necesario . Por supuesto, debo leer demasiado el DailyWTF, ya que me imagino sobrecargar al operador de índices de matriz de C ++ para que también lo haga sin memoria contigua de la misma manera.