Эффективные коллекции

Несколько дней назад у меня появилась необходимость максимально эффективного доступа к элементам, которые хранятся в объекте-хранилище. Все элементы имеют одного предка, определяющего их общие признаки и идентифицирующий каждый элемент уникальным целочисленным идентификатором. Каждый тип элементов хранится в отдельной коллекции. Для хранения элементов в объекте-хранилище я использовал обобщенную коллекцию List, по одной на каждый тип. Мне был необходим метод, позволявший получать элементы из хранилища по типу и идентификатору. Этот метод не должен быть обобщенным, так как должен вызывается через делегат из метода, который имеет только лишь Type запрашиваемого элемента. Таким образом, эффективность применения List сводилась на нет, процесс получения элемента работал очень медленно. На одном из форумов RSDN мне подсказали решение основанное на KeyedCollection. Оно оказалось настолько эффективным для моей задачи, что я был просто поражен. Результаты сравнения решений с использованием List и KeyedCollection, которые приведены здесь, показывают превосходство второго способа более чем в 500 раз. Думаю, это больше чем хорошая мотивация, что бы присмотреться к данному решению. Кстати, в процессе тестирования я помимо этих двух вариантов добавил вариант с использованием ArrayList, для того что бы показать что использование List ничем не отличается по эффективности от использования необобщенной коллекции. Итак, приступим к описанию всех решений.

Иерархия элементов для тестирования эффективности:

  public class base1
  {
      public int i;
      public base1(int iq) { i = iq; }
  };

  public class der1 : base1
  {
      public string s1;
      public der1(int iq, string s) : base(iq) { s1 = s; }
  };

  public class der2 : base1
  {
      public string s2;
      public der2(int iq, string s) : base(iq) { s2 = s; }
  };

Абстрактный класс, описывающий произвольный объект-хранилище для хранения элементов и выполнения требуемых для данной задачи операций:

public abstract class BaseRep
  {
      // инициализация репозитория
      public abstract void Init(Type[] ar);
    
      // добавление элемента
      public abstract void Add<T>(T item) where T : base1;  
    
      // выборка элемента
      public abstract base1 GetCollectionItem(Type collectionType,
      int input);  
    
      // используется для вывода названия типа 
  // репозитория в процессе выполнения теста
      public string GetName() { return this.GetType().Name; }      
  }

Реализация объекта-хранилища с использованием KeyedCollection:

      // интерфейс для быстрого доступа к элементам хранилища
  public interface IIndexable<TKey, TItem>
  {
      TItem this[TKey key] { get; }
  }

  // реализация коллекции, используемой для хранения элементов
  public class myCollection<T> : KeyedCollection<int, T>,
   IIndexable<int, base1> where T : base1
  {
  // переопределение абстрактного метода KeyedCollection
      protected override int GetKeyForItem(T item)
      {
          return item.i;
      }

  // реализация метода интерфейса
      base1 IIndexable<int, base1>.this[int key]
      {
          get
          {
              base1 value = null;
              if (Contains(key))
                  value = this[key];
              return value;
          }
      }
  }

  // реализация объекта-хранилища
  public class keyedRep : BaseRep
  {
      private Dictionary<Type, IIndexable<int, base1>> array =
              new Dictionary<Type, IIndexable<int, base1>>();

      public override void Init(Type[] ar)
      {
          foreach (Type type in ar)
          {
              Type genType = typeof(myCollection<>).MakeGenericType(type);
              array.Add(type, (IIndexable<int,
          base1>)Activator.CreateInstance(genType));
          }
      }

      public override void Add<T>(T item)
      {
          ((myCollection<T>)array[typeof(T)]).Add(item);
      }

      public override base1 GetCollectionItem(Type collectionType,
      int input)
      {
          return array[collectionType][input];
      }
  };

Более простая реализация объекта-хранилища с использованием List:

public class listRep : BaseRep
  {
      Dictionary<Type, object> array = new Dictionary<Type, object>();

      public override void Init(Type[] ar)
      {
          foreach (Type type in ar)
          {
              Type genType = typeof(List<>).MakeGenericType(new Type[] { type });
              array.Add(type, Activator.CreateInstance(genType));
          }
      }

      public override void Add<T>(T item)
      {
          ((List<T>)array[typeof(T)]).Add(item);
      }

      public override base1 GetCollectionItem(Type collectionType, int input)
      {
          if (array.ContainsKey(collectionType))
          {
              IEnumerable collection = (IEnumerable)array[collectionType];
              foreach (base1 item in collection)
              {
                  if (item.i == input)
                      return item;
              }
          }
          return null;
      }
  }

Реализация объекта-хранилища практически аналогичная предыдущей, за исключением того, что вместо List используется ArrayList:

  public class arrayListRep : BaseRep
  {
      Dictionary<Type, ArrayList> array = new Dictionary<Type, ArrayList>();

      public override void Init(Type[] ar)
      {
          foreach (Type type in ar)
          {
              array.Add(type, (ArrayList)Activator.CreateInstance(typeof(ArrayList)));
          }
      }

      public override void Add<T>(T item)
      {
          ((ArrayList)array[typeof(T)]).Add(item);
      }

      public override base1 GetCollectionItem(Type collectionType, int input)
      {
          if (array.ContainsKey(collectionType))
          {
              ArrayList collection = array[collectionType];
              foreach (base1 item in collection)
              {
                  if (item.i == input)
                      return item;
              }
          }
          return null;
      }
  }

И наконец, метод осуществляющий тестирование всех трех вариантов:

  private static void Test()
  {
      // количество элементов каждого типа и количество итераций при выборке
      int iterCount = 10000;

      // типы элементов, которые мы будем использовать
      Type[] types = new Type[] { typeof(der1), typeof(der2) };

      // формируем списки каждого типа элементов,
      // которые позже будем использовать при добавлении в репозиторий
      List<der1> d1 = new List<der1>();
      List<der2> d2 = new List<der2>();
      for (int i = 0; i < iterCount; i++)
      {
          d1.Add(new der1(i, "test"));
          d2.Add(new der2(i, "test"));
      }

      // эмуляция произвольного доступа, определяем индексы элементов
      // которые будем получать в процессе выборки 
      //(выборка должна быть одинаковая для всех, что бы никому не было обидно;))
      List<int> accessInd = new List<int>();
      Random rnd = new Random();
      for (int i = 0; i < iterCount; i++)
      {
          accessInd.Add(rnd.Next(iterCount - 1));
      }

      //формируем список репозиториев для тестирования
      BaseRep[] reps = { new listRep(), new arrayListRep(), new keyedRep() };

      //
      Stopwatch sw = new Stopwatch();

      // для каждого репозитория проводим добавление и выборку
      // с подсчетом затраченного времени на каждую операцию
      foreach (BaseRep rep in reps)
      {
          // инициализация
          rep.Init(types);

          sw.Start();

          // заполнение
          for (int i = 0; i < iterCount; i++)
          {
              rep.Add(d1[i]);
              rep.Add(d2[i]);
          }
          sw.Stop();

          // результаты
          System.Console.WriteLine("{0} adding: {1} ticks or {2} ms",
                  rep.GetName(), sw.ElapsedTicks, sw.ElapsedMilliseconds);
          sw.Reset();

          sw.Start();

          // выборка
          for (int i = 0; i < accessInd.Count; i++)
          {
              // попеременно запрашиваем элементы различных типов
              base1 b = rep.GetCollectionItem(types[i % 2], accessInd[i]);
          }
          sw.Stop();

          // результаты
          System.Console.WriteLine("{0} reading: {1} ticks or {2} ms",
                  rep.GetName(), sw.ElapsedTicks, sw.ElapsedMilliseconds);
          sw.Reset();

          System.Console.WriteLine(Environment.NewLine);
      }
  }

Таким образом, вот какие я получил результаты на своем компьютере:

Результаты (MSVS2k5, Release, WinXP, Athlon64 3000+):

listRep adding: 25441 ticks or 7 ms
listRep reading: 8778434 ticks or 2452 ms


arrayListRep adding: 24542 ticks or 6 ms
arrayListRep reading: 9088774 ticks or 2539 ms


keyedRep adding: 68186 ticks or 19 ms
keyedRep reading: 19248 ticks or 5 ms

Решения с List и ArrayList показили себя практически одинаково малоэффективно.
Однако, добавление в такие коллекции осуществляется в 3 раза быстрее, чем в случае с KeyedCollection. Оно и понятно — в линейных коллекциях добавление не требует каких-либо чрезмерных усилий и дополнительных затрат.
А вот резульаты произвольной выборки — это что-то... 5 мс против ~2500 мс, то есть практически в 500 раз KeyedCollection работает эффективней.
В виду того на практике в большинстве случаев выборка или получение элементов из хранилища используется гораздо чаще, чем операция добавления (удаления, изменения), то фактом более медленного добавления в принципе можно пренебречь. Таким образом, если у Вас возникнет ситуация похожая на ту, которая опианная здесь, Вы уже знаете что делать