maneira mais rápida de encontrar objetos de uma coleção acompanhada por condição de membro corda

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

Pergunta

Suponha que eu tenho uma coleção (seja ele um array, lista genérica, ou o que é o mais rápidos solução para este problema) de uma determinada classe, vamos chamá-lo ClassFoo: 

class ClassFoo
{
    public string word;
    public float score;
    //... etc ...
}

Suponha que não vai ser como 50.000 itens na coleção, tudo em memória. Agora eu quero obter o mais rápido possível todas as instâncias na coleção que obedecer a uma condição em seu membro do bar, por exemplo como este: 

List<ClassFoo> result = new List<ClassFoo>();
foreach (ClassFoo cf in collection)
{
    if (cf.word.StartsWith(query) || cf.word.EndsWith(query))
        result.Add(cf);
}

Como faço para obter os resultados o mais rápido possível? Devo considerar algumas técnicas avançadas de indexação e datastructures?

O domínio de aplicação para este problema é uma autocompleter, que recebe uma consulta e dá uma coleção de sugestões como resultado. Suponha que a condição não existe nada mais complexo do que isso. Considere-se também que não vai ser um monte de pesquisas.

Foi útil?

Solução

Com a restrição de que a cláusula de condição pode ser "qualquer coisa", então você está limitado a digitalização de toda a lista e aplicar a condição.

Se existem limitações sobre a cláusula de condição, então você pode olhar para organizar os dados para lidar com mais eficiência as consultas.

Por exemplo, o amostra de código com o "byFirstLetter" dicionário não ajuda em nada com uma consulta "endsWith".

Assim, ele realmente se resume ao que consulta você quer fazer contra esses dados.

Em bancos de dados, este problema é o peso do "otimizador de consulta". Em um banco de dados típico, se você tiver um banco de dados sem índices, obviamente, cada consulta vai ser uma verificação de tabela. Como você adicionar índices para a tabela, o otimizador pode usar esses dados para fazer planos de consulta mais sofisticados para melhor obter os dados. Isso é essencialmente o problema que você está descrevendo.

Uma vez que você tem um subconjunto mais concreta dos tipos de consultas, em seguida, você pode fazer uma melhor decisão quanto ao que estrutura é melhor. Além disso, é preciso considerar a quantidade de dados. Se você tem uma lista de 10 elementos cada menos de 100 bytes, uma varredura de tudo pode muito bem ser a coisa mais rápida que você pode fazer uma vez que você tem uma pequena quantidade de dados. Obviamente que não escala para um elementos 1m, mas até mesmo técnicas de acesso inteligentes têm um custo na instalação, manutenção (como a manutenção do índice), e memória.

Editar , com base no comentário

Se for um completer auto, se os dados é estático, em seguida, classificá-lo e usar uma pesquisa binária. Você realmente não vai chegar mais rápido do que isso.

Se os dados é dinâmico, em seguida, armazená-lo em uma árvore equilibrada, e procurar que. Isso é efetivamente uma busca binária, e permite que você mantenha adicionar os dados aleatoriamente.

Qualquer outra coisa é certa especialização nesses conceitos.

Outras dicas

Var Respostas = myList.Where (ponto => item.bar.StartsWith (query) || item.bar.EndsWith (query));

que é o mais fácil na minha opinião, deve ser executado rapidamente.

Não tenho certeza eu entendo ... Tudo que você realmente pode fazer é otimizar a regra, essa é a parte que precisa ser mais rápido. Você não pode acelerar o ciclo sem justa jogar mais hardware para ele.

Você pode paralelizar se você tiver vários núcleos ou máquinas.

Eu não estou no meu Java agora, mas eu gostaria de pensar sobre as coisas seguintes.

Como você está criando sua lista? Talvez você pode criar já encomendados de uma forma que reduz o tempo de comparação.

Se você está apenas fazendo um laço em linha reta através de sua coleção, você não verá muita diferença entre armazená-lo como uma matriz ou como uma lista ligada.

Para armazenar os resultados, dependendo de como você está coletando-los, a estrutura poderia fazer uma diferença (mas assumindo estruturas genéricas do Java é inteligente, não vai). Como eu disse, eu não estou no meu Java, mas presumo que a lista encadeada genérica iria manter um ponteiro cauda. Neste caso, não seria realmente fazer a diferença. Alguém com mais conhecimento da matriz subjacente vs implementação lista ligada e como ele acaba olhando no código byte provavelmente poderia dizer se anexando a uma lista ligada com um ponteiro de cauda ou inserir em uma matriz é mais rápido (o meu palpite seria a matriz ). Por outro lado, você precisa saber o tamanho do seu conjunto de resultados ou sacrificar algum espaço de armazenamento e torná-lo tão grande como toda a coleção que você é a iteração através se você quisesse usar uma matriz.

Otimizando sua consulta comparação por descobrir que a comparação é mais provável que seja verdade e fazer que um primeiro poderia também ajuda. isto é:. Se, em geral, 10% do tempo um membro da coleção começa com a sua consulta, e 30% do tempo de extremidades de membros com a consulta, você iria querer fazer a comparação final em primeiro lugar

Para o seu exemplo em particular, classificando a coleção ajudaria como você poderia binarychop para o primeiro item que começa com consulta e terminar cedo, quando chegar o próximo que não; você também pode produzir uma tabela de ponteiros para itens de coleção classificada pelo reverso de cada corda para a segunda cláusula.

Em geral, se você conhece a estrutura da consulta com antecedência, você pode classificar sua coleção (ou construir vários índices ordenados para sua coleção se houver várias cláusulas) de forma adequada; se você não fizer isso, você não será capaz de fazer melhor do que a busca linear.

Se é algo em que você preencher a lista uma vez e depois fazer muitas pesquisas (milhares ou mais), então você pode criar algum tipo de consulta do dicionário que mapeia começa com / termina com os valores para seus valores reais. Isso seria uma pesquisa rápida, mas usaria muito mais memória. Se você não está fazendo que muitas pesquisas ou sabe que vai ser repovoamento da lista, pelo menos, semi-freqüentemente eu iria com a consulta LINQ que CQ sugeriu.

Você pode criar algum tipo de índice e pode chegar mais rápido.

Podemos construir um índice assim: 

Dictionary<char, List<ClassFoo>> indexByFirstLetter;
foreach (var cf in collection) {
  indexByFirstLetter[cf.bar[0]] = indexByFirstLetter[cf.bar[0]] ?? new List<ClassFoo>();
  indexByFirstLetter[cf.bar[0]].Add(cf);
  indexByFirstLetter[cf.bar[cf.bar.length - 1]] = indexByFirstLetter[cf.bar[cf.bar.Length - 1]] ?? new List<ClassFoo>();
  indexByFirstLetter[cf.bar[cf.bar.Length - 1]].Add(cf);
}

Em seguida, use o assim: 

foreach (ClasssFoo cf in indexByFirstLetter[query[0]]) {
  if (cf.bar.StartsWith(query) || cf.bar.EndsWith(query))
    result.Add(cf);
}

Agora nós possivelmente não tem que percorrer tantos ClassFoo como no seu exemplo, mas, novamente, temos de manter o índice atualizado. Não há garantia de que ele é mais rápido, mas é definitivamente mais complicado.

Depende. São todos os seus objetos sempre vai ser carregado na memória? Você tem um limite finito de objetos que podem ser carregados? Será que suas consultas têm de considerar os objetos que não foram carregadas ainda?

Se a coleção terá grande, eu definitivamente usar um índice.

Na verdade, se a coleção pode crescer a um tamanho arbitrário e você não tiver certeza de que você será capaz de caber tudo na memória, eu olhar para um ORM, um banco de dados in-memory, ou outro incorporado base de dados. XPO de DevExpress para ORM ou SQLite.Net para in-memory database vem à mente.

Se você não quer ir tão longe, fazer um índice simples que consiste o "bar" referências membros mapeamento para referências de classe.

Se o conjunto de possíveis critérios é fixo e pequeno, você pode atribuir uma máscara de bits para cada elemento na lista. O tamanho da máscara de bits é o tamanho do conjunto dos critérios. Quando você cria um elemento / adicioná-lo à lista, você verificar quais critérios ela satisfaz e, em seguida, definir os bits correspondentes na máscara de bits deste elemento. Combinando os elementos da lista vai ser tão fácil como combinar seus bitmasks com a máscara de bits alvo. Um método mais geral é o filtro Bloom.

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