两种查找算法的比较

2019/04/12 12:53
阅读数 5

1、普通查找:双层循环遍历,第二层循环中找到即break,查找时间复杂度O(M*N/2)

List<PtCameraInfo> cameraList = new List<PtCameraInfo>();
List<string> cameraIdList = dataIds.Split(',').ToList();
List<PtCameraInfo> oldList = this.cameraList.Cameras.ToList();

for (int i = 0; i < cameraIdList.Count; i++)
{
    string cameraId = cameraIdList[i];
    for (int j = 0; j < _cameraList.Count; j++)
    {
        PtCameraInfo camera = _cameraList[j];
        if (camera.ID == cameraId && !oldList.Exists(a => a.ID == camera.ID))
        {
            cameraList.Add(camera);
            break;
        }
    }
}
View Code

2、高效查找:排序虽然费时,但数量级低,所以耗时很低,排序时间复杂度O(M*logM+N*logN),查找过程也是双层循环,但第二层循环比较省时,查找时间复杂度O(M*logN),总的时间复杂度:O(M*logM+N*logN+M*logN)

List<PtCameraInfo> cameraList = new List<PtCameraInfo>();
List<string> cameraIdList = dataIds.Split(',').ToList();
List<PtCameraInfo> oldList = this.cameraList.Cameras.ToList();

//排序
this._cameraList.Sort(new Comparison<PtCameraInfo>((a, b) =>
{
    return string.Compare(a.ID.PadLeft(36, '0'), b.ID.PadLeft(36, '0'));
}));
cameraIdList.Sort((a, b) =>
{
    return string.Compare(a.PadLeft(36, '0'), b.PadLeft(36, '0'));
});

//高效查找
int k = 0;
for (int i = 0; i < cameraIdList.Count; i++)
{
    string cameraId = cameraIdList[i];
    for (int j = k; j < _cameraList.Count; j++)
    {
        PtCameraInfo camera = _cameraList[j];
        if (camera.ID == cameraId && !oldList.Exists(a => a.ID == camera.ID))
        {
            cameraList.Add(camera);
            k = j;
            break;
        }
    }
}
View Code

说明:cameraList的数量级是2万,当cameraIdList数量从1到大约1000时,高效查找耗时始终是0.1秒多左右,而普通查找,当cameraIdList数量很少时,很快,0.05秒,当cameraIdList数量接近1000时,大约2秒。

3、使用Dictionary实现高效查找

 

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部