Una implementazione C # della linea numerica

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

  •  06-07-2019
  •  | 
  •  

Domanda 

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

line.CheckRange(10, 25);

NumberLine è una classe che rappresenta una linea numerica. Voglio segnare su di esso diversi intervalli di numeri. Il metodo CheckRange dovrebbe restituire quali parti di 10-25 sono state contrassegnate e quali no. In questo caso dovrebbe restituire che 10-20 non è contrassegnato e che 20-25 è contrassegnato.

Come posso implementare un'attuazione efficace di questo, che non farebbe o (n)?

Grazie.

NOTA: questo è NON compiti a casa. Ne ho bisogno per le mie transazioni di implementazione del database personalizzato. Sto imparando a programmare da solo .

È stato utile?

Soluzione

La soluzione è semplice: aggiungi tutti i valori evidenziati a un AVL o Albero rosso-nero . Voglio dire, quando fai AddRange (1,3), inserisci i valori interi 1,2 e 3 nella struttura.

Quando si controllano gli intervalli, è sufficiente cercare i valori dell'endpoint. Ciò richiede O (log n) che è considerevolmente più veloce di O (n).

Nota: l'inserimento e l'eliminazione di tutti prendono O (registro n) .

Altri suggerimenti

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

Non sono sicuro di ciò che si desidera restituire da CheckRange o se si desidera solo che stampi una stringa. Per qualcosa di semplice come gli intervalli che hai specificato, puoi usare: 

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

Non gestirà intervalli divisi come: 

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

Ma dovrebbe portarti sulla strada giusta.

OK, vedo dove stai andando con questo.

Lucene lo fa con campi di bit molto grandi.

Supponi che il tuo possibile intervallo di numeri vada da 1 a 64, ognuno di questi numeri corrisponde al bit in quella posizione su un int a 64 bit. (Il numero 1 è il bit 0, il numero 2 è il bit 1).

Se aggiungi un numero a un intervallo, attivi quel bit (nel tuo esempio passeresti i bit da 0 a 4 e da 19 a 29).

Ora per controllare un intervallo di numeri, crei un altro int a 64 bit con quell'intervallo di bit attivato ed esegui un And bit per bit (& amp;) sui campi a due bit. Il 1 bit nel risultato è l'intervallo di sovrapposizione.

Per più numeri di 64, basta aumentare il numero di bit (possibilmente lavorando con matrici o liste di numeri interi)

Spero che questo aiuti :)

Aggiorna : scalabilità

Diciamo che stai lavorando su un'architettura a 64 bit e puoi AND AND 64 bit interi in una singola operazione. Idealmente, useresti ints a 64 bit.

Ora, supponiamo che il tuo possibile intervallo di numeri sia compreso tra 1 e 64.000, per questo sono necessari 1000 inte 64 bit.

Ora diamo un'occhiata a un paio di casi d'uso

  1. Voglio controllare l'intervallo tra 70 e 80. Per fare ciò non abbiamo bisogno di altri 1000 ints per il controllo, solo un int e sappiamo che lo stiamo confrontando con il 2 ° elemento nel nostro array.

  2. Voglio controllare l'intervallo 2000 - 10.000 Ancora una volta, abbiamo solo bisogno di un int, calcola la sua posizione nell'array 31st (penso) e imposta i bit di conseguenza e confronta. Quindi fai scorrere l'elenco fino a quando non raggiungi 10.000 (posizione 156?), Confrontando lungo il percorso e costruendo l'elenco di numeri interi da restituire.

Aggiornamento 2 : non è O (1)

A seconda della dimensione dell'intervallo da verificare, è possibile implementarlo come O (1)

Comunque usando questo algoritmo il caso generale è ancora O (n)

Che dire se si memorizzano gli intervalli stessi in NumberLine. È possibile eseguire l'unione quando vengono aggiunti intervalli sovrapposti. CheckRange può quindi interrogare gli intervalli memorizzati in NumberLine anziché i singoli elementi. Questo diventa quindi O (N) nel numero di intervalli, anziché O (N) nel numero di elementi. Se si uniscono intervalli, quando possibile, il numero di intervalli diventa inferiore al numero di chiamate a AddRange.

Vedi l'esempio di codice qui sotto. Non sono un esperto di raccolte .Net, quindi un'implementazione più efficiente potrebbe essere possibile selezionando tipi di raccolta migliori. _NT ha suggerito di memorizzare i valori in una struttura ad albero. Puoi applicarlo anche agli intervalli e memorizzarli in base al numero iniziale. Ciò rende più veloce la ricerca degli intervalli, sia durante l'aggiunta che il controllo. Nella mia attuale implementazione, aggiungere Ranges alla fine è più lento dell'aggiunta di range all'inizio. Quando lo si memorizza in un albero efficiente, la complessità diventa O (log N) nel numero di intervalli. 

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 che varia come il numero di elementi O (1) significa tempo costante

Neanche io riesco a pensare a un modo O (1) per implementarlo.

Non sono sicuro dei dettagli dell'app, ma la mia intuizione mi dice che sarebbe molto meglio gestito nel database, poiché si tratta di un'operazione basata su set.

cioè. 

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

Se hai provato ad affrontare questo problema in modo iterativo, ciò potrebbe essere d'aiuto. Ad esempio, carica la tua classe LineNumber con un elenco di intervalli, tali intervalli hanno un inizio e una fine int in essi. Quindi invece di un metodo 'checkrange (a, b)', implementa semplicemente un metodo 'hasNumber (a)'. Fallo semplicemente scorrendo il tuo elenco di intervalli e chiamando un metodo 'isInRange (a) sulla classe Range Quindi il tuo modello di dati potrebbe essere: 

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

Questo ti darà del codice funzionante e un'interfaccia. Potrebbe non essere abbastanza veloce, ma non lo sai ancora. Lasciare l'implementazione di lucene per dopo. :)

Questa non è una soluzione completa, ma forse un approccio diverso potrebbe aiutare a ottenere risultati migliori.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top