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

比对List和SortedList

比对容器

• 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必须要先排序

• List塞值不排，要做演算法时才排
• SortdeList边塞边排，可直接使用验算法

先看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￣▂ξ

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