Реализация числовой строки на C #
https://stackoverflow.com/questions/1614137
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
NumberLine line = new NumberLine();
line.AddRange(1, 5);
line.AddRange(20, 30);
line.CheckRange(10, 25);
NumberLine это класс, который представляет числовую строку.Я хочу отметить на нем разные диапазоны чисел.Тот Самый CheckRange метод должен возвращать, какие части из 10-25 Я пометил, а чего не делал.В этом случае он должен вернуть это 10-20 не помечен, и что 20-25 помечен.
Как я могу реализовать эффективную реализацию этого, которая не выполняла бы o (n)?
Спасибо.
ПРИМЕЧАНИЕ: Это НЕТ домашнее задание.Мне это нужно для транзакций реализации моей пользовательской базы данных.Я учусь программированию один.
Решение
Решение простое: добавьте все выделенные значения в AVL или Красно-черное дерево . Я имею в виду, когда вы делаете AddRange (1,3), вставьте целые значения 1,2 и 3 в дерево.
При проверке диапазонов просто ищите значения конечной точки. Это займет O (log n) , что значительно быстрее , чем O (n).
Примечание. Вставка и удаление всех дублей O (log n) .
Другие советы
Используйте 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;
}
}
Не уверен, что вы хотите вернуть из CheckRange или просто хотите, чтобы он напечатал строку. Для чего-то простого, например, указанных вами диапазонов, вы можете использовать:
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);
}
Он не будет обрабатывать разделенные диапазоны, такие как:
Marked: 10-15, 20-25
Not Marked: 16-19
Но это должно вывести вас на правильный путь.
Хорошо, я понимаю, куда ты идешь с этим.
Lucene делает это с очень большими битовыми полями.
Скажем, ваш возможный диапазон чисел варьируется от 1 до 64, каждое из этих чисел соответствует биту в этой позиции в 64-битном целом. (№ 1 - это бит 0, № 2 - это бит 1).
Если вы добавите число в диапазон, вы включите этот бит (в вашем примере вы включите биты с 0 по 4 и с 19 по 29).
Теперь, чтобы проверить диапазон чисел, вы создаете еще одно 64-битное целое число с включенным диапазоном битов и выполняете битовую And (& amp;) для двух битовых полей. 1 бит в результате - это перекрывающийся диапазон.
Если число больше 64, просто увеличьте количество бит (возможно, работая с массивами или списками целых чисел)
Надеюсь, это поможет:)
Обновление : масштабируемость
Допустим, вы работаете над 64-битной архитектурой, и вы можете И 64-битные целые числа за одну операцию. В идеале вы должны использовать 64-битные целые.
Допустим, допустимый диапазон номеров составляет от 1 до 64 000, для этого вам потребуется 1000 64-битных целых.
Теперь давайте рассмотрим пару вариантов использования
<Ол>Я хочу проверить диапазон от 70 до 80. Для этого нам не нужны еще 1000 int для проверки, только одно int, и мы знаем, что проверяем его по второму элементу в нашем массиве.
Я хочу проверить диапазон 2000 - 10000 Опять же, нам нужно только одно целое, вычислить его позицию в массиве 31-го (я думаю) и соответственно установить биты и сравнить. Затем вы перебираете список до тех пор, пока не достигнете 10000 (позиция 156?), Сравниваясь по пути и создавая список целых чисел, которые нужно вернуть.
Обновление 2 . Это не O (1)
В зависимости от размера проверяемого диапазона вы можете реализовать это как O (1)
Однако, используя этот алгоритм, общий случай все еще O (n)
Что делать, если вы храните сами диапазоны в пределах NumberLine. Вы можете выполнить слияние при добавлении перекрывающихся диапазонов. Затем CheckRange может запрашивать диапазоны, которые хранятся внутри NumberLine, а не отдельных элементов. Затем он становится O (N) в количестве диапазонов, а не O (N) в количестве элементов. Если вы делаете слияние диапазонов, когда это возможно, то число диапазонов становится меньше, чем количество вызовов AddRange.
См. пример кода ниже. Я не эксперт по коллекциям .Net, поэтому возможна более эффективная реализация, если выбрать лучшие типы коллекций. _NT предложили хранить значения в древовидной структуре. Вы можете применить это также к диапазонам и сохранить их по начальному номеру. Это ускоряет поиск диапазонов как при добавлении, так и при проверке. В моей текущей реализации добавление диапазонов в конец происходит медленнее, чем добавление диапазонов в начале. При сохранении этого в эффективном дереве сложность становится равной O (log N) в количестве диапазонов.
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) означает, что изменяется как количество элементов O (1) означает постоянное время
Я тоже не могу придумать O (1) способ реализации этого.
Я не уверен в специфике приложения, но моя интуиция подсказывает мне, что это было бы намного лучше обработано в базе данных, поскольку это операция, основанная на множестве.
Т.Е.
Select
*
from numberlines
where
number_group = @group_id
marked = 1
and number >= @min_range
and number <= @max_range
Если вы пытались решить эту проблему многократно, это может помочь. Например, загрузите ваш класс LineNumber со списком диапазонов. В этих диапазонах есть начало и конец int. Затем вместо метода checkrange (a, b) просто реализуйте метод hasNumber (a). Сделайте это просто, просматривая список диапазонов и вызывая метод isInRange (a) в классе Range. Таким образом, ваша модель данных может быть:
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);
}
Это даст вам рабочий код и интерфейс. Это может быть недостаточно быстро, но вы еще этого не знаете. Оставьте реализацию lucene на потом. :)
Это не полное решение, но, возможно, другой подход может помочь получить лучшие результаты.
