Есть ли C# эквивалент C++ std :: partial_sort?

Question

Я пытаюсь реализовать алгоритм поискового вызова для набора данных, отсортированного по многим критериям. К сожалению, хотя некоторые из этих критериев могут быть реализованы на уровне базы данных, некоторые из них должны выполняться на уровне приложения (мы должны интегрироваться с другим источником данных). У нас есть запрос подкачки (на самом деле бесконечный прокрутка) и вы ищете способ минимизировать боль при сортировке всего набора данных на уровне приложения с каждым вызовом поискового вызова.

Каков наилучший способ сделать частичный вид, только сортировка части списка, которую необходимо отсортировать? Существует ли эквивалент функции C++ std::partial_sort, доступной в библиотеках .NET? Как мне решить эту проблему?

EDIT: Вот пример того, что я иду:

Допустим, мне нужно получить элементы 21-40 из множества 1000 элементов, согласно некоторым критериям сортировки. Чтобы ускорить сортировку, и поскольку я все равно должен проходить через весь набор данных (это веб-сервис через HTTP, который является апатридом), мне не нужен весь набор данных, заказанный. Мне нужно только правильно настроить элементы 21-40. Достаточно создать 3 раздела: Элементы 1-20, unsorted (но все меньше элемента 21); элементы 21-40, отсортировано; и элементы 41-1000, несортированы (но все больше элемента 40).

Answer 1

OK. Вот что я хотел бы попробовать на основе того, что вы сказали в ответ на мой комментарий.

Я хочу, чтобы иметь возможность сказать «четвёртую через 6» и получить что-то вроде: 3, 2, 1 (несортированный, но все меньше правильного 4-го элемента); 4, 5, 6 (отсортировано и в том же месте они будут для отсортированного списка); 8, 7, 9 (несортированный, но все больше, чем правильный 6-й элемент).

Позволяет добавить 10 в наш список, чтобы сделать его проще: 10, 9, 8, 7, 6, 5, 4, 3, 2, 1.

Итак, что вы можете сделать, это использовать quick select algorithm, чтобы найти i ^th и k ^th элементов. В вашем случае выше i равно 4, а k равно 6. Это, конечно же, вернет значения 4 и 6. Это займет два прохода через ваш список. Итак, до сих пор среда исполнения O (2n) = O (n). Разумеется, следующая часть проста. У нас есть нижняя и верхняя границы данных, о которых мы заботимся. Все, что нам нужно сделать, это сделать еще один проход через наш список, ища любой элемент, который находится между нашими верхними и нижними границами. Если мы найдем такой элемент, мы переместим его в новый список. Наконец, мы сортируем наш список, который содержит только i ^th через k ^th элементов, которые нас волнуют.

Таким образом, я считаю, что общее время выполнения заканчивается время O (N) + O ((ки) Л.Г. (ки))

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

Вы можете использовать List<T>.Sort(int, int, IComparer<T>):

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

Answer 3

Array.Sort() имеет перегрузку, которая принимает index и length аргументы, что позволяет сортировать подмножество массива. То же самое существует для List.

Вы не можете отсортировать IEnumerable напрямую, конечно.