none
Dictionary & SortedDictionary RRS feed

  • Вопрос

  • Всем привет!

    До сих пор я был уверен в том,
    что SortedDictionary относительно Dictionary создан для ускорения поиска и выборки,
    пусть даже за счет замедления записи.
    Оказалось все наоборот.
    В ниже приведенной программе показана последовательная выборка из словарей,
    но при случайной выборке происходит то же самое.
    Что-то мне уже разонравился этот самый SortedDictionary...
    Какой-то он тормозной...

    //	Dictionary & SortedDictionary
    using System;
    using System.Collections.Generic;
    public class Program
    {	static	void		Main			()
    	{	int		K = 1000, T, I;
    		double	d;
    		DateTime t;
    		Random R = new Random ();
    		Dictionary <int,int> Dct = new Dictionary<int,int>();
    		SortedDictionary <int,int> SrtDct = new SortedDictionary <int,int>();
    
    		t		=	DateTime.Now;
    		for		(	int i=0;i<1000;i++)	Dct.Add (i,i);
    		d		=	((DateTime.Now-t).TotalMilliseconds );
    /*	1 ms		*/	Console.WriteLine	(	"Запись - "+d.ToString(	"F2"	) + " ms"	);
    		t		=	DateTime.Now;
    		for		(	int i=0;i<1000;i++)	SrtDct.Add (i,i);
    		d		=	((DateTime.Now-t).TotalMilliseconds );
    /*	10 ms	*/	Console.WriteLine	(	"Сорт.,Запись - "+d.ToString(	"F2"	) + " ms"	);
    
    		t		=	DateTime.Now;
    		for		(	int i=0;i<K;i++){	for	(int j=0;j<Dct.Count;j++)		I = Dct[i];		}
    		T		=	(int)((DateTime.Now-t).TotalMilliseconds * 1000 * 1000 / Dct.Count / K);
    /*	90 ns	*/	Console.WriteLine	(	"Чтение - " + T + " ns");	
    		t		=	DateTime.Now;
    		for		(	int i=0;i<K;i++){	for	(int j=0;j<SrtDct.Count;j++)	I = SrtDct[i];	}
    		T		=	(int)((DateTime.Now-t).TotalMilliseconds * 1000 * 1000 / SrtDct.Count / K);
    /*	380 ns	*/	Console.WriteLine	(	"Сорт.,Чтение - " + T + " ns");	
    		Console.ReadKey();	
    }	}
    	













    • Изменено QazRdx 14 января 2014 г. 3:13
    12 января 2014 г. 23:07

Ответы

  • Большинство различий между Dictionary и SortedDictionary происходят из того факта, что эти коллекции используют разные алгоритмы/структуры: Dictionary использует хэш-таблицу, а SortedDictionary использует дерево поиска. В часности: SortedDictionary даёт гарантированное время O(logN) вставки, удаления и поиска, а также возможность вывести содержимое в отсортированном порядке за O(N). В то время как вставка элемента в хэш-таблицу может потребовать её перестройки, а скорость поиска напрямую зависит от качества хэш-функции.
    • Помечено в качестве ответа QazRdx 15 января 2014 г. 4:54
    13 января 2014 г. 1:00
  • Я проверил производительность с Вашим вариантом вывода сортированного словаря:
    Random r=new Random();
    Dictionary<int,int> dict=new Dictionary<int,int>();
    SortedDictionary<int,int> sortDict=new SortedDictionary<int,int>();
    for(int i=0,j=r.Next(1000);i<1000;++i,j+=r.Next(1,1001)){
        dict.Add(j,j);
        sortDict.Add(j,j);
    }
    Stopwatch sw=new Stopwatch();
    for(int j=0;j<10;++j){
        sw.Restart();
        foreach(KeyValuePair<int,int> current in dict.OrderBy(a=>a.Key)){
            int t=current.Value;
        }
        sw.Stop();
        Console.WriteLine(sw.ElapsedTicks);
        sw.Restart();
        foreach(KeyValuePair<int,int> current in sortDict){
            int t=current.Value;
        }
        sw.Stop();
        Console.WriteLine(sw.ElapsedTicks);
        Console.WriteLine();
    }
    Вот мои результаты:
    119294
    77224
    
    2282
    819
    
    2919
    777
    
    2954
    770
    
    2884
    798
    
    2954
    749
    
    3024
    798
    
    2989
    805
    
    2968
    798
    
    2926
    882
    То есть у меня SortedDictionary в 3-4 раза быстрее чем Dictionary. Также заметьте существенную разницу между первыми и вторыми результатами. JIT компиляция, которая необходима при первом проходе кода, может существенно исказить результаты, так что одиночный замер не показатель.
    Не совсем понятно, в чем же отличие
    почленной выборки в моем примере?
    Разве что разностью арифметической прогрессии ключей.
    Как я уже говорил, скорость выборки из хеш-таблицы напрямую зависит от качества хеширования. Последовательные натуральные числа самый удобный вариант, так как исключают коллизии хеша, поэтому выборка происходит очень быстро. Если же все элементы дают одинаковый хеш (в данном случае в хеш-таблице будет именно 1931 ячейка, так что хеш вычисляется по модулю 1931), то вместо выбора по хешу, мы получает линейный поиск. SortedDictionary лишён такого недостатка и всегда даёт стабильный результат.
    После копирования отсортированного Dictionary в массив и последовательной выборки из этого массива получаю результат в 30 раз лучше, чем при выборке из SortedDictionary, и в 300 раз лучше, чем при выборке из Dictionary.
    Правда писанины чуть - чуть побольше,
    но ради такого результата подпрыгнуть лишний раз не лень.
    Необходимо учитывать время, необходимое на заполнение массива. Если массив используется один единственный раз, то возможно будет быстрее сразу использовать данные, нежели сначала заполнять ими массив.
    • Помечено в качестве ответа QazRdx 15 января 2014 г. 4:54
    14 января 2014 г. 9:37
  • Уважаемый PetSerAl!

    Благодарю Вас за содержательную и очень полезную консультацию.
    Это позволило мне найти весьма важное для меня решение -

    Для словарей с регулярным обновлением 
    и последующей ранжированной по ключу выборкой
    лучше использовать SortedDictionary,
    во всех остальных случаях - Dictionary.
    Тем более, если требуется ранжирование не по ключу,
    а по одному или нескольким полям в содержательной части.

    "...существенная разница между первыми и вторыми результатами..."

    Да! Причем последующая коррекция словарей 
    практически не влияет на соотношение скоростей выборок,
    поскольку, как Вы отметили, первичная компиляция 
    уже была осуществлена при первом проходе.

    "... Если все элементы дают одинаковый хеш
    (в данном случае в хеш-таблице будет именно 1931 ячейка, 
    так что хеш вычисляется по модулю 1931), 
    то вместо выбора по хешу, мы получаем линейный поиск. 
    SortedDictionary лишён такого недостатка и 
    всегда даёт стабильный результат ..."

    Для словарей с "модульными" ключами - да.
    Правда, я в своей практике не припомню таких словарей.
    Хотя, конечно же, это очень ценное наблюдение.

    У меня обычно используются словари 
    со случайными целочисленными или строчными ключами.
    А в таких словарях, при использовании Dictionary,
    как следует из приведенной далее программы,
    скорость выборки в 3 - 4 раза превосходит 
    скорость выборки из SortedDictionary,
    причем предварительная сортировка практически не влияет 
    на эту скорость.

    Первый запрос -

    2000 - Dictionary с сортировкой
    10000 - SortedDictionary

    Далее - 10 замеров со следующими примерными соотношениями -

    150 - Dictionary с НЕупорядоченными ключами
    140 - Dictionary с упорядоченными по возрастанию ключами
    2000 - Dictionary с сортировкой
    500 - SortedDictionary

    "... Если массив используется один единственный раз, 
    то возможно будет быстрее сразу использовать данные, 
    нежели сначала заполнять ими массив..."

    Этот мой пример с массивами не совсем удачен.
    Если предполагается многократная ранжированная выборка,
    то - да, массив полезен, 
    поскольку выборка из массива наименее затратна.
    И не жаль потратиться один раз на создание такого массива.
    Но для произвольной выборки по ключу массив не подходит -
    поскольку это сводится к линейному поиску нужной записи.

    Большое спасибо!

    using System;
    using System.Linq;
    using System.Diagnostics;
    using System.Collections.Generic;
    public class Program
    {	static	void		Main	()
    	{	Random r=new Random();
    		Dictionary<int,int> dict=new Dictionary<int,int>();
    		Dictionary<int,int> Dict=new Dictionary<int,int>();
    		SortedDictionary<int,int> sortDict=new SortedDictionary<int,int>();
    //	Словари с упорядоченными по возрастанию ключами
    //		for	(	int i=0,j=r.Next(1000);i<1000;++i,j+=r.Next(1,1001))		{	dict.Add(j,j);		sortDict.Add(j,j);	}
    //	Словари с НЕупорядоченными ключами
    		while	(	dict.Count != 1000	)
    		{	int j = r.Next(2000) * r.Next(1000);
    			if	( !dict.ContainsKey(j)	)
    			{	dict.Add(j,j);
    				sortDict.Add(j,j);
    		}	}
    //	Сортировка
    		foreach		(	KeyValuePair<int,int> current in dict.OrderBy(a=>a.Key)	)		Dict.Add (current.Key, current.Value); 
    		Stopwatch	sw		=	new Stopwatch();	int t,n;
    //	Выборки
    		for	(	int j=0;j<10;++j	)
    		{	sw.Restart();
    			foreach		(	KeyValuePair<int,int> current in dict	)		t=current.Value;   
    /* 150 */		sw.Stop();		Console.WriteLine		(	sw.ElapsedTicks + "	- Dictionary c НЕупорядоченными ключами");
    
    			sw.Restart();
    			foreach		(	KeyValuePair<int,int> current in Dict	)	t=current.Value;   
    /* 140 */		sw.Stop();		Console.WriteLine		(	sw.ElapsedTicks + "	- Dictionary c упорядоченными по возрастанию ключами");
    
    //	Дополнение одной записи
    			while	(true)	{	n = 	r.Next(2000) * r.Next(1000);	if	(!dict.ContainsKey(n))	{	dict.Add (n,n);	break;	}	}
    			sw.Restart();
    			foreach		(	KeyValuePair<int,int> current in dict.OrderBy(a=>a.Key)	)			t=current.Value;
    /* 2500 */		sw.Stop();		Console.WriteLine		(	sw.ElapsedTicks + "	- Dictionary с предварительной сортировкой");
    
    //	Дополнение одной записи
    			while	(true)	{	n = 	r.Next(2000) * r.Next(1000);	if	(!sortDict.ContainsKey(n))	{	dict.Add (n,n);	break;	}	}
    			sw.Restart();
    			foreach		(	KeyValuePair<int,int> current in sortDict)		t=current.Value;
    /* 500 */		sw.Stop();		Console.WriteLine		(	sw.ElapsedTicks + "	- SortedDictionary"	);
    			Console.WriteLine();
    			Console.ReadKey();
    }	}	}	






    • Изменено QazRdx 15 января 2014 г. 0:13
    • Помечено в качестве ответа QazRdx 15 января 2014 г. 4:55
    14 января 2014 г. 17:55

Все ответы

  • Большинство различий между Dictionary и SortedDictionary происходят из того факта, что эти коллекции используют разные алгоритмы/структуры: Dictionary использует хэш-таблицу, а SortedDictionary использует дерево поиска. В часности: SortedDictionary даёт гарантированное время O(logN) вставки, удаления и поиска, а также возможность вывести содержимое в отсортированном порядке за O(N). В то время как вставка элемента в хэш-таблицу может потребовать её перестройки, а скорость поиска напрямую зависит от качества хэш-функции.
    • Помечено в качестве ответа QazRdx 15 января 2014 г. 4:54
    13 января 2014 г. 1:00
  • Да! Я все это понимаю, 
    именно так я и думал и продолжаю думать.
    Тем не менее факт на лицо.
    У меня из-за этого великие проблемы,
    везде стоит SortedDictionary -
    видимо, поэтому что-то где-то
    не успевает отрабатывать и глючит,
    и я не могу ничего с этим поделать.
    Попробую заменить на Dictionary, может быть что-то решится.
    Спасибо!
    13 января 2014 г. 4:31
  • Кстати, дополнительно к предыдущему я попробовал Запись и Удаление -
    результат тот же.
    Вставки нет ни в том, ни в другом словаре.
    Остается вопрос - в чем же преимущество сортированного словаря?

    		t		=	DateTime.Now;
    		for	(	int i=1000;i<2000;i++)		{	Dct.Add (i,i);	Dct.Remove(i-500);	}
    		d		=	((DateTime.Now-t).TotalMilliseconds);
    /*	1 ms		*/	Console.WriteLine			(	"Запись и Удаление - "+d.ToString("F2") + " ms"	);
    		t		=	DateTime.Now;
    		for	(	int i=1000;i<2000;i++)		{	SrtDct.Add (i,i);	SrtDct.Remove(i-500);	}
    		d		=	((DateTime.Now-t).TotalMilliseconds);
    /*	10 ms	*/	Console.WriteLine			(	"Сорт.,Запись и Удаление - "+d.ToString("F2") + " ms"	);






    • Изменено QazRdx 13 января 2014 г. 5:24
    13 января 2014 г. 5:05
  • Вставки, по идее, и быть не должно,
    поскольку вставка - это то же самое дополнение.
    13 января 2014 г. 7:11
  • Остается вопрос - в чем же преимущество сортированного словаря
    Возможность быстро получить содержимое, отсортированное по ключу.
    Random r=new Random();
    Dictionary<int,int> dict=new Dictionary<int,int>();
    SortedDictionary<int,int> sortDict=new SortedDictionary<int,int>();
    for(int i=0,j=r.Next(1000);i<1000;++i,j+=r.Next(1,1001)){
        dict.Add(j,j);
        sortDict.Add(j,j);
    }
    
    //Напишите тут сортированный вывод Dictionary
    
    foreach(KeyValuePair<int,int> current in sortDict){
        Console.WriteLine(current.Key);
    }
    Отсутствие плохих наборов данных.
    Dictionary<int,int> dict=new Dictionary<int,int>();
    SortedDictionary<int,int> sortDict=new SortedDictionary<int,int>();
    for(int i=0;i<1000;++i){
        dict.Add(i*1931,i);
        sortDict.Add(i*1931,i);
    }
    Stopwatch sw=new Stopwatch();
    for(int j=0;j<10;++j){
        sw.Restart();
        for(int i=0;i<1000;++i){
            int t=dict[i*1931];
        }
        sw.Stop();
        Console.WriteLine(sw.ElapsedTicks);
        sw.Restart();
        for(int i=0;i<1000;++i){
            int t=sortDict[i*1931];
        }
        sw.Stop();
        Console.WriteLine(sw.ElapsedTicks);
        Console.WriteLine();
    }
    • Изменено PetSerAl 13 января 2014 г. 18:11
    13 января 2014 г. 18:09
  • using System;
    using System.Linq;
    using System.Diagnostics;
    using System.Collections.Generic;
    public class Program
    {	static	void	Main	()
    	{	int	I;
    		Random r=new Random();
    		Dictionary<int,int> dict=new Dictionary<int,int>();
    		SortedDictionary<int,int> sortDict=new SortedDictionary<int,int>();
    		for	(	int i=0,j=r.Next(1000);i<1000;++i,j+=r.Next(1,1001))	{	dict.Add(j,j);		sortDict.Add(j,j);	}
    //	Сортированный вывод Dictionary
    		Stopwatch sw = new Stopwatch();
    		sw.Start();
    		var	V	=	dict.OrderBy(a=>a.Key);
    		foreach		(	KeyValuePair<int,int> Current in V)			I = Current.Value;	//	Console.WriteLine(Current.Key);
    		sw.Stop();
    /*	19000	*/		Console.WriteLine	(	"Dictionary - " + sw.ElapsedTicks	);
    		Console.ReadKey();
    //	Сортированный вывод SortedDictionary
    		sw.Start();
    		foreach		(	KeyValuePair<int,int> current in sortDict)		I = current.Value;	//	Console.WriteLine(current.Key);
    		sw.Stop();
    /*	39000	*/		Console.WriteLine	(	"SortedDictionary - " + sw.ElapsedTicks	);
    		Console.ReadKey();
    		dict		=	new Dictionary<int,int>();
    		sortDict	=	new SortedDictionary<int,int>();
    		for	(int i=0;i<1000;++i)		{	dict.Add(i*1931,i);	sortDict.Add(i*1931,i);	}
    		for	(	int j=0;j<10;++j)
    		{	sw.Restart();
    			for	(int i=0;i<1000;++i)		I=dict[i*1931];
    			sw.Stop();
    /*	10000	*/	Console.WriteLine	(	"Dictionary - " + sw.ElapsedTicks	);
    			sw.Restart();
    			for(int i=0;i<1000;++i)		I=sortDict[i*1931];
    			sw.Stop();
    /*	1000	*/	Console.WriteLine	(	"SortedDictionary - " + sw.ElapsedTicks	);
    			Console.ReadKey();
    }	}	}





    • Изменено QazRdx 13 января 2014 г. 19:54
    13 января 2014 г. 19:51
  • Получается, что выборка скопом через foreach
    все-таки быстрее у Dictionary, примерно в 2 раза,
    а почленная выборка значительно, на порядок, быстрее у SortedDictionary.
    При этом загрузка в Dictionary, на порядок быстрее, чем в SortedDictionary.
    Не совсем понятно, в чем же отличие
    почленной выборки в моем примере?
    Разве что разностью арифметической прогрессии ключей.
    • Изменено QazRdx 13 января 2014 г. 20:12
    13 января 2014 г. 20:01
  • using System;
    using System.Linq;
    using System.Diagnostics;
    using System.Collections.Generic;
    public class Program
    {	static	void		Main	()
    	{	int	I, k=-1;
    		int[]	Arr;
    		Random r=new Random();
    		Dictionary<int,int> dict=new Dictionary<int,int>();
    		SortedDictionary<int,int> sortDict=new SortedDictionary<int,int>();
    		for	(	int i=0,j=r.Next(1000);i<1000;++i,j+=r.Next(1,1001))		{	dict.Add(j,j);		sortDict.Add(j,j);	}
    		Stopwatch sw = new Stopwatch();
    //	Сортированный вывод Dictionary в массив
    		sw.Start();
    		var	V	=	dict.OrderBy(a=>a.Key);
    		Arr = new int [dict.Count];
    		foreach		(	KeyValuePair<int,int> Current in V)	{	k++;	Arr[k] = Current.Value;	}
    		sw.Stop();
    		Console.WriteLine	(	"Dictionary - " + sw.ElapsedTicks	);				//	19000
    //	Сортированный вывод SortedDictionary
    		sw.Start();
    		foreach		(	KeyValuePair<int,int> current in sortDict)		I = current.Value;
    		sw.Stop();
    		Console.WriteLine	(	"SortedDictionary - " + sw.ElapsedTicks	);			//	39000
    		Console.ReadKey();
    
    //	Новые словари
    		dict		=	new Dictionary<int,int>();
    		sortDict	=	new SortedDictionary<int,int>();
    		for	(int i=0;i<1000;++i)			{	dict.Add(i*1931,i);	sortDict.Add(i*1931,i);	}
    //	Сортированный вывод из Dictionary в массив
    		Arr		= 	new int [dict.Count];
    		var	W	=	dict.OrderBy(a=>a.Key);					k=-1;
    		foreach		(	KeyValuePair<int,int> Current in W)	{	k++;	Arr[k] = Current.Value;	}
    		for	(	int j=0;j<10;++j)
    		{	sw.Restart();
    			for	(int i=0;i<1000;++i)			I=Arr[i];
    			sw.Stop();
    			Console.WriteLine		(	"Sorted Array - " + sw.ElapsedTicks	);		//	30
    //	Последовательный вывод из Dictionary
    			sw.Restart();
    			for	(int i=0;i<1000;++i)			I=dict[i*1931];
    			sw.Stop();
    			Console.WriteLine		(	"Dictionary - " + sw.ElapsedTicks	);		//	10000
    //	Последовательный ( сортированный ) вывод из SortedDictionary
    			sw.Restart();
    			for(int i=0;i<1000;++i)			I=sortDict[i*1931];
    			sw.Stop();
    			Console.WriteLine		(	"SortedDictionary - " + sw.ElapsedTicks	);	//	1000
    			Console.ReadKey();
    }	}	}

    После копирования отсортированного Dictionary в массив
    и последовательной выборки из этого массива получаю
    результат в 30 раз лучше, чем при выборке из SortedDictionary,
    и в 300 раз лучше, чем при выборке из Dictionary.
    Правда писанины чуть - чуть побольше,
    но ради такого результата подпрыгнуть лишний раз не лень.







    • Изменено QazRdx 14 января 2014 г. 2:44
    14 января 2014 г. 2:29
  • Я проверил производительность с Вашим вариантом вывода сортированного словаря:
    Random r=new Random();
    Dictionary<int,int> dict=new Dictionary<int,int>();
    SortedDictionary<int,int> sortDict=new SortedDictionary<int,int>();
    for(int i=0,j=r.Next(1000);i<1000;++i,j+=r.Next(1,1001)){
        dict.Add(j,j);
        sortDict.Add(j,j);
    }
    Stopwatch sw=new Stopwatch();
    for(int j=0;j<10;++j){
        sw.Restart();
        foreach(KeyValuePair<int,int> current in dict.OrderBy(a=>a.Key)){
            int t=current.Value;
        }
        sw.Stop();
        Console.WriteLine(sw.ElapsedTicks);
        sw.Restart();
        foreach(KeyValuePair<int,int> current in sortDict){
            int t=current.Value;
        }
        sw.Stop();
        Console.WriteLine(sw.ElapsedTicks);
        Console.WriteLine();
    }
    Вот мои результаты:
    119294
    77224
    
    2282
    819
    
    2919
    777
    
    2954
    770
    
    2884
    798
    
    2954
    749
    
    3024
    798
    
    2989
    805
    
    2968
    798
    
    2926
    882
    То есть у меня SortedDictionary в 3-4 раза быстрее чем Dictionary. Также заметьте существенную разницу между первыми и вторыми результатами. JIT компиляция, которая необходима при первом проходе кода, может существенно исказить результаты, так что одиночный замер не показатель.
    Не совсем понятно, в чем же отличие
    почленной выборки в моем примере?
    Разве что разностью арифметической прогрессии ключей.
    Как я уже говорил, скорость выборки из хеш-таблицы напрямую зависит от качества хеширования. Последовательные натуральные числа самый удобный вариант, так как исключают коллизии хеша, поэтому выборка происходит очень быстро. Если же все элементы дают одинаковый хеш (в данном случае в хеш-таблице будет именно 1931 ячейка, так что хеш вычисляется по модулю 1931), то вместо выбора по хешу, мы получает линейный поиск. SortedDictionary лишён такого недостатка и всегда даёт стабильный результат.
    После копирования отсортированного Dictionary в массив и последовательной выборки из этого массива получаю результат в 30 раз лучше, чем при выборке из SortedDictionary, и в 300 раз лучше, чем при выборке из Dictionary.
    Правда писанины чуть - чуть побольше,
    но ради такого результата подпрыгнуть лишний раз не лень.
    Необходимо учитывать время, необходимое на заполнение массива. Если массив используется один единственный раз, то возможно будет быстрее сразу использовать данные, нежели сначала заполнять ими массив.
    • Помечено в качестве ответа QazRdx 15 января 2014 г. 4:54
    14 января 2014 г. 9:37
  • Уважаемый PetSerAl!

    Благодарю Вас за содержательную и очень полезную консультацию.
    Это позволило мне найти весьма важное для меня решение -

    Для словарей с регулярным обновлением 
    и последующей ранжированной по ключу выборкой
    лучше использовать SortedDictionary,
    во всех остальных случаях - Dictionary.
    Тем более, если требуется ранжирование не по ключу,
    а по одному или нескольким полям в содержательной части.

    "...существенная разница между первыми и вторыми результатами..."

    Да! Причем последующая коррекция словарей 
    практически не влияет на соотношение скоростей выборок,
    поскольку, как Вы отметили, первичная компиляция 
    уже была осуществлена при первом проходе.

    "... Если все элементы дают одинаковый хеш
    (в данном случае в хеш-таблице будет именно 1931 ячейка, 
    так что хеш вычисляется по модулю 1931), 
    то вместо выбора по хешу, мы получаем линейный поиск. 
    SortedDictionary лишён такого недостатка и 
    всегда даёт стабильный результат ..."

    Для словарей с "модульными" ключами - да.
    Правда, я в своей практике не припомню таких словарей.
    Хотя, конечно же, это очень ценное наблюдение.

    У меня обычно используются словари 
    со случайными целочисленными или строчными ключами.
    А в таких словарях, при использовании Dictionary,
    как следует из приведенной далее программы,
    скорость выборки в 3 - 4 раза превосходит 
    скорость выборки из SortedDictionary,
    причем предварительная сортировка практически не влияет 
    на эту скорость.

    Первый запрос -

    2000 - Dictionary с сортировкой
    10000 - SortedDictionary

    Далее - 10 замеров со следующими примерными соотношениями -

    150 - Dictionary с НЕупорядоченными ключами
    140 - Dictionary с упорядоченными по возрастанию ключами
    2000 - Dictionary с сортировкой
    500 - SortedDictionary

    "... Если массив используется один единственный раз, 
    то возможно будет быстрее сразу использовать данные, 
    нежели сначала заполнять ими массив..."

    Этот мой пример с массивами не совсем удачен.
    Если предполагается многократная ранжированная выборка,
    то - да, массив полезен, 
    поскольку выборка из массива наименее затратна.
    И не жаль потратиться один раз на создание такого массива.
    Но для произвольной выборки по ключу массив не подходит -
    поскольку это сводится к линейному поиску нужной записи.

    Большое спасибо!

    using System;
    using System.Linq;
    using System.Diagnostics;
    using System.Collections.Generic;
    public class Program
    {	static	void		Main	()
    	{	Random r=new Random();
    		Dictionary<int,int> dict=new Dictionary<int,int>();
    		Dictionary<int,int> Dict=new Dictionary<int,int>();
    		SortedDictionary<int,int> sortDict=new SortedDictionary<int,int>();
    //	Словари с упорядоченными по возрастанию ключами
    //		for	(	int i=0,j=r.Next(1000);i<1000;++i,j+=r.Next(1,1001))		{	dict.Add(j,j);		sortDict.Add(j,j);	}
    //	Словари с НЕупорядоченными ключами
    		while	(	dict.Count != 1000	)
    		{	int j = r.Next(2000) * r.Next(1000);
    			if	( !dict.ContainsKey(j)	)
    			{	dict.Add(j,j);
    				sortDict.Add(j,j);
    		}	}
    //	Сортировка
    		foreach		(	KeyValuePair<int,int> current in dict.OrderBy(a=>a.Key)	)		Dict.Add (current.Key, current.Value); 
    		Stopwatch	sw		=	new Stopwatch();	int t,n;
    //	Выборки
    		for	(	int j=0;j<10;++j	)
    		{	sw.Restart();
    			foreach		(	KeyValuePair<int,int> current in dict	)		t=current.Value;   
    /* 150 */		sw.Stop();		Console.WriteLine		(	sw.ElapsedTicks + "	- Dictionary c НЕупорядоченными ключами");
    
    			sw.Restart();
    			foreach		(	KeyValuePair<int,int> current in Dict	)	t=current.Value;   
    /* 140 */		sw.Stop();		Console.WriteLine		(	sw.ElapsedTicks + "	- Dictionary c упорядоченными по возрастанию ключами");
    
    //	Дополнение одной записи
    			while	(true)	{	n = 	r.Next(2000) * r.Next(1000);	if	(!dict.ContainsKey(n))	{	dict.Add (n,n);	break;	}	}
    			sw.Restart();
    			foreach		(	KeyValuePair<int,int> current in dict.OrderBy(a=>a.Key)	)			t=current.Value;
    /* 2500 */		sw.Stop();		Console.WriteLine		(	sw.ElapsedTicks + "	- Dictionary с предварительной сортировкой");
    
    //	Дополнение одной записи
    			while	(true)	{	n = 	r.Next(2000) * r.Next(1000);	if	(!sortDict.ContainsKey(n))	{	dict.Add (n,n);	break;	}	}
    			sw.Restart();
    			foreach		(	KeyValuePair<int,int> current in sortDict)		t=current.Value;
    /* 500 */		sw.Stop();		Console.WriteLine		(	sw.ElapsedTicks + "	- SortedDictionary"	);
    			Console.WriteLine();
    			Console.ReadKey();
    }	}	}	






    • Изменено QazRdx 15 января 2014 г. 0:13
    • Помечено в качестве ответа QazRdx 15 января 2014 г. 4:55
    14 января 2014 г. 17:55