Utilizo a TreeMap que é uma Red-Black Tree ??? Há outras b-trees mais eficientes para indexação ou estou bem servido com a TreeMap?
Pra que serve a função binarySearch da classe Collections ???
No artigo é comentado que o padrão do Oracle para indexação é B-Tree. Basicamente quero utilizar essa mesma estratégia em Java, mas como estrutura de dados não é o meu forte fiquei com as dúvidas acima.
Você tem duas opções para usar árvores binárias em Java: utilizar um TreeMap ou um TreeSet.
O TreeSet utiliza no seu interior um TreeMap, e um TreeMap é como você perguntou uma Red-Black Tree, seja lá o que for isso… tá na documentação (nem sabia que essas árvores tinham cores :-p).
Outra sigla de árvore que conheço é a BSP tree (Árvore de Particionamento Espacial Binário), muito usada em jogos, mas na verdade não sei se a implementação em si é diferente das outras…
[quote]Pra que serve a função binarySearch da classe Collections ???
[/quote]
Faz uma pesquisa binária num dado array.detalhe:esse array deve estar ordenado,senão dará erro.(não terá um valor de retorno definido).Se o valor não for localizado,retornará um número negativo.Caso o valor passado a binarySearch seja encontrado,será retornado a localização do índice em que o valor passado foi localizado.Ex.:1,2,3,10 se pesquisar por 10,será retornado 3(a posição q 10 está contido no array).
Fiz mais uma pesquisa desesperada na net e dessa vez consegui me situar.
Primeiro: B-Tree não é uma Árvore Binária. Uma B-Tree ao invés de NODES possui PÁGINAS DE NODES. Pra que ??? Pra vc ter que acessar menos o disco !!! Se vc lê uma página com 10 NODES, vc está cortando por dez a sua procura e não por dois como seria o caso de uma árvore binária. Então a regra é: Em memória utilize uma árvore binária. Já em disco utilize um B-Tree!
Segundo: Acredito que Java não tem uma implementação padrão de B-Tree. Então estou fazendo uma na mão. Não é muito simples, mas estou me guiando por um livro de estrutura de dados.
Terceiro: Como eu quero essa B-Tree para fazer indexação de tabelas, como num banco de dados, estou querendo sugar até a última gota de performance. Logo não estou usando collections, o que poderia simplificar bastante o código MAS ME OBRIGARIA A FAZER MILHÕES DE CASTS. Começo a entender e a gostar dos Generics !!!
Quarto: Tb não quero trabalhar com objetos, e me deparei com um problema em Java: Uma função em Java não tem como retornar um int e um Objeto sem me obrigar a colocar o int num Integer e retornar tudo num Object []. Mas isso é custoso pra caramba. Primeiro porque tenho que ficar criando um Integer toda a hora e segundo porque vou ter que fazer dois casts depois, para o meu objeto e para o Integer. Isso ocorre porque nao temos como passar a referencia pra dentro de uma função Java como podemos em C com o operador &. É claro que eu poderia retornar um Object com esses dois atributos, mas aí eu teria que ficar dando new para retornar esses objetos toda a hora. Também se eu não quiser criar nenhum objeto em Java fica difícil. É que como eu falei estou tentando sugar até a última gota de performance e criação de objeto tem overhead como a gente sabe.
Tem certeza que eh “custoso pra caramba”? O que os seus benchmarks mostraram?[/quote]
Como eu falei, estou exagerando na necessidade por performance.
Não é muito custoso, mas tem o seu overhead. E se vc considerar que esse código vai estar sendo executado algumas milhares de vezes por segundo, faz sentigo.
Para confirmar:
De 0 a 10, quanto um Cast é custoso em Java ???
De 0 a 10, quando um new é custoso em Java ???
Se tivesse que chutar, chutaria que um cast é bem mais custoso que um new.
…e, como eu sou um cara bonzinho, aqui vai o código que prova que a sua afirmação (chute, como queira) de que um cast é mais lento que um new, está errada.
Primeiro, vamos definir alguns objetos bobinhos só pra gente ter o que fazer:
[code]interface X { }
interface Y { }
interface Z { }
class A implements X {}
class B extends A implements Y { }
class C extends B implements Z { }[/code]
E, depois, vamos instanciar e fazer casts deles até a VM cansar (note que estou rodando os testes 3 vezes, para dar tempo ao hotspot):
[code]public class CastVersusNew {
public static void main(String[] args) {
for (int i = 1; i <= 3; i++) {
System.out.println("Run " + i);
testNew();
testCast();
}
}
private static void testCast() {
A a = new C();
long start = System.currentTimeMillis();
for (int i = 0; i < 1000000000; i++) {
B b = (B) a;
}
System.out.println("Cast: " + (System.currentTimeMillis() - start));
}
private static void testNew() {
long start = System.currentTimeMillis();
for (int i = 0; i < 1000000000; i++) {
C c = new C();
}
System.out.println("New: " + (System.currentTimeMillis() - start));
}
}[/code]
Não testei no desktop, mas no notebook (P4, 512mb, JVM Sun 1.4.2-b28 com HotSpot Client), os resultados sao:
Run 1
New: 14616
Cast: 4648
Run 2
New: 16759
Cast: 5049
Run 3
New: 18652
Cast: 5299
Editado: usando -server, o resultado eh mais aparente ainda:
Run 1
New: 15557
Cast: 10
Run 2
New: 15306
Cast: 0
Run 3
New: 15207
Cast: 0
Estou me baseando num livro de estrutura de dados para fazer o algoritmo. A tática que eles recomendam é utilizar um stack para gravar o transverse da árvore, assim se tiver que dar marcha ré é tranquilo.
O que vc quer dizer com page clustering ??? A vantagem do B-Tree é que vc pode fazer o fetch página por página do HD, economizando acesso a disco. É isso que vc se refere?
Que parada é essa de raw disk ??? Boiei ??? Onde eu pesquiso sobre isso ??? Como eu descubro esse e outros pulos do gato que o Oracle utiliza ??? Existe algum livro Oracle Internals ou Oracle Secrets ??? É claro que os caras não vão entregar todos os pulos de gato, mas algumas coisas devem ser do conhecimento geral.
Cria uma classe e chame ela por um nome bonitinho, como MeuRetornoDoMetodo, sei lá… nela você coloca dois atributos, um int e um Object.
Na classe que tem o método, defina um atributo que seja dessa classe aí, talvez static seja até melhor não sei, e dá um new nele lá no construtor da classe que tem o tal método. Aí, quando executar o método, coloca os valores nessa classe e retorna ela. Pronto! Lembre-se de copiar os valores pra outro lugar antes de chamar o método de novo…
Cria uma classe e chame ela por um nome bonitinho, como MeuRetornoDoMetodo, sei lá… nela você coloca dois atributos, um int e um Object.
Na classe que tem o método, defina um atributo que seja dessa classe aí, talvez static seja até melhor não sei, e dá um new nele lá no construtor da classe que tem o tal método. Aí, quando executar o método, coloca os valores nessa classe e retorna ela. Pronto! Lembre-se de copiar os valores pra outro lugar antes de chamar o método de novo…
Falou ^__^[/quote]
Acho que vc tem toda razão. Dessa maneira eu não preciso ficar dando new toda hora. Esse objeto vai ser mutátvel e vai servir só como um burro de carga !!! Se a classe for thread-safe (meu caso) vai funcionar bonito !!!
Sobre Raw Disk, trabalhar com ele indica que sua aplicação vai ter acesso direto ao disco, sem passar pelo SO nem filesystem, logo sem seus buffers [e eventuais benefícios].
Oracle, DB2, MySQL, etc. implementam isto como uma boa solução, você pode colocar sua database num arquivo ou em uma partição [ou um disco, ou um array de dsicos, ou…] que a aplicação [neste caso, o banco de dados] lê diretamente, em modo caracter.
Isto significa que você não vai precisar ficar trocando blocos com o disco, pdoe trabalhar com uma unidade muito menor, o que geralmente te garante alguma performance. Hoje em dia, não é tããããão significativo assim, mas se você quer correr atrás de cada ciclo e bytezinho, pode tentar.
