Примечание: Возможно, я выбрал неправильное слово в названии; возможно, я действительно говорю о полиномиальном росте здесь. См. Результат теста в конце этого вопроса.
Давайте начнем с этих трех рекурсивных общих интерфейсов & dagger; которые представляют неизменяемые стеки:
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, похоже, не позволяет создавать общие типы с глубиной рекурсии & ge; 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 и т.д.), которые имеют те же характеристики?
& dagger;) Относящаяся к теме сноска: эти типы довольно интересны кстати. потому что они позволяют компилятору поймать определенные ошибки, такие как:
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 x 64 (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);
}
(Каждое измерение выполняется в отдельном домене приложения, поскольку это гарантирует, что все типы времени выполнения должны быть заново созданы в каждой итерации цикла.)
Здесь график X-Y выхода:
-
Горизонтальная ось: N обозначает глубину рекурсии типа, то есть:
- N = 1 указывает a
NonEmptyStack<EmptyStack<T>> - N = 2 указывает a
NonEmptyStack<NonEmptyStack<EmptyStack<T>>> - и др.
- N = 1 указывает a
-
Вертикальная ось: t - время (в миллисекундах), необходимое для перемещения N целых чисел в стек. (Время, необходимое для создания типов времени выполнения, если это действительно происходит, включено в это измерение.)
