none
Indexof为何运行速度区别这么大,微软的代码比最原始的算法还慢? RRS feed

  • 问题

  •         static void Main(string[] args)
            {
                string text = @"<!doctype html><html><head><meta http-equiv=""Content-Type"" content=""text/html;charset=gb2312""><title>百度一下,你就知道      </title><style>html{overflow-y:auto}body{font:12px arial;text-align:center;background:#fff}body,p,form,ul,li{margin:0;padding:0;list-style:none}body,form,#fm{position:relative}td{text-align:left}img{border:0}a{color:#00c}a:active{color:#f60}#u{padding:7px 10px 3px 0;text-align:right}#m{width:680px;margin:0 auto}#nv{font-size:16px;margin:0 0 4px;text-align:left;text-indent:117px}#nv a,#nv b,.btn,#lk{font-size:14px}#fm{padding-left:90px;text-align:left}#kw{width:404px;height:22px;padding:4px 7px;padding:6px 7px 2px\9;font:16px arial;background:url(http://www.baidu.com/img/i-1.0.0.png) no-repeat -304px 0;_background-attachment:fixed;border:1px solid #cdcdcd;border-color:#9a9a9a #cdcdcd #cdcdcd #9a9a9a;vertical-align:top}.btn{width:95px;height:32px;padding:0;padding-top:2px\9;border:0;background:#ddd url(http://www.baidu.com/img/i-1.0.0.png) no-repeat;cursor:pointer}.btn_h{background-position:-100px 0}#kw,.btn_wr{margin:0 5px 0 0}.btn_wr{width:97px;height:34px;display:inline-block;background:url(http://www.baidu.com/img/i-1.0.0.png) no-repeat -202px 0;_top:1px;*position:relative}#lk{margin:33px 0}#lk span{font:14px ""宋体""}#lm{height:60px}#lh{margin:16px 0 5px;word-spacing:3px}.tools{position:absolute;top:-4px;*top:10px;right:-13px;}#mHolder{width:62px;position:relative;z-index:296;display:none}#mCon{height:18px;line-height:18px;position:absolute;cursor:pointer;padding:0 18px 0 0;background:url(http://www.baidu.com/img/bg-1.0.0.gif) no-repeat right -134px;background-position:right -136px\9}#mCon span{color:#00c;cursor:default;display:block}#mCon .hw{text-decoration:underline;cursor:pointer}#mMenu{width:56px;border:1px solid #9a99ff;list-style:none;position:absolute;right:7px;top:28px;display:none;background:#fff}#mMenu a{width:100%;height:100%;display:block;line-height:22px;text-indent:6px;text-decoration:none}#mMenu a:hover{background:#d9e1f6}#mMenu .ln{height:1px;background:#ccf;overflow:hidden;margin:2px;font-size:1px;line-height:1px}#cp,#cp a{color:#77c}#seth{display:none;behavior:url(#default#homepage)}#setf{display:none}</style>
                ";
                string pattern = @".ln{height:1px;background:#ccf;overflow:hidden;margin:2px;font-size:1px;line-height:1px}#cp,#cp a{color:#77c}#seth{display:none;behavior:url(#default#homepage)}";
                Console.Read();
                Stopwatch watch = new Stopwatch();
                watch.Start();
                for (int j = 0; j < 1000; j++)
                {
                    int i = Indexof(text, pattern);
                }
                Console.WriteLine(watch.ElapsedTicks);
                watch.Stop();
                watch.Reset();
                watch.Start();
                for (int j = 0; j < 1000; j++)
                {
                    int i = text.IndexOf(pattern);
                }
                Console.WriteLine(watch.ElapsedTicks);
                Console.ReadKey();
            }
            public static int Indexof(string text, string pattern)
            {
                int Tsize = text.Length;
                int Psize = pattern.Length;
                for (int i = 0; i < Tsize; i++)
                {
                    for (int j = 0; j < Psize; j++)
                    {
                        if (text[i + j] != pattern[j])
                        {
                            goto next;
                        }
                    }
                    return i;
                next:
                    continue;
                }
                return -1;
            }
    
    


    控制台显示:

    59662

    135929

    为何运行速度区别这么大,微软的代码比最原始的算法还慢?

    2011年11月28日 9:09

答案

  • Hi sql studio,

    这是因为.NET自带的IndexOf方法不止包括了你自己实现的Indexof方法的功能, 它的内部实现是非常复杂的, 大部分是错误和异常处理的逻辑, 另外还有对语言文化, 是否忽略大小写, 日语平假名,片假名 等等等等的考虑.
    你可以先看看CompareOptions枚举:
    http://msdn.microsoft.com/zh-cn/library/system.globalization.compareoptions.aspx.

    然后这里给出IndexOf(String pattern)方法的部分内部实现:
    public int IndexOf(string value)
    {
        return this.IndexOf(value, StringComparison.CurrentCulture);
    }
    

    -----------
    [TargetedPatchingOptOut("Performance critical to inline across NGen image boundaries"), SecuritySafeCritical]
    public int IndexOf(string value, StringComparison comparisonType)
    {
        return this.IndexOf(value, 0, this.Length, comparisonType);
    }

    -----------
    public int IndexOf(string value, int startIndex, int count, StringComparison comparisonType)
    {
        if (value == null)
        {
            throw new ArgumentNullException("value");
        }
        if ((startIndex < 0) || (startIndex > this.Length))
        {
            throw new ArgumentOutOfRangeException("startIndex", Environment.GetResourceString("ArgumentOutOfRange_Index"));
        }
        if ((count < 0) || (startIndex > (this.Length - count)))
        {
            throw new ArgumentOutOfRangeException("count", Environment.GetResourceString("ArgumentOutOfRange_Count"));
        }
        switch (comparisonType)
        {
            case StringComparison.CurrentCulture:
                return CultureInfo.CurrentCulture.CompareInfo.IndexOf(this, value, startIndex, count, CompareOptions.None);
    
            case StringComparison.CurrentCultureIgnoreCase:
                return CultureInfo.CurrentCulture.CompareInfo.IndexOf(this, value, startIndex, count, CompareOptions.IgnoreCase);
    
            case StringComparison.InvariantCulture:
                return CultureInfo.InvariantCulture.CompareInfo.IndexOf(this, value, startIndex, count, CompareOptions.None);
    
            case StringComparison.InvariantCultureIgnoreCase:
                return CultureInfo.InvariantCulture.CompareInfo.IndexOf(this, value, startIndex, count, CompareOptions.IgnoreCase);
    
            case StringComparison.Ordinal:
                return CultureInfo.InvariantCulture.CompareInfo.IndexOf(this, value, startIndex, count, CompareOptions.Ordinal);
    
            case StringComparison.OrdinalIgnoreCase:
                return TextInfo.IndexOfStringOrdinalIgnoreCase(this, value, startIndex, count);
        }
        throw new ArgumentException(Environment.GetResourceString("NotSupported_StringComparison"), "comparisonType");
    }
    
    -----------
    后继调用的方法这里就不贴了, 你可以下载一个.NET的反射工具来查看.NET FCL的内部实现. 正因为.NET对一个方法实现的比较完善, 多了很多逻辑, 所以用的时间就稍微多一些, 但都是经过优化了.

    祝你快乐每一天,
    Leo Liu [MSFT]
    MSDN Community Support | Feedback to us
    2011年11月29日 9:05
    版主