Обучение LINQ: QuickSort
Чтобы получить ' dataX = urllib.urlopen (url) .read () ', работающий в python3 (это было бы правильно для python2) вы должны просто изменить 2 маленькие вещи.
1: сам оператор urllib (добавьте ссылку .request в середине):
dataX = urllib.request.urlopen(url).read()
2: Заявление об импорте, предшествующее ему (измените с «import urlib» на:
import urllib.request
И он должен работать в python3:)
5 ответов
Просто измените тип параметра к IEnumerable и используйте var создайте вместо Вашего List<int> для Ваших локальных переменных.
Это сделает Ваш QSLinq метод лучше, потому что это примет больше типов параметров, например int[], а также List<int>.
См. новый метод:
public static IEnumerable<int> QSLinq(IEnumerable<int> _items)
{
if (_items.Count() <= 1)
return _items;
var _pivot = _items.First();
var _less = from _item in _items where _item < _pivot select _item;
var _same = from _item in _items where _item == _pivot select _item;
var _greater = from _item in _items where _item > _pivot select _item;
return QSLinq(_less).Concat(QSLinq(_same)).Concat(QSLinq(_greater));
}
Надеюсь, это поможет.
Забавный Вопрос! Это не превосходит OrderBy по характеристикам, но он действительно ограничивает повторные перечисления некоторые.
public static IEnumerable<int> QSort2(IEnumerable<int> source)
{
if (!source.Any())
return source;
int first = source.First();
return source
.GroupBy(i => i.CompareTo(first))
.OrderBy(g => g.Key)
.SelectMany(g => g.Key == 0 ? g : QSort2(g));
}
Я непреднамеренно генерировал stackoverflow во время разработки как я QSorted когда Ключ == 0.
Только для забавы я протестировал эти решения. Я фиксировал кардинальное тестирование sin(тестирования производительности в режиме отладки), но я не думаю, что влияет на большой эффект O, который мы будем видеть. Вот вход (инвертированный вход является худшим случаем для quicksort),
IEnumerable<int> source = Enumerable.Range(0, 1000).Reverse().ToList();
- Тройное concat-где решение взяло 71 000 миллисекунд.
- Мое решение взяло 330 миллисекунд
- OrderBy. ToArray взял 15 миллисекунд (разрешение таймера, таким образом, фактическое время, вероятно, меньше),
Вот другое решение с помощью Агрегата. Я называю его: Группа и Идет Рыба. Этот берет 170 мс моими 1 000 обратных тестов элементов.
public static IEnumerable<int> QSort3(IEnumerable<int> source)
{
if (!source.Any())
return source;
int first = source.First();
QSort3Helper myHelper =
source.GroupBy(i => i.CompareTo(first))
.Aggregate(new QSort3Helper(), (a, g) =>
{
if (g.Key == 0)
a.Same = g;
else if (g.Key == -1)
a.Less = g;
else if (g.Key == 1)
a.More = g;
return a;
});
IEnumerable<int> myResult = Enumerable.Empty<int>();
if (myHelper.Less != null)
myResult = myResult.Concat(QSort3(myHelper.Less));
if (myHelper.Same != null)
myResult = myResult.Concat(myHelper.Same);
if (myHelper.More != null)
myResult = myResult.Concat(QSort3(myHelper.More));
return myResult;
}
public class QSort3Helper
{
public IEnumerable<int> Less;
public IEnumerable<int> Same;
public IEnumerable<int> More;
}
Почему это - быстрее, чем мое использование решения OrderBy? Я предполагаю, что это является немного более стойким к худшему случаю.
Как насчет этого? (Если я понимаю хорошо, что Вам не нравятся вызовы.ToList),
public static IEnumerable<int> QSLinq(IEnumerable<int> items)
{
if (items.Count() <= 1)
return items;
int pivot = items.First();
return QSLinq(items.Where(i => i < pivot))
.Concat(items.Where(i => i == pivot))
.Concat(QSLinq(items.Where(i => i > pivot)));
}
Правовая оговорка на основе ответа Jon: НЕ используйте этот алгоритм в настоящей проблеме. Это очень неэффективно.
Весь кастинг включен? Я не вижу кастинга. То, что я действительно вижу, является вызовами к "ToList", которые ужасно неэффективны. В основном LINQ разработан для работы по последовательностям, которые внутренне не позволяют Вам работать на месте (или в дублирующемся пространстве) в способе, к которому склоняется quicksort. В основном у Вас есть очень большое копирование данных, продолжающееся здесь :(