Implementação de lista que mantém a ordem

https://stackoverflow.com//questions/10675446

12-12-2019
|

Pergunta

Existe um existente List implementação em Java que mantém a ordem com base no fornecido Comparator?

Algo que pode ser usado da seguinte maneira:

Comparator<T> cmp = new MyComparator<T>();
List<T> l = new OrderedList<T>(cmp);
l.add(someT);

para que someT é inserido de forma que a ordem na lista seja mantida de acordo com cmp

(Por sugestão do @andersoj estou completando minha pergunta com mais uma solicitação)

Também quero poder percorrer a lista em ordem de classificação sem remover os elementos, ou seja:

T min = Const.SMALLEST_T;
for (T e: l) {
  assertTrue(cmp.compare(min, e) >= 0);
  min = e;
}

deveria passar.

Todas as sugestões são bem-vindas (exceto dizer-me para usar Collections.sort na lista completa não ordenada), porém, eu preferiria algo em java.* ou eventualmente org.apache.* já que seria difícil introduzir novas bibliotecas neste momento.

Observação:(ATUALIZAÇÃO4) Percebi que implementações desse tipo de lista teriam desempenho inadequado.Existem duas abordagens gerais:

Use estrutura vinculada (uma espécie de) árvore B ou similar
Use array e inserção (com pesquisa binária)

Não 1.Tem problemas com o cache da CPU erra o nº 2.tem problema com a mudança de elementos na matriz.

ATUALIZAÇÃO2: TreeSet não funciona porque usa o comparador fornecido (MyComparator) para verificar a igualdade e com base nisso assume que os elementos são iguais e os exclui.Eu preciso desse comparador apenas para ordenação, não para filtragem de "singularidade" (já que os elementos por sua ordem natural não são iguais)

ATUALIZAÇÃO3: PriorityQueue não funciona como List (conforme preciso) pois não há como percorrê-lo na ordem em que está "classificado", para obter os elementos na ordem de classificação é necessário removê-los da coleção.

ATUALIZAR:

Pergunta semelhante:
Uma boa lista ordenada para Java
Lista de array classificada em Java

Solução

Resposta ao novo requisito.Vejo dois potenciais:

Faça o que o JavaDoc faz PriorityQueue diz:

Esta classe e seu iterador implementam todos os métodos opcionais das interfaces Collection e Iterator.O Iterador fornecido no método iterator() não é garantido que atravesse os elementos da fila de prioridade em qualquer ordem específica.Se você precisar de passagem ordenada, considere usar Arrays.sort(pq.toArray()).

Suspeito que isso produzirá o melhor desempenho de acordo com seus requisitos.Se isso não for aceitável, você precisará explicar melhor o que está tentando realizar.
Construir um Lista que simplesmente se classifica mediante a adição de novos elementos.Isso é uma verdadeira dor...se você usou uma estrutura vinculada, poderá fazer uma classificação de inserção eficiente, mas a localidade é ruim.Se você usou uma estrutura baseada em array, a classificação por inserção é um problema, mas a travessia é melhor.Se a iteração/travessia não for frequente, você poderá manter o conteúdo da lista sem classificação e classificá-lo somente sob demanda.

Considere usar um Fila de prioridade como sugeri, e caso você precise iterar em ordem, escreva um iterador wrapper:

class PqIter implements Iterator<T>
{
   final PriorityQueue<T> pq;
   public PqIter(PriorityQueue <T> source)
   {
     pq = new PriorityQueue(source); 
   }

   @Override
   public boolean hasNext()
   {
     return pq.peek() != null
   }

   @Override
   public T next()
   { return pq.poll(); }

   @Override
   public void remove()
   { throw new UnsupportedOperationException(""); }
}

Use goiaba TreeMultiSet.Eu testei o seguinte código com Integer e parece fazer a coisa certa.

import com.google.common.collect.TreeMultiset;

public class TreeMultiSetTest { 
  public static void main(String[] args) {
    TreeMultiset<Integer> ts = TreeMultiset.create();
    ts.add(1);  ts.add(0); ts.add(2);
    ts.add(-1); ts.add(5); ts.add(2);

    for (Integer i : ts) {
      System.out.println(i);
    } 
  } 
}

O texto abaixo aborda o problema de exclusividade/filtragem que você estava enfrentando ao usar um SortedSet.Vejo que você também quer um iterador, então isso não funcionará.

Se o que você realmente quer é um pedido semelhante a uma lista coisa, você pode fazer uso de um PriorityQueue.

Comparator<T> cmp = new MyComparator<T>();
PriorityQueue<T> pq = new PriorityQueue<T>(cmp);
pq.add(someT);

Observe o que a documentação da API diz sobre as propriedades de tempo de várias operações:

Nota de implementação:esta implementação fornece O(log(n)) tempo para os métodos de enfileiramento e dequeing (offer, poll, remove() e add); linear hora para o remove(Object) e contains(Object) métodos;e constante tempo para os métodos de recuperação (peek, element, e size).

Você também deve estar ciente de que os iteradores produzidos por PriorityQueue não se comporte como seria de esperar:

O Iterator fornecido no método iterator() não é garantido que atravesse os elementos da fila de prioridade em qualquer ordem específica.Se você precisar de passagem ordenada, considere usar Arrays.sort(pq.toArray()).

Acabei de notar que o Guava fornece um MinMaxPriorityQueue.Esta implementação é baseada em array, em vez do formulário vinculado fornecido no JDK PriorityQueue, e, portanto, provavelmente tem um comportamento de temporização diferente.Se você estiver fazendo algo sensível ao desempenho, talvez queira dar uma olhada.Embora as notas forneçam tempos O grandes ligeiramente diferentes (lineares e logarítmicos), todos esses tempos também devem ser limitados, o que pode ser útil.

Não há um List implementação em si que mantém a ordem, mas o que você provavelmente está procurando são implementações de SortedSet.A TreeSet é o mais comum.A outra implementação, uma ConcurrentSkipListSet é para usos mais específicos.Observe que um SortedSet fornece ordenação, mas não permite entradas duplicadas, assim como um List.

Referências:

Postagem no blog PriorityQueue iterador não está ordenado
Então pergunta sobre Iterador ordenado PQ

Outras dicas

Você provavelmente deveria estar usando um Conjunto de árvores:

Os elementos são ordenados usando sua ordenação natural ou por um Comparador fornecido no momento da criação do conjunto, dependendo de qual construtor é utilizado.

Exemplo:

Comparator<T> cmp = new MyComparator<T>();
TreeSet<T> t = new TreeSet<T>(cmp);
l.add(someT);

Observe que este é um definir, portanto, nenhuma entrada duplicada será permitida.Isso pode ou não funcionar para seu caso de uso específico.

Estou com um problema semelhante e estou pensando em usar um TreeSet.Para evitar a exclusão de elementos "iguais", modificarei o comparador para que, em vez de retornar 0, ele retorne um número aleatório entre (-1,1) ou retorne sempre 1.

Se você não tem controle sobre o Comparador ou se o estiver usando para algo diferente de inserir esta solução não funcionará para você.

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow