真是O(1)吗?想清楚了没?
2013-01-18 11:21 by 老赵, 15406 visits当然标题里这个O(1)可以换成任何复杂度。
话说写程序的时候我们会用到各种数据结构,但十有八九不会由我们自己从头写起,都会直接拿来用。于是很多人就会记住,譬如HashMap
或Dictionary
的存取是O(1)的操作,二分查找什么的则是O(log(N))。不过,我们在实践中直接把这些类拿来用的时候,最好也留个心眼,知道这些类内部到底做了些什么,为什么它们能够达到O(1)之类的时间复杂度。
例如,我们都知道List<T>
的Add
是O(1)的操作,但之所以它是O(1),是因为它的“扩容”操作被均摊了(amortized),但每次扩容时其实还是需要复制所有元素,次数越少越好,于是实践中在可行的情况下我们往往应该给它指定一个初始容量——用StringBuilder
的时候也是一样。
我这里还可以再举一个更为复杂的例子,例如HashSet
和SortedSet
,我们要向其中添加N个元素(如字符串),哪个会更快一些?从文档上可以知道,HashSet
的Add
方法是O(1)的操作,而SortedSet
内部是用了红黑树,它的Add
方法是O(log(N))的操作(但它能顺序输出元素)。显然,从时间复杂度上来讲,SortedSet
的性能要落后于HashSet
,不过我们能否设计一个用例,让HashSet
慢于SortedSet
呢?
当然可以,例如以前那个由哈希碰撞引起的DoS安全漏洞,其实就是设计了一些Hash Code相同,但具体内容不同的字符串,让Dictionary(原理与HashSet
相同)Add
/Remove
操作的时间复杂度从O(1)退化为O(N),这显然低于O(log(N))。不过如今的BCL中的实现已经对碰撞次数设置了阈值,超过这个阈值则会对哈希函数进行随机化,因此这种做法已经很难生效了。所以这里我们可以设计出另一个案例,且看代码:
static string[] GetRandomStrings(int number, int length) { var random = new Random(DateTime.Now.Millisecond); var array = new string[number]; var buffer = new char[length]; for (var i = 0; i < array.Length; i++) { for (var j = 0; j < buffer.Length; j++) { buffer[j] = (char)(random.Next(Char.MinValue, Char.MaxValue) + 1); } array[i] = new string(buffer); } Console.WriteLine("Generated"); return array; } static void CollectGarbage() { for (var i = 0; i < 10; i++) { GC.Collect(); GC.WaitForPendingFinalizers(); } } static void AddToSetTime(string name, ISet<string> set, string[] array) { CollectGarbage(); var watch = new Stopwatch(); watch.Start(); foreach (var s in array) { set.Add(s); } Console.WriteLine(name + ": " + watch.ElapsedMilliseconds); } static void Main() { var array = GetRandomStrings(5000, 50000); AddToSetTime("HashSet", new HashSet<string>(), array); AddToSetTime("SortedSet", new SortedSet<string>(), array); }
GetRandomStrings
方法用于生成一系列的随机字符串,我们会将这些字符串使用AddToSetTime
方法放入一个集合类中,并输出耗时。这段程序在我的机器上输出:
Generated HashSet: 165 SortedSet: 17
您可以自己尝试一下,具体数值可能不同,但HashSet
显著慢于SortedSet
则基本是确定的。为什么会这样?O(1)为什么完败于O(log(N))?难道HashSet
的常数就那么大么?其实原因很简单,我们只需想想HashSet
和SortedSet
分别是怎么实现的就行。
HashSet
:调用元素的GetHashCode
方法获得Hash Code,算出该元素放在哪个Bucket中,然后顺着链表使用Equals
方法依次比较Hash Code的相同元素。由于Hash Code散列程度较高,相同Bucket中重复元素极少,因此时间复杂度近似为O(1)。SortedSet
:使用CompareTo
方法比较新元素与红黑树里的元素,以此决定元素的树中的“走向”,需要时再进行“平衡”操作。由于一颗平衡二叉树的高度为log(N),因此添加一个元素要进行大约log(N)次比较(以及最多log(N)次O(1)的平衡操作),其时间复杂度大约为O(log(N))。
看起来很正常嘛,但是其中还隐含一些“假设”,那就是GetHashCode
、Equals
还有CompareTo
方法都是O(1)的操作,但事实真是如此吗?针对以上代码生成的随机字符串来说,Equals
和CompareTo
方法都可以几乎瞬间返回(比较第一个字符即可)。不过GetHashCode
便麻烦一些了,便顺手从BCL的代码里摘抄出来吧:
namespace System { public sealed class String { public override int GetHashCode() { #if FEATURE_RANDOMIZED_STRING_HASHING if (HashHelpers.s_UseRandomizedStringHashing) { return InternalMarvin32HashString(this, this.Length, 0); } #endif // FEATURE_RANDOMIZED_STRING_HASHING unsafe { fixed (char* src = this) { Contract.Assert(src[Length] == '\0', "src[this.Length] == '\\0'"); Contract.Assert(((int)src) % 4 == 0, "Managed string should start at 4 bytes boundary"); #if WIN32 int hash1 = (5381 << 16) + 5381; #else int hash1 = 5381; #endif int hash2 = hash1; #if WIN32 // 32 bit machines. int* pint = (int*)src; int len = Length; while (len > 2) { hash1 = ((hash1 << 5) + hash1 + (hash1 >> 27)) ^ pint[0]; hash2 = ((hash2 << 5) + hash2 + (hash2 >> 27)) ^ pint[1]; pint += 2; len -= 4; } if (len > 0) { hash1 = ((hash1 << 5) + hash1 + (hash1 >> 27)) ^ pint[0]; } #else int c; char* s = src; while ((c = s[0]) != 0) { hash1 = ((hash1 << 5) + hash1) ^ c; c = s[1]; if (c == 0) break; hash2 = ((hash2 << 5) + hash2) ^ c; s += 2; } #endif #if DEBUG // We want to ensure we can change our hash function daily. // This is perfectly fine as long as you don't persist the // value from GetHashCode to disk or count on String A // hashing before string B. Those are bugs in your code. hash1 ^= ThisAssembly.DailyBuildNumber; #endif return hash1 + (hash2 * 1566083941); } } } } }
从代码里可以看出,撇开最先的InternalMarvin32HashString
这个不谈,其他分支下的哈希算法都是与字符串的长度呈线性关系。至于Marvin32这个神秘的哈希算法,我只知道可用于避免哈希碰撞攻击,但搜索了半天都找不到它的具体信息,只有一个“疑似”的简化实现。目前,我们还是用简单的测试来验证字符串长度与GetHashCode
方法耗时的关系:
static void GetHashCodeTime(string name, string str, int iteration) { CollectGarbage(); str.GetHashCode(); // warm up var watch = new Stopwatch(); watch.Start(); for (var i = 0; i < iteration; i++) { str.GetHashCode(); } Console.WriteLine(name + ": " + watch.ElapsedMilliseconds); } static void Main() { var shortStr = new string('a', 100); var longStr = new string('a', 10000); var iteration = 1000000; GetHashCodeTime("Short", shortStr, iteration); GetHashCodeTime("Long", longStr, iteration); }
我们创建了长度相差百倍的字符串,并比较其GetHashCode
方法的耗时。我们可以开启随机化的字符串哈希算法(即使用Marvin32哈希算法),例如打开之后在我的机器上执行结果是:
Short: 114 Long: 9142
耗时与长度基本呈线性关系。关闭“随机化哈希”之后执行速度略有提高,但耗时与长度的关系依然不变,其实从代码上也已经能够看出这点。
再回到最早针对HashSet
和SortedSet
的实验,由于我故意生成了长度高达5w的字符串,因此HashSet
时间复杂度为O(1)又如何?单次GetHashCode
方法调用的耗时,就已经远远超过许多次CompareTo
方法了。从中我们也可以看出,假如我们用字符串作为字典的键,其效率会较int
或是普通未重载过GetHashCode
和Equals
方法的类型为低。话说回来,其实用一个最普通的类作为字典的键效率很高,因为它的GetHashCode
可以直接返回它的初始地址,而Equals
方法则直接比较两个对象的引用。
在实践中,我遇到各种需要以字符串作为键的场景,我都会思考下有没有简单的替代方法,例如使用int
做键,甚至直接使用数组。例如,前段时间@左耳朵耗子提到对一个csv文件里的数据进行排序,我们可以使用一个字典来保存一行数据,其中键为字段名:
List<Dictionary<string, string>> data = ...; var ordered = data .OrderBy(row => row["column0"]) // 先以column0排序 .ThenBy(row => row["column1"]); // 再以column1排序
但更有效率(内存使用也更紧凑)的做法是以一个数组来保存一行数据。我们先找出需要排序的列的下标,然后再从数组中找出排序用的字段值:
string[] columns = ...; var index0 = columns.IndexOf("column0"); var index1 = columns.IndexOf("column1"); List<string[]> data = ...; var ordered = data .OrderBy(row => row[index0]) .ThenBy(row => row[index1]);
从理论上讲,两种做法的时间复杂度一致,但实际上后者比前者会有不少提高。我们在了解“理论”的同时也需要注意实践上的细节,例如,其实在实践中O(log(N))其实也是个不比O(1)大多少的时间复杂度,此时可能也需要考虑下“常数”会对性能造成多大影响。
好文章...
话说最后那个,如果人家列数非常非常多,而且非常非常稀疏,可能Dic会好些(有点像邻接矩阵,邻接表的区别)...
最让我激动的是那个“(内存使用也更紧凑)”,Bjarne有一个演讲专门提到这个。他是讲的非常好,然后我就鸡毛当令箭了,上次在google面试,竟然脑子抽筋拿这个来问面试官...