вторник, 7 апреля 2009 г.

Экономим байты исходного кода. Реализация алгоритма QSort

Однажды, когда я проходил трейнинг по C#, нам было задано домашние задание, одним из пунктов которого было реализовать алгоритм быстрой сортировки(QSort) на C#. По достаточно хорошему описанию алгоритма на страницах Википедии, я все-таки реализовал алгоритм по-своему, но решил продолжить поиск наиболее «короткого» решении. И я его нашел. Следующий код написан на языке Perl, и это то, к чему нужно стремиться:

sub qsort {
return () if !@_;
return (qsort(grep { $_ < $_[0] } (@_)[1..$#_]), $_[0],
qsort(grep { $_ >= $_[0] } (@_)[1..$#_]));
}


Превосходно! Реализация алгоритма наглядна и прекрасно запоминается. Я попытался переписать исходный код с Perl на C#, и вот что у меня получилось:

public static List<T> QSort<T>(List<T> sourceArray)
where T : IComparable<T>
{
if ( sourceArray.Count == 0 )
{
return new List<T>();
}
T firstItem = sourceArray[0];
sourceArray.RemoveAt(0);

List<T> greaterList = new List<T>();
List<T> lessList = new List<T>();
List<T> sortedArray = new List<T>();


foreach (T item in sourceArray)
{
if (item.CompareTo(firstItem) < 0) lessList.Add(item);
}

foreach (T item in sourceArray)
{
if (item.CompareTo(firstItem) >= 0) greaterList.Add(item);
}

sortedArray.AddRange(QSort(lessList));
sortedArray.Add(firstItem);
sortedArray.AddRange(QSort(greaterList));

return sortedArray;
}


Вроде бы ничего, по крайней мере, задание сдал. Но, вот недавно я увидел следующее решение на C#:

public static IEnumerable<T> QuickSort<T>(this IEnumerable<T> list)
where T : IComparable
{
if (!list.Any())
{
return Enumerable.Empty<T>();
}
var pivot = list.First();
var smaller = list.Where(item => item.CompareTo(pivot) <= 0).QuickSort();
var larger = list.Where(item => item.CompareTo(pivot) > 0).QuickSort();

return smaller.Concat(new[] {pivot}).Concat(larger);
}


Кто короче?! ;)

9 коммент.:

vadim комментирует...

Scala:
def qsort(lst: List[Int]):List[Int] =
lst match {
case Nil => Nil
case pivot::tail => qsort(tail filter { _ < pivot })
::: pivot :: qsort(tail filter { _ >= pivot })
}

andriy dmytrenko комментирует...

Haskell:

qsort [] = []
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)

DmytroZ комментирует...

Пока что вариант на Haskell всех порвал ;)

Максим Вуец комментирует...

А разве в Сишарпе можно писать "if (!list.Any())" вместо "if (list.Any() == false)"?

DmytroZ комментирует...

Да, если метод возвращает bool, то его не обязательно явно сравнивать с true/false.
Так же, говорят, что в C# запрещена операция присвоения в if, но это дело можно легко обойти:

int i = 10;
int j = 10;
int n;
if ((n = i) > 0) Console.Write(n);

Максим Вуец комментирует...

Ага, это значит неявные преобразования типа запрещены, типа "if (list.Count)". Теперь понятно, спасибо.

Ну, а в твоем примере у тебя четкий логический контекст в конечном счете, все верно (:

Анонимный комментирует...

В с# ничего не запрещается делать в if, главное чтоб результат выражения был булевого типа, в отличие от с++, где все что не равно нулю расценивается как true.
Максим Вуец, как ты себе представляешь неявное преобразование int в bool?

Анонимный комментирует...

Спасибо.
Работает почти на 10% быстрее если строки
T firstItem = sourceArray[0];
sourceArray.RemoveAt(0);
поменять на
T firstItem = sourceArray[sourceArray.Count - 1];
sourceArray.RemoveAt(sourceArray.Count - 1);

Только почему то с моим компаратором не хочет работать (

DmytroZ комментирует...

Спасибо, g-host07. Операция RemoveAt(sourceArray.Count - 1); действительно работает быстрее чем RemoveAt(0);

За 500000 итераций удаление элементов массива я получил следующие результаты:

Remove0: 267059 ms
RemoveAtCountMinusOne: 4 ms

====================================

static void Remove0(IList list)
{
for (int i = 0; i< list.Count; i++)
{
list.RemoveAt(0);
}
}

static void RemoveAtCountMinusOne(IList list)
{
for (int i = 0; i < list.Count; i++)
{
list.RemoveAt(list.Count - 1);
}
}

static void Main(string[] args)
{
Stopwatch sw1 = new Stopwatch();
Stopwatch sw2 = new Stopwatch();

List list1 = new List();
List list2 = new List();

for (int i = 1; i < 500000; i++)
{
list1.Add(i);
list2.Add(i);
}

sw1.Start();
Remove0(list1);
sw1.Stop();

sw2.Start();
RemoveAtCountMinusOne(list2);
sw2.Stop();

Console.WriteLine("Remove0: {0} ms", sw1.ElapsedMilliseconds);
Console.WriteLine("RemoveAtCountMinusOne: {0} ms", sw2.ElapsedMilliseconds);
}

Отправить комментарий

 

.NET ate my MOSK;. Powered By Blogger © 2009 Bombeli | Theme Design: ooruc