藍色、天空、貓: 【C# 語言】Dictionary & SortedDictionary & SortedList 比較

今天居裡貓知道了一個新的"字典(Dictionary)"的應用方法，因此寫了一個簡單的應用，用來比較之間的差異。平常在使用字典的時候並不會去注意到時間或是記憶體空間，

使用上也偏向單純，只是把 value 找出對應的 key 建立起字典，

接著就用一些方法去新增、搜尋、移除等等。

今天知道了這個新的"字典"方法，

看到網路上及 Microsoft docs 上的說明，心想這東西的用途跟效果如何！？

所以開起來這篇的練習！！

原有常見的字典為：Dictionary
這個就是一個利用 key & value 來建立資料組合，

不可以有重複的 key 否則在加入的時候會產生錯誤！

另外發現的"字典"有兩個為：

SortedDicationary

SortedList

這兩種字典有著跟 Dictionary 一樣的特性，

但就是多了排序(Sort)這件事情，

他們都會將加入的資料 key 值經過排序，

不過這裡可能要注意的是，key 最好是使用 C# 中原有的類別，

自定義類別可能無法達成排序的效果。

在 docs 中，有著一段的備註資料：

簡單的說明就是，

SortedList 有著比 SortedDictionary 較少的記憶體消耗。

SortedDictionary 針對未排序的資料，插入和刪除有著比 SortedList 更快的速度。

針對以排序的資料，SortedList 有著比 SortedDictionary 更快的加入速度。

接著看到網路上的資料整理(Time complexity overview: Dictionary classes)，

好的說到這裡，

就開始說明本次練習的內容吧！！

本次居裡貓針對幾個提到的特性來做比較，

加入速度、移除速度、已排序未排序資料，

依這幾個面向來觀察之間的差異性。

本次練習會透過設定的資料筆數針對三種字典來加入資料，

因為字典不可以出現重複的 key 值，

所以針對未排序資料會透過一些方法來隨機產生不同的 key 值，

已達到未排序的 key 值。

已排序資料則是以 for loop 來決定 key 值。

資料部份皆以隨機方式產生。

針對尋找的部份單純尋找總比數除以 2 的 key 資料。

刪除的行為一樣針對資料總比數除以 2 的 key 資料進行刪除。

以下為練習的視窗介面：

紅框處：資料總筆數

橘框處：未來序、已排序三種字典的三個測試按鈕

粉框處：顯示三種字典執行花費時間

以下為執行之後產生的執行結果：

由上圖結果可以看出，Dictionary 不管是排序還是位排序的結果都快過其他兩者，

也如 docs 上及網路資料說的一樣。

而 SortedDictionary 及 SortedList 也如同 docs 上跟網路資料說的一樣，

在未排序的資料 SortedDictionary 有著比較快的加入跟移除速度。

SortedList 則在排序資料中獲得的叫快的加入速度，而且速度與 Dictionary 非常接近。

總和上述的測試結果，

如同 docs 上描述的時間花費相同，

這時有人會問，那原本的 Dcitionary 有著比這兩個方法還要快的速度，

為什麼還要使用這兩個方法呢！？

這的確是，但居裡貓自己則認為，必須考量到使用情境的問題，

假設今天呈現資料、使用資料是必須要經過排序的，

如果使用原本的 dictionary 就得再做一次排序的方法，

這時的時間花費不見的比較快，並且在程式碼中還會額外多了一些。

因此類似情境下，可以幫忙排序的方法就便利便捷許多！

在針對兩個排序的字典來看，可能會在動作行為上，

SortedDictionary 在通常情境下，操作的時間花費都比較低，

但 SortedList 也有自身優勢，已有排序的資料，還有記憶體空間較小，

在這些條件比較特殊的時候很有優勢的！

好的，本次的練習分享就到這裡。

如果有什麼見解可以與我分享～希望同時也可以幫助到大家～

以下為程式碼的分享～

※註：本次程式碼也是利用程式碼產生介面，詳見 Create___With

----------------------------------程式碼分割線--------------------------------------------------------------

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;
using System.Diagnostics;
namespace Practice_Dictionary_SortedDictionary_SortedList
{
public partial class frmMain : Form
{
#region Fields
private Dictionary<int, int> _NoSortIndex_dictionary;
private SortedDictionary<int, int> _NoSortIndex_sortedDictionary;
private SortedList<int, int> _NoSortIndex_sortedList;
private Random _NoSortIndex, _NoSortIndexData;
private List<int> _lsIndexTable;
private Dictionary<int, int> _dictionary;
private SortedDictionary<int, int> _sortedDictionary;
private SortedList<int, int> _sortedList;
private Random _SortIndexData;
NumericUpDown[] _nudDataCount = new NumericUpDown[1];
Button[] _btnWork = new Button[6];
Label[] _lblTitle = new Label[4];
ListBox[] _lsbResult = new ListBox[3];
Button _btnTestUI;
Stopwatch sw;
delegate void SetControlsCallBack(Control _crtl, object _obj);
#endregion // Fields
#region Construct
public frmMain()
{
InitializeComponent();
}
#endregion // Construct
#region Event
private void frmMain_Load(object sender, EventArgs e)
{
Initialize();
}
private void _btnTestUI_Click(object sender, EventArgs e)
{
this.Controls.Clear();
Initialize();
}
private void _btnWork_Click(object sender, EventArgs e)
{
Button _tmpBtn = (Button)sender;
switch (_tmpBtn.Name)
{
case "btnNoSortDictionary":
NoSortIndexDictionary((int)(_nudDataCount.First(_ => _.Name == "nudDataCount").Value));
break;
case "btnNoSortSortedDictionary":
NoSortIndexSortedDictionary((int)(_nudDataCount.First(_ => _.Name == "nudDataCount").Value));
break;
case "btnNoSortSortedList":
NoSortIndexSortedList((int)(_nudDataCount.First(_ => _.Name == "nudDataCount").Value));
break;
case "btnSortDictionary":
SortIndexDictionary((int)(_nudDataCount.First(_ => _.Name == "nudDataCount").Value));
break;
case "btnSortSortedDictionary":
SortIndexSortedDictionary((int)(_nudDataCount.First(_ => _.Name == "nudDataCount").Value));
break;
case "btnSortSortedList":
SortIndexSortedList((int)(_nudDataCount.First(_ => _.Name == "nudDataCount").Value));
break;
}
}
#endregion // Event
#region Functions
private void Initialize()
{
this.Width = 720;
this.Height = 720;
_NoSortIndex = new Random(Guid.NewGuid().GetHashCode());
_NoSortIndexData = new Random();
_SortIndexData = new Random();
sw = new Stopwatch();
////CreateButtonWithTestUI();
CreateLabelWithTitle(4);
CreateNumericUpDownWithDataCount(1);
CreateButtonWithWork(6);
CreateListBoxWithResult(3);
}
private void ControlsCallBackFunction(Control _ctl, object _obj)
{
if (_ctl is ListBox)
{
ListBox _tmpLsb = _ctl as ListBox;
switch (_tmpLsb.Name)
{
case "lsbDictionaryResult":
if (_tmpLsb.InvokeRequired == true)
{
SetControlsCallBack d = new SetControlsCallBack(ControlsCallBackFunction);
_tmpLsb.Invoke(d, new object[] { _tmpLsb, _obj });
}
else
{
_tmpLsb.Items.Add(_obj);
_tmpLsb.SelectedIndex = _tmpLsb.Items.Count - 1;
}
break;
case "lsbSortedDictionaryResult":
if (_tmpLsb.InvokeRequired == true)
{
SetControlsCallBack d = new SetControlsCallBack(ControlsCallBackFunction);
_tmpLsb.Invoke(d, new object[] { _tmpLsb, _obj });
}
else
{
_tmpLsb.Items.Add(_obj);
_tmpLsb.SelectedIndex = _tmpLsb.Items.Count - 1;
}
break;
case "lsbSortedListResult":
if (_tmpLsb.InvokeRequired == true)
{
SetControlsCallBack d = new SetControlsCallBack(ControlsCallBackFunction);
_tmpLsb.Invoke(d, new object[] { _tmpLsb, _obj });
}
else
{
_tmpLsb.Items.Add(_obj);
_tmpLsb.SelectedIndex = _tmpLsb.Items.Count - 1;
}
break;
}
}
}
#region Work
private void NoSortIndexDictionary(int _DataCount)
{
_NoSortIndex_dictionary = new Dictionary<int, int>();
_lsIndexTable = new List<int>(Enumerable.Range(1, _DataCount + 1));
_lsIndexTable = _lsIndexTable.OrderBy(_ => _NoSortIndex.Next()).ToList<int>();
sw.Reset();
sw.Restart();
for (int i = 1; i <= _DataCount; i++)
{
_NoSortIndex_dictionary.Add(_lsIndexTable[i], _NoSortIndexData.Next(0, 999999));
}
sw.Stop();
string _strMessage = "NoSortIndexDictionary cost: " + sw.Elapsed.TotalMilliseconds.ToString() + " ms";
ControlsCallBackFunction(_lsbResult.First(_ => _.Name == "lsbDictionaryResult"), _strMessage);
sw.Reset();
sw.Restart();
foreach (var _v in _NoSortIndex_dictionary)
{
if (_v.Key == (_DataCount / 2))
{
break;
}
}
sw.Stop();
_strMessage = "NoSortIndexDictionary find key value whith " + (_DataCount / 2).ToString() + " cost: " + sw.Elapsed.TotalMilliseconds.ToString() + " ms";
ControlsCallBackFunction(_lsbResult.First(_ => _.Name == "lsbDictionaryResult"), _strMessage);
sw.Reset();
sw.Restart();
_NoSortIndex_dictionary.Remove(_DataCount / 2);
sw.Stop();
_strMessage = "NoSortIndexDictionary remove key value whith " + (_DataCount / 2).ToString() + " cost: " + sw.Elapsed.TotalMilliseconds.ToString() + " ms";
ControlsCallBackFunction(_lsbResult.First(_ => _.Name == "lsbDictionaryResult"), _strMessage);
}
private void NoSortIndexSortedDictionary(int _DataCount)
{
_NoSortIndex_sortedDictionary = new SortedDictionary<int, int>();
_lsIndexTable = new List<int>(Enumerable.Range(1, _DataCount + 1));
_lsIndexTable = _lsIndexTable.OrderBy(_ => _NoSortIndex.Next()).ToList<int>();
sw.Reset();
sw.Restart();
for (int i = 1; i <= _DataCount; i++)
{
_NoSortIndex_sortedDictionary.Add(_lsIndexTable[i], _NoSortIndexData.Next(0, 999999));
}
sw.Stop();
string _strMessage = "NoSortIndexSortedDictionary cost: " + sw.Elapsed.TotalMilliseconds.ToString() + " ms";
ControlsCallBackFunction(_lsbResult.First(_ => _.Name == "lsbSortedDictionaryResult"), _strMessage);
sw.Reset();
sw.Restart();
foreach (var _v in _NoSortIndex_sortedDictionary)
{
if (_v.Key == (_DataCount / 2))
{
break;
}
}
sw.Stop();
_strMessage = "NoSortIndexSortedDictionary find key value whith " + (_DataCount / 2).ToString() + " cost: " + sw.Elapsed.TotalMilliseconds.ToString() + " ms";
ControlsCallBackFunction(_lsbResult.First(_ => _.Name == "lsbSortedDictionaryResult"), _strMessage);
sw.Reset();
sw.Restart();
_NoSortIndex_sortedDictionary.Remove(_DataCount / 2);
sw.Stop();
_strMessage = "NoSortIndexSortedDictionary remove key value whith " + (_DataCount / 2).ToString() + " cost: " + sw.Elapsed.TotalMilliseconds.ToString() + " ms";
ControlsCallBackFunction(_lsbResult.First(_ => _.Name == "lsbSortedDictionaryResult"), _strMessage);
}
private void NoSortIndexSortedList(int _DataCount)
{
_NoSortIndex_sortedList = new SortedList<int, int>();
_lsIndexTable = new List<int>(Enumerable.Range(1, _DataCount + 1));
_lsIndexTable = _lsIndexTable.OrderBy(_ => _NoSortIndex.Next()).ToList<int>();
sw.Reset();
sw.Restart();
for (int i = 1; i <= _DataCount; i++)
{
_NoSortIndex_sortedList.Add(_lsIndexTable[i], _NoSortIndexData.Next(0, 999999));
}
sw.Stop();
string _strMessage = "NoSortIndexSortedList cost: " + sw.Elapsed.TotalMilliseconds.ToString() + " ms";
ControlsCallBackFunction(_lsbResult.First(_ => _.Name == "lsbSortedListResult"), _strMessage);
sw.Reset();
sw.Restart();
foreach (var _v in _NoSortIndex_sortedList)
{
if (_v.Key == (_DataCount / 2))
{
break;
}
}
sw.Stop();
_strMessage = "NoSortIndexSortedList find key value whith " + (_DataCount / 2).ToString() + " cost: " + sw.Elapsed.TotalMilliseconds.ToString() + " ms";
ControlsCallBackFunction(_lsbResult.First(_ => _.Name == "lsbSortedListResult"), _strMessage);
sw.Reset();
sw.Restart();
_NoSortIndex_sortedList.Remove(_DataCount / 2);
sw.Stop();
_strMessage = "NoSortIndexSortedList remove key value whith " + (_DataCount / 2).ToString() + " cost: " + sw.Elapsed.TotalMilliseconds.ToString() + " ms";
ControlsCallBackFunction(_lsbResult.First(_ => _.Name == "lsbSortedListResult"), _strMessage);
}
private void SortIndexDictionary(int _DataCount)
{
_dictionary = new Dictionary<int, int>();
sw.Reset();
sw.Restart();
for (int i = 1; i <= _DataCount; i++)
{
_dictionary.Add(i, _NoSortIndexData.Next(0, 999999));
}
sw.Stop();
string _strMessage = "SortIndexDictionary cost: " + sw.Elapsed.TotalMilliseconds.ToString() + " ms";
ControlsCallBackFunction(_lsbResult.First(_ => _.Name == "lsbDictionaryResult"), _strMessage);
sw.Reset();
sw.Restart();
foreach (var _v in _dictionary)
{
if (_v.Key == (_DataCount / 2))
{
break;
}
}
sw.Stop();
_strMessage = "SortIndexDictionary find key value whith " + (_DataCount / 2).ToString() + " cost: " + sw.Elapsed.TotalMilliseconds.ToString() + " ms";
ControlsCallBackFunction(_lsbResult.First(_ => _.Name == "lsbDictionaryResult"), _strMessage);
sw.Reset();
sw.Restart();
_dictionary.Remove(_DataCount / 2);
sw.Stop();
_strMessage = "SortIndexDictionary remove key value whith " + (_DataCount / 2).ToString() + " cost: " + sw.Elapsed.TotalMilliseconds.ToString() + " ms";
ControlsCallBackFunction(_lsbResult.First(_ => _.Name == "lsbDictionaryResult"), _strMessage);
}
private void SortIndexSortedDictionary(int _DataCount)
{
_sortedDictionary = new SortedDictionary<int, int>();
sw.Reset();
sw.Restart();
for (int i = 1; i <= _DataCount; i++)
{
_sortedDictionary.Add(i, _NoSortIndexData.Next(0, 999999));
}
sw.Stop();
string _strMessage = "SortIndexSortedDictionary cost: " + sw.Elapsed.TotalMilliseconds.ToString() + " ms";
ControlsCallBackFunction(_lsbResult.First(_ => _.Name == "lsbSortedDictionaryResult"), _strMessage);
sw.Reset();
sw.Restart();
foreach (var _v in _sortedDictionary)
{
if (_v.Key == (_DataCount / 2))
{
break;
}
}
sw.Stop();
_strMessage = "SortIndexSortedDictionary find key value whith " + (_DataCount / 2).ToString() + " cost: " + sw.Elapsed.TotalMilliseconds.ToString() + " ms";
ControlsCallBackFunction(_lsbResult.First(_ => _.Name == "lsbSortedDictionaryResult"), _strMessage);
sw.Reset();
sw.Restart();
_sortedDictionary.Remove(_DataCount / 2);
sw.Stop();
_strMessage = "SortIndexSortedDictionary remove key value whith " + (_DataCount / 2).ToString() + " cost: " + sw.Elapsed.TotalMilliseconds.ToString() + " ms";
ControlsCallBackFunction(_lsbResult.First(_ => _.Name == "lsbSortedDictionaryResult"), _strMessage);
}
private void SortIndexSortedList(int _DataCount)
{
_sortedList = new SortedList<int, int>();
sw.Reset();
sw.Restart();
for (int i = 1; i <= _DataCount; i++)
{
_sortedList.Add(i, _NoSortIndexData.Next(0, 999999));
}
sw.Stop();
string _strMessage = "SortIndexSortedList cost: " + sw.Elapsed.TotalMilliseconds.ToString() + " ms";
ControlsCallBackFunction(_lsbResult.First(_ => _.Name == "lsbSortedListResult"), _strMessage);
sw.Reset();
sw.Restart();
foreach (var _v in _sortedList)
{
if (_v.Key == (_DataCount / 2))
{
break;
}
}
sw.Stop();
_strMessage = "SortIndexSortedList find key value whith " + (_DataCount / 2).ToString() + " cost: " + sw.Elapsed.TotalMilliseconds.ToString() + " ms";
ControlsCallBackFunction(_lsbResult.First(_ => _.Name == "lsbSortedListResult"), _strMessage);
sw.Reset();
sw.Restart();
_sortedList.Remove(_DataCount / 2);
sw.Stop();
_strMessage = "SortIndexSortedList remove key value whith " + (_DataCount / 2).ToString() + " cost: " + sw.Elapsed.TotalMilliseconds.ToString() + " ms";
ControlsCallBackFunction(_lsbResult.First(_ => _.Name == "lsbSortedListResult"), _strMessage);
}
#endregion // Work
#region Create Controls
private void CreateButtonWithTestUI()
{
_btnTestUI = new Button();
_btnTestUI.Name = "btnTestUI";
_btnTestUI.Text = "Test UI";
_btnTestUI.Location = new Point(this.Width - 100, this.Height - 100);
_btnTestUI.Click += _btnTestUI_Click;
this.Controls.Add(_btnTestUI);
}
private void CreateLabelWithTitle(int _total)
{
_lblTitle = new Label[_total];
for (int i = 0; i < _total; i++)
{
_lblTitle[i] = new Label();
switch (i)
{
case 0:
_lblTitle[i].Name = "lblDataCount";
_lblTitle[i].Text = "Data Count:";
_lblTitle[i].Location = new Point(20, 20);
_lblTitle[i].Size = new Size(100, 20);
break;
case 1:
_lblTitle[i].Name = "lblDictionaryResult";
_lblTitle[i].Text = "Dictionary Result:";
_lblTitle[i].Location = new Point(20, 200);
_lblTitle[i].Size = new Size(100, 20);
break;
case 2:
_lblTitle[i].Name = "lblSortedDictionaryResult";
_lblTitle[i].Text = "Sorted Dictionary Result:";
_lblTitle[i].Location = new Point(20, 350);
_lblTitle[i].Size = new Size(100, 20);
break;
case 3:
_lblTitle[i].Name = "lblSortedListResult";
_lblTitle[i].Text = "Sorted List Result:";
_lblTitle[i].Location = new Point(20, 500);
_lblTitle[i].Size = new Size(100, 20);
break;
}
this.Controls.Add(_lblTitle[i]);
}
}
private void CreateNumericUpDownWithDataCount(int _total)
{
_nudDataCount = new NumericUpDown[_total];
for (int i = 0; i <_total; i++)
{
_nudDataCount[i] = new NumericUpDown();
switch (i)
{
case 0:
_nudDataCount[i].Name = "nudDataCount";
_nudDataCount[i].Value = 100;
_nudDataCount[i].Minimum = 1;
_nudDataCount[i].Maximum = 99999;
_nudDataCount[i].Location = new Point(130, 20);
_nudDataCount[i].Size = new Size(100, 20);
break;
}
this.Controls.Add(_nudDataCount[i]);
}
}
private void CreateButtonWithWork(int _total)
{
_btnWork = new Button[_total];
for (int i = 0; i < _total; i++)
{
_btnWork[i] = new Button();
switch (i)
{
case 0:
_btnWork[i].Name = "btnNoSortDictionary";
_btnWork[i].Text = "No Sort Index Dictionary";
_btnWork[i].Location = new Point(20, 45);
_btnWork[i].Size = new Size(170, 20);
break;
case 1:
_btnWork[i].Name = "btnNoSortSortedDictionary";
_btnWork[i].Text = "No Sort Index SortedDictionary";
_btnWork[i].Location = new Point(20, 70);
_btnWork[i].Size = new Size(170, 20);
break;
case 2:
_btnWork[i].Name = "btnNoSortSortedList";
_btnWork[i].Text = "No Sort Index SortedList";
_btnWork[i].Location = new Point(20, 95);
_btnWork[i].Size = new Size(170, 20);
break;
case 3:
_btnWork[i].Name = "btnSortDictionary";
_btnWork[i].Text = "Sort Index Dictionary";
_btnWork[i].Location = new Point(20, 120);
_btnWork[i].Size = new Size(170, 20);
break;
case 4:
_btnWork[i].Name = "btnSortSortedDictionary";
_btnWork[i].Text = "Sort Index SortedDictionary";
_btnWork[i].Location = new Point(20, 145);
_btnWork[i].Size = new Size(170, 20);
break;
case 5:
_btnWork[i].Name = "btnSortSortedList";
_btnWork[i].Text = "Sort Index SortedList";
_btnWork[i].Location = new Point(20, 170);
_btnWork[i].Size = new Size(170, 20);
break;
}
_btnWork[i].Click += _btnWork_Click;
this.Controls.Add(_btnWork[i]);
}
}
private void CreateListBoxWithResult(int _total)
{
_lsbResult = new ListBox[_total];
for (int i = 0; i < _total; i++)
{
_lsbResult[i] = new ListBox();
switch (i)
{
case 0:
_lsbResult[i].Name = "lsbDictionaryResult";
_lsbResult[i].HorizontalScrollbar = true;
_lsbResult[i].Location = new Point(20, 220);
_lsbResult[i].Size = new Size(500, 130);
break;
case 1:
_lsbResult[i].Name = "lsbSortedDictionaryResult";
_lsbResult[i].HorizontalScrollbar = true;
_lsbResult[i].Location = new Point(20, 370);
_lsbResult[i].Size = new Size(500, 130);
break;
case 2:
_lsbResult[i].Name = "lsbSortedListResult";
_lsbResult[i].HorizontalScrollbar = true;
_lsbResult[i].Location = new Point(20, 520);
_lsbResult[i].Size = new Size(500, 130);
break;
}
this.Controls.Add(_lsbResult[i]);
}
}
#endregion // Create Controls
#endregion // Functions
}
}

藍色、天空、貓

關於我自己

2021年3月1日星期一

【C# 語言】Dictionary & SortedDictionary & SortedList 比較

沒有留言:

張貼留言

分享至 Facebook 臉書

分享至 Plurk 噗浪

阿榮福利味

重灌狂人

海芋小站