CWYAlpha

Just another WordPress.com site

Thought this was cool: O(1)?想清楚了没?

leave a comment »


当然标题里这个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] == '', "src[this.Length] == '\'");
                    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)大多少的时间复杂度,此时可能也需要考虑下“常数”会对性能造成多大影响。


0

   

0

udpwork.com 聚合
|
评论: 0
|
要! 要! 即刻! Now!

from IT牛人博客聚合网站: http://www.udpwork.com/item/9110.html

Written by cwyalpha

一月 18, 2013 在 6:53 上午

发表在 Uncategorized

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s

%d 博主赞过: