* Por tudo, quero dizer a execução relativamente rápida de operações em um único elemento de uma matriz.As estruturas de dados que implementam a lista estão completas. Todo mundo tem suas próprias vantagens e desvantagens. Por exemplo, no mundo Java - dependendo das operações necessárias - você pode usar:- add (obj), get (obj), set (index, obj): um conjunto básico de quase todas as listas, por exemplo, ArrayList.
- add (index, obj): estruturas semelhantes a árvores, por exemplo, TreeList de apache common-collections.
- remove (index): o mesmo que acima.
- contém (obj), indexOf (obj): você pode usar vários ArrayList e HashMap.
- remove (obj): ... Acho difícil responder. Em alguns casos, você pode conviver com um LinkedHashSet. É resolvido trivialmente na presença dos dois pontos anteriores, mas que estruturas podem ambas rapidamente?
Quando eu precisava de uma estrutura com adição rápida (obj), get (index), remove (index) e indexOf (obj), o google não dava uma resposta. Não encontrei nenhum exemplo de código ou descrição de tais estruturas. Talvez eu não estivesse olhando para lá, tive que inventar eu mesma. Mas se alguém soltar o link nos comentários, eu aprecio muito.Talvez alguém tenha percebido que você pode usar um TreeList, que pode inserir / remover itens rapidamente no meio da lista e adicionar um HashMap do objeto ao índice no TreeList para execução rápida de indexOf (obj). E será uma decisão simples, elegante, mas incorreta. Afinal, ao adicionar ao meio ou remover do meio, será necessário recalcular os índices, em média, para metade dos elementos. Isso degradará o desempenho para O (n).A seguir, falarei sobre uma estrutura de dados que pode fazer todas as opções acima. Que executa qualquer operação em um elemento no tempo O (log (n)). Bem, quase - pois o logaritmo é realizado no caso em que todos os objetos da lista são diferentes. Se a lista contiver os mesmos objetos, é possível reduzir o desempenho até O (log (n) ^ 2).Avisarei imediatamente que não pintarei o código aqui. Pode ser bastante complicado para o artigo. Mas é, escrito em Java. Baseado na classe TreeList do apache common-collections. A solicitação pull já existe, mas no momento da redação, o artigo ainda não foi lançado.Além disso, não descreverei algoritmos conhecidos. Por exemplo, algoritmos de balanceamento de árvore. Para a maioria, pode ser suficiente tomar como certo o fato de que a árvore pode ser mantida equilibrada. Isso não afeta o entendimento da idéia geral. Quem quer saber mais pode encontrar facilmente informações. Mas vou falar brevemente sobre algumas coisas básicas, porque sem o conhecimento do básico, muitos elementos-chave não podem ser entendidos.Os links estarão no final.Por que isso é necessário?
Na verdade, não é tão fácil criar situações em que tudo é necessário diretamente da lista. É improvável que isso seja algum tipo de estrutura super necessária, caso contrário todos saberiam sobre isso. No entanto, alguns exemplos em que essa lista pode ser útil podem ser dados.Reconheço que muitos dos exemplos são absurdos. Tudo ou quase tudo pode ser resolvido de outra maneira.Armazenamento em cache e compactação
Minha tarefa inicial, por causa da qual comecei a pesquisar o assunto. Jogou com compactação de dados específicos e precisava de uma lista para o cache do objeto.A idéia é a seguinte: ao processar outro objeto, procuramos na lista. Se não encontrado, salve o objeto e adicione-o ao topo da lista. Se encontrado, pegamos seu índice na lista e, em vez do objeto, salvamos apenas seu índice, após o qual movemos o objeto para o topo da lista. Assim, os objetos que ocorrem geralmente recebem índices pequenos e os objetos que ocorrem apenas uma vez acabam sendo movidos para o final da lista e excluídos.Virar
Se, em vez da fila FIFO usual, para algumas tarefas, uma estrutura semelhante for usada, as seguintes operações poderão ser realizadas:- Responda à pergunta: quantas tarefas estão na fila antes desta tarefa.
- Remova as tarefas da fila.
É como em um supermercado. Se você veio para uma barra de chocolate, mas vê que a linha está se movendo lentamente, talvez a barra de chocolate não seja tão necessária? :)Tabela de pontuação
Suponha que queremos armazenar o tempo durante o qual os jogadores completam um nível em um jogo. Existem muitos jogadores e todos eles competem, tentando mostrar o tempo mínimo. Os dados do jogador podem ser colocados em uma matriz e classificados por tempo. Usando essa estrutura, você pode:- Mova os jogadores para o topo da lista se eles apresentarem melhores resultados do que antes.
- Remova os jogadores da lista, por exemplo, no caso de uma proibição de trapaça.
- Mostre a cada jogador onde ele está.
- Mostrar a tabela de registros página por página.
- Mostre uma tabela esparsa em locais, por exemplo, horário 1, 2, 3, 5, 10, 20, 50, 100, 1000, 10000 locais.
Estrutura de dados
A estrutura é baseada em uma árvore com uma chave implícita. É nessa abordagem, por exemplo, que TreeList nas coleções comuns do apache se baseia. Para seguir em frente, você precisa entender como essa estrutura funciona.Árvore de chaves implícita
Uma árvore consiste em nós (nós). Cada nó contém um link para um objeto que é armazenado no nó e 2 links para outros nós: esquerdo e direito. O nó superior é chamado nó raiz. No caso mais simples, o nó se parece com isso:class Node<T> {
obj: T
left: Node<T>
right: Node<T>
}
Na árvore binária clássica de cada nó na subárvore esquerda, todos os objetos são menores que no nó atual e no direito - grande. Por exemplo: [ element: 25 ]
/ \
/ \
[ element: 14 ] [ element: 45 ]
/ \ / \
/ \ / \
[ element: 10 ] [ element: 22 ] [ element: 27 ] [ element: 90 ]
/ \ /
/ \ /
[ element: 17 ] [ element: 23 ] [ element: 80 ]
Mas, para nosso propósito, essa árvore não é adequada. Não precisamos armazenar objetos classificados, mas precisamos ter acesso a eles por índice, como em uma matriz.Como posso colocar uma matriz em uma árvore? Vamos selecionar um elemento com o índice i no meio da matriz. Coloque o i-ésimo elemento da matriz no nó raiz. 2 subárvores saem do nó raiz. Na subárvore esquerda, colocamos metade da matriz com índice <i, e na direita, com índice> i. Como fazer isso? Da mesma forma: selecionamos um elemento do meio em um sub-arranjo, colocamos esse elemento em um nó, obtemos mais 2 sub-arranjos menores. E assim, até colocarmos todos os elementos da matriz nos nós da árvore.Por exemplo, uma matriz com os elementos ["q", "w", "e", "r", "t", "y", "u"] pode ter a seguinte aparência: [el: r, size: 7]
/ : \
/ : \
[el: w, size: 3] : [el: y, size: 3]
/ : \ : / : \
/ : \ : / : \
[el: q, size: 1] : [el: e, size: 1] : [el: t, size: 1] : [el: u, size: 1]
: : : : : : :
: : : : : : :
[q] [w] [e] [r] [t] [y] [u]
Index: 0 1 2 3 4 5 6
O elemento do meio na matriz "r", nós o colocamos no nó raiz. Duas sub-matrizes ["q", "w", "e"] e ["t", "y", "u"] são colocadas nas subárvores esquerda e direita. Para isso, os elementos centrais são selecionados a partir das sub-matrizes, no nosso caso, são "w" e "y" e se enquadram nos nós do próximo nível. E assim por dianteNo nosso caso, a árvore é equilibrada, a profundidade de todas as subárvores é a mesma. Mas isso não precisa ser assim.Na figura acima, cada nó, além do elemento e links para os nós esquerdo e direito, contém o número de elementos de toda a subárvore. Esta informação deve ser atualizada corretamente quando a árvore for alterada.Vamos ver como encontrar, por exemplo, um elemento com índice = 4 nessa árvore.Iniciamos o rastreamento a partir do nó raiz (raiz, no nosso caso, com o elemento "r"). Temos três opções: já estamos no nó direito, o nó direito à esquerda, o nó direito à direita. Para entender onde procurar o elemento desejado, você precisa comparar o tamanho da subárvore esquerda (no nosso caso left.size = 3) e o índice atual (no nosso caso 4). Se esses 2 números forem iguais, encontramos o nó necessário e o elemento desejado. Se o tamanho da subárvore esquerda for maior, o nó necessário na subárvore esquerda. Se for menor, será necessário procurar na subárvore direita, mas reduzir o índice desejado: index = index - left.size - 1.Como no nosso caso left.size <index, estamos procurando na subárvore direita o elemento com o novo índice 4 - 3 - 1 = 0. Mova para o nó com o elemento "y".Em seguida, fazemos a mesma coisa que fizemos no nó raiz. Compare left.size e index. Desde 1> 0, olhamos na subárvore esquerda, movemos para o nó com o elemento "t".Não há subárvore esquerda neste nó e seu tamanho é 0. index = left.size, o que significa que encontramos um nó com o índice 4 e podemos obter o elemento necessário "t" a partir dele.No pseudo-código, é algo parecido com isto:function get(node: Node<T>, index: int): T {
val leftSize: int = (node.left == null) ? 0 : node.left.size;
if (leftSize == index) {
return node.obj;
} else if (leftSize > index) {
return get(node.left, index);
} else {
return get(node.right, index — leftSize — 1);
}
}
Tentei descrever o princípio principal de como colocar uma matriz em uma árvore. Essa estrutura funciona, é claro, mais lentamente que a matriz clássica, para O (log (n)) versus O (1). Mas tem uma vantagem importante: adicionar um elemento ao meio ou remover do meio também funciona para O (log (n)) versus O (n) para a matriz. Obviamente, desde que a árvore esteja mais ou menos equilibrada. Existem muitos algoritmos para manter uma árvore de maneira quase equilibrada. Por exemplo, árvore vermelho-preta, árvore AVL, árvore cartesiana. Não anotarei os detalhes do balanceamento da árvore, qualquer algoritmo é adequado para nós. Vamos apenas assumir que a árvore é equilibrada em média e sua profundidade máxima não é muito diferente da mínima.Otimização leve
A abordagem descrita acima, com a verificação do tamanho da árvore à esquerda, é conveniente para a percepção, mas pode ser feita com um pouco mais de eficiência. Para não olhar para a subárvore esquerda a cada vez, em vez do tamanho da árvore, é possível armazenar no nó sua posição em relação à posição do nó pai. O nó raiz armazena uma posição absoluta que corresponde ao tamanho da subárvore esquerda. [el: r, pos: 3]
/ : \
/ : \
[el: w, pos: -2] : [el: y, pos: +2]
/ : \ : / : \
/ : \ : / : \
[el: q, pos: -1] : [el: e, pos: +1] : [el: t, pos: -1] : [el: u, pos: +1]
: : : : : : :
: : : : : : :
[q] [w] [e] [r] [t] [y] [u]
Index: 0 1 2 3 4 5 6
Por exemplo, o nó raiz "r" tem a posição 3. O nó "w" tem a posição -2 em relação ao nó pai ou a posição absoluta 3 + (-2) = 1. Da mesma forma, você pode descer mais um nível, por exemplo, o nó "e" tem a posição 3 + (-2) + (+1) = 2. Ou seja, O índice do nó é a soma das posições da raiz da árvore até esse nó.Essa otimização, além de uma pesquisa mais rápida por um item da lista, fornecerá uma pesquisa mais rápida e fácil para o índice no nó. Mas, é claro, atualizar corretamente a posição ao mudar a árvore se tornou um pouco mais difícil.Adicionar indexação
Assim, na árvore, podemos pegar um elemento por índice, alterar seu valor, adicionar elementos ao meio e excluir. Basicamente, precisamos apenas adicionar uma pesquisa rápida de índice por valor, indexOf (obj). Em seguida, contém (obj) e remove (obj) serão resolvidos trivialmente.Mas primeiro, vamos simplificar um pouco a tarefa. Vamos criar uma estrutura que armazene apenas elementos únicos.Para procurar algo rapidamente, eles geralmente usam uma tabela. No mundo Java, as tabelas são chamadas de Mapa, com duas implementações principais: HashMap e TreeMap. A chave da tabela será um link para o objeto e o valor será um link para seu nó:class IndexedTreeListSet<T> {
root: Node<T>
indexMap: Map<T, Node<T>>
}
Essa. a estrutura consiste em duas partes: a própria árvore de lista e a tabela com links para objetos e nós desta árvore. Ao atualizar a árvore, a tabela também deve ser atualizada. Não vou descrever o processo em detalhes. Intuitivamente, deve ser compreensível: adicione um nó - coloque-o na tabela, exclua-o - exclua-o da tabela. Na prática, há nuances no balanceamento da árvore: o algoritmo deve alterar os links entre os nós e não mover objetos entre os nós. Caso contrário, você precisará fazer muitas atualizações na tabela e o desempenho diminuirá.Ok, vamos assumir que podemos encontrar rapidamente o nó pelo elemento que ele contém. E daí? Precisamos encontrar seu índice, mas isso ainda não pode ser feito. Mas podemos complicar a classe do nó para que ela contenha não apenas links para os nós esquerdo e direito, mas também para seu pai:class Node<T> {
obj: T
left: Node<T>
right: Node<T>
parent: Node<T>
pos: int
}
Obviamente, atualizar a árvore é um pouco mais complicado, porque agora precisamos atualizar cuidadosamente o link para o pai. Mas agora, conhecendo o nó, podemos subir na árvore e calcular o índice de qualquer nó. Se usamos a otimização do capítulo anterior, precisamos apenas calcular a soma das posições do nó atual até a raiz.Para uma lista que contém elementos exclusivos, o problema pode ser considerado resolvido.É verdade que temos um pequeno problema. Suponha que chamamos set (index, obj). Podemos facilmente substituir um elemento em um nó por outro, mas apenas se ainda não houver um novo elemento na lista. E se sim, o que devo fazer? Retire o excesso de item da posição antiga e coloque um novo? Ou vice-versa, primeiro adicione e exclua? O resultado pode ser diferente. E você não pode fazer nada ou lançar uma exceção. Não há solução perfeita.A classificação por métodos padrão dessa lista, provavelmente, também não funcionará. Afinal, o algoritmo de classificação não saberá sobre a necessidade de exclusividade de objetos e criará duplicatas ao mover itens na lista.Removemos a singularidade
Ok, complicando ainda mais as coisas, vamos manter os mesmos objetos. Obviamente, você precisa fazer algo com a mesa. A primeira idéia para armazenar uma lista de nós nela não parece muito boa: com um aumento no tamanho da lista, o desempenho se deteriorará. Até O (n) se todos os itens da lista forem iguais.Então vamos tentar armazenar uma árvore classificada de nós em uma tabela em vez de em uma lista. Classificado por posição na lista.class IndexedTreeList<T> {
root: Node<T>
indexMap: Map<T, TreeSet<Node<T>>>
}
Em seguida, a inserção / exclusão de / para o TreeSet <Nó> de tamanho m ocorrerá durante as comparações de log (m) das posições dos nós e cada comparação ocorrerá durante o tempo de log (n). A complexidade final da inserção ou exclusão em uma estrutura semelhante ocorrerá em O (log (n) * (1 + log (m))), onde n é o número total de elementos na lista e m é o número de elementos na lista igual ao inserido / excluído. No pior caso, quando todos os elementos são iguais, obtemos a complexidade O (log (n) ^ 2).Um leitor atento provavelmente contestará: mas e a imutabilidade? Afinal, não podemos alterar objetos se forem chaves de tabela? Em geral, é. No entanto, para uma árvore que armazena objetos classificados em chaves, além das regras padrão para comparações, é suficiente preservar o invariante: se a <b, essa propriedade não deve mudar com o tempo. Este é apenas o nosso caso: se a posição de um nó for menor que a posição de outro nó, essa propriedade será preservada, independentemente de quantos nós foram adicionados ou excluídos entre eles.É possível tornar a estrutura persistente?
Resposta curta: não, é impossível. Devido à bioconectividade da árvore, da raiz às folhas e costas, temos todos os nós da árvore conectados a cada um. A persistência não pode ser feita dessa maneira; você precisa recriar toda a estrutura com qualquer alteração.Mas tenho um entendimento de como implementar uma estrutura persistente para casos em que não precisamos inserir elementos no meio da lista. Você pode adicionar elementos ao começo ou ao fim e excluir do meio. As demais propriedades são as mesmas.Se você estiver interessado, tentarei escrever um artigo sobre essa estrutura. Talvez eu até o implemente em Java, Kotlin ou Scala. Mas, muito provavelmente, não será em breve.Alguns recursos de implementação
Aqui, quero descrever alguns recursos que tive que enfrentar.Sobre uma das otimizações sobre o armazenamento da posição do nó na lista, escrevi acima. Aqui se manifesta a força do código-fonte aberto: peguei o código TreeList pronto e não mergulhei nos detalhes da árvore AVL, rotações de nós, atualizações de posição etc.Outro recurso herdado do TreeList são os links para as subárvores nas folhas das árvores. Cada nó armazena leftIsPrevious e rightIsNext. Essas variáveis indicam a presença ou ausência de uma subárvore esquerda / direita. Se não houver subárvore, em esquerda / direita, em vez de um link para a subárvore, será armazenado um link para o nó que corresponde ao elemento anterior ou ao próximo. No nosso exemplo, ["q", "w", "e", "r", "t", "y", "u"] o nó "e" é frondoso, não possui subárvores. Assim, leftIsPrevious e rightIsNext são verdadeiros, e esquerda e direita apontam para os nós "w" e "r", respectivamente. Essa abordagem ajuda a percorrer a lista mais rapidamente. E isso interfere na programação de novos recursos :)Um pouco sobre como trabalhar com o objeto de tabela → nó. Idealmente, você precisa colocar um elemento na tabela uma vez ao adicioná-lo à estrutura e excluí-lo uma vez ao excluir da estrutura. Na prática, não consegui isso. Quando você adiciona um item, ele é adicionado à tabela, tudo está como deveria. No entanto, quando você exclui um item, o algoritmo de balanceamento às vezes move itens entre os nós. O resultado são duas exclusões e um registro na tabela em vez de uma exclusão. Isso pode ser corrigido se você remover a otimização de leftIsPrevious e rightIsNext. E até obtenha um pequeno ganho de desempenho, e não apenas durante a remoção. Em alguns testes, o aumento foi de 10 a 20%. Mas a velocidade da iteração cai significativamente, 1,5-2,5 vezes nos meus testes. Decidi deixar a otimização por enquanto.Em Java, os principais tipos de tabelas são HashMap e TreeMap. Para uma tabela, um objeto → um nó usa o HashMap por padrão. No entanto, você pode usar o TreeMap com um comparador específico de tarefas. Nesse caso, indexOf (obj) e remove (obj) procurarão / excluirão o objeto que é igual ao objeto especificado, de acordo com o código do Comparador. Por exemplo, armazenamos uma lista de usuários e o comparador compara os usuários apenas pelo nome. Em seguida, podemos responder à pergunta “Quais posições da lista são usuários com o nome 'Napoleão?'”. Ou remova todos os Napoleões da lista :).A estrutura não suporta nulo. Você pode consertá-lo, mas não há a sensação de que seja necessário.Quanto ao fato de a estrutura “saber tudo”, eu, é claro, era um pouco enganadora. Obviamente, ao trabalhar com elementos únicos, tudo está bem e sob certas condições, mesmo para o logaritmo. No entanto, ela não sabe algumas coisas que outras estruturas podem. Por exemplo, uma árvore cartesiana com uma chave implícita, havia artigos sobre ela no hub Ele não sabe como fazer indexOf rapidamente, mas sabe como criar uma sublist e concatenar duas listas em uma para o logaritmo (em média, não garantido), além de poder ser persistente.atuação
Em Java, o desempenho é geralmente medido usando a estrutura jmh. Os testes foram conduzidos no MacBook Pro de 2017 sob Java11.Comparei o desempenho do ArrayList padrão, TreeList do apache common-collections e minhas duas classes IndexedTreeList e IndexedTreeListSet em vários cenários. Em cada cenário, foram executadas 1000 operações do mesmo tipo, portanto o resultado deve ser multiplicado por 1000.Código sob o spoiler@Fork(1)
@Warmup(iterations = 3)
@Measurement(iterations = 5)
public class PerformanceCompare {
public static final Map<String, Class> CLASSES = Stream.of(TreeList.class, IndexedTreeListSet.class, IndexedTreeList.class,
ArrayList.class)
.collect(Collectors.toMap(c -> c.getSimpleName(), c -> c));
public static final int ITERATIONS = 1000;
@State(Scope.Benchmark)
public static class Plan {
@Param({"10", "100", "1000", "10000", "100000", "1000000"/*, "10000000"*/})
public int size;
@Param({"ArrayList", "TreeList", "IndexedTreeList", "IndexedTreeListSet"})
public String className;
private Random random;
private List<Integer> list;
@Setup
public void init() throws IllegalAccessException, InstantiationException {
random = new Random();
list = (List<Integer>) CLASSES.get(className).newInstance();
for (int i = 0; i < size; i++) {
list.add(i);
}
}
}
@Benchmark
public void indexOfKnown(Plan plan, Blackhole blackhole) {
List<Integer> list = plan.list;
Random random = plan.random;
int value = 0;
for (int i = 0; i < ITERATIONS; i++) {
value = list.indexOf(random.nextInt(plan.size));
}
blackhole.consume(value);
}
@Benchmark
public void indexOfUnknown(Plan plan, Blackhole blackhole) {
List<Integer> list = plan.list;
Random random = plan.random;
int value = 0;
for (int i = 0; i < ITERATIONS; i++) {
value += list.indexOf(random.nextInt());
}
blackhole.consume(value);
}
@Benchmark
public void addRemoveRandom(Plan plan, Blackhole blackhole) {
List<Integer> list = plan.list;
Random random = plan.random;
int value = 0;
for (int i = 0; i < ITERATIONS; i++) {
list.add(random.nextInt(list.size() + 1), random.nextInt());
value += list.remove(random.nextInt(list.size()));
}
blackhole.consume(value);
}
@Benchmark
public void get(Plan plan, Blackhole blackhole) {
List<Integer> list = plan.list;
Random random = plan.random;
int value = 0;
for (int i = 0; i < ITERATIONS; i++) {
value += list.get(random.nextInt(list.size()));
}
blackhole.consume(value);
}
@Timeout(time = 1, timeUnit = TimeUnit.MILLISECONDS)
public static void main(String[] args) throws RunnerException {
Options opt = new OptionsBuilder()
.include(PerformanceCompare.class.getSimpleName())
.forks(1)
.build();
new Runner(opt).run();
}
}
Para começar, comparei a velocidade de obter um item aleatório de uma lista. Avisarei imediatamente que neste teste a sobrecarga é muito significativa. Os resultados que se aproximam de 100.000 * 1.000 operações por segundo estão gravemente distorcidos.Obter resultado do testePerformanceCompare.get ArrayList 10 thrpt 5 79865.412 ± 10145.202 ops/s
PerformanceCompare.get ArrayList 100 thrpt 5 81862.243 ± 983.727 ops/s
PerformanceCompare.get ArrayList 1000 thrpt 5 81033.507 ± 4540.206 ops/s
PerformanceCompare.get ArrayList 10000 thrpt 5 64096.123 ± 1430.361 ops/s
PerformanceCompare.get ArrayList 100000 thrpt 5 41289.491 ± 11286.114 ops/s
PerformanceCompare.get ArrayList 1000000 thrpt 5 8598.944 ± 2048.461 ops/s
PerformanceCompare.get TreeList 10 thrpt 5 33912.275 ± 3754.284 ops/s
PerformanceCompare.get TreeList 100 thrpt 5 21346.854 ± 863.588 ops/s
PerformanceCompare.get TreeList 1000 thrpt 5 14808.414 ± 508.098 ops/s
PerformanceCompare.get TreeList 10000 thrpt 5 8679.384 ± 109.250 ops/s
PerformanceCompare.get TreeList 100000 thrpt 5 4605.998 ± 1028.945 ops/s
PerformanceCompare.get TreeList 1000000 thrpt 5 2241.381 ± 768.147 ops/s
PerformanceCompare.get IndexedTreeList 10 thrpt 5 34054.357 ± 3682.829 ops/s
PerformanceCompare.get IndexedTreeList 100 thrpt 5 21934.002 ± 2339.947 ops/s
PerformanceCompare.get IndexedTreeList 1000 thrpt 5 14626.691 ± 369.893 ops/s
PerformanceCompare.get IndexedTreeList 10000 thrpt 5 7386.863 ± 342.150 ops/s
PerformanceCompare.get IndexedTreeList 100000 thrpt 5 4562.126 ± 352.772 ops/s
PerformanceCompare.get IndexedTreeList 1000000 thrpt 5 2105.718 ± 702.064 ops/s
PerformanceCompare.get IndexedTreeListSet 10 thrpt 5 33317.503 ± 2307.829 ops/s
PerformanceCompare.get IndexedTreeListSet 100 thrpt 5 21247.440 ± 1253.386 ops/s
PerformanceCompare.get IndexedTreeListSet 1000 thrpt 5 14665.557 ± 487.833 ops/s
PerformanceCompare.get IndexedTreeListSet 10000 thrpt 5 7667.214 ± 80.093 ops/s
PerformanceCompare.get IndexedTreeListSet 100000 thrpt 5 3454.023 ± 82.994 ops/s
PerformanceCompare.get IndexedTreeListSet 1000000 thrpt 5 1768.701 ± 35.878 ops/s
Aqui, curiosamente, o maior interesse é o ArrayList padrão. Teoricamente, a velocidade de sair dela deve ser constante e não depender do número de elementos. Na prática, o desempenho primeiro realiza cerca de 90.000 * 1000 operações por segundo (lembre-se da sobrecarga), mas com um comprimento de lista de vários milhares de itens, ele começa a cair. Isso ocorre devido à falta cada vez mais frequente de cache: o cache do processador não possui os dados necessários e, cada vez mais, você precisa buscar dados na RAM. Com um milhão de elementos, a velocidade do teste é 10 vezes menor, mas, na prática, o rebaixamento do desempenho é ainda maior.TreeList, IndexedTreeList e IndexedTreeListSet esperam resultados semelhantes. Esperado muito mais lento que ArrayList. Mesmo com um pequeno número de elementos, o TreeList é várias vezes mais lento que o ArrayList, embora o teste mostre a diferença apenas 2 vezes.O próximo teste é addRemoveRandom. Aqui, em cada teste, insiro um elemento em uma posição aleatória e removo um elemento de uma posição aleatória.Resultado do teste AddRemoveRandomPerformanceCompare.addRemoveRandom ArrayList 10 thrpt 5 12440.764 ± 485.642 ops/s
PerformanceCompare.addRemoveRandom ArrayList 100 thrpt 5 9880.123 ± 464.014 ops/s
PerformanceCompare.addRemoveRandom ArrayList 1000 thrpt 5 5288.905 ± 1219.055 ops/s
PerformanceCompare.addRemoveRandom ArrayList 10000 thrpt 5 1024.942 ± 179.366 ops/s
PerformanceCompare.addRemoveRandom ArrayList 100000 thrpt 5 91.219 ± 25.380 ops/s
PerformanceCompare.addRemoveRandom ArrayList 1000000 thrpt 5 5.499 ± 0.400 ops/s
PerformanceCompare.addRemoveRandom TreeList 10 thrpt 5 6242.607 ± 350.290 ops/s
PerformanceCompare.addRemoveRandom TreeList 100 thrpt 5 3117.945 ± 116.066 ops/s
PerformanceCompare.addRemoveRandom TreeList 1000 thrpt 5 1829.778 ± 80.516 ops/s
PerformanceCompare.addRemoveRandom TreeList 10000 thrpt 5 1230.077 ± 53.381 ops/s
PerformanceCompare.addRemoveRandom TreeList 100000 thrpt 5 443.571 ± 69.207 ops/s
PerformanceCompare.addRemoveRandom TreeList 1000000 thrpt 5 308.963 ± 84.077 ops/s
PerformanceCompare.addRemoveRandom IndexedTreeList 10 thrpt 5 3556.511 ± 144.596 ops/s
PerformanceCompare.addRemoveRandom IndexedTreeList 100 thrpt 5 2120.777 ± 83.848 ops/s
PerformanceCompare.addRemoveRandom IndexedTreeList 1000 thrpt 5 1211.112 ± 92.288 ops/s
PerformanceCompare.addRemoveRandom IndexedTreeList 10000 thrpt 5 789.458 ± 19.450 ops/s
PerformanceCompare.addRemoveRandom IndexedTreeList 100000 thrpt 5 302.989 ± 40.030 ops/s
PerformanceCompare.addRemoveRandom IndexedTreeList 1000000 thrpt 5 178.822 ± 92.853 ops/s
PerformanceCompare.addRemoveRandom IndexedTreeListSet 10 thrpt 5 4138.007 ± 119.943 ops/s
PerformanceCompare.addRemoveRandom IndexedTreeListSet 100 thrpt 5 2435.803 ± 20.276 ops/s
PerformanceCompare.addRemoveRandom IndexedTreeListSet 1000 thrpt 5 1445.054 ± 276.909 ops/s
PerformanceCompare.addRemoveRandom IndexedTreeListSet 10000 thrpt 5 972.256 ± 19.987 ops/s
PerformanceCompare.addRemoveRandom IndexedTreeListSet 100000 thrpt 5 366.608 ± 94.487 ops/s
PerformanceCompare.addRemoveRandom IndexedTreeListSet 1000000 thrpt 5 227.677 ± 48.276 ops/s
Pode-se supor que ArrayList é mais rápido em pequenas listas. No entanto, o fato de ele vencer neste teste em listas de até 10.000 elementos parece interessante. Aparentemente, o System.arrayCopy está muito bem otimizado e usa todos os recursos dos processadores modernos. A partir de 10.000 itens, estruturas de dados especializadas estão começando a ganhar. Com 1.000.000 de elementos, a diferença de velocidade é de 30 a 50 vezes.Espera-se que IndexedTreeList e IndexedTreeListSet sejam mais lentos que TreeList. Cerca de 1,5 - 2 vezes.Os 2 testes restantes indexOfKnown e indexOfUnknown devem apenas demonstrar o principal recurso dessa estrutura. A diferença entre os testes é que, em um caso, estamos procurando um elemento que está na lista e, no outro, estamos procurando um elemento que não está na lista.Resultado do teste indexOfKnown e indexOfUnknownPerformanceCompare.indexOfKnown ArrayList 10 thrpt 5 41424.356 ± 549.047 ops/s
PerformanceCompare.indexOfKnown ArrayList 100 thrpt 5 17216.477 ± 1444.744 ops/s
PerformanceCompare.indexOfKnown ArrayList 1000 thrpt 5 2296.306 ± 76.372 ops/s
PerformanceCompare.indexOfKnown ArrayList 10000 thrpt 5 233.863 ± 26.926 ops/s
PerformanceCompare.indexOfKnown ArrayList 100000 thrpt 5 23.208 ± 2.776 ops/s
PerformanceCompare.indexOfKnown ArrayList 1000000 thrpt 5 0.919 ± 0.455 ops/s
PerformanceCompare.indexOfKnown TreeList 10 thrpt 5 26740.708 ± 1323.125 ops/s
PerformanceCompare.indexOfKnown TreeList 100 thrpt 5 5670.923 ± 99.638 ops/s
PerformanceCompare.indexOfKnown TreeList 1000 thrpt 5 745.408 ± 26.827 ops/s
PerformanceCompare.indexOfKnown TreeList 10000 thrpt 5 52.288 ± 1.362 ops/s
PerformanceCompare.indexOfKnown TreeList 100000 thrpt 5 4.224 ± 0.855 ops/s
PerformanceCompare.indexOfKnown TreeList 1000000 thrpt 5 0.193 ± 0.052 ops/s
PerformanceCompare.indexOfKnown IndexedTreeList 10 thrpt 5 34485.128 ± 1582.703 ops/s
PerformanceCompare.indexOfKnown IndexedTreeList 100 thrpt 5 29209.412 ± 1544.268 ops/s
PerformanceCompare.indexOfKnown IndexedTreeList 1000 thrpt 5 21139.584 ± 1442.867 ops/s
PerformanceCompare.indexOfKnown IndexedTreeList 10000 thrpt 5 12544.306 ± 312.097 ops/s
PerformanceCompare.indexOfKnown IndexedTreeList 100000 thrpt 5 3538.201 ± 272.537 ops/s
PerformanceCompare.indexOfKnown IndexedTreeList 1000000 thrpt 5 1420.119 ± 538.476 ops/s
PerformanceCompare.indexOfKnown IndexedTreeListSet 10 thrpt 5 39201.995 ± 1887.065 ops/s
PerformanceCompare.indexOfKnown IndexedTreeListSet 100 thrpt 5 34204.112 ± 1122.517 ops/s
PerformanceCompare.indexOfKnown IndexedTreeListSet 1000 thrpt 5 25374.557 ± 1596.746 ops/s
PerformanceCompare.indexOfKnown IndexedTreeListSet 10000 thrpt 5 14291.317 ± 391.180 ops/s
PerformanceCompare.indexOfKnown IndexedTreeListSet 100000 thrpt 5 4215.898 ± 283.680 ops/s
PerformanceCompare.indexOfKnown IndexedTreeListSet 1000000 thrpt 5 1729.100 ± 1260.815 ops/s
PerformanceCompare.indexOfUnknown ArrayList 10 thrpt 5 59053.313 ± 1845.665 ops/s
PerformanceCompare.indexOfUnknown ArrayList 100 thrpt 5 10867.572 ± 142.823 ops/s
PerformanceCompare.indexOfUnknown ArrayList 1000 thrpt 5 1186.583 ± 28.003 ops/s
PerformanceCompare.indexOfUnknown ArrayList 10000 thrpt 5 120.953 ± 4.146 ops/s
PerformanceCompare.indexOfUnknown ArrayList 100000 thrpt 5 11.936 ± 0.320 ops/s
PerformanceCompare.indexOfUnknown ArrayList 1000000 thrpt 5 0.566 ± 0.335 ops/s
PerformanceCompare.indexOfUnknown TreeList 10 thrpt 5 28134.237 ± 2291.670 ops/s
PerformanceCompare.indexOfUnknown TreeList 100 thrpt 5 3153.930 ± 158.734 ops/s
PerformanceCompare.indexOfUnknown TreeList 1000 thrpt 5 322.383 ± 44.245 ops/s
PerformanceCompare.indexOfUnknown TreeList 10000 thrpt 5 25.674 ± 1.787 ops/s
PerformanceCompare.indexOfUnknown TreeList 100000 thrpt 5 1.867 ± 0.291 ops/s
PerformanceCompare.indexOfUnknown TreeList 1000000 thrpt 5 0.093 ± 0.008 ops/s
PerformanceCompare.indexOfUnknown IndexedTreeList 10 thrpt 5 66625.126 ± 5232.668 ops/s
PerformanceCompare.indexOfUnknown IndexedTreeList 100 thrpt 5 70038.055 ± 5803.848 ops/s
PerformanceCompare.indexOfUnknown IndexedTreeList 1000 thrpt 5 63240.467 ± 885.956 ops/s
PerformanceCompare.indexOfUnknown IndexedTreeList 10000 thrpt 5 54731.988 ± 3950.150 ops/s
PerformanceCompare.indexOfUnknown IndexedTreeList 100000 thrpt 5 22049.476 ± 821.924 ops/s
PerformanceCompare.indexOfUnknown IndexedTreeList 1000000 thrpt 5 9459.862 ± 804.738 ops/s
PerformanceCompare.indexOfUnknown IndexedTreeListSet 10 thrpt 5 70274.968 ± 15830.355 ops/s
PerformanceCompare.indexOfUnknown IndexedTreeListSet 100 thrpt 5 71017.685 ± 6920.447 ops/s
PerformanceCompare.indexOfUnknown IndexedTreeListSet 1000 thrpt 5 66405.960 ± 1127.231 ops/s
PerformanceCompare.indexOfUnknown IndexedTreeListSet 10000 thrpt 5 57983.963 ± 3276.142 ops/s
PerformanceCompare.indexOfUnknown IndexedTreeListSet 100000 thrpt 5 41277.110 ± 9919.893 ops/s
PerformanceCompare.indexOfUnknown IndexedTreeListSet 1000000 thrpt 5 9840.185 ± 2159.352 ops/s
Aqui, ArrayList e TreeList quase não têm surpresas. Com o aumento do tamanho, a velocidade diminui quase linearmente. Espera-se que a pesquisa de um item de uma não-lista seja 2 vezes mais lenta que a pesquisa de um item da lista, porque você precisa percorrer toda a matriz em vez da metade, em média.Mas IndexedTreeList e IndexedTreeListSet aqui mostram o bom resultado esperado. Essas estruturas de dados mostram uma velocidade de execução indexOf comparável a ArrayList, mesmo com 10 elementos. Com 1000 elementos, essas estruturas são 10 vezes mais rápidas, com 1.000.000 mais rápidas 1000 vezes. Ao pesquisar por um item que não esteja na lista, espera-se que ele dê uma velocidade melhor do que ao procurar por um item da lista.O que mais é interessante prestar atenção é a subsidência de desempenho de IndexedTreeList e IndexedTreeListSet no teste indexOfUnknown. Aqui a situação é semelhante à do teste com ArrayList.get. Teoricamente, não deveríamos ter conseguido uma queda no desempenho, mas, na prática, devido à falta de cache, conseguimos, além disso, significativamente.Em vez de uma conclusão
Ainda não sei se a estrutura proposta tem uma novidade ou não. Por um lado, a idéia não é complicada se você souber como a árvore funciona por uma chave implícita. Por outro lado, não vi uma descrição de uma estrutura com essas propriedades. E, nesse caso, faz sentido tornar a estrutura mais famosa; pode ser útil para alguém.Mas mesmo que essa seja outra bicicleta, tentei torná-la útil. Uma solicitação de recebimento em coleções comuns foi criada, mas no momento da redação deste artigo ainda não foi lançado. Sabendo o quão lentamente tudo pode acontecer em código aberto, não ficarei surpreso se o processo se arrastar por meses.Um pouco surpreso com o resultado da comparação do desempenho de ArrayList e TreeList. Os testes mostraram que o TreeList não faz sentido usar até 10.000 elementos no tamanho da lista. Seria interessante tentar a árvore b em vez de uma árvore binária. Essa estrutura deve usar a memória com mais cuidado e, provavelmente, trabalhar mais rapidamente. E para isso você pode adaptar a ideia com a indexação.De qualquer forma, é divertido ter um instrumento no arsenal que pode (quase) fazer tudo com complexidade previsível.Referências
Projeto de
solicitação de recebimento original no apache common-collectionsTicket em Jira