Como procurar o intervalo de um conjunto de intervalos contíguos para um determinado número

Question

de forma simples, é isso que estou tentando fazer:

Eu tenho uma coleção de Range objetos que são contíguos (não sobrepostos, sem espaços entre eles), cada um contendo um start e end int e uma referência a outro objeto obj.Esses intervalos não têm tamanho fixo (o primeiro pode ser 1-49, o segundo 50-221, etc.).Esta coleção pode crescer bastante.

Espero encontrar uma maneira de procurar o intervalo (ou mais especificamente, o objeto ao qual ele faz referência) que inclui um determinado número sem ter que iterar por toda a coleção, verificando cada intervalo para ver se inclui o número.Essas pesquisas serão realizadas com frequência, portanto, velocidade/desempenho são fundamentais.

Alguém sabe de um algoritmo/equação que possa me ajudar aqui?Estou escrevendo em Java.Posso fornecer mais detalhes, se necessário, mas decidi tentar manter as coisas simples.

Obrigado.

Answer 1

Se parece que você deseja usar um TreeMap, onde a chave é a parte inferior do intervalo e o valor é o Range objeto.

Então, para identificar o intervalo correto, basta usar o floorEntry() método para chegar muito rapidamente ao valor mais próximo (menor ou igual) Range, que deve conter a chave, assim:

    TreeMap<Integer, Range> map = new TreeMap<>();
    map.put(1, new Range(1, 10));
    map.put(11, new Range(11, 30));
    map.put(31, new Range(31, 100));

    // int key = 0; // null
    // int key = 1; // Range [start=1, end=10]
    // int key = 11; // Range [start=11, end=30]
    // int key = 21; // Range [start=11, end=30]
    // int key = 31; // Range [start=31, end=100]
    // int key = 41; // Range [start=31, end=100]
    int key = 101; // Range [start=31, end=100]
    // etc.

    Range r = null;
    Map.Entry<Integer, Range> m = map.floorEntry(key);
    if (m != null) {
        r = m.getValue();
    }
    System.out.println(r);

Como a árvore é sempre classificada pela ordem natural do limite inferior do intervalo, todas as suas pesquisas serão, na pior das hipóteses, O(log(n)).

Você desejará adicionar alguma verificação de integridade para quando sua chave estiver completamente fora dos limites (por exemplo, quando a chave estiver além do final do mapa, ela retornará o último Range no mapa), mas isso deve lhe dar uma ideia de como proceder.

Answer 2

Supondo que suas pesquisas sejam de extrema importância e você possa poupar O(N) memória e aproximadamente O(N^2) tempo de pré-processamento, o algoritmo seria:

• apresentar uma aula ObjectsInRange, que contém:início do intervalo (int startOfRange) e um conjunto de objetos (Set<Object> objects)
• apresentar um ArrayList<ObjectsInRange> oir, que conterá ObjectsInRange ordenado pelo startOfRange
• para cada Range r, certifique-se de que exista ObjectsInRange (vamos chamá-los a e b) de tal modo que a.startOfRange = r.start e b.startOfRange = b.end.Então, para todos ObjectsInRange x entre a, e até (mas não incluindo) b, adicionar r.obj para o seu x.objects definir

A pesquisa, então, é a seguinte:

• para número inteiro x, encontre tal i que oir[i].startOfRange <= x e oir[i+1].startOfRange > x
• observação: i pode ser encontrado com bissecção em tempo O (log N)!
• seus objetos são oir[i].objects

Answer 3

Se a coleção estiver em ordem, você poderá implementar uma pesquisa binária para encontrar o intervalo correto em tempo O(log(n)).Não é tão eficiente quanto o hash para coleções muito grandes, mas se você tiver menos de 1.000 intervalos, pode ser mais rápido (porque é mais simples).