Estou perplexo por não conseguir encontrar uma resposta rápida para isso. Estou procurando essencialmente uma estrutura de dados em Java que implemente a java.util.List
interface, mas que armazene seus membros em uma ordem classificada. Eu sei que você pode usar um normal ArrayList
e usar Collections.sort()
nele, mas tenho um cenário em que ocasionalmente estou adicionando e frequentemente recuperando membros da minha lista e não quero ter que classificá-lo toda vez que recuperar um membro no caso de um um novo foi adicionado. Alguém pode me indicar algo que existe no JDK ou mesmo em bibliotecas de terceiros?
EDIT : A estrutura de dados precisará preservar duplicatas.
RESUMO DA RESPOSTA : Achei tudo isso muito interessante e aprendi muito. Aioobe, em particular, merece menção por sua perseverança em tentar cumprir meus requisitos acima (principalmente uma implementação java.util.List classificada que oferece suporte a duplicatas). Aceitei sua resposta como a mais precisa pelo que perguntei e mais instigante sobre as implicações do que estava procurando, mesmo que o que perguntei não fosse exatamente o que eu precisava.
O problema com o que eu pedi está na própria interface List e no conceito de métodos opcionais em uma interface. Para citar o javadoc:
O usuário desta interface tem controle preciso sobre onde na lista cada elemento é inserido.
Inserir em uma lista classificada não tem controle preciso sobre o ponto de inserção. Então, você tem que pensar como irá lidar com alguns dos métodos. Tomemos add
por exemplo:
public boolean add (Object o)
Appends the specified element to the end of this list (optional operation).
Você agora fica na situação desconfortável de 1) Romper o contrato e implementar uma versão classificada de adicionar 2) Permitir add
adicionar um elemento ao final da lista, quebrando sua ordem classificada 3) Deixar de add
fora (como opcional) jogando um UnsupportedOperationException
e implementando outro método que adiciona itens em uma ordem de classificação.
A opção 3 é provavelmente a melhor, mas acho desagradável ter um método add que você não pode usar e outro método SortAdd que não está na interface.
Outras soluções relacionadas (sem ordem específica):
- java.util.PriorityQueue que é provavelmente o mais próximo do que eu precisava do que pedi. Uma fila não é a definição mais precisa de uma coleção de objetos no meu caso, mas funcionalmente ela faz tudo o que preciso.
- net.sourceforge.nite.util.SortedList . No entanto, essa implementação quebra o contrato da interface List ao implementar a classificação no
add(Object obj)
método e, estranhamente, tem um método sem efeito paraadd(int index, Object obj)
. O consenso geral sugere quethrow new UnsupportedOperationException()
pode ser uma escolha melhor neste cenário. - TreeMultiSet do Guava Um conjunto de implementação que suporta duplicatas
- ca.odell.glazedlists.SortedList Essa classe vem com a advertência em seu javadoc:
Warning: This class breaks the contract required by List
fonte
Respostas:
Solução Minimalista
Aqui está uma solução "mínima".
class SortedArrayList<T> extends ArrayList<T> { @SuppressWarnings("unchecked") public void insertSorted(T value) { add(value); Comparable<T> cmp = (Comparable<T>) value; for (int i = size()-1; i > 0 && cmp.compareTo(get(i-1)) < 0; i--) Collections.swap(this, i, i-1); } }
A inserção é executada em tempo linear, mas seria o que você obteria usando um ArrayList de qualquer maneira (todos os elementos à direita do elemento inserido teriam que ser deslocados de uma forma ou de outra).
A inserção de algo não comparável resulta em uma ClassCastException. (Esta é a abordagem adotada por
PriorityQueue
também: Uma fila de prioridade baseada na ordenação natural também não permite a inserção de objetos não comparáveis (fazer isso pode resultar em ClassCastException). )Substituindo
List.add
Observe que substituir
List.add
(ouList.addAll
nesse caso) para inserir elementos de uma forma ordenada seria uma violação direta da especificação da interface . O que você pode fazer é substituir esse método para lançar umUnsupportedOperationException
.Dos documentos de
List.add
:O mesmo raciocínio se aplica a ambas as versões de
add
, ambas as versões deaddAll
eset
. (Todas são operações opcionais de acordo com a interface da lista.)Alguns testes
SortedArrayList<String> test = new SortedArrayList<String>(); test.insertSorted("ddd"); System.out.println(test); test.insertSorted("aaa"); System.out.println(test); test.insertSorted("ccc"); System.out.println(test); test.insertSorted("bbb"); System.out.println(test); test.insertSorted("eee"); System.out.println(test);
.... imprime:
fonte
The user of this interface has precise control over where in the list each element is inserted
que não é a melhor descrição para inserir elementos de uma forma ordenada e você ainda tem que lidar com oadd(int index, Object obj)
método de interface. Esses problemas provavelmente explicam porque List não foi implementado de forma ordenada..add
em um SortedArrayList. Sim, o mesmo raciocínio se aplica a ambas as versões de add, ambas as versões de addAll e set. (Todas são operações opcionais de acordo com a interface da lista.)Use
java.util.PriorityQueue
.fonte
Dê uma olhada em SortedList
fonte
addAll()
e pensando que todos os elementos de uma forma ordenada. Concorde com a UnsupportedOperationException também.Você pode tentar TreeMultiSet do Guava .
Multiset<Integer> ms=TreeMultiset.create(Arrays.asList(1,2,3,1,1,-1,2,4,5,100)); System.out.println(ms);
fonte
A collection that supports order-independent equality, like Set, but may have duplicate elements
A abordagem de Aioobe é o caminho a percorrer. Eu gostaria de sugerir a seguinte melhoria em relação à solução dele.
class SortedList<T> extends ArrayList<T> { public void insertSorted(T value) { int insertPoint = insertPoint(value); add(insertPoint, value); } /** * @return The insert point for a new value. If the value is found the insert point can be any * of the possible positions that keeps the collection sorted (.33 or 3.3 or 33.). */ private int insertPoint(T key) { int low = 0; int high = size() - 1; while (low <= high) { int mid = (low + high) >>> 1; Comparable<? super T> midVal = (Comparable<T>) get(mid); int cmp = midVal.compareTo(key); if (cmp < 0) low = mid + 1; else if (cmp > 0) high = mid - 1; else { return mid; // key found } } return low; // key not found } }
A solução da aioobe fica muito lenta ao usar listas grandes. Usar o fato de que a lista está classificada nos permite encontrar o ponto de inserção para novos valores usando a pesquisa binária.
Eu também usaria composição em vez de herança, algo na linha de
fonte
As listas geralmente preservam a ordem em que os itens são adicionados. Você definitivamente precisa de uma lista , ou um conjunto classificado (por exemplo
TreeSet<E>
) seria adequado para você? Basicamente, você precisa preservar as duplicatas?fonte
Pode ser um pouco pesado para você, mas GlazedLists tem uma SortedList que é perfeita para usar como modelo de uma mesa ou JList
fonte
Você poderia criar uma subclasse de ArrayList e chamar Collections.sort (this) depois que qualquer elemento for adicionado - você precisaria substituir duas versões de add e duas de addAll para fazer isso.
O desempenho não seria tão bom quanto uma implementação mais inteligente que inserisse elementos no lugar certo, mas daria certo. Se o acréscimo à lista for raro, o custo amortizado em todas as operações da lista deve ser baixo.
fonte
Basta fazer uma nova classe como esta:
public class SortedList<T> extends ArrayList<T> { private final Comparator<? super T> comparator; public SortedList() { super(); this.comparator = null; } public SortedList(Comparator<T> comparator) { super(); this.comparator = comparator; } @Override public boolean add(T item) { int index = comparator == null ? Collections.binarySearch((List<? extends Comparable<? super T>>)this, item) : Collections.binarySearch(this, item, comparator); if (index < 0) { index = index * -1 - 2; } super.add(index+1, item); return true; } @Override public void add(int index, T item) { throw new UnsupportedOperationException("'add' with an index is not supported in SortedArrayList"); } @Override public boolean addAll(Collection<? extends T> items) { boolean allAdded = true; for (T item : items) { allAdded = allAdded && add(item); } return allAdded; } @Override public boolean addAll(int index, Collection<? extends T> items) { throw new UnsupportedOperationException("'addAll' with an index is not supported in SortedArrayList"); } }
Você pode testá-lo assim:
List<Integer> list = new SortedArrayList<>((Integer i1, Integer i2) -> i1.compareTo(i2)); for (Integer i : Arrays.asList(4, 7, 3, 8, 9, 25, 20, 23, 52, 3)) { list.add(i); } System.out.println(list);
fonte
Acho que a escolha entre SortedSets / Lists e coleções classificáveis 'normais' depende se você precisa classificar apenas para fins de apresentação ou em quase todos os pontos durante o tempo de execução. Usar uma coleção classificada pode ser muito mais caro porque a classificação é feita toda vez que você insere um elemento.
Se você não pode optar por uma coleção no JDK, você pode dar uma olhada nas Coleções do Apache Commons
fonte
Uma vez que as implementações propostas atualmente que implementam uma lista classificada quebrando a API Collection, têm uma implementação própria de uma árvore ou algo semelhante, fiquei curioso em saber como seria o desempenho de uma implementação baseada no TreeMap. (Principalmente porque o TreeSet também se baseia no TreeMap)
Se alguém também estiver interessado nisso, ele ou ela pode se sentir à vontade para investigar:
TreeList
É parte da biblioteca central , você pode adicioná-lo por meio da dependência do Maven, é claro. (Licença Apache)
Atualmente a implementação parece se comparar muito bem no mesmo nível que a Goiaba SortedMultiSet e a TreeList da biblioteca Apache Commons.
Mas eu ficaria feliz se mais do que apenas eu testasse a implementação para ter certeza de que não perdi algo importante.
Cumprimentos!
fonte
Eu tive o mesmo problema. Então, peguei o código-fonte de java.util.TreeMap e escrevi IndexedTreeMap . Ele implementa meu próprio IndexedNavigableMap :
public interface IndexedNavigableMap<K, V> extends NavigableMap<K, V> { K exactKey(int index); Entry<K, V> exactEntry(int index); int keyIndex(K k); }
A implementação é baseada na atualização dos pesos dos nós na árvore vermelha e preta quando ela é alterada. Peso é o número de nós filhos abaixo de um determinado nó, mais um próprio. Por exemplo, quando uma árvore é girada para a esquerda:
private void rotateLeft(Entry<K, V> p) { if (p != null) { Entry<K, V> r = p.right; int delta = getWeight(r.left) - getWeight(p.right); p.right = r.left; p.updateWeight(delta); if (r.left != null) { r.left.parent = p; } r.parent = p.parent; if (p.parent == null) { root = r; } else if (p.parent.left == p) { delta = getWeight(r) - getWeight(p.parent.left); p.parent.left = r; p.parent.updateWeight(delta); } else { delta = getWeight(r) - getWeight(p.parent.right); p.parent.right = r; p.parent.updateWeight(delta); } delta = getWeight(p) - getWeight(r.left); r.left = p; r.updateWeight(delta); p.parent = r; } }
updateWeight simplesmente atualiza os pesos até a raiz:
void updateWeight(int delta) { weight += delta; Entry<K, V> p = parent; while (p != null) { p.weight += delta; p = p.parent; } }
E quando precisamos encontrar o elemento por índice aqui está a implementação que usa pesos:
public K exactKey(int index) { if (index < 0 || index > size() - 1) { throw new ArrayIndexOutOfBoundsException(); } return getExactKey(root, index); } private K getExactKey(Entry<K, V> e, int index) { if (e.left == null && index == 0) { return e.key; } if (e.left == null && e.right == null) { return e.key; } if (e.left != null && e.left.weight > index) { return getExactKey(e.left, index); } if (e.left != null && e.left.weight == index) { return e.key; } return getExactKey(e.right, index - (e.left == null ? 0 : e.left.weight) - 1); }
Também é muito útil encontrar o índice de uma chave:
public int keyIndex(K key) { if (key == null) { throw new NullPointerException(); } Entry<K, V> e = getEntry(key); if (e == null) { throw new NullPointerException(); } if (e == root) { return getWeight(e) - getWeight(e.right) - 1;//index to return } int index = 0; int cmp; index += getWeight(e.left); Entry<K, V> p = e.parent; // split comparator and comparable paths Comparator<? super K> cpr = comparator; if (cpr != null) { while (p != null) { cmp = cpr.compare(key, p.key); if (cmp > 0) { index += getWeight(p.left) + 1; } p = p.parent; } } else { Comparable<? super K> k = (Comparable<? super K>) key; while (p != null) { if (k.compareTo(p.key) > 0) { index += getWeight(p.left) + 1; } p = p.parent; } } return index; }
Você pode encontrar o resultado deste trabalho em http://code.google.com/p/indexed-tree-map/
TreeSet / TreeMap (bem como suas contrapartes indexadas do projeto de mapa de árvore indexado) não permitem chaves duplicadas, você pode usar 1 chave para uma matriz de valores. Se você precisar de um SortedSet com duplicatas, use TreeMap com valores como matrizes. Eu faria isso.
fonte