Estou trabalhando em ummplementação c # jquery e estou tentando descobrir um algoritmo eficiente para localizar elementos em um subconjunto de todo o DOM (por exemplo, um subseletor). No momento, estou criando um índice de seletores comuns: class, id e tag quando o DOM é criado.

A estrutura de dados básica é como seria de esperar, uma árvore deElements Que contêmIEnumerable<Element> Children eParent. Isso é simples ao pesquisar todo o domínio usando umDictonary<string,HashSet<Element>> para armazenar o índice.

Não consegui entender a maneira mais eficaz de pesquisar subconjuntos de elementos usando um índice. Eu uso o termo "subconjunto" para me referir ao conjunto inicial a partir do qual um seletor subsequente em uma cadeia será executado. A seguir, são métodos que eu pensei:

Recupere correspondências de todo o DOM para uma subconsulta e elimine aquelas que não fazem parte do subconjunto. Isso exige que os pais de cada correspondência sejam percorridos até que a raiz seja encontrada (e seja eliminada) ou um membro do subconjunto seja encontrado (e seja um filho, portanto incluído) Mantenha o índice separadamente para cada element Mantenha um conjunto de pais para cada elemento (para acelerar o número 1 eliminando a travessi Recrie o índice inteiro para cada subconsult Basta pesquisar manualmente, exceto nos seletores principai

O custo de cada técnica possível depende muito da operação exata que está sendo realizada. O número 1 é provavelmente muito bom na maioria das vezes, já que na maioria das vezes quando você faz uma sub-seleção, você está direcionando elementos específicos. O número de iterações necessárias seria o número de resultados * a profundidade média de cada element

O segundo método seria de longe o mais rápido para a seleção, mas às custas dos requisitos de armazenamento que aumentam exponencialmente com a profundidade e a difícil manutenção do índice. Eu praticamente eliminei isso.

O terceiro método tem uma pegada de memória bastante ruim (embora muito melhor que o nº 2) - pode ser razoável, mas além dos requisitos de armazenamento, adicionar e remover elementos se torna substancialmente mais caro e complicad

O 4º método exige atravessar toda a seleção, de modo que parece inútil, pois a maioria das subconsultas será executada apenas uma vez. Só seria benéfico se se esperasse que uma subconsulta fosse repetida. (Como alternativa, eu poderia fazer isso enquanto percorria um subconjunto de qualquer maneira - exceto que alguns seletores não exigem a pesquisa em todo o subdomínio, por exemplo, seletores de ID e posição

O quinto método será bom para subconjuntos limitados, mas muito pior que o primeiro método para subconjuntos que são grande parte do DO

Quaisquer pensamentos ou outras idéias sobre a melhor forma de conseguir isso? Eu poderia fazer um híbrido dos nºs 1 e 4, adivinhando o que é mais eficiente, considerando o tamanho do subconjunto pesquisado versus o tamanho do DOM, mas isso é bastante confuso e eu prefiro encontrar uma solução universal. No momento, estou apenas usando o nº 4 (apenas consultas com DOM completo usam o índice), o que é bom, mas muito ruim se você decidiu fazer algo como$('body').Find('#id')

Aviso: Esta é a otimização antecipada. Não tenho um gargalo que precisa ser resolvido, mas como um problema acadêmico não consigo parar de pensar nisso ...

Soluçã

Aqui está a implementação da estrutura de dados proposta pela resposta. Está funcionando perfeitamente como substituto quase imediato de um dicionário.

interface IRangeSortedDictionary<TValue>: IDictionary<string, TValue>
{
    IEnumerable<string> GetRangeKeys(string subKey);
    IEnumerable<TValue> GetRange(string subKey);

}
public class RangeSortedDictionary<TValue> : IRangeSortedDictionary<TValue>
{
    protected SortedSet<string> Keys = new SortedSet<string>();
    protected Dictionary<string,TValue> Index = 
        new Dictionary<string,TValue>();
    public IEnumerable<string> GetRangeKeys(string subkey)
    {
        if (string.IsNullOrEmpty(subkey)) {
            yield break;
        }
        // create the next possible string match
        string lastKey = subkey.Substring(0,subkey.Length - 1) +
            Convert.ToChar(Convert.ToInt32(subkey[subkey.Length - 1]) + 1);

        foreach (var key in Keys.GetViewBetween(subkey, lastKey))
        {
            // GetViewBetween is inclusive, exclude the last key just in case
            // there's one with the next value
            if (key != lastKey)
            {
                yield return key;
            }
        }
    }

    public IEnumerable<TValue> GetRange(string subKey)
    {
        foreach (var key in GetRangeKeys(subKey))
        {
            yield return Index[key];
        }
    }
    // implement dictionary interface against internal collections
}

Code está aqui:http: //ideone.com/UIp9