Hello World
Spiga

真是O(1)吗?想清楚了没?

2013-01-18 11:21 by 老赵, 15406 visits

当然标题里这个O(1)可以换成任何复杂度。

话说写程序的时候我们会用到各种数据结构,但十有八九不会由我们自己从头写起,都会直接拿来用。于是很多人就会记住,譬如HashMapDictionary的存取是O(1)的操作,二分查找什么的则是O(log(N))。不过,我们在实践中直接把这些类拿来用的时候,最好也留个心眼,知道这些类内部到底做了些什么,为什么它们能够达到O(1)之类的时间复杂度。

例如,我们都知道List<T>Add是O(1)的操作,但之所以它是O(1),是因为它的“扩容”操作被均摊了(amortized),但每次扩容时其实还是需要复制所有元素,次数越少越好,于是实践中在可行的情况下我们往往应该给它指定一个初始容量——用StringBuilder的时候也是一样。

我这里还可以再举一个更为复杂的例子,例如HashSetSortedSet,我们要向其中添加N个元素(如字符串),哪个会更快一些?从文档上可以知道,HashSetAdd方法是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的常数就那么大么?其实原因很简单,我们只需想想HashSetSortedSet分别是怎么实现的就行。

  • 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))。

看起来很正常嘛,但是其中还隐含一些“假设”,那就是GetHashCodeEquals还有CompareTo方法都是O(1)的操作,但事实真是如此吗?针对以上代码生成的随机字符串来说,EqualsCompareTo方法都可以几乎瞬间返回(比较第一个字符即可)。不过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

耗时与长度基本呈线性关系。关闭“随机化哈希”之后执行速度略有提高,但耗时与长度的关系依然不变,其实从代码上也已经能够看出这点。

再回到最早针对HashSetSortedSet的实验,由于我故意生成了长度高达5w的字符串,因此HashSet时间复杂度为O(1)又如何?单次GetHashCode方法调用的耗时,就已经远远超过许多次CompareTo方法了。从中我们也可以看出,假如我们用字符串作为字典的键,其效率会较int或是普通未重载过GetHashCodeEquals方法的类型为低。话说回来,其实用一个最普通的类作为字典的键效率很高,因为它的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)大多少的时间复杂度,此时可能也需要考虑下“常数”会对性能造成多大影响。

Creative Commons License

本文基于署名 2.5 中国大陆许可协议发布,欢迎转载,演绎或用于商业目的,但是必须保留本文的署名赵劼(包含链接),具体操作方式可参考此处。如您有任何疑问或者授权方面的协商,请给我留言

Add your comment

11 条回复

  1. jerry
    114.212.81.*
    链接

    jerry 2013-01-19 01:28:36

    好文章...

    话说最后那个,如果人家列数非常非常多,而且非常非常稀疏,可能Dic会好些(有点像邻接矩阵,邻接表的区别)...

    最让我激动的是那个“(内存使用也更紧凑)”,Bjarne有一个演讲专门提到这个。他是讲的非常好,然后我就鸡毛当令箭了,上次在google面试,竟然脑子抽筋拿这个来问面试官...

  2. 老赵
    admin
    链接

    老赵 2013-01-19 15:20:13

    @jerry

    嗯嗯,假如很稀疏的话,用Dictionary<int, string>会好些,甚至可以跟string[]混用,只要支持int -> string就行,总之都比string -> string好……

  3. waynebaby
    116.226.231.*
    链接

    waynebaby 2013-01-23 12:16:35

    总之咱俩还是对啥是算法漏洞保持平行对吧。。。

  4. 老赵
    admin
    链接

    老赵 2013-01-23 21:12:53

    @waynebaby

    不清楚……不过这种定义上的问题关系不大。

  5. 标题党啊
    122.234.211.*
    链接

    标题党啊 2013-01-26 19:19:49

    内容错得一塌糊涂

    一个算法的复杂度本来就有好几个,有时间和空间的区分,也有最好,最坏,平均的区分。光一个平均时间复杂度O(1)当然不能反映所有情况。

    基于bucket的HashTable,最坏情形的时间复杂度是O(N*N),要是只是O(N)那还是可以接受的。

    Marvin32只有正确使用的时候才能避免Hash碰撞攻击,因为那只是把Hash函数的初始值用seed替换了而已。显然假如一直用同一个seed,那还是会被这么攻击。

  6. 老赵
    admin
    链接

    老赵 2013-01-27 01:07:30

    @标题党啊

    你都没看懂这篇文章在讲什么。

    O(N)还是可以接受的是什么意思?遍历都只要O(N),给一个O(N*N)的资料看看吧。

    还有能否给些Marvin32的资料?

  7. 江湖闲云
    58.246.10.*
    链接

    江湖闲云 2013-08-28 10:00:52

    不错,还是来这里能静下心来学习,博客园虽有高手,但天天发首页的基本都是水文。。。。

  8. leasunhy
    112.96.105.*
    链接

    leasunhy 2014-07-13 01:20:06

    博主写得非常好,很有启发意义,还给出了详细的非常具有说服力的例子~谢谢博主写出这么好的文章! 稍稍说一下我看完文章后的想法: 其实大O记号只给出需要进行的特定的某个操作跟输入规模的函数的上界。 这里有几个陷阱…… 一是本文的中心思想:“特定操作”其实一点也不明确。它本身其实可以是任何操作。 二是“上界”……其实大O记号没有给出下界……而且上界也并非上确界。我们一直使用的语义其实属于big-theta记号。也就是Θ。

  9. samuel.song
    52.229.205.*
    链接

    samuel.song 2020-08-10 16:35:52

    雷晨(英語:Rita Lei Chen,1992年2月25日-),出生於中國安徽省合肥市,香港大學畢業,香港本土派人士,香港獨立運動組織者,學生獨立聯盟發言人。

  10. cathalia
    34.92.184.*
    链接

    cathalia 2020-12-03 23:56:10

    隔音性能好。EPS产品隔音主要通过两个途径彩票,一是吸收声波能量福彩双色球,减少反射和传递;二是消除共振,减少噪音幸运飞艇

  11. kericnnoe
    111.242.194.*
    链接

    kericnnoe 2022-12-21 04:07:25

    能在娛樂城獲利對象大多是有玩過魔龍傳奇試玩的玩家居多

发表回复

登录 / 登录并记住我 ,登陆后便可删除或修改已发表的评论 (请注意保留评论内容)

昵称:(必填)

邮箱:(必填,仅用于Gavatar

主页:(可选)

评论内容(大于5个字符):

  1. Your Name yyyy-MM-dd HH:mm:ss

使用Live Messenger联系我