C # Sort 및 OrderBy 비교

C # Sort 및 OrderBy 비교

---

Sort 또는 OrderBy를 사용하여 목록을 정렬 할 수 있습니다. 어느 것이 더 빠릅니까? 둘 다 동일한 알고리즘에서 작동합니까?

List<Person> persons = new List<Person>();
persons.Add(new Person("P005", "Janson"));
persons.Add(new Person("P002", "Aravind"));
persons.Add(new Person("P007", "Kazhal"));

1.

persons.Sort((p1,p2)=>string.Compare(p1.Name,p2.Name,true));

2.

var query = persons.OrderBy(n => n.Name, new NameComparer());

class NameComparer : IComparer<string>
{
    public int Compare(string x,string y)
    {
      return  string.Compare(x, y, true);
    }
}

---

측정하지 않는 이유 :

class Program
{
    class NameComparer : IComparer<string>
    {
        public int Compare(string x, string y)
        {
            return string.Compare(x, y, true);
        }
    }

    class Person
    {
        public Person(string id, string name)
        {
            Id = id;
            Name = name;
        }
        public string Id { get; set; }
        public string Name { get; set; }
    }

    static void Main()
    {
        List<Person> persons = new List<Person>();
        persons.Add(new Person("P005", "Janson"));
        persons.Add(new Person("P002", "Aravind"));
        persons.Add(new Person("P007", "Kazhal"));

        Sort(persons);
        OrderBy(persons);

        const int COUNT = 1000000;
        Stopwatch watch = Stopwatch.StartNew();
        for (int i = 0; i < COUNT; i++)
        {
            Sort(persons);
        }
        watch.Stop();
        Console.WriteLine("Sort: {0}ms", watch.ElapsedMilliseconds);

        watch = Stopwatch.StartNew();
        for (int i = 0; i < COUNT; i++)
        {
            OrderBy(persons);
        }
        watch.Stop();
        Console.WriteLine("OrderBy: {0}ms", watch.ElapsedMilliseconds);
    }

    static void Sort(List<Person> list)
    {
        list.Sort((p1, p2) => string.Compare(p1.Name, p2.Name, true));
    }

    static void OrderBy(List<Person> list)
    {
        var result = list.OrderBy(n => n.Name, new NameComparer()).ToArray();
    }
}

릴리스 모드에서 컴파일하면 내 컴퓨터에서이 프로그램은 다음을 인쇄합니다.

Sort: 1162ms
OrderBy: 1269ms

---

최신 정보:

@Stefan이 제안한대로 큰 목록을 더 적게 정렬 한 결과는 다음과 같습니다.

List<Person> persons = new List<Person>();
for (int i = 0; i < 100000; i++)
{
    persons.Add(new Person("P" + i.ToString(), "Janson" + i.ToString()));
}

Sort(persons);
OrderBy(persons);

const int COUNT = 30;
Stopwatch watch = Stopwatch.StartNew();
for (int i = 0; i < COUNT; i++)
{
    Sort(persons);
}
watch.Stop();
Console.WriteLine("Sort: {0}ms", watch.ElapsedMilliseconds);

watch = Stopwatch.StartNew();
for (int i = 0; i < COUNT; i++)
{
    OrderBy(persons);
}
watch.Stop();
Console.WriteLine("OrderBy: {0}ms", watch.ElapsedMilliseconds);

인쇄물:

Sort: 8965ms
OrderBy: 8460ms

이 시나리오에서는 OrderBy가 더 잘 수행되는 것처럼 보입니다.

---

업데이트 2 :

임의 이름 사용 :

List<Person> persons = new List<Person>();
for (int i = 0; i < 100000; i++)
{
    persons.Add(new Person("P" + i.ToString(), RandomString(5, true)));
}

어디:

private static Random randomSeed = new Random();
public static string RandomString(int size, bool lowerCase)
{
    var sb = new StringBuilder(size);
    int start = (lowerCase) ? 97 : 65;
    for (int i = 0; i < size; i++)
    {
        sb.Append((char)(26 * randomSeed.NextDouble() + start));
    }
    return sb.ToString();
}

수율 :

Sort: 8968ms
OrderBy: 8728ms

여전히 OrderBy가 더 빠릅니다.

---

아니요, 동일한 알고리즘이 아닙니다. 우선 LINQ OrderBy는 안정된 것으로 문서화됩니다 (즉, 두 항목이 동일한 Name경우 원래 순서대로 표시됨).

또한 쿼리를 버퍼링하는지 아니면 여러 번 반복하는지에 따라 달라집니다 (결과를 버퍼링하지 않는 한 LINQ-to-Objects는마다 다시 정렬됩니다 foreach).

OrderBy쿼리의 경우 다음을 사용하고 싶습니다.

OrderBy(n => n.Name, StringComparer.{yourchoice}IgnoreCase);

(용 {yourchoice}의 하나 CurrentCulture, Ordinal또는 InvariantCulture).

List<T>.Sort

이 메서드는 QuickSort 알고리즘을 사용하는 Array.Sort를 사용합니다. 이 구현은 불안정한 정렬을 수행합니다. 즉, 두 요소가 같으면 순서가 유지되지 않을 수 있습니다. 반대로 안정적인 정렬은 동일한 요소의 순서를 유지합니다.

Enumerable.OrderBy

이 방법은 안정적인 정렬을 수행합니다. 즉, 두 요소의 키가 같으면 요소의 순서가 유지됩니다. 반대로 불안정한 정렬은 동일한 키를 가진 요소의 순서를 유지하지 않습니다. 종류; 즉, 두 요소가 같으면 순서가 유지되지 않을 수 있습니다. 반대로 안정적인 정렬은 동일한 요소의 순서를 유지합니다.

---

Darin Dimitrov의 답변은 이미 정렬 된 입력에 직면했을 OrderBy때보 다 약간 더 빠르다 는 것을 보여줍니다 List.Sort. 정렬되지 않은 데이터를 반복적으로 정렬하도록 그의 코드를 수정했으며 OrderBy대부분의 경우 약간 느립니다.

또한 OrderBy테스트는 ToArrayLinq 열거자를 강제로 열거하는 데 사용 하지만 Person[]입력 유형 ( List<Person>) 과 다른 유형 ( )을 반환합니다 . 따라서 ToList대신 사용하여 테스트를 다시 실행하고 ToArray더 큰 차이를 얻었습니다.

Sort: 25175ms
OrderBy: 30259ms
OrderByWithToList: 31458ms

코드:

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;

class Program
{
    class NameComparer : IComparer<string>
    {
        public int Compare(string x, string y)
        {
            return string.Compare(x, y, true);
        }
    }

    class Person
    {
        public Person(string id, string name)
        {
            Id = id;
            Name = name;
        }
        public string Id { get; set; }
        public string Name { get; set; }
        public override string ToString()
        {
            return Id + ": " + Name;
        }
    }

    private static Random randomSeed = new Random();
    public static string RandomString(int size, bool lowerCase)
    {
        var sb = new StringBuilder(size);
        int start = (lowerCase) ? 97 : 65;
        for (int i = 0; i < size; i++)
        {
            sb.Append((char)(26 * randomSeed.NextDouble() + start));
        }
        return sb.ToString();
    }

    private class PersonList : List<Person>
    {
        public PersonList(IEnumerable<Person> persons)
           : base(persons)
        {
        }

        public PersonList()
        {
        }

        public override string ToString()
        {
            var names = Math.Min(Count, 5);
            var builder = new StringBuilder();
            for (var i = 0; i < names; i++)
                builder.Append(this[i]).Append(", ");
            return builder.ToString();
        }
    }

    static void Main()
    {
        var persons = new PersonList();
        for (int i = 0; i < 100000; i++)
        {
            persons.Add(new Person("P" + i.ToString(), RandomString(5, true)));
        } 

        var unsortedPersons = new PersonList(persons);

        const int COUNT = 30;
        Stopwatch watch = new Stopwatch();
        for (int i = 0; i < COUNT; i++)
        {
            watch.Start();
            Sort(persons);
            watch.Stop();
            persons.Clear();
            persons.AddRange(unsortedPersons);
        }
        Console.WriteLine("Sort: {0}ms", watch.ElapsedMilliseconds);

        watch = new Stopwatch();
        for (int i = 0; i < COUNT; i++)
        {
            watch.Start();
            OrderBy(persons);
            watch.Stop();
            persons.Clear();
            persons.AddRange(unsortedPersons);
        }
        Console.WriteLine("OrderBy: {0}ms", watch.ElapsedMilliseconds);

        watch = new Stopwatch();
        for (int i = 0; i < COUNT; i++)
        {
            watch.Start();
            OrderByWithToList(persons);
            watch.Stop();
            persons.Clear();
            persons.AddRange(unsortedPersons);
        }
        Console.WriteLine("OrderByWithToList: {0}ms", watch.ElapsedMilliseconds);
    }

    static void Sort(List<Person> list)
    {
        list.Sort((p1, p2) => string.Compare(p1.Name, p2.Name, true));
    }

    static void OrderBy(List<Person> list)
    {
        var result = list.OrderBy(n => n.Name, new NameComparer()).ToArray();
    }

    static void OrderByWithToList(List<Person> list)
    {
        var result = list.OrderBy(n => n.Name, new NameComparer()).ToList();
    }
}

---

나는 또 다른 차이점주의하는 것이 중요하다고 생각 Sort과 OrderBy:

Person.CalculateSalary()많은 시간이 걸리는 방법 이 있다고 가정합니다 . 큰 목록을 정렬하는 작업보다 더 많을 수 있습니다.

비교

// Option 1
persons.Sort((p1, p2) => Compare(p1.CalculateSalary(), p2.CalculateSalary()));
// Option 2
var query = persons.OrderBy(p => p.CalculateSalary()); 

Option 2 may have superior performance, because it only calls the CalculateSalary method n times, whereas the Sort option might call CalculateSalary up to 2n log(n) times, depending on the sort algorithm's success.

---

In a nutshell :

List/Array Sort() :

• Unstable sort.
• Done in-place.
• Use Introsort/Quicksort.
• Custom comparison is done by providing a comparer. If comparison is expensive, it might be slower than OrderBy() (which allow to use keys, see below).

OrderBy/ThenBy() :

• Stable sort.
• Not in-place.
• Use Quicksort. Quicksort is not a stable sort. Here is the trick : when sorting, if two elements have equal key, it compares their initial order (which has been stored before sorting).
• Allows to use keys (using lambdas) to sort elements on their values (eg : x => x.Id). All keys are extracted first before sorting. This might result in better performance than using Sort() and a custom comparer.

Sources: MDSN, reference source and dotnet/coreclr repository (GitHub).

Some of the statements listed above are based on current .NET framework implementation (4.7.2). It might change in the future.

---

you should calculate the complexity of algorithms used by the methods OrderBy and Sort. QuickSort has a complexity of n (log n) as i remember, where n is the length of the array.

i've searched for orderby's too, but i could not find any information even in msdn library. if you have not any same values and sorting related to only one property, i prefer to use Sort() method; if not than use OrderBy.

---

I just want to add that orderby is way more useful.

Why? Because I can do this:

Dim thisAccountBalances = account.DictOfBalances.Values.ToList
thisAccountBalances.ForEach(Sub(x) x.computeBalanceOtherFactors())
thisAccountBalances=thisAccountBalances.OrderBy(Function(x) x.TotalBalance).tolist
listOfBalances.AddRange(thisAccountBalances)

Why complicated comparer? Just sort based on a field. Here I am sorting based on TotalBalance.

Very easy.

I can't do that with sort. I wonder why. Do fine with orderBy.

As for speed it's always O(n).

참고URL : https://stackoverflow.com/questions/1832684/c-sharp-sort-and-orderby-comparison