Итераторы

Архитектура

Абстракция через итерацию — один из методов абстракции доступа к данным, получивший широкое распространение ввиду своей универсальности. Доступ к элементам коллекции осуществляется последовательно, через итератор.

Итерируемые коллекции в C# должны реализовывать интерфейс IEnumerable.

Оператор foreach

Для более удобной работы с итерируемыми коллекциями в языке предусмотрен оператор foreach.

IEnumerable<int> collection = new int[] { 2, 3, 4, 5, 6, 7, 8, 9 };

foreach (int i in collection)
  Console.WriteLine(i);	

Особенности использования с массивами

В случае итерации коллекций с произвольным доступом, например массивов, для доступа к элементам лучше воспользоваться оператором for. Для этого есть три веские причины:

• Для получения элементов и изменения итератора производится вызов виртуальных методов GetCurrent и MoveNext. Это дольше, нежели просто инкрементация индекса;
• При использовании оператора foreach неявно создаётся объект-итератор. При этом производится выделение памяти в управляемой куче. Создание объекта требует вычислительных ресурсов и памяти. Так как сам итератор требует незначительного количества памяти, частое использование оператора foreach может привести к излишней фрагментации памяти, что потребует дополнительных вычислительных ресурсов на её дефрагментацию;
• Цикл foreach оборачивается блоком try/finally;

Это следует учитывать при разработке систем, критичных к времени работы или на платформах, обладающих ограниченными вычислительными ресурсами и памятью, а так же высоконагруженных (облачных) приложений.

Расставим точки над ё

Посчитаем, сколько времени требуется для получения доступа к элементам через итератор и через индекс. Напишем простую программу, вызывающую определенное количество раз функцию, в которой элементы массива обходится тем или иным способом. Текст программы приведен в конце страницы.

Тест проведем в несколько этапов. На каждом этапе будем на порядок увеличивать количество элементов в массиве, и на порядок уменьшать количество циклов. Таким образом, можно посмотреть на корреляцию времени, в зависимости от размера коллекции и количества вызовов.

Тест времени доступа. Компьютер Intel Core2Duo 2.2.Ghz, 800 Mhz FSB
	
Элементов - 10, циклов 1000000
	______________________________________________
	Доступ итерированием.
	Тактов: 9305626
	Миллисекунд: 650
	
	Доступ по индексу.
	Тактов: 2938638
	Миллисекунд: 205
	
	
	Элементов - 100, циклов 100000
	______________________________________________
	Доступ итерированием.
	Тактов: 6130662
	Миллисекунд: 428
	
	Доступ по индексу.
	Тактов: 2450851
	Миллисекунд: 171
	
	
	Элементов - 1000, циклов 10000
	______________________________________________
	Доступ итерированием.
	Тактов: 5578007
	Миллисекунд: 389
	
	Доступ по индексу.
	Тактов: 2351414
	Миллисекунд: 164
	
	
	Элементов - 10000, циклов 1000
	______________________________________________
	Доступ итерированием.
	Тактов: 5555724
	Миллисекунд: 388
	
	Доступ по индексу.
	Тактов: 2352066
	Миллисекунд: 164
	
	
	Элементов - 100000, циклов 100
	______________________________________________
	Доступ итерированием.
	Тактов: 5597581
	Миллисекунд: 391
	
	Доступ по индексу.
	Тактов: 2361441
	Миллисекунд: 165
	
	
	Элементов - 1000000, циклов 10
	______________________________________________
	Доступ итерированием.
	Тактов: 5572387
	Миллисекунд: 390
	
	Доступ по индексу.
	Тактов: 2412830
	Миллисекунд: 170
	
	
	Элементов - 10000000, циклов 1
	______________________________________________
	Доступ итерированием.
	Тактов: 5570852
	Миллисекунд: 391
	
	Доступ по индексу.
	Тактов: 2438235
	Миллисекунд: 172

Как нетрудно заметить, разница есть. Причем на самом «рабочем» варианте, небольшой размер коллекции и большое количество циклов, разница в скорости работы составляет около трех раз. С уменьшением количества циклов разница во времени уменьшается и, начиная примерно с тысячи элементов, остаётся неизменной.

Почему с увеличением размера коллекции увеличивается время работы варианта с доступом по индексу? Наиболее вероятное объяснение — маленькая коллекция целиком ложится в кэш. Если бы объекты были не по четыре байта,  а размером в несколько килобайт, разница могла бы быть ощутимее. Но это вопрос отдельного исследования.

Текст программы

public class SpeedTest<T> where T:struct
	{
		private T [] _array;
		private IEnumerable<T> _collection;

		public SpeedTest(int power)
		{
			List<T> t = new List<T>(power);
			for (int i = 0; i < power; i++)
				t.Add(default(T));

			_array = t.ToArray();
			_collection = _array;
		}

		public int Power
		{
			get { return _array.Length; }
		}

		public void Enumerate()
		{
			T value = default(T);
			foreach (T i in _collection)
				value = i;
		}
		public void Index()
		{
			T value = default(T);
			for(int i = 0; i < _array.Length; i++)
				value = _array[i];
		}
	}

	class Program
	{
		public static void RunCycles(int count, string name, Action testFunction)
		{
			Console.WriteLine(name);
			System.Diagnostics.Stopwatch sw = new Stopwatch();

			sw.Start();
			for (int i = 0; i < count; i++)
				testFunction();

			Console.WriteLine(string.Format("Тактов: {0}", sw.ElapsedTicks));
			Console.WriteLine(string.Format("Миллисекунд: {0}", sw.ElapsedMilliseconds));
		}
		static void Main(string[] args)
		{
			for (int power = 1; power <= 7; power++)
			{
				int cp = (int)Math.Pow(10, power);
				int cycles = (int)Math.Pow(10, 7 - power);
				SpeedTest<int> t = new SpeedTest<int>(cp);
								
				Console.WriteLine(string.Format("Элементов - {0}, циклов {1}", t.Power, cycles));
				Console.WriteLine("______________________________________________");
				
				RunCycles(cycles, "Доступ итерированием.", t.Enumerate);
				Console.WriteLine();
				RunCycles(cycles, "Доступ по индексу.", t.Index);

				Console.WriteLine();
				Console.WriteLine();
				
			}
			Console.WriteLine("Нажмите любую клавишу для завершения работы.");
			Console.ReadKey();
		}
	}