Esiste un equivalente C# a C++ std :: partial_sort?

Question

Sto cercando di implementare un algoritmo di paging per un set di dati ordinabile tramite molti criteri. Sfortunatamente, mentre alcuni di questi criteri possono essere implementati a livello di database, alcuni devono essere eseguiti a livello di app (dobbiamo integrarli con un'altra fonte di dati). Abbiamo un requisito di cercapersone (effettivamente infinito) e stiamo cercando un modo per ridurre al minimo il dolore di ordinare l'intero set di dati a livello di app con ogni chiamata cercapersone.

Qual è il modo migliore per eseguire un ordinamento parziale, solo per ordinare la parte dell'elenco che deve assolutamente essere ordinata? Esiste un equivalente alla funzione di C++ disponibile nelle librerie .NET? Come dovrei andare a risolvere questo problema?

EDIT: Ecco un esempio di quello che sto andando per:

Diciamo che ho bisogno di ottenere elementi 21-40 di un elemento di set 1000, secondo alcuni criteri di ordinamento. Per accelerare l'ordinamento e poiché devo passare attraverso l'intero set di dati ogni volta (questo è un servizio web su HTTP, che è senza stato), non ho bisogno dell'intero set di dati ordinato. Ho solo bisogno degli elementi 21-40 per essere correttamente ordinati. È sufficiente creare 3 partizioni: Elementi 1-20, non ordinati (ma tutti inferiori all'elemento 21); elementi 21-40, ordinati; ed elementi 41-1000, non ordinati (ma tutti maggiori dell'elemento 40).

Answer 1

OK. Ecco cosa proverei in base a ciò che hai detto in risposta al mio commento.

Voglio essere in grado di dire "4th al 6" e ottenere qualcosa di simile: 3, 2, 1 (non differenziati, ma tutti a meno di una corretta 4 ° elemento); 4, 5, 6 (ordinati e nello stesso posto in cui si troverebbero per una lista ordinata); 8, 7, 9 (non ordinati, ma tutti più grandi del 6 ° elemento).

aggiungiamo 10 alla nostra lista per rendere più facile: 10, 9, 8, 7, 6, 5, 4, 3, 2, 1.

Allora, che cosa si potrebbe fare è utilizzare il quick select algorithm per trovare il i ^th e k ^th elementi. Nel tuo caso sopra i è 4 e k è 6. Ciò ovviamente restituirà i valori 4 e 6. Questo richiederà due passaggi nella tua lista. Quindi, finora il tempo di esecuzione è O (2n) = O (n). La prossima parte è facile, ovviamente. Abbiamo limiti inferiori e superiori sui dati che ci interessano. Tutto quello che dobbiamo fare è fare un altro passaggio attraverso la nostra lista alla ricerca di qualsiasi elemento che si trova tra i nostri limiti superiore e inferiore. Se troviamo un elemento del genere lo gettiamo in una nuova lista. Infine, ordiniamo la nostra lista che contiene solo l'i ^th tramite k ^o elementi che ci interessano.

Quindi, credo che il tempo di esecuzione totale finisce per essere O (N) + O ((ki) lg (ki))

static void Main(string[] args) { 
    //create an array of 10 million items that are randomly ordered 
    var list = Enumerable.Range(1, 10000000).OrderBy(x => Guid.NewGuid()).ToList(); 

    var sw = Stopwatch.StartNew(); 
    var slowOrder = list.OrderBy(x => x).Skip(10).Take(10).ToList(); 
    sw.Stop(); 
    Console.WriteLine(sw.ElapsedMilliseconds); 
    //Took ~8 seconds on my machine 

    sw.Restart(); 
    var smallVal = Quickselect(list, 11); 
    var largeVal = Quickselect(list, 20); 
    var elements = list.Where(el => el >= smallVal && el <= largeVal).OrderBy(el => el); 
    Console.WriteLine(sw.ElapsedMilliseconds); 
    //Took ~1 second on my machine 
} 

public static T Quickselect<T>(IList<T> list , int k) where T : IComparable { 
    Random rand = new Random(); 
    int r = rand.Next(0, list.Count); 
    T pivot = list[r]; 
    List<T> smaller = new List<T>(); 
    List<T> larger = new List<T>(); 
    foreach (T element in list) { 
     var comparison = element.CompareTo(pivot); 
     if (comparison == -1) { 
      smaller.Add(element); 
     } 
     else if (comparison == 1) { 
      larger.Add(element); 
     } 
    } 

    if (k <= smaller.Count) { 
     return Quickselect(smaller, k); 
    } 
    else if (k > list.Count - larger.Count) { 
     return Quickselect(larger, k - (list.Count - larger.Count)); 
    } 
    else { 
     return pivot; 
    } 
} 

Answer 2

È possibile utilizzare List<T>.Sort(int, int, IComparer<T>):

inputList.Sort(startIndex, count, Comparer<T>.Default); 

Answer 3

Array.Sort() ha un sovraccarico che accetta index e length argomenti che ti permette di ordinare un sottoinsieme di una matrice. Lo stesso esiste per List.

Non è possibile ordinare uno IEnumerable direttamente, ovviamente.