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 коммент.:
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 })
}
Haskell:
qsort [] = []
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)
Пока что вариант на Haskell всех порвал ;)
А разве в Сишарпе можно писать "if (!list.Any())" вместо "if (list.Any() == false)"?
Да, если метод возвращает 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);
Только почему то с моим компаратором не хочет работать (
Спасибо, 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);
}
Отправить комментарий