A C # Implementación de la recta numérica
https://stackoverflow.com/questions/1614137
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
NumberLine line = new NumberLine();
line.AddRange(1, 5);
line.AddRange(20, 30);
line.CheckRange(10, 25);
NumberLine es una clase que representa una recta numérica. Quiero marcar en él diferentes rangos de números. El método CheckRange debería devolver qué partes de 10-25 marqué y cuáles no. En este caso, debería devolver que 10-20 no está marcado y que 20-25 está marcado.
¿Cómo puedo implementar una implementación efectiva de esto, que no funcionaría o (n)?
Gracias.
NOTA: Esta es NO tarea. Necesito esto para mis transacciones de implementación de bases de datos personalizadas. Estoy aprendiendo a programar solo .
Solución
La solución es simple: agregue todos los valores resaltados a un AVL o Árbol rojo-negro . Quiero decir que cuando haces AddRange (1,3), inserta los valores enteros 1,2 y 3 en el árbol.
Al verificar rangos, simplemente busque los valores de punto final. Eso requiere O (log n) que es considerablemente más rápido que O (n).
Nota: la inserción y eliminación de todas las tomas O (log n) .
Otros consejos
Use un HashSet < T > ;:
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;
}
}
No estoy seguro de lo que quería devolver de CheckRange, o si solo quería que imprimiera una cadena. Para algo simple como los rangos que especificó, puede 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);
}
No manejará rangos divididos como:
Marked: 10-15, 20-25
Not Marked: 16-19
Pero debería llevarte por el camino correcto.
OK, veo a dónde vas con esto.
Lucene hace esto con campos de bits muy grandes.
Digamos que su posible rango de números va del 1 al 64, cada uno de estos números corresponde al bit en esa posición en un bit de 64 bits int. (No 1 es el bit 0, No 2 es el bit 1).
Si agrega un número a un rango, activa ese bit (en su ejemplo, activaría los bits 0 a 4 y 19 a 29).
Ahora, para verificar un rango de números, crea otro int de 64 bits con ese rango de bits activado y realiza un bit a nivel Y (& amp;) en los campos de dos bits. El 1 bit en el resultado es el rango superpuesto.
Para más números que 64, simplemente amplíe el número de bits (posiblemente trabajando con matrices o listas de enteros)
Espero que esto ayude :)
Actualización : Escalabilidad
Digamos que está trabajando en una arquitectura de 64 bits y puede Y enteros de 64 bits en una sola operación. Lo ideal sería usar entradas de 64 bits.
Ahora, digamos que su posible rango de números va de 1 a 64,000, para esto necesita 1000 ints de 64 bits.
Ahora veamos un par de casos de uso
-
Quiero verificar el rango de 70 - 80. Para hacer esto, no necesitamos otros 1000 ints para la verificación, solo uno int, y sabemos que lo estamos verificando con el segundo elemento de nuestra matriz.
-
Quiero verificar el rango de 2000 - 10,000 Nuevamente, solo necesitamos un int, calcule su posición en la matriz 31 (creo) y configure los bits en consecuencia y compare. Luego, recorre la lista hasta llegar a 10,000 (¿posición 156?), Compara en el camino y construye su lista de enteros para devolver.
Actualización 2 : Eso no es O (1)
Dependiendo del tamaño del rango a verificar, puede implementar esto como O (1)
Sin embargo, utilizando este algoritmo, el caso general sigue siendo O (n)
¿Qué pasa si almacena los rangos dentro de NumberLine? Puede fusionar cuando se agregan rangos superpuestos. CheckRange puede consultar los rangos almacenados dentro de NumberLine en lugar de los elementos individuales. Esto se convierte en O (N) en el número de rangos, en lugar de O (N) en el número de elementos. Si combina rangos cuando sea posible, el número de rangos se vuelve más pequeño que el número de llamadas a AddRange.
Vea el ejemplo de código a continuación. No soy un experto en colecciones .Net, por lo que podría ser posible una implementación más eficiente seleccionando mejores tipos de colecciones. _NT sugirió almacenar valores en una estructura de árbol. Puede aplicar esto también a rangos y almacenarlos por el número de inicio. Esto hace que la búsqueda de los rangos sea más rápida, tanto al agregar como al verificar. En mi implementación actual, agregar rangos al final es más lento que agregar rangos al principio. Al almacenar esto en un árbol eficiente, la complejidad se convierte en O (log N) en el número de rangos.
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) significa que varía según el número de elementos O (1) significa tiempo constante
Tampoco puedo pensar en una forma O (1) de implementar esto.
No estoy seguro acerca de los detalles de la aplicación, pero mi intuición me dice que esto se manejaría mucho mejor en la base de datos, ya que es una operación basada en conjuntos.
I.E.
Select
*
from numberlines
where
number_group = @group_id
marked = 1
and number >= @min_range
and number <= @max_range
Si trató de abordar este problema de forma iterativa, eso puede ayudar. Por ejemplo, cargue su clase LineNumber con una lista de rangos, esos rangos tienen un comienzo y un final int en ellos. Luego, en lugar de un método 'checkrange (a, b)', simplemente implemente un método 'hasNumber (a)'. Haga esto simplemente recorriendo su lista de rangos y llame a un método 'isInRange (a) en la clase Range para que su modelo de datos sea:
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);
}
Esto le dará un código de trabajo y una interfaz. Puede que no sea lo suficientemente rápido, pero aún no lo sabes. Deje la implementación de lucene para más tarde. :)
Esta no es una solución completa, pero quizás un enfoque diferente podría ayudar a obtener mejores resultados.
