Я пишу различные реализации неизменяемых бинарных деревьев в С#, и я хотел, чтобы мои деревья наследовали некоторые распространенные методы из базового класса.
К сожалению, классы, которые происходят из базового класса, ужасно медленны. Непроизводные классы работают адекватно. Вот две почти идентичные реализации дерева AVL для демонстрации:
- AvlTree: http://pastebin.com/V4WWUAyT
- DerivedAvlTree: http://pastebin.com/PussQDmN
Два дерева имеют один и тот же код, но я переместил метод DerivedAvlTree.Insert в базовый класс. Здесь тестовое приложение:
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using Juliet.Collections.Immutable;
namespace ConsoleApplication1
{
class Program
{
const int VALUE_COUNT = 5000;
static void Main(string[] args)
{
var avlTreeTimes = TimeIt(TestAvlTree);
var derivedAvlTreeTimes = TimeIt(TestDerivedAvlTree);
Console.WriteLine("avlTreeTimes: {0}, derivedAvlTreeTimes: {1}", avlTreeTimes, derivedAvlTreeTimes);
}
static double TimeIt(Func<int, int> f)
{
var seeds = new int[] { 314159265, 271828183, 231406926, 141421356, 161803399, 266514414, 15485867, 122949829, 198491329, 42 };
var times = new List<double>();
foreach (int seed in seeds)
{
var sw = Stopwatch.StartNew();
f(seed);
sw.Stop();
times.Add(sw.Elapsed.TotalMilliseconds);
}
// throwing away top and bottom results
times.Sort();
times.RemoveAt(0);
times.RemoveAt(times.Count - 1);
return times.Average();
}
static int TestAvlTree(int seed)
{
var rnd = new System.Random(seed);
var avlTree = AvlTree<double>.Create((x, y) => x.CompareTo(y));
for (int i = 0; i < VALUE_COUNT; i++)
{
avlTree = avlTree.Insert(rnd.NextDouble());
}
return avlTree.Count;
}
static int TestDerivedAvlTree(int seed)
{
var rnd = new System.Random(seed);
var avlTree2 = DerivedAvlTree<double>.Create((x, y) => x.CompareTo(y));
for (int i = 0; i < VALUE_COUNT; i++)
{
avlTree2 = avlTree2.Insert(rnd.NextDouble());
}
return avlTree2.Count;
}
}
}
- AvlTree: вставляет 5000 элементов в 121 мс
- DerivedAvlTree: вставляет 5000 элементов в 2182 мс
Мой профилировщик указывает, что программа тратит чрезмерное количество времени в BaseBinaryTree.Insert. Любой, кто заинтересован, может увидеть файл журнала EQATEC, который я создал с помощью кода выше (вам понадобится профилировщик EQATEC, чтобы иметь смысл файла).
Я действительно хочу использовать общий базовый класс для всех моих двоичных деревьев, но я не могу этого сделать, если производительность будет страдать.
Что заставляет мой DerivedAvlTree работать так плохо, и что я могу сделать, чтобы исправить его?
