variedade Judy para idiomas gerenciados

StackOverflow https://stackoverflow.com/questions/550204

Pergunta

matriz Judy é estrutura de dados rápido que pode representar uma matriz esparsa ou um conjunto de valores. Existe a sua execução para idiomas gerenciados, como C #? Graças

Foi útil?

Solução

É importante notar que estas são muitas vezes chamado Judy árvores ou Judy Tenta se você estiver pesquisando para eles.

Eu também olhou para uma implementação do .NET, mas não encontrou nada. Também digno de nota que:

A implementação é pesadamente concebida em torno de utilização de cache eficiente, uma vez que tais detalhes de execução podem ser altamente dependente do tamanho de determinadas construções utilizadas dentro dos sub-estruturas. A Net conseguiu implementação pode ser um pouco diferente a este respeito.

Existem alguns obstáculos significativos para ele que eu posso ver (e há provavelmente mais que minha breve verificação perdidos)

  • A API tem alguns aspectos OO bastante anti (por exemplo, um ponteiro nulo é visto como uma árvore vazia), de modo simplista, mover o ponteiro do estado para a LHS e funções fazer a conversão métodos de instância para C ++ não iria funcionar.
  • A implementação das sub estruturas Olhei fizeram uso pesado de ponteiros. Eu não posso vê-los de forma eficiente sendo traduzido para referências em idiomas gerenciados.
  • A implementação é uma destilação de um monte de idéias muito complexas que desmente a simplicidade da API pública.
  • O código base é de cerca de 20K linhas (mais do mesmo complexo), isso não me parece uma porta fácil.

Você poderia tomar a biblioteca e coloque o código C em C ++ / CLI (provavelmente simplesmente segurando, internamente, um ponteiro que é o trie c api e ter todas as chamadas c apontam para este). Isto proporcionaria uma implementação simplista, mas as bibliotecas vinculadas para a implementação nativa pode ser problemático (como alocação de memória poder). Você também provavelmente precisa lidar com a conversão .Net cordas para plain byte velho * na transição bem (ou apenas trabalhar com bytes diretamente)

Outras dicas

Judy realmente não se encaixa bem com linguagens gerenciadas. Eu não acho que você vai ser capaz de usar algo como SWIG e obter a primeira camada feito automaticamente.

Eu escrevi PyJudy e acabei tendo que fazer algumas mudanças na API não triviais para caber bem em Python. Por exemplo, eu escrevi na documentação:

matrizes JudyL mapear as palavras de máquinas para palavras da máquina. Na prática, as palavras armazenar inteiros sem sinal ou ponteiros. PyJudy suporta todas as quatro mapeamentos como classes distintas.

  • pyjudy.JudyLIntInt - Mapa não assinado chaves inteiras para inteiro sem sinal valores
  • pyjudy.JudyLIntObj - Mapa não assinado chaves inteiras para valores de objetos Python
  • pyjudy.JudyLObjInt - Mapa Python chaves de objeto para inteiro sem sinal valores
  • pyjudy.JudyLObjObj - Mapa Python chaves de objeto para valores de objetos Python

Eu não olhei o código para alguns anos para as minhas memórias sobre ele são muito nebuloso. Foi minha primeira biblioteca de extensão Python, e eu lembro que eu cortei juntos uma espécie de sistema modelo para a geração de código. Hoje em dia eu iria usar algo como Genshi.

Eu não posso apontar alternativas para Judy -. Essa é uma razão pela qual eu estou procurando Stackoverflow

Edit:. Eu tenho dito que os meus números de cronometragem na documentação estão fora do que a documentação do Judy sugere porque Judy é desenvolvido para linhas de cache de 64 bits e meu PowerBook foi de apenas 32 bits

Alguns outros links:

A última tem números de comparação para diferentes implementações de alto desempenho Trie.

Este está provando mais complicado do que eu pensava. PyJudy pode valer a pena um olhar, como seria Tie :: Judy . Há algo sobre Softpedia , e algo rubi-ish . O problema é que nenhum deles é especificamente .NET.

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top