Примечание: Возможно, я выбрал не то слово в названии;возможно, я действительно говорю о полиномиальном росте здесь.См. Результат теста в конце этого вопроса.
Давайте начнем с этих трех рекурсивных универсальных интерфейсов † , которые представляют неизменяемые стеки:
interface IStack<T>
{
INonEmptyStack<T, IStack<T>> Push(T x);
}
interface IEmptyStack<T> : IStack<T>
{
new INonEmptyStack<T, IEmptyStack<T>> Push(T x);
}
interface INonEmptyStack<T, out TStackBeneath> : IStack<T>
where TStackBeneath : IStack<T>
{
T Top { get; }
TStackBeneath Pop();
new INonEmptyStack<T, INonEmptyStack<T, TStackBeneath>> Push(T x);
}
Я создал простые реализации EmptyStack<T>, NonEmptyStack<T,TStackBeneath>.
Обновление № 1: См. Код ниже.
Я заметил следующие моменты, касающиеся их производительности во время выполнения:
- Выдвижение 1000 элементов в
EmptyStack<int> в первый раз занимает более 7 секунд. - Выкладывание 1000 предметов на
EmptyStack<int> практически не тратит времени. - Производительность экспоненциально ухудшается, чем больше предметов я помещаю в стек.
Обновление № 2:
Я наконец выполнил более точное измерение.См. Код и результаты теста ниже.
В ходе этих тестов я только обнаружил, что .NET 3.5, похоже, не допускает универсальные типы с глубиной рекурсии≥ 100. Похоже, что в .NET 4 нет этого ограничения.
Первые два факта заставляют меня подозревать, что низкая производительность не связана с моей реализацией, а точнее для системы типов: .NET должен создать 1000 различных закрытых универсальных типов , т. е .:
EmptyStack<int>NonEmptyStack<int, EmptyStack<int>>NonEmptyStack<int, NonEmptyStack<int, EmptyStack<int>>>NonEmptyStack<int, NonEmptyStack<int, NonEmptyStack<int, EmptyStack<int>>>>- и т. Д.
Вопросы:
- Является ли моя оценка выше верной?
- Если так, то почему экземпляры универсальных типов, таких как
T<U>, T<T<U>>, T<T<T<U>>> и т. Д., Получают экспоненциально медленнее, чем глубжеони вложенные? - Известно ли, что реализации CLR, кроме .NET (Mono, Silverlight, .NET Compact и т. Д.), Обладают такими же характеристиками?
† ) Сноска не по теме: Кстати, эти типы довольно интересны.потому что они позволяют компилятору перехватывать определенные ошибки, такие как:
stack.Push(item).Pop().Pop();
// ^^^^^^
// causes compile-time error if 'stack' is not known to be non-empty.
Или вы можете выразить требования для определенных операций стека:
TStackBeneath PopTwoItems<T, TStackBeneath>
(INonEmptyStack<T, INonEmptyStack<T, TStackBeneath> stack)
Обновление № 1: Реализация вышеупомянутых интерфейсов
internal class EmptyStack<T> : IEmptyStack<T>
{
public INonEmptyStack<T, IEmptyStack<T>> Push(T x)
{
return new NonEmptyStack<T, IEmptyStack<T>>(x, this);
}
INonEmptyStack<T, IStack<T>> IStack<T>.Push(T x)
{
return Push(x);
}
}
// ^ this could be made into a singleton per type T
internal class NonEmptyStack<T, TStackBeneath> : INonEmptyStack<T, TStackBeneath>
where TStackBeneath : IStack<T>
{
private readonly T top;
private readonly TStackBeneath stackBeneathTop;
public NonEmptyStack(T top, TStackBeneath stackBeneathTop)
{
this.top = top;
this.stackBeneathTop = stackBeneathTop;
}
public T Top { get { return top; } }
public TStackBeneath Pop()
{
return stackBeneathTop;
}
public INonEmptyStack<T, INonEmptyStack<T, TStackBeneath>> Push(T x)
{
return new NonEmptyStack<T, INonEmptyStack<T, TStackBeneath>>(x, this);
}
INonEmptyStack<T, IStack<T>> IStack<T>.Push(T x)
{
return Push(x);
}
}
Обновление № 2: Код и результаты теста
Я использовал следующий код для измерения рекурсивного универсального типавремя создания экземпляра .NET 4 на ноутбуке с Windows 7 SP 1 x64 (Intel U4100 @ 1,3 ГГц, 4 ГБ ОЗУ).Это другой, более быстрый компьютер, чем тот, который я использовал изначально, поэтому результаты не совпадают с приведенными выше утверждениями.
Console.WriteLine("N, t [ms]");
int outerN = 0;
while (true)
{
outerN++;
var appDomain = AppDomain.CreateDomain(outerN.ToString());
appDomain.SetData("n", outerN);
appDomain.DoCallBack(delegate {
int n = (int)AppDomain.CurrentDomain.GetData("n");
var stopwatch = new Stopwatch();
stopwatch.Start();
IStack<int> s = new EmptyStack<int>();
for (int i = 0; i < n; ++i)
{
s = s.Push(i); // <-- this "creates" a new type
}
stopwatch.Stop();
long ms = stopwatch.ElapsedMilliseconds;
Console.WriteLine("{0}, {1}", n, ms);
});
AppDomain.Unload(appDomain);
}
(Каждое измерение выполняется в отдельном домене приложения, поскольку это гарантирует, что все время выполнениятипы должны быть воссозданы в каждой итерации цикла.)
Вот график XY вывода:
Горизонтальныйось: N обозначает глубину рекурсии типа, т.е.:
- N = 1 обозначает
NonEmptyStack<EmptyStack<T>> - N = 2 указывает
NonEmptyStack<NonEmptyStack<EmptyStack<T>>> - и т. Д.
Вертикальная ось: t - время (в миллисекундах)) требуется поместить N целых чисел в стек.(Время, необходимое для создания типов времени выполнения, если это действительно происходит, включено в это измерение.)