Qual estrutura de dados persistente para um conjunto de elementos parcialmente pedidos?

Eu preciso armazenar conjuntos de elementos do tipo a. O tipo a é parcialmente ordenado, portanto, a comparação de e pode retornar menor, maior, igual ou incomparável. $a_1$ $a_2$

Um problema com as hashtables é que dois elementos iguais podem ser representados de maneira diferente, e eu não tenho acesso a uma função de hash consistente com a igualdade.

A comparação de dois elementos pode ser um processo demorado, pelo que seria interessante minimizar as comparações. Se necessário, é possível memorizar as chamadas para o operador de comparação. Agora percebo que só precisarei armazenar antichains (ou vamos supor). Mais precisamente, as operações que precisarei executar são as seguintes:

Remova um elemento do antichain;
Tente adicionar um elemento. Se o elemento for menor que um membro, não o adicione, caso contrário, adicione-o e remova todos os elementos menores que ele.

Também posso vincular cada elemento por dois números inteiros, de modo que, se eu souber que e , conhecer instantaneamente me dará . Obviamente, não significa ... Encontrar limites inteiros é uma operação relativamente barata em comparação com uma comparação 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
fonte

Acho que precisamos saber mais para responder de maneira inteligente à sua pergunta. Você está armazenando os elementos e a ordem parcial é facilmente calculada? Ou você também está armazenando a ordem parcial em algum tipo de tabela de pesquisa? Como você pretende usar a ordem parcial? Você espera usá-lo da mesma maneira que a ordem linear é usada para armazenar conjuntos (por exemplo, em árvores de pesquisa)?

Andrej Bauer

Agora que percebi que só terei antichains, não tenho certeza de que haja algo melhor do que a solução ingênua de armazenar os resultados em uma lista. Se sim, desculpe pelo problema!

Abdallah

Se você acha que sua pergunta agora é discutível, talvez você deva sinalizá-la para exclusão / fechamento?

Suresh Venkat

Quaisquer dois elementos no conjunto serão incomparáveis, mas isso não significa que a representação ingênua é o melhor que você pode fazer. Por exemplo, considere multisets finitos ordenados por inclusão (= números inteiros ordenados com divisibilidade): existe muito potencial para otimização, dependendo da sua representação de dados (usando cardinalidade, usando o conjunto de suporte,…). Essas otimizações dependerão fortemente da natureza da relação de ordem. Depois, há a questão separada de decidir se vale a pena manter as informações sobre os elementos excluídos agora: você os comparará frequentemente com novas adições?

Gilles 'SO- stop be evil'

Ok, obrigada. Então, adicionei algumas informações (a possibilidade de limite inteiro) que poderiam levar a otimizações.

Abdallah

Qual estrutura de dados persistente para um conjunto de elementos parcialmente pedidos?

Respostas: