资料结构与演算法[3] - List和SortedList与BinarySearch

比对List和SortedList

比对容器

比较方法

开始测试

演算法 - Binary Search

List

public static int Search_List(List<int> list, int num){    int left = 0, right = list.Count() - 1;    while (left <= right)    {        int middle = (right + left) / 2;        if (list[middle] == num)            return middle;        if (list[middle] > num)            right = middle - 1;        else            left = middle + 1;    }    return -1;}

SortedList

public static int Search_SortedList(SortedList<int, int> sortedSet, int num){    int left = 0, right = sortedSet.Count() - 1;    while (left <= right)    {        int middle = (right + left) / 2;        if (sortedSet.Keys[middle] == num)            return middle;        if (sortedSet.Keys[middle] > num)            right = middle - 1;        else            left = middle + 1;    }    return -1;}

测试流程

List

static void ListTest(int testNumber, int targetNumber){    Console.WriteLine("=====List Test=====");    List<int> list = new List<int>();    Stopwatch stopwatch = new Stopwatch();    stopwatch.Start();    for (int i = testNumber; i >= 0; i--)    {        list.Add(i);    }    stopwatch.Stop();    Console.WriteLine($"Add data cost time : {stopwatch.ElapsedMilliseconds}");    stopwatch.Restart();    list.Sort();    var data = BinarySearcher.Search_List(list, targetNumber);    stopwatch.Stop();    Console.WriteLine($"Find Result = {data}");    Console.WriteLine($"Search Time : {stopwatch.ElapsedMilliseconds}ms");}

SortedList

static void SortedListTest(int testNumber, int targetNumber){    Console.WriteLine("=====SortedList Test=====");    Stopwatch stopwatch = new Stopwatch();    SortedList<int, int> sortedList = new SortedList<int, int>();    stopwatch.Start();    for (int i = testNumber; i >= 0; i--)    {        sortedList.Add(i, i);    }    stopwatch.Stop();    Console.WriteLine($"Add data cost time : {stopwatch.ElapsedMilliseconds}");    stopwatch.Restart();    var data = BinarySearcher.Search_SortedList(sortedList, targetNumber);    stopwatch.Stop();    Console.WriteLine($"Find Result = {data}");    Console.WriteLine($"Search Time : {stopwatch.ElapsedMilliseconds}ms");}

开始测试

List<int> list = new List<int>();int testNumber = 500000;int targetNumber = 1500;Console.WriteLine($"Test Number = {testNumber}");ListTest(testNumber, targetNumber);Console.WriteLine();SortedListTest(testNumber, targetNumber);Console.WriteLine();Console.WriteLine();testNumber = 2000;Console.WriteLine($"Test Number = {testNumber}");ListTest(testNumber, targetNumber);Console.WriteLine();SortedListTest(testNumber, targetNumber);

测试结果

小结

Binary Search必须要先排序

先看2000笔资料的比对
因为数值少，在毫秒内就处理完了，没感觉。

不过在加大为500000笔资料后就有很大差距了
SortedList塞资料塞半天，超级放浪费时间
不过搜寻到是han快，毕竟已经排好了
List塞值很快，要做演算法前先才排序，所以浪费点时间。

依结果来看，用List就好了。￣ 3￣▂ξ

=============新增测试============
假如把原本的塞值testNumber到0改成0到testNumber的话

for (int i = testNumber; i >= 0; i--){    sortedList.Add(i, i);}

改成

for (int i = 0; i < testNumber; i++){    sortedList.Add(i, i);}

结果如下 :

因为本来就排好排满了，SortedList塞值变快很多，除非需要不断的大量搜寻，不然...

依结果来看，还是用List就好了。￣ 3￣▂ξ

=============又新增测试了============
后来想到List只要Sort一次就好，不用每次都去Sort，所以测试了只Sort一次，之后的搜寻就直接用这个List去跑演算法。
跑出来结果Search Time大概会降到9ms左右

依结果来看，还是用List就好了。￣ 3￣▂ξ￣ 3￣▂ξ

新手发文，若有错误的地方请不吝色的指正，谢谢。