Как отсортировать список <String>в порядке убывания как можно быстрее

Question

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

Строки выглядят так, как показано ниже, где я добавляю 100 000 элементов в цикле:

-0,awb/aje - ddfas/asa - asoo/qwa
-1,awb/aje - ddfas/asa - asoo/qwa
-2,awb/aje - ddfas/asa - asoo/qwa

Поэтому я хочу отсортировать в порядке убывания первого аргумента с разделителями-запятыми, который имеет двойное значение, например: -0, -1, -2 и т. Д.

Я испробовал 3 подхода, где на самом деле только подход 1сортирует правильно.Подходы 2 и 3 сортируются не совсем корректно в порядке убывания чисел.

Таким образом, подход 1, который сортирует правильно, делает это за 30 секунд.Дело в том, что у меня будет около 3 миллионов элементов, а не только 100 000, как в этом примере, что затем должно занять не менее 900 секунд или более.

Мой вопрос заключается в том, как правильно отсортировать 100 000 или более 3 миллионов элементов.Быстро настолько, насколько это возможно? Запуск: sortingtestBENCHMARKS () покажет результаты

    public void sortingtestBENCHMARKS()
    {
        List<String> dataLIST = new List<String>(); List<String> sortedLIST = new List<String>(); String resultString = ""; int index = 0;
        DateTime starttime = DateTime.Now; DateTime endtime = DateTime.Now; TimeSpan span = new TimeSpan();
        for (double i = 0; i < 100000; i+=1)
        {
            dataLIST.Add("-" + i + "," + "awb/aje" + " - " + "ddfas/asa" + " - " + "asoo/qwa");
        }
        dataLIST = shuffle(dataLIST);

        /*--------------------------------------------------------------------------*/
        //APPROACH 1: 30 seconds (Sorts correctly in descending order)
        starttime = DateTime.Now;
        dataLIST = sortLIST(dataLIST);
        endtime = DateTime.Now;
        span = endtime - starttime;
        resultString = "Approach 1: " + span.TotalSeconds;
        dataLIST = shuffle(dataLIST);

        /*--------------------------------------------------------------------------*/
        //APPROACH 2: 55 seconds (Sorts INcorrectly in descending order)
        starttime = DateTime.Now;
        for (int i = 0; i < dataLIST.Count; i++) 
        {
            index = sortedLIST.BinarySearch(dataLIST[i]);
            if (index < 0)
            {
                sortedLIST.Insert(~index, dataLIST[i]);
            }
        }
        endtime = DateTime.Now;
        span = endtime - starttime;
        resultString = resultString + "\nApproach 2: " + span.TotalSeconds;

        /*--------------------------------------------------------------------------*/
        //APPROACH 3: 2 seconds (Sorts INcorrectly in descending order)
        starttime = DateTime.Now;
        dataLIST.Sort(); //1.6 seconds
        endtime = DateTime.Now;
        span = endtime - starttime;
        resultString = resultString + "\nApproach 3: " + span.TotalSeconds;

        /*--------------------------------------------------------------------------*/

        MessageBox.Show("Elapsed Times:\n\n" + resultString);
    }
    List<String> sortLIST(List<String> theLIST)
    {
        System.Threading.Thread.CurrentThread.CurrentCulture = new System.Globalization.CultureInfo("en-US");
        theLIST.Sort(new Comparison<String>((a, b) =>
        {
            int result = 0;
            double ad = 0;
            double bd = 0;
            NumberFormatInfo provider = new NumberFormatInfo();
            provider.NumberGroupSeparator = ",";
            provider.NumberDecimalSeparator = ".";
            provider.NumberGroupSizes = new int[] { 5 };
            ad = Convert.ToDouble(a.Replace("a", "").Replace("c", "").Split(',')[0], provider);
            bd = Convert.ToDouble(b.Replace("a", "").Replace("c", "").Split(',')[0], provider);
            if (ad < bd)
            {
                result = 1;
            }
            else if (ad > bd)
            {
                result = -1;
            }
            return result;
        }));
        return theLIST;
    }
    List<String> shuffle(List<String> list)
    {
        var randomizedList = new List<String>();
        var rnd = new Random();
        while (list.Count != 0)
        {
            var index = rnd.Next(0, list.Count);
            randomizedList.Add(list[index]);
            list.RemoveAt(index);
        }
        return randomizedList;
    }

Answer 1

Вы должны оптимизировать внутренний цикл так сильно, как только можете, потому что большая часть времени обработки тратится там.Я предлагаю реализовать строковый токенизатор самостоятельно, поскольку вам нужен только первый токен, а строка очень однородна.Вторая возможная оптимизация - умножение всего числа на -1, поэтому сортировка списка в обратном порядке проста.Примерно так:

private static double getNumberFromString(String s){
    int posFirstComma=0;
    for (; posFirstComma<s.length() && s.charAt(posFirstComma)!=','; posFirstComma++);
    return Convert.toDouble(s.subString(0, posFirstComma)*(-1);
}
myData.sort(new Comparision<String>((a,b)=> getNumberFromString(a)-getNumberFromString(b));

Лично я не буду касаться алгоритма сортировки в самой библиотеке, потому что он уже полностью оптимизирован.Просто оптимизируйте все в цикле for.

Answer 2

Мне кажется, что вы можете просто разбить вашу строку на символ ,, убрать - с первого элемента в массиве разбиения, а затем использовать OrderBy для этого результата:

var sorted = dataLIST.OrderBy(i => double.Parse(i.Split(',')[0].TrimStart('-'))).ToList();

Я сделал копию вашего кода, а затем использовал один из ваших рабочих методов и сравнил его с запуском OrderBy в методе разделения строк, упомянутом выше.Метод OrderBy / Split работает чуть более чем в 30 раз.

public static void sortingtestBENCHMARKS()
{
    var dataLIST = new List<string>();

    // Create the list
    for (var i = 0; i < 100000; i ++)
    {
        dataLIST.Add("-" + i + "," + "awb/aje" + " - " + "ddfas/asa" + " - " + "asoo/qwa");
    }

    // Shuffle the list
    dataLIST = shuffle(dataLIST);

    // Make two copies of the same shuffled list
    var copy1 = dataLIST.ToList();
    var copy2 = dataLIST.ToList();

    // Use a stopwatch for measuring time when benchmark testing
    var stopwatch = new Stopwatch();

    /*--------------------------------------------------------------------------*/
    //APPROACH 1: 2.83 seconds (Sorts correctly in descending order)
    stopwatch.Start();
    copy2 = sortLIST(copy2);
    stopwatch.Stop();
    Console.WriteLine($"sortLIST method: {stopwatch.Elapsed.TotalSeconds} seconds");

    /*--------------------------------------------------------------------------*/
    //APPROACH 2: 0.09 seconds (Sorts correctly in descending order)
    stopwatch.Restart();
    copy1 = copy1.OrderBy(i => double.Parse(i.Split(',')[0].TrimStart('-'))).ToList();
    stopwatch.Stop();
    Console.WriteLine($"OrderBy method:  {stopwatch.Elapsed.TotalSeconds} seconds");

    // Ensure that the lists are sorted identically
    Console.WriteLine($"Lists are the same: {copy1.SequenceEqual(copy2)}");
}

Выход

Answer 3

var sortedList = theLIST.OrderByDescending(s=>s);