Algoritmo para encontrar interseções de span em um conjunto ordenado

5

Eu tenho um conjunto de itens estritamente pedidos no prazo. Cada item pode ser único (sem Avançar, sem Anterior) ou parte de um intervalo (com 1 ou 2 pontos de extremidade adicionais). Por exemplo, na figura A faz parte de um intervalo de 3 elementos 1 - > 4 - > 5, B faz parte de uma extensão de 2 elementos 2 - > 3 e C faz parte de um intervalo de 2 elementos 6 - > 16. Como você pode ver, os espaços podem se sobrepor (start2 > start1, end1 > end2).

O que eu quero fazer é elaborar um algoritmo rápido para descobrir quais extensões (ou indivíduos) estão se cruzando em um determinado intervalo Min - > Max.

Minha abordagem ingênua é simplesmente testar cada item do conjunto, com algo como:

for(auto const & e : items)
{
    if(e.Previous)
    {
        // Middle or last item in a set (already been tested).

        continue;
    }

    auto t1 = e.Time, t2 = e.Time;

    if(e.Next)
    {           
        if(e.Next.Next)
        {
            // Part of a 3 item span (start, middle, end).

            t2 = e.Next.Next.Time;
        }
        else
        {
            // Part of a 2 item span (start, end).

            t2 = e.Next.Time;
        }
    }       

    if(t1 > MaxTime || t2 < MinTime)
    {
        // Does not intersect the span.

        continue;
    }       

    ... Do something with the item, such as draw it.
}

Isso não funciona muito mal com 250.000 itens, mas começa a ficar muito lento quando você chega a milhões.

Eu tenho muito tempo disponível na inicialização para obter um std: future instalado e em execução para pré-processar essas coisas em uma estrutura mais útil, se isso ajudar. Eu também preciso ser capaz de acrescentar ao final do conjunto, embora mantendo a ordem de tempo estritamente crescente (por exemplo, now () > = items.last (). Time).

Alguma coisa acontece com alguém?

    
por Robinson 22.03.2016 / 14:42
fonte

1 resposta

3

Uma boa estrutura de dados para o que você deseja fazer é uma Árvore de Intervalo . Você pode construir um em O (nlogn) e as consultas levam O (logn + k), onde k é o número de intervalos retornados pela consulta.

    
por 23.03.2016 / 17:07
fonte