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

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

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

EDIT: Вот пример того, что я собираюсь:

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

Ответ 1

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

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

Давайте добавим 10 к нашему списку, чтобы упростить его: 10, 9, 8, 7, 6, 5, 4, 3, 2, 1.

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

Итак, я считаю, что общая продолжительность выполнения заканчивается O (N) + O ((k-i) lg (k-i))

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

Ответ 2

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

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

Ответ 3

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

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