我记得大约在半年前,有个朋友问我一个问题,现在有一个选型:
【数组还是HashSet?】一个性能敏感场景,有一个集合,需要确定某一个元素在不在这个集合中,我是用数组直接Contains
还是使用HashSet<T>.Contains
?
文章插图
大家肯定想都不用想,都选使用
HashSet<T>
,毕竟HashSet<T>
的时间复杂度是O(1),但是后面又附加了一个条件:这个集合的元素很少,就4-5个 。那这时候就有一些动摇了,只有4-5个元素,是不是用数组
Contains
或者直接遍历会不会更快一些?当时我也觉得可能元素很少,用数组就够了 。而最近在编写代码时,又遇到了同样的场景,我决定来做一下实验,看看元素很少的情况下,是不是使用数组优于
HashSet<T>
。测试我构建了一个测试,分别尝试在不同的容量下,查找一个元素,使用数组和HashSet的区别,代码如下所示:
[GcForce(true)][MemoryDiagnoser][Orderer(SummaryOrderPolicy.FastestToSlowest)]public class BenchHashSet{ private HashSet<string> _hashSet; private string[] _strings; [Params(1,2,4,64,512,1024)] public int Size { get; set; } [GlobalSetup] public void Setup() {_strings = Enumerable.Range(0, Size).Select(s => s.ToString()).ToArray();_hashSet = new HashSet<string>(_strings); } [Benchmark(Baseline = true)] public bool EnumerableContains() => _strings.Contains("8192"); [Benchmark] public bool HashSetContains() => _hashSet.Contains("8192");}
大家猜猜结果怎么样,就算Size只为1,那么HashSet也比数组Contains
遍历快40% 。文章插图
那么故事就这么结束了吗?所以无论如何场景我们都直接无脑使用HashSet就行了吗?大家看滑动条就知道,故事没有这么简单 。
刚刚我们是引用类型的比较,那值类型怎么样?结论就是一样的结果,就算只有1个元素也比数组的Contains快 。
文章插图
那么问题出在哪里?点进去看一下数组
Contains
方法的实现就清楚了,这个东西使用的是Enumerable
迭代器匹配 。文章插图
那么我们直接来个原始的,
Array.IndexOf
匹配和for
循环匹配试试,于是有了如下代码:[GcForce(true)][MemoryDiagnoser][Orderer(SummaryOrderPolicy.FastestToSlowest)]public class BenchHashSetValueType{ private HashSet<int> _hashSet; private int[] _arrays; [Params(1,4,16,32,64)] public int Size { get; set; } [GlobalSetup] public void Setup() {_arrays = Enumerable.Range(0, Size).ToArray();_hashSet = new HashSet<int>(_arrays); } [Benchmark(Baseline = true)] public bool EnumerableContains() => _arrays.Contains(42); [Benchmark] public bool ArrayContains() => Array.IndexOf(_arrays,42) > -1; [Benchmark] public bool ForContains() {for (int i = 0; i < _arrays.Length; i++){if (_arrays[i] == 42) return true;}return false; } [Benchmark] public bool HashSetContains() => _hashSet.Contains(42);}
接下来结果就和我们预想的差不多了,在数组元素小的时候,使用原始的for
循环比较会快,然后HashSet就变为最快的了,在更多元素的场景中Array.IndexOf会比for更快:文章插图
至于为什么在元素多的情况
Array.IndexOf
会比for
更快,那是因为Array.IndexOf
经验总结扩展阅读
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- 2023高考完学车有优惠吗 高考完学车好还是大学学车好
- 入梅下雨好还是不下雨好
- 十一点是上午还是中午吗
- 腊肉冷水煮还是开水煮
- 皖鱼刺多吗
- 柠檬泡水用热水还是冷水
- 成都属于一线城市还是二线城市
- 甲鱼是王八还是鳖
- 叠墅和大平层哪个保值 买平层好还是叠墅好
- 卧室做榻榻米好还是做床好?