A C # Implementação da Linha Número
https://stackoverflow.com/questions/1614137
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
NumberLine line = new NumberLine();
line.AddRange(1, 5);
line.AddRange(20, 30);
line.CheckRange(10, 25);
NumberLine é uma classe que representa uma linha de número. Quero marcar nele diferentes gamas de números. O método CheckRange deve retornar quais partes do 10-25 I marcado e que eu não fiz. Neste caso, ele deve retornar que 10-20 não está marcada, e que 20-25 é marcada.
Como posso implementar uma aplicação eficaz do presente, que não faria o (n)?
Obrigado.
NOTA: Esta é não lição de casa. Eu preciso disso para os meus personalizados transações de implementação de banco de dados. Estou aprendendo programação somente .
Solução
A solução é simples: Adicione todos os valores destacados a um AVL ou Red-black árvore . Quero dizer, quando você faz AddRange (1,3), inserir os valores inteiros 1,2 e 3 na árvore.
Ao verificar faixas, simplesmente pesquisar os valores de ponto final. Isso leva O (log n) que é consideravelmente mais rápido do que O (n).
Nota:. Inserção e excluir todos take O (log n)
Outras dicas
Use um HashSet
public class NumberLine : HashSet<int>
{
public void AddRange(int start, int end)
{
int count = (end-start)+1;
UnionWith(Enumerable.Range(start, count));
}
public IEnumerable<int> CheckRange(int start, int end)
{
NumberLine other = new NumberLine();
other.AddRange(start, end);
other.IntersectWith(this); // marked
// other.ExceptWith(this); // not marked
return other;
}
}
Não sei o que você queria retornar de CheckRange, ou se você apenas queria para imprimir uma string. Para simples algo como os intervalos especificados, você poderia usar:
public string CheckRange(int start, int end)
{
NumberLine other = new NumberLine();
other.AddRange(start, end);
IEnumerable<int> marked = other.Intersect(this);
IEnumerable<int> notMarked = other.Except(this);
int markedMin = marked.Min();
int markedMax = marked.Max();
int notMarkedMin = notMarked.Min();
int notMarkedMax = notMarked.Max();
string markedString = (markedMin == markedMax)
? markedMin.ToString()
: string.Format("{0} - {1}", markedMin, markedMax);
string notMarkedString = (notMarkedMin == notMarkedMax)
? notMarkedMin.ToString()
: string.Format("{0} - {1}", notMarkedMin, notMarkedMax);
return string.Format("Marked: {0}\r\nNot Marked: {1}", markedString, notMarkedString);
}
Não vai lidar com faixas divididas como:
Marked: 10-15, 20-25
Not Marked: 16-19
Mas deverá fazê-lo no caminho certo.
OK, eu ver onde você está indo com isso.
Lucene faz isso com campos de bits muito grandes.
Say sua gama possível de números vai de 1 a 64, cada um destes números corresponde ao bit nessa posição em um 64 bit int. (No 1 é o bit 0, No 2 é o bit 1).
Se você adicionar um número a um intervalo, você liga que pouco (no seu exemplo você ligar os bits 0 a 4 e 19 a 29).
Agora, para verificar um intervalo de números, você criar outra int de 64 bits com essa gama de bits ligado e executar um bit a bit E (&) nos dois campos de bits. Os bits 1 no resultado é a gama sobrepostas.
Para mais números do que 64, apenas ampliar o número de bits (possivelmente por trabalhar com matrizes ou listas de números inteiros)
Espero que isso ajude:)
Atualizar : Escalabilidade
Vamos dizer que você está trabalhando em arquitetura de 64 bits e você pode e 64 bit inteiros em uma única operação. Idealmente, você usaria 64 ints bits.
Agora, vamos dizer que a sua gama possível de números vai de 1 a 64.000, para isso você precisa 1000 64 ints bits.
Agora vamos olhar para um par de casos de uso
-
Eu quero verificar o intervalo de 70 - 80. Para isso não precisamos de mais 1000 ints para a verificação, apenas um int, e nós sabemos que estamos verificando-la contra o 2º elemento em nossa matriz.
-
Eu quero verificar a gama de 2000 - 10.000 Novamente, nós só precisamos de um int, calcular a sua posição no dia 31 de array (eu acho) e definir os bits em conformidade e comparar. Então você percorrer a lista até que você bateu 10.000 (posição 156?), Comparando ao longo do caminho, e construir você está lista de inteiros de retorno.
Update 2 : Isso não é O (1)
Dependendo do tamanho da faixa de seleção, você pode implementar isso como O (1)
No entanto utilizando este algoritmo o caso geral ainda é O (n)
E se você armazenar-se os intervalos dentro da Reta numérica. Você pode fazer uma mesclagem quando intervalos sobrepostos são adicionadas. CheckRange seguida, pode consultar os intervalos que são armazenados dentro Reta numérica em vez dos elementos individuais. Isto torna-se então O (N) do número de intervalos, em vez de O (N) do número de elementos. Se você faz intervalos de mesclagem quando possível, em seguida, o número de faixas torna-se menor do que o número de chamadas para AddRange.
Veja o exemplo de código abaixo. Eu não sou um especialista em coleções .Net assim uma implementação mais eficiente poderia ser possível, selecionando melhores tipos de coleção. _NT sugeriu armazenar valores em uma estrutura de árvore. Você pode aplicar isto também a faixas e armazená-los pelo número começo. Isso faz com que a pesquisa das faixas mais rápido, tanto ao adicionar e verificar. Na minha implementação atual adicionar faixas até o fim é mais lenta do que a adição de faixas no início. Ao armazenar esta em uma árvore eficiente a complexidade torna-se O (log N) do número de intervalos.
using System;
using System.Collections.Generic;
using System.Collections.ObjectModel;
namespace NumberLine
{
class Program
{
static void Main(string[] args)
{
NumberLine line = new NumberLine();
line.AddRange(1, 5);
line.AddRange(10, 12);
line.AddRange(20, 30);
List<Range> ranges = line.CheckRange(10, 25);
foreach (Range r in ranges)
{
for (int i = r.Start; i <= r.End; i++)
{
Console.WriteLine(i);
}
}
}
}
class Range
{
public int Start;
public int End;
}
class NumberLine
{
private SortedList<int, Range> Ranges = new SortedList<int, Range>();
public void AddRange(int start, int end)
{
if (Ranges.Count == 0)
{
Ranges.Add(start, new Range() { Start = start, End = end });
}
else
{
foreach (Range currentRange in Ranges.Values)
{
if (start <= currentRange.Start)
{
if (end >= currentRange.End)
{
currentRange.Start = start;
currentRange.End = end;
}
else
{
currentRange.Start = start;
}
Ranges.RemoveAt(start);
Ranges.Add(start, currentRange);
break;
}
else
{
if (start <= currentRange.End)
{
currentRange.End = end;
break;
}
else
{
Ranges.Add(start, new Range(){ Start = start, End = end });
break;
}
}
}
}
}
public List<Range> CheckRange(int start, int end)
{
List<Range> result = new List<Range>();
foreach (Range currentRange in Ranges.Values)
{
if (start <= currentRange.End)
{
if (end <= currentRange.End)
{
result.Add(new Range() { Start = currentRange.Start, End = end });
break;
}
else
{
if (start <= currentRange.Start)
{
result.Add(new Range() { Start = currentRange.Start, End = currentRange.End });
}
else
{
result.Add(new Range() { Start = start, End = currentRange.End });
}
}
}
}
return result;
}
}
}
O (n) meios varia com o número de elementos O (1) significa constante de tempo
Eu não posso pensar de um O (1) forma de implementar isso, qualquer um.
Eu não tenho certeza sobre as especificidades do aplicativo, mas minha intuição me diz que isto seria muito melhor tratado no banco de dados, uma vez que é um conjunto operação baseada.
I.E.
Select
*
from numberlines
where
number_group = @group_id
marked = 1
and number >= @min_range
and number <= @max_range
Se você tentou resolver este problema em forma iterativa que ajuda maio. Por exemplo carregar sua classe LineNumber-se com uma lista de intervalos, As faixas têm um começo e int fim neles. Então, em vez de um 'checkrange (a, b)' método, apenas implementar um 'hasNumber (a)' método. Fazer isso simplesmente por looping através de sua lista de faixas e chamar um método 'isInRange (a) na classe Range Portanto, o seu modelo de dados pode ser:
LineNumber {
List<Range> ranges;
aadRange(a,b);
// Loops through all ranges and calls isInRange on each method
isInRange(a);
//just iterates over isInRange from a to b
checkRange(a,b)
}
Range {
Range(a,b)
isInRange(a);
}
Isso vai te dar algum código de trabalho, e uma interface. Pode não ser rápido o suficiente, mas você não sabe disso ainda. Deixar a implementação lucene para mais tarde. :)
Esta não é uma solução completa, mas talvez uma abordagem diferente poderia ajudar a produzir melhores resultados.
