metodos - sintaxis c#

Estructura de datos para las relaciones (2)

Debe preguntarse (y decirnos) qué tipo de patrón de uso espera. Si estas relaciones se agregan en orden o al azar, haga que sus consultas entren en orden (tal como las muestra) o de forma aleatoria, y esto es esencialmente un proceso por lotes - cárguelos, lea las consultas - o espera hacerlo es "en línea" en el sentido de que puede agregar algunos, luego consultar algunos, luego agregar algunos más y consultar algunos más?

¿Sabrá cuántos quiere almacenar de antemano, y cuántos espera almacenar? Docenas? ¿Miles? ¿Decenas de millones?

Aquí hay algunas sugerencias:

si sabes de antemano cuántos esperas almacenar, no es un número realmente grande, no esperas agregarlos después de la primera carga, no hay duplicados en el lado izquierdo del par, y ellos '' razonablemente "denso" en el sentido de que no hay grandes diferencias entre los números en el lado izquierdo del par, entonces es probable que desee una matriz. La inserción es O (1) , el acceso es O (1) , pero no puede tener índices duplicados y expandirlo después de compilarlo es una molestia.
si el número es realmente grande, como> 10 ⁸ , probablemente desee algún tipo de base de datos. Las bases de datos son relativamente muy lentas (de 4 a 5 órdenes de magnitud mayores que las estructuras de datos en la memoria), pero manejan datos realmente grandes.
Si tienes inserciones después de la primera carga, y te preocupa el orden, vas a querer algún tipo de árbol, como un árbol 2-3. Inserción y acceso a ambos O (lg n) . Probablemente encuentres una implementación bajo un nombre como "lista ordenada" (no soy un tipo C #).
En la mayoría de los casos, es probable que desee un hash. Promedio de inserción y acceso a O (1) , como una matriz; El peor caso [que no alcanzará con estos datos] es O (n)

Estoy convirtiendo un VB6 en C # y quiero hacer que mi estructura de datos mantenga los valores y las relaciones más eficientes. En VB tengo una colección de valores y otra colección de relaciones entre esos valores con prioridades para esas relaciones. También tengo un algoritmo que cuando se le pasa un conjunto de valores, se devuelven todas las relaciones necesarias para unir esos valores. Por ejemplo, supongamos que la colección de valores contiene 1-10 y la colección de relaciones contiene

1,2
3,2
5,2
2,8
8,10
9,10

Si la entrada fuera 1,9,10, las relaciones devueltas serían:

1,2
2,8
8,10
9,10

Dado que puede haber múltiples rutas, se devuelve la menor cantidad de relaciones, pero existe una advertencia de prioridades de relación. Si una relación tiene una prioridad más alta, esa relación se agregará y el resto de las relaciones se agregarán desde allí. Estoy pensando en usar una estructura de datos Disjuntos, pero no estoy seguro.

¿Algunas ideas?

Gracias

Más información --

El número de valores normalmente sería inferior a 100 y las relaciones inferiores a 500. Las colecciones son estáticas y el algoritmo se utilizará una y otra vez para encontrar rutas. Además, no pregunté esto, pero ¿sería el algoritmo en la estructura de datos Disjuntos configurada la más eficiente?

Parece que lo que tienes es un Gráfico . Esta es una estructura con Nodos y Bordes. Hay muchas bibliotecas y herramientas que se ocupan de Gráficos. Microsoft incluso publicó un documento sobre cómo lidiar con ellos. Creo que los gráficos son geniales y extremadamente útiles en muchas situaciones.

Un gran beneficio con los gráficos es la capacidad de asignar prioridades a los bordes entre los nodos. Luego, cuando desee encontrar la ruta entre dos nodos, boom, el gráfico puede elegir la ruta con la prioridad ideal.

En su situación, sus valores son los nodos y sus relaciones son los bordes.