Um algoritmo gama intersecção melhor do que o (n)?
https://stackoverflow.com/questions/303591
-
08-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Gama intersecção é um simples, mas o problema não-trivial.
A sua foi respondida já por duas vezes:
As primeiras soluções é O (n) e a segunda solução é para uma base de dados (o qual é menos do que o (n) de curso).
Eu tenho o mesmo problema, mas para um grande n e eu não estou dentro de um banco de dados.
Este problema parece ser muito semelhante ao pontos loja 2D para recuperação rápida dos que dentro de um retângulo mas eu não vejo como ele mapeia.
Então, o que estrutura de dados que você armazenar o conjunto de intervalos em, de tal forma que a procura em uma escala custa menos de O (n)? (Crédito extra para o uso de bibliotecas disponíveis para Java)
EDIT:
Eu quero começar um subconjunto de todas as faixas de interseção, ou seja, o intervalo de pesquisa poderia se cruzam vários intervalos.
O método que deve ser menor do que o (n) em Java é:
public class RangeSet {
....
public Set<Range> intersects(Range range);
....
}
Onde Gama é apenas uma classe que contém um par de início int e fim.
Esta não é uma pergunta impossível, eu já tenho a solução, eu só queria ver se havia uma maneira mais padrão / mais simples de fazê-lo
Solução
A abordagem padrão é usar um intervalo de árvore .
Em ciência da computação, uma árvore de intervalo é uma estrutura de dados árvore para intervalos de espera. Especificamente, ele permite que se encontrar de forma eficiente todos os intervalos que se sobrepõem com qualquer ponto ou intervalo. Ele é frequentemente usado para o janelamento consultas, por exemplo, para encontrar todas as estradas em um mapa computadorizado dentro de uma janela retangular, ou para encontrar todos os elementos visíveis dentro de uma cena tridimensional. Uma estrutura de dados semelhante é a árvore segmento.
A solução trivial é visitar cada intervalo e teste se cruza com o dado ponto ou intervalo de tempo, o que requer tempo O (n), onde n é o número de intervalos na colecção. Uma vez que uma consulta pode retornar todos os intervalos, por exemplo, se a consulta é um grande intervalo de interseção todos os intervalos na coleção, esta é assintoticamente ótima; no entanto, podemos fazer melhor, considerando algoritmos sensíveis a saída, onde o tempo de execução é expressa em termos de m, o número de intervalos produzidos pela consulta. árvores intervalo tem um tempo de consulta de O (N log N + m) e um tempo de criação inicial de O (N log N), limitando ao mesmo tempo o consumo de memória para o (n). Após a criação, árvores de intervalo pode ser dinâmica, permitindo a inserção eficiente e eliminação de um intervalo de O (N log N). Se os pontos finais dos intervalos estão dentro de um intervalo pequeno número inteiro (por exemplo, no intervalo de [1, ..., S (n)]), existem estruturas de dados mais rápidos [1] com o pré-processamento de tempo O (n) e o tempo de consulta O ( 1 + m) para os intervalos de geração m contendo um determinado ponto de consulta.
Outras dicas
Editar: Parece que esta solução é mais ou menos um Interval Tree. Uma implementação mais completa de uma árvore Intervalo pode ser encontrada aqui .
class TreeNode
{
public:
long pivot;
List<Range> leaves; //Any ranges that intersect the pivot
TreeNode left; //Tree nodes that fall to the left of the pivot
TreeNode right; //Tree nodes that fall to the right of the pivot
};
Prep O (N log N):
- Criar lista de faixas
- Escolha os pontos de articulação (possivelmente usando uma lista ordenada das datas de término.) ??
- Construa a sua árvore.
Pesquisar:
- Use binário busca para encontrar o primeiro pivô que é> = TestRange.End
-
Traverse a árvore até o pivô> TestRange.Start
2a. Adicione as folhas ao seu resultado.
Exemplo:
intervalos:
- 0-2
- 1-2
- 2-3
- 1-4
- 2-4
- 0-5
- 4-5
- 2-6
- 3-7
Tree:
4
--------------+------------------
3 | 7
| 1-4 |
| 2-4 |
| 0-5 |
| 4-5 |
---------+------ --------+--------
2 | null 6 | null
-----+---- 2-3 ----+---- 3-7
null | null null | null
0-2 2-6
1-2
Não sobreposição de intervalos:
Prep O (N log N):
- Faça uma matriz / vetor das faixas.
- Ordenar o vector para o fim do intervalo (laços ruptura por triagem pelo início do intervalo)
Pesquisar:
- Use binário busca para encontrar o primeiro intervalo com um valor final de> = TestRange.Start
-
Iterator começando na busca binária até encontrar um Iniciar> TestRange.End:
2a. Se o intervalo se o intervalo atual está dentro do TestRange, adicioná-lo ao seu resultado.
Isso depende do seu problema exato, na questão ligada, os intervalos onde distinta, parte não comum, ea pesquisados ??variaram poderia abranger várias faixas. Se o seu problema é o mesmo, a sua é muito fácil: Tomar uma matriz das gamas, classificá-las pelos seus valores mais baixos (desde que não se sobreponham, isto seria também a mesma ordem como classificados pelos seus valores mais altos).
Agora é só fazer uma Binsearch para o valor mais baixo o seu alvo (ou menor, se não exato) e um para o valor superior alvo (ou maior, se não exata). Os índices resultantes são os das gamas que são coverd. Você tem que verificar wheter os intervalos no próprio índices são de entrada ou excluídas, mas que são apenas 2 cheques. No geral complexidade O (log n).
intervalos sobrepostos:
Prep O (N log N):
- Faça uma matriz / vetor das faixas.
- Ordenar o vector para o fim do intervalo (laços ruptura por triagem pelo início do intervalo)
-
Faça um segundo vector de inteiros. Isto representa o ponto em que você pode parar de procurar.
int stop[size]; stop[size-1] = Ranges[size - 1].start; for (int i = size - 2; i >= 0; i--) { stop[i] = min(Ranges[i].start, stop[i+1]); }
Pesquisar:
- Use binário busca para encontrar o primeiro intervalo com um valor final de> = TestRange.Start
-
Iterator começando na busca binária até parar [i]> TestRange.End:
2a. Se o intervalo se o intervalo atual está dentro do TestRange, adicioná-lo ao seu resultado.
Se os intervalos se sobrepõem, e se quer recuperar todas os intervalos que se sobrepõem (ou conter) um determinado intervalo de destino, a maioria das soluções acima não aparecem para trabalhar.
Como alguns têm fora pontas, se (pior caso) todas os intervalos acontecer para cruzar a faixa de destino (por exemplo, se o intervalo de destino é {0..MAXINT} ou similar), em seguida, é claro que leva o (n) para retornar as n varia.
Mas não é o interessante e caso típico / média, onde apenas uma pequena% do total de n faixas se cruzam a faixa-alvo? Ligue para o número que não Intersect "m" - nesse caso, você pode concebivelmente ser capaz de fazer, bem como O (m). E se n = 10 ^ 9 e m = 10, que é uma diferença make-or-break.
Considere o caso simples de um documento de texto que tem várias regiões marcadas por seu "tipo" - talvez você quiser encontrar todas as unidades marcadas-up que contêm ou Intersect um determinado intervalo contíguo de texto (por exemplo, um parágrafo). Em HTML, XML ou semelhante aqueles só pode ser ancestrais do texto-nó (s) contendo pelo menos alguns dos caracteres da gama alvo. Em representações típicas com ponteiros-mãe em cada nó, que é O (m) - muito melhor do que o (n), especialmente porque m é (para as gamas alvo curtos ou síncronos) meramente a árvore profundidade de sobreposição, o que tende a ser ainda menor do que ln (n) porque grandes documentos XML na prática obter bushier não mais profundo.
O caso interessante é mais difícil: o que se seus "elementos" não formam uma árvore como em XML, mas podem se sobrepor como no MECS, CLIX, LMNL, e alguns outros sistemas? Você ainda quer encontrar todas as regiões / "elementos" que se sobrepõem seu alvo, mas eles não são tão facilmente organizados.
Por outro lado, você deve ser capaz de fazer muito bem porque faixas marcadas-up em muitas aplicações são mais frequentemente pequena - há muito mais palavras, frases e parágrafos em um livro, que há capítulos. Assim, mesmo que pode haver um grande número de intervalos que começar antes do alvo e um número enorme esse fim depois dele, o cruzamento será muito pequeno, em média.
Eu acho que isso é o que a pergunta original foi chegando, e eu tenho medo que eu não vi uma resposta que endereços que problema. Se não é o que a pergunta original era, então eu gostaria de colocá-la como uma nova questão.
Parece que você precisa de uma classe que implementa a interface SortedSet. TreeSet é a implementação que acompanha o API núcleo.
têm um conjunto segurando as faixas classificadas segundo valor mais baixo, e um classificadas segundo maior valor.
Você pode então implementar o equivalente do algoritmo de banco de dados usando os conjuntos na memória.
Quanto a saber se este é realmente mais rápido do que O (n), eu não poderia dizer.
Assim como uma árvore quad trabalha para um conjunto de pontos 2D, uma árvore binária simples devem trabalhar para este caso. Criar uma árvore com os seus intervalos.
Para explicar melhor: Cada nó na árvore contém dois inteiros, o início eo fim do intervalo, e os dois filhos, se não é um nó folha. Para encontrar as faixas que seus vãos faixa de entrada, em seguida, começando no topo da árvore
- if the node range intersects the input range:
- if it's a leaf node, then add the range to your result list
- if it's not a leaf node, then traverse down to the child nodes and repeat this process.
Deve ser O (log N)
Além disso detalhe: A árvore binária seria estruturada como uma versão 1-d de uma árvore quad. Cada nó teria três inteiros (desculpe, eu disse dois acima, mas agora eu percebo que você precisa de três), o mais baixo representando o valor mais baixo da faixa mais baixa que está abaixo deste nó, o mais alto representando o valor mais alto da gama mais alta que a do abaixo deste nó, e o pivô. A criança esquerda iria abranger desde a este menor nó para seu pivô. A criança direita iria abranger desde pivô deste nó para o mais alto deste nó. Se há apenas um intervalo que vai de "menor" para "alto", você não teria um pivô e isso seria uma folha. O ideal é você pegar os pivôs para cada nó para manter a árvore balanceada.
Quando eu tive esse problema, eu usei um array ordenado de intervalos e uma busca binária para procurar cruzamentos. Este é (creio eu) O (log n) performance, com um pouco de sobrecarga para lidar com sobreposição de faixas.
A resposta à sua pergunta é, penso eu, produzidos a partir de código abaixo, mas parando curto da inserção. Eu apresentar o código de toda a confusão evitar pelo contexto diferindo -. I necessário para inserir um intervalo de pontos de código Unicode em uma lista dos intervalos codepoint
- EDIT -
Adaptando o código abaixo para determinar cruzamentos de múltiplas faixas envolve uma busca para a frente trivial do ponto de inserção até uma gama é encontrado que não há intersecta mais longos.
- END EDIT -
classe A Faixa contém:
final int lower; // lower end of range
final int upper; // upper end of range
public int compareTo(Object obj) {
if(obj==null) { return -1; }
Range oth=(Range)obj;
if(lower<oth.lower) { return -1; }
if(lower>oth.lower) { return 1; }
if(upper<oth.upper) { return -1; }
if(upper>oth.upper) { return 1; }
return 0;
}
Faixa de Inclusão:
public Builder addRange(int fir, int las) {
if(fir!=-1) { fir&=0x001FFFFF; }
if(las!=-1) { las&=0x001FFFFF; }
if(codepoints==null || codepoints.length==0) {
codepoints=new Range[]{new Range(fir,las)};
}
else {
int idx=Range.findChar(codepoints,fir);
int ins=(idx<0 ? -(idx+1) : idx);
if(idx<0) {
if (ins>0 && fir==(codepoints[ins-1].upper+1)) { idx=(ins-1); } // new range adjoins the following range (can't overlap or idx would be >=0)
else if(ins<codepoints.length && las>=(codepoints[ins ].lower-1)) { idx=ins; } // new range overlaps or adjoins the following range
}
if(idx<0) {
codepoints=(Range[])Util.arrayInsert(codepoints,ins,new Range(fir,las));
}
else {
boolean rmv=false;
for(int xa=(idx+1); xa<codepoints.length && codepoints[xa].lower<=las; xa++) {
if(las<codepoints[xa].upper) { las=codepoints[xa].upper; }
codepoints[xa]=null;
rmv=true;
}
if(codepoints[idx].lower>fir || codepoints[idx].upper<las) {
codepoints[idx]=new Range((codepoints[idx].lower < fir ? codepoints[idx].lower : fir),(codepoints[idx].upper>las ? codepoints[idx].upper : las));
}
if(rmv) { codepoints=Range.removeNulls(codepoints); }
}
}
return this;
}
Binary Pesquisa:
static int findChar(Range[] arr, int val) {
if(arr.length==1) {
if (val< arr[0].lower) { return -1; } // value too low
else if(val<=arr[0].upper) { return 0; } // value found
else { return -2; } // value too high
}
else {
int lowidx=0; // low index
int hghidx=(arr.length-1); // high index
int mididx; // middle index
Range midval; // middle value
while(lowidx<=hghidx) {
mididx=((lowidx+hghidx)>>>1);
midval=arr[mididx];
if (val< midval.lower) { hghidx=(mididx-1); } // value too low
else if(val<=midval.upper) { return mididx; } // value found
else { lowidx=(mididx+1); } // value too high
}
return -(lowidx+1); // value not found.
}
}
