A C # Реализация номерной линии

Question

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)?

Спасибо.

ПРИМЕЧАНИЕ: Это НЕ домашнее задание. Мне нужно это для моих пользовательских транзакций реализации базы данных. Я учусь программированию один .

Answer 1

Решение простое: добавьте все выделенные значения в дерево AVL или Красно-черный . Я имею в виду, когда вы делаете AddRange (1,3), вставьте целые значения 1,2 и 3 в дерево.

При проверке диапазонов просто ищите значения конечной точки. Это займет O (log n) , что на значительно быстрее , чем O (n).

Примечание: вставка и удаление всех дублей O (log n) .

Answer 2

Что делать, если вы храните сами диапазоны в пределах 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;
        }
    }

}

Answer 3

Используйте 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;
    }
}

Не уверен, что вы хотите вернуть из 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

Но это должно вывести вас на правильный путь.

Answer 4

Хорошо, я вижу, куда вы идете с этим.

Lucene делает это с очень большими битовыми полями.

Допустим, ваш возможный диапазон чисел варьируется от 1 до 64, каждое из этих чисел соответствует биту в этой позиции в 64-битном int. (№ 1 - это бит 0, № 2 - это бит 1).

Если вы добавите число в диапазон, вы включите этот бит (в вашем примере вы включите биты с 0 по 4 и с 19 по 29).

Теперь, чтобы проверить диапазон чисел, вы создаете еще одно 64-битное целое число с включенным диапазоном битов и выполняете побитовое И (&) для двух битовых полей. 1 бит в результате - это перекрывающийся диапазон.

Если число больше 64, просто увеличьте количество бит (возможно, работая с массивами или списками целых чисел)

Надеюсь, это поможет:)

Обновление : Масштабируемость

Допустим, вы работаете над 64-битной архитектурой, и вы можете И 64-битные целые числа за одну операцию. В идеале вы должны использовать 64-битные целые числа.

Теперь допустим, что ваш возможный диапазон чисел составляет от 1 до 64 000, для этого вам нужно 1000 64-битных целых.

Теперь давайте рассмотрим пару вариантов использования

1. Я хочу проверить диапазон 70 - 80. Для этого нам не нужны еще 1000 int для проверки, только одно int, и мы знаем, что проверяем его по второму элементу в нашем массиве.

2. Я хочу проверить диапазон 2000 - 10000 Опять же, нам нужно только одно целое, вычислить его позицию в массиве 31-го (я думаю) и соответственно установить биты и сравнить. Затем вы перебираете список, пока не достигнете 10000 (позиция 156?), Сравниваясь по пути и создавая список целых чисел, которые нужно вернуть.

Обновление 2 : Это не O (1)

В зависимости от размера проверяемого диапазона, вы можете реализовать это как O (1)

Однако при использовании этого алгоритма общий случай все еще O (n)

Answer 5

Если вы пытались решить эту проблему многократно, это может помочь. Например, загрузите ваш класс 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 на потом. :)

Это не полное решение, но, возможно, другой подход может помочь получить лучшие результаты.

Answer 6

Я не уверен насчет специфики приложения, но моя интуиция подсказывает мне, что это будет лучше обрабатываться в базе данных, поскольку это операция на основе множеств.

И.Е.

Select
*
from numberlines
where 
number_group = @group_id
marked = 1
and number >= @min_range
and number <= @max_range

Answer 7

O (n) означает, варьируется в зависимости от количества элементов O (1) означает постоянное время

Я тоже не могу придумать O (1) способ реализации этого.