Оптимизировать список <T>. Сортировать (Сравнить) - PullRequest
Новая
       23

Оптимизировать список <T>. Сортировать (Сравнить)

3 голосов
/ 21 апреля 2009

У меня есть список, в котором хранится потеря целых чисел. Мне не нравится, как работает List.Sort () по умолчанию, так как я хочу, чтобы список упорядочивался по размеру фактического int. Пока у меня есть это:

О, и целые числа хранятся в строках, например, "1234". Это то, что я не могу изменить. 

public class IntComparer : IComparer<string>
{
    public int Compare(string x, string y)
    {
        if (x == null)
        {
            if (y == null)
            {
                // If x is null and y is null, they're
                // equal. 
                return 0;
            }
            else
            {
                // If x is null and y is not null, y
                // is greater. 
                return -1;
            }
        }
        else
        {
            // If x is not null...
            //
            if (y == null)
            // ...and y is null, x is greater.
            {
                return 1;
            }
            else
            {
                // ...and y is not null, compare the 
                // lengths of the two strings.
                //
                int xInt = Convert.ToInt32(x);
                int yInt = Convert.ToInt32(y);

                if (x > y)
                {
                    // If the strings are not of equal length,
                    // the longer string is greater.
                    //
                    return 1;
                }
                else if (xInt == yInt)
                {
                    return 0;
                }
                else
                {
                    // If the strings are of equal length,
                    // sort them with ordinary string comparison.


        //
                return -1;
            }
        }
    }
}

Но, насколько мне известно, это пузырьковая сортировка, верно? Что я должен реализовать вместо этого? Quicksort? Кроме того, мне может понадобиться помощь в написании этого.

Да, и мой список содержит не более 2 тысяч элементов, которые хранят числа в строках

Также я называю своего IComparer следующим образом: 

IntComparer intSort = New IntComparer();
List<T>.Sort(intSort);

Ответы [ 6 ]

6 голосов
/ 21 апреля 2009

Предполагая, что вы хотите отсортировать по значению целого числа, хранящегося в виде строки, вы можете просто сделать что-то вроде этого: 

numbers.Sort((x,y) => Int32.Parse(x).CompareTo(Int32.Parse(y)));
4 голосов
/ 21 апреля 2009

Вы должны знать, что компаратор и алгоритм сортировки не определяют друг друга. Таким образом, этот компаратор может использоваться как с пузырьковой сортировкой, так и с быстрой сортировкой, heapsort или любым другим алгоритмом сортировки. Встроенный алгоритм сортировки List.Sort является быстрой сортировкой, в соответствии с MSDN.

1 голос
/ 21 апреля 2009

Я думаю, вы должны сначала преобразовать string s во временный список int, так как другой код здесь (пока) преобразует строки снова и снова, для каждого сравнения. (Вы также можете использовать пустые целые, если важно хранить null s). После этого вы сортируете список и при необходимости конвертируете обратно в строки.

1 голос
/ 21 апреля 2009

Нет, алгоритм, используемый для сортировки списка, - QuickSort, поэтому вы не можете легко улучшить его.

List<T>.Sort метод

Этот метод использует Array.Sort, который использует алгоритм быстрой сортировки.

Я выполнил сравнение: 

public class IntComparer : IComparer<string> {

    private static int ParseInt32(string text) {
        long value = 0;
        foreach (char c in text) {
                if (c >= '0' && c <= '9') {
                value = value * 10 + c - '0';
            } else {
                throw new FormatException();
            }
        }
        if (value > int.MaxValue) throw new OverflowException();
        return (int)value;
    }


    public int Compare(string x, string y) {
        if (x == null) {
            if (y == null) {
                // If x is null and y is null, they're
                // equal. 
                return 0;
            } else {
                // If x is null and y is not null, y
                // is greater. 
                return -1;
            }
        } else {
            // If x is not null...
            //
            if (y == null) {
                // ...and y is null, x is greater.
                return 1;
            } else {
                // ...and y is not null, compare the 
                // lengths of the two strings.
                //
                if (x.Length != y.Length) {
                    // If the strings are not of equal length,
                    // the longer string is greater.
                    return x.Length - y.Length;
                } else {
                    // compare numerically
                    int xInt = ParseInt32(x);
                    int yInt = ParseInt32(y);
                    return xInt - yInt;
                }
            }
        }
    }

}

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

1 голос
/ 21 апреля 2009

Итак, у вас есть список строк, представляющих целые числа в качестве входных данных, и вы хотите отсортированный список целых чисел в качестве выходных данных?

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

с использованием системы; 

using System.Collections.Generic;
using System.Linq;

namespace ConsoleApplication6
{
    internal class Program
    {
        private static void Main(string[] args)
        {
            var unsortedListOfStringsAsInts = new List<string> {"1234", "2345", "7", "9"};
            var sortedListOfInts = unsortedListOfStringsAsInts.Select(x => int.Parse(x)).OrderBy(x => x).ToList();

            foreach (var i in sortedListOfInts)
                Console.WriteLine(i);
        }
    }
}

И я не буду беспокоиться об оптимизации вашего алгоритма сортировки вручную с помощью 2 тысяч элементов - это не так уж много элементов для сортировки, если только это не «все», что делает ваше приложение.

0 голосов
/ 21 апреля 2009

Вот краткий пример, если вы используете проект .net 3.5 (Linq) 

using System.Linq;
using System.Collections.Generic;

List<string> unorderedList = List<string>();
list.Add("3");
list.Add("5");
list.Add("2");
list.Add("10");
list.Add("-6");
list.Add("7");

List<string> orderedList = list.OrderBy(x => int.Parse(x)).ToList();
...