Une implémentation C # de Number Line

StackOverflow https://stackoverflow.com/questions/1614137

  •  06-07-2019
  •  | 
  •  

Question 

NumberLine line = new NumberLine();
line.AddRange(1, 5);
line.AddRange(20, 30);

line.CheckRange(10, 25);

NumberLine est une classe qui représente une droite numérique. Je veux marquer différentes plages de chiffres. La méthode CheckRange doit renvoyer les parties de 10-25 que j'ai marquées et celles que je n'ai pas marquées. Dans ce cas, vous devez indiquer que 10-20 n'est pas marqué et que 20-25 est marqué.

Comment puis-je mettre en œuvre une implémentation efficace de ce qui ne ferait pas o (n)?

Merci.

REMARQUE: ceci est un devoir PAS . J'ai besoin de cela pour mes transactions d'implémentation de base de données personnalisées. J'apprends à programmer seul .

Était-ce utile?

La solution

La solution est simple: ajoutez toutes les valeurs en surbrillance à un AVL ou Arbre rouge-noir . Je veux dire quand vous faites AddRange (1,3), insérez les valeurs entières 1,2 et 3 dans l’arborescence.

Lors de la vérification des plages, il suffit de rechercher les valeurs de point final. Cela prend O (log n) , ce qui est considérablement plus rapide que O (n).

Remarque: l'insertion et la suppression de toutes les prises O (journal n) .

Autres conseils

Utilisez un hachage < 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;
    }
}

Vous ne savez pas exactement ce que vous voulez renvoyer de CheckRange ou si vous souhaitez simplement imprimer une chaîne. Pour quelque chose de simple, comme les plages que vous avez spécifiées, vous pouvez utiliser: 

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);
}

Il ne gérera pas les plages divisées telles que: 

Marked: 10-15, 20-25
Not Marked: 16-19

Mais cela devrait vous mettre sur la bonne voie.

OK, je vois où vous allez avec cela.

Lucene le fait avec de très grands champs de bits.

Dites que votre plage de nombres possible va de 1 à 64, chacun de ces nombres correspondant au bit dans cette position sur un int de 64 bits. (N ° 1 est le bit 0, N ° 2 est le bit 1).

Si vous ajoutez un nombre à une plage, vous l'activez (dans votre exemple, vous activez les bits 0 à 4 et 19 à 29).

Maintenant, pour vérifier une plage de nombres, vous créez un autre int de 64 bits avec cette plage de bits activée, puis effectuez une opération binaire And (& amp;) sur les deux champs de bits. Les 1 bits du résultat correspondent à la plage de chevauchement.

Pour plus de nombres que 64, augmentez simplement le nombre de bits (éventuellement en travaillant avec des tableaux ou des listes d'entiers)

J'espère que cela vous aidera:)

Mise à jour : évolutivité

Disons que vous travaillez sur une architecture 64 bits et que vous pouvez ET des entiers 64 bits en une seule opération. Idéalement, vous utiliseriez des bits 64 bits.

Maintenant, disons que votre plage de nombres possible va de 1 à 64 000, pour cela vous avez besoin de 1000 ints 64 bits.

Regardons maintenant quelques cas d'utilisation

  1. Je veux vérifier la plage de 70 - 80. Pour faire cela, nous n'avons pas besoin de 1000 autres ints pour le contrôle, juste d'un entier, et nous savons que nous le vérifions par rapport au 2e élément de notre tableau.

  2. Je souhaite vérifier la plage de 2000 à 10 000 Encore une fois, nous n'avons besoin que d'un seul int, calculons sa position dans le tableau 31 (je pense) et définissons les bits en conséquence et comparons. Ensuite, vous parcourez la liste jusqu'à atteindre 10 000 (position 156?), En comparant en cours de route et en construisant votre liste d'entiers à renvoyer.

Mise à jour 2 : ce n'est pas O (1)

En fonction de la taille de la plage à vérifier, vous pouvez l'implémenter sous la forme O (1)

Cependant, en utilisant cet algorithme, le cas général est toujours O (n)

Et si vous stockiez les plages elles-mêmes dans NumberLine. Vous pouvez effectuer une fusion lorsque des plages superposées sont ajoutées. CheckRange peut alors interroger les plages stockées dans NumberLine au lieu des éléments individuels. Cela devient alors O (N) dans le nombre de plages, au lieu de O (N) dans le nombre d'éléments. Si vous fusionnez des plages lorsque cela est possible, le nombre de plages devient inférieur au nombre d'appels vers AddRange.

Voir l'exemple de code ci-dessous. Je ne suis pas un expert des collections .Net, donc une mise en œuvre plus efficace pourrait être possible en sélectionnant de meilleurs types de collection. _NT a suggéré de stocker les valeurs dans une structure arborescente. Vous pouvez également appliquer cela aux plages et les stocker par le numéro de départ. Cela accélère la recherche dans les plages, lors de l'ajout et de la vérification. Dans mon implémentation actuelle, ajouter des plages à la fin est plus lent que d'ajouter des plages au début. Lors du stockage dans un arbre efficace, la complexité devient O (log N) dans le nombre de plages. 

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) signifie que le nombre d'éléments varie O (1) signifie temps constant

Je ne vois pas non plus de moyen O (1) de mettre cela en œuvre.

Je ne suis pas sûr des spécificités de l'application, mais mon intuition me dit que cela serait beaucoup mieux géré dans la base de données, puisqu'il s'agit d'une opération basée sur un ensemble.

I.E. 

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

Si vous avez essayé de résoudre ce problème de manière itérative, cela peut aider. Par exemple, chargez votre classe LineNumber avec une liste de plages. Ces plages ont un début et une fin int. Ensuite, au lieu d'une méthode 'checkrange (a, b)', implémentez simplement une méthode 'hasNumber (a)'. Faites cela simplement en parcourant votre liste de plages et appelez une méthode 'isInRange (a) de la classe Range. Ainsi, votre modèle de données pourrait être: 

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);
}

Cela vous donnera un code de travail et une interface. Ce n'est peut-être pas assez rapide, mais vous ne le savez pas encore. Laissez l'application Lucene pour plus tard. :)

Ce n'est pas une solution complète, mais peut-être qu'une approche différente pourrait-elle aider à produire de meilleurs résultats.

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top