¿Qué estructura de datos persistente para un conjunto de elementos parcialmente ordenados?

Necesito almacenar conjuntos de elementos de tipo a. El tipo a está parcialmente ordenado, por lo que comparar y puede devolver menor, mayor, igual o incomparable. $a_1$ $a_2$

Un problema con las tablas hash es que dos elementos iguales se pueden representar de manera diferente, y no tengo acceso a una función hash coherente con la igualdad.

Comparar dos elementos puede ser un proceso largo, por lo que sería interesante minimizar las comparaciones. Si es necesario, es posible memorizar llamadas al operador de comparación. Ahora me doy cuenta de que solo necesitaré almacenar antichains (o supongamos que sí). Más precisamente, las operaciones que tendré que realizar son las siguientes:

Eliminar un elemento de la antichain;
Intenta agregar un elemento. Si el elemento es más pequeño que un miembro, no lo agregue, de lo contrario, agréguelo y elimine todos los elementos más pequeños.

También puedo vincular cada elemento con dos enteros, de modo que si sé que e , entonces saber me da instantáneamente . Por supuesto, no significa ... Encontrar límites enteros es una operación relativamente barata en comparación con una comparación completa de elementos. $i_1 < a < i_2$ $i_3 < b < i_4$ $i_2 < i_3$ $a < b$ $i_2 \not< i_3$ $a \not < b$

ds.data-structures functional-programming sorting Abdallah
fuente

Creo que necesitamos saber más para responder inteligentemente su pregunta. ¿Está almacenando los elementos y el orden parcial se calcula fácilmente? ¿O también está almacenando el orden parcial en algún tipo de tabla de búsqueda? ¿Cómo piensa utilizar el orden parcial? ¿Espera usarlo de la misma manera que se usa el orden lineal para almacenar conjuntos (por ejemplo, en árboles de búsqueda)?

Andrej Bauer, el

Ahora que me di cuenta de que solo tendré antichains, no estoy seguro de que haya algo mejor que la solución ingenua de almacenar los resultados en una lista. Si es así, ¡disculpen las molestias!

Abdallah

Si cree que su pregunta ahora es discutible, ¿tal vez debería marcarla para su eliminación / cierre?

Suresh Venkat

Cualquiera de los dos elementos en el conjunto será incomparable, pero esto no significa que la representación ingenua es lo mejor que puede hacer. Por ejemplo, considere múltiples conjuntos finitos ordenados por inclusión (= enteros ordenados con divisibilidad): hay mucho potencial para la optimización, dependiendo de su representación de datos (usando cardinalidad, usando el conjunto de soporte, ...). Estas optimizaciones dependerán en gran medida de la naturaleza de la relación de orden. Luego está la cuestión separada de decidir si vale la pena mantener información sobre los elementos ahora eliminados: ¿los comparará a menudo con las nuevas incorporaciones?

Gilles 'SO- deja de ser malvado'

Ok, gracias. Así que agregué información (la posibilidad de límite de enteros) que podría conducir a optimizaciones.

Abdallah

Respuestas:

El documento "Clasificación y selección en PoSets" de Daskalakis, Karp, Mossel, Risensefield, Verbin, 2008, que describe una representación dinámica de PoSets basada en antichains.

También puede estar interesado en el artículo "Posets sucintos" de Munro, Nicholson, 2012 publicado recientemente en Arxiv y en la bibliografía que contiene. Su estructura de datos es estática, pero supongo que el siguiente paso es tener una estructura de datos dinámica.

Jeremy
fuente

La clasificación y selección en Posets es genial para tener una idea de lo que se necesita para una estructura de datos, pero los algoritmos suponen el etiquetado de elementos en el poset (por ejemplo, exactamente el problema que queremos resolver en el primer lugar!) para calcular la relación entre dos elementos en después de construir la estructura de datos en consultas . Por lo tanto, el documento supone que las consultas sobre la relación entre dos elementos son costosas y que los elementos de mapeo de los posets son triviales, mientras que las estructuras de datos de mapas generalmente suponen lo contrario de lo primero para resolver lo último.

O (1)

$\mathcal{O}(1)$

O (1)

$\mathcal{O}(1)$

O (q n)

$\mathcal{O}(qn)$

Sebastian Graf

Tener mapas representados como una descomposición (mínima) de cadenas es una buena idea. Sin embargo, preservar esa invariante mediante eliminaciones es lo complicado.

Sebastian Graf

¿Has visto "Buscar en órdenes parciales dinámicas de árbol dinámico" de Heeringa et al . Proporcionan una estructura de datos dinámica para el problema anterior en los posets. Está diseñado para una RAM, pero puede representar matrices como árboles binarios balanceados e incurrir solo en una sobrecarga multiplicativa mientras hace que la estructura sea puramente funcional. $O(\lg n)$

jbapple
fuente

Tenga en cuenta que esto solo cubre órdenes parciales 'en forma de árbol', por ejemplo, cumplir con semilattices, donde todos los elementos menores o iguales a algún elemento eforman una cadena.

Sebastian Graf