تنفيذ خط الأعداد في 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 في الشجرة.

عند التحقق من النطاقات، ما عليك سوى البحث عن قيم نقطة النهاية.أن يأخذ يا(سجل ن) الذي أسرع بكثير من على).

ملحوظة:الإدراج وحذف كافة اتخاذ يا(سجل ن).

Answer 2

استخدم 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

ولكن يجب أن تضعك على المسار الصحيح.

Answer 3

حسنًا، أرى إلى أين أنت ذاهب بهذا.

لوسين يفعل هذا مع حقول بت كبيرة جدًا.

لنفترض أن النطاق المحتمل للأرقام يتراوح من 1 إلى 64، وكل رقم من هذه الأرقام يتوافق مع البت الموجود في هذا الموضع على 64 بت.(لا يوجد 1 هو البت 0، ولا 2 هو البت 1).

إذا قمت بإضافة رقم إلى نطاق، فإنك تقوم بتشغيل هذا البت (في المثال الخاص بك، يمكنك تشغيل البتات من 0 إلى 4 ومن 19 إلى 29).

الآن للتحقق من نطاق من الأرقام، يمكنك إنشاء عدد صحيح 64 بت آخر مع تشغيل نطاق البتات هذا، وإجراء عملية "و" (&) على الحقلين المكونين من البتات.البتات 1 في النتيجة هي النطاق المتداخل.

بالنسبة للأعداد الأكبر من 64، ما عليك سوى زيادة عدد البتات (ربما من خلال العمل مع المصفوفات أو قوائم الأعداد الصحيحة)

أتمنى أن يساعدك هذا :)

تحديث:قابلية التوسع

لنفترض أنك تعمل على بنية 64 بت ويمكنك استخدام أعداد صحيحة 64 بت في عملية واحدة.من الأفضل أن تستخدم 64 بت ints.

الآن، لنفترض أن النطاق المحتمل للأرقام يمتد من 1 إلى 64000، ولهذا تحتاج إلى 1000 64 بت.

الآن دعونا نلقي نظرة على بعض حالات الاستخدام

1. أريد التحقق من النطاق من 70 إلى 80.للقيام بذلك، لا نحتاج إلى 1000 int أخرى للتحقق، فقط int واحد، ونحن نعلم أننا نتحقق منه مقابل العنصر الثاني في مصفوفتنا.

2. ثم تقوم بالتكرار عبر القائمة حتى تصل إلى 10000 (الموضع 156؟)، والمقارنة على طول الطريق، وإنشاء قائمة بالأعداد الصحيحة التي يجب إرجاعها.

تحديث 2:هذا ليس يا (1)

اعتمادًا على حجم النطاق المراد التحقق منه، يمكنك تنفيذ ذلك كـ O(1)

ولكن باستخدام هذه الخوارزمية فإن الحالة العامة لا تزال O(n)

Answer 4

ماذا لو قمت بتخزين النطاقات نفسها داخل 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 5

O(n) means varies as the number of elements O(1) means constant time

لا أستطيع التفكير في طريقة O(1) لتنفيذ ذلك أيضًا.

Answer 6

لست متأكدًا من تفاصيل التطبيق، لكن حدسي يخبرني أنه سيكون من الأفضل التعامل مع هذا الأمر في قاعدة البيانات، نظرًا لأنها عملية قائمة على المجموعة.

أي.

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

Answer 7

إذا حاولت معالجة هذه المشكلة بشكل متكرر فقد يساعدك ذلك.على سبيل المثال، قم بتحميل فئة LineNumber الخاصة بك بقائمة النطاقات، وهذه النطاقات لها بداية ونهاية فيها.ثم بدلاً من طريقة "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);
}

سيوفر لك هذا بعض أكواد العمل والواجهة.قد لا يكون الأمر سريعًا بما فيه الكفاية، لكنك لا تعرف ذلك بعد.اترك تطبيق لوسين لوقت لاحق.:)

وهذا ليس حلاً كاملاً، ولكن ربما يساعد اتباع نهج مختلف في تحقيق نتائج أفضل.