由前帖引发：代码可读性与性能的选择

前一帖子参考： for的效率测试和结果，分享一下
里面很多同学都说，我提的那点性能，影响不大，不建议改进，而建议使用可读性好的代码写法，这里我分享一个我的实际经验。

我现在负责一个日pv访问过千万的搜索接口，数据大约几十万条
因为SqlServer的LIKE效率太低，而SqlServer的全文检索又不尽人意，于是方案定为把这些记录全部加载到内存，代码一开始如下：
Dictionary<string, int> name_id = 加载几十万条 标题_id 的记录;
string key = "要搜索的关键词";
StringBuilder sb = new StringBuilder(10000);
foreach (KeyValuePair<string, int> pair in name_id)
{
    if (pair.Key.IndexOf(key) >= 0)
        sb.AppendFormat("{0},", pair.Value);
}
return sb.ToString()

这段代码上线后，执行效率不是很好，后来通过性能工具测试，发现问题比较大的一个地方，就是
IndexOf(key)和AppendFormat("{0},", pair.Value)占用了大约30%的执行时间
因为访问量大，加上每次访问都要循环执行IndexOf(key)几十万次
后面改成了：
foreach (KeyValuePair<string, int> pair in name_id)
{
    if (pair.Key.IndexOf(key, StringComparison.Ordinal) >= 0)
        sb.AppendFormat("{0},", pair.Value.ToString());
}

由这个例子，虽然每次的IndexOf(key)或AppendFormat("{0},", pair.Value)，影响的效率可能是微秒计，但是如果执行次数多了，效率也是很可观的，比如上述例子就占了1/3的执行时间

想起了一句话：勿以善而不为。不要以为性能改善极其微小，就按自己的想法去做

130 个解决方案

#1

你还来啊

#2

这种设计,要是被sp1234看到
肯定又是一顿喷

#3

真那么在乎性能的话就该直接用哈希表，或者专门写个key的搜索算法。

#4

设计的问题由cao和sp来喷
我说说代码的问题哈

sb.AppendFormat("{0},", pair.Value);
sb.AppendFormat("{0},", pair.Value.ToString());

我看了三遍,我怎么感觉第一行代码比第二行性能高很多啊
这种感觉很强烈

先看看AppendFormat的原型
public StringBuilder AppendFormat(string format, object arg0);

第二个参数是object,你To成了String就不用装箱了?
没事找事嘛
真要性能,你在加载数据时,就把id转成object类型
Dictionary<string, object>
这样就不用装箱了
别喷我,我知道这是错误的

#5

这次泪奔了
喷错了
To成了String真的不用装箱了
String本来就是引用类型了
但是To成String的性能也不高吧

#6

这个无语，装箱再ToString，跟直接ToString，你说哪个性能好？

引用 5 楼  的回复:

这次泪奔了
喷错了
To成了String真的不用装箱了
String本来就是引用类型了
但是To成String的性能也不高吧

#7

个人水平有限，这个类似SQL的 like '%关键词%'
的算法，按你说 应该怎么写？

引用 3 楼  的回复:

真那么在乎性能的话就该直接用哈希表，或者专门写个key的搜索算法。

#8

写这个帖子的目的，也有等大师来喷的意思
因为个人水平的确有限

等待SP1234或Cao中
指点下小弟，就标题这个应用 如何设计，效率最高？

引用 2 楼  的回复:

这种设计,要是被sp1234看到
肯定又是一顿喷

#9

    
没有抠语句的性能
只在外面多加了一个精确缓存
可能性能会更差

/// <summary>
    /// 搜索Key类
    /// </summary>
    public class SearchKey
    {
        private Dictionary<String, Int32> _NameId;

        // 精确缓存
        private Dictionary<String, HashSet<Int32>> _AccuratelyCache;

        public SearchKey()
        {
            _NameId = new Dictionary<String, Int32>(10000);

            // 加载数据时,最好能从标题里提取关键字填充这个缓存,如果没有,只能在搜索过程填充
            _AccuratelyCache = new Dictionary<String, HashSet<Int32>>(10000);

            for (int i = 0; i < 1000000; i++)
            {
                _NameId.Add(String.Format("标题啊{0}", i), i);
            }
        }

        /// <summary>
        /// 搜索
        /// </summary>
        /// <param name="key"></param>
        /// <returns></returns>
        public String Search(String key)
        {
            String strRet = String.Empty;
            
            if (!String.IsNullOrEmpty(key))
            {
                String strNewKey = key.ToUpper();
                HashSet<Int32> hsId;

                // 先从精确缓存里查找,如果没有,再从NameId缓存查找
                if (!_AccuratelyCache.TryGetValue(strNewKey, out hsId))
                {
                    hsId = new HashSet<Int32>();
                    foreach (KeyValuePair<String, Int32> pair in _NameId)
                    {
                        if (!hsId.Contains(pair.Value) && pair.Key.IndexOf(strNewKey) >= 0)
                        {
                            // 如果能找到,把ID加到精确缓存里
                            hsId.Add(pair.Value);
                        }
                    }

                    // 填充精确缓存
                    _AccuratelyCache.Add(strNewKey, hsId);
                }

                StringBuilder sb = new StringBuilder(10000);
                foreach (Int32 id in hsId)
                {
                }
                return sb.ToString();
            }

            return String.Empty;
        }
    }

#10

答复楼上：“最好能从标题里提取关键字填充这个缓存”

这个就是SqlServer或一些开源的全文检索做的事情，这个对中文分词的支持，始终不是很好，百度的效果都做的不是很好，

所以我才一直使用类似SQL的 like '%关键词%' 方案

目前我的核心代码就是一楼写的那样，然后外层对一些常见关键字做HttpRuntimeCache的缓存
再就是多台机器用lvs做负载均衡了

真心希望有好算法，我个人是想不到更好的方案了

#11

比如百度搜索：的都
没有匹配结果

搜索：的都好
的都结果也出来了

古歌就很不错，不知道具体实现

#12

太难了
还是继续抠语句的性能容易点

引用 10 楼  的回复:

答复楼上：“最好能从标题里提取关键字填充这个缓存”

这个就是SqlServer或一些开源的全文检索做的事情，这个对中文分词的支持，始终不是很好，百度的效果都做的不是很好，

所以我才一直使用类似SQL的 like '%关键词%' 方案

目前我的核心代码就是一楼写的那样，然后外层对一些常见关键字做HttpRuntimeCache的缓存
再就是多台机器用lvs做负载均衡了

真……

#13

该回复于2012-07-20 15:05:37被版主删除

#14

修改成下面这样
性能继续提升20%
别喷我啊


Dictionary<string, object> name_id = 加载几十万条 标题_id 的记录;
string key = "要搜索的关键词";
StringBuilder sb = new StringBuilder(10000);
foreach (KeyValuePair<string, object> pair in name_id)
{
  if (pair.Key.IndexOf(key, StringComparison.Ordinal) >= 0)
  sb.AppendFormat("{0},", pair.Value);
}
return sb.ToString()

#15

你这个把装箱放到索引生成里去了
但是sb.AppendFormat("{0},", object);
最终还是调用了Int.ToString(string format, IFormatProvider provider)

跟我在一楼写的方法没有区别

引用 14 楼  的回复:

C# code


修改成下面这样
性能继续提升20%
别喷我啊


Dictionary<string, object> name_id = 加载几十万条 标题_id 的记录;
string key = "要搜索……

#16

http://www.builder.com.cn/2008/0531/893872.shtml
摘抄如下：
在执行检索时，Google通常遵循以下步骤（以下所指的是单个检索词的情况）： 
(1)将检索词转化成相应的wordID； 
(2)利用Lexicon，检索出包含该wordID的网页的docID； 
(3)根据与Lexicon相连的倒排档索引，分析各网页中的相关索引项的情况，计算各网页和检索词的匹配程度，必要时调用顺排档索引； 
(4)根据各网页的匹配程度，结合根据Link产生的相应网页的PageRank情况，对检索结果进行排序； 
(5)调用Document Index中的docID及其相应的URL，将排序结果生成检索结果的最终列表，提供给检索用户。 


如果这是事实，那么谷歌也是全文分词？？那连“的都”这样的非词组也分？那它的索引得多大？这么大的索引，如何快速搜索？
有没有人了解？或者指点下小弟，如果改善我那简单的搜索接口

#17

自己顶下

#18

该回复于2012-07-25 10:46:57被版主删除

#19

该回复于2012-07-21 13:15:33被版主删除

#20

pair.Key.IndexOf(key) 看看这个是怎么实现的，是否能够手写优化

#21

俺写的代码可读性与性能都很好。

#22

引用 21 楼  的回复:

俺写的代码可读性与性能都很好。

发点代码学习学习

#23

我认为举得例子非常不好。这个应用需求其实应该使用搜索引擎实现，而不是这样的笨办法。
这种情况下，你无论怎么调优，怎么优化代码，搞各种技巧，能够加百分之几就非常不错了，而付出的代价则很大。不容易维护、BUG、开发调试周期长、人员变动没人敢维护等等。还不如干脆加钱买新服务器呢。
但是如果使用了合理的解决方案、效率更高的算法，则可以一下子提高几十几百倍的效率。

#24

细节是需要关注的，for循环的写法大多数写的不规范，不过影响不大是因为数据量少，js里面就有个习惯要把长度给预存起来。
搜索引擎的查找原理也是索引起来，具体情况不知道呵呵

#25

支持············

#26

pair.Value.ToString()？为什么要ToString?
本来就是int

#27

IndexOf换成Contains我觉得可读性更好。性能差不多（未精确测定）

#28

引用 26 楼  的回复:

pair.Value.ToString()？为什么要ToString?
本来就是int

我猜,是因为sb.AppendFormat的参数要求是object
直接传int会装箱
ToString后就不用了装了

#29

引用 28 楼  的回复:

引用 26 楼  的回复:

pair.Value.ToString()？为什么要ToString?
本来就是int

我猜,是因为sb.AppendFormat的参数要求是object
直接传int会装箱
ToString后就不用了装了

恩 微软为什么要弄个object的参数
不过测试了感觉时间差不多，粗略的呵呵

#30

引用 2 楼  的回复:

这种设计,要是被sp1234看到
肯定又是一顿喷

#31

引用 6 楼  的回复:

这个无语，装箱再ToString，跟直接ToString，你说哪个性能好？

引用 5 楼  的回复:
这次泪奔了
喷错了
To成了String真的不用装箱了
String本来就是引用类型了
但是To成String的性能也不高吧

楼主这个其实也是你的猜测。
为什么ToString()性能要好？期待解答

#32

恩，通过IL查看明白了，还是基础知识不牢固

 int i = 123;
            Console.WriteLine((object)i.ToString());

.method private hidebysig static void  Main(string[] args) cil managed
{
  .entrypoint
  // 代码大小       24 (0x18)
  .maxstack  1
  .locals init ([0] int32 i)
  IL_0000:  nop
  IL_0001:  ldc.i4.s   123
  IL_0003:  stloc.0
  IL_0004:  ldloca.s   i
  IL_0006:  call       instance string [mscorlib]System.Int32::ToString()
  IL_000b:  call       void [mscorlib]System.Console::WriteLine(object)
  IL_0010:  nop
  IL_0011:  call       int32 [mscorlib]System.Console::Read()
  IL_0016:  pop
  IL_0017:  ret
} // end of method Program::Main

没有装箱的操作，ToString()就转成了字符串，但不发生装箱操作。

#33

不过有个疑问就是  整型到字符串，不是值类型到引用类型吗？为什么不存在装箱？

#34

引用 32 楼  的回复:

恩，通过IL查看明白了，还是基础知识不牢固

C# code
 int i = 123;
            Console.WriteLine((object)i.ToString());



Assembly code
.method private hidebysig static void  Main(string[] args) cil managed
{
  .e……

ToString是一个基类的方法，这个方法在Object中就存在。所以根本不需要拆就可以直接调用。

#35

性能的问题根本就不是问题。可读性的问题，才是大问题。

#36

。。。http://community.csdn.net/help/GetUsablePoint.htm

#37

代码应该先保证可读性。
关于性能，只有通过测试，某段确实有性能问题，才会牺牲可读性换取性能。
不要一开始就纠结于性能。

#38

不要函数调用  所有东西写在一起，性能最好

#39

引用 2 楼  的回复:

这种设计,要是被sp1234看到
肯定又是一顿喷

是啊！

这个也算是for语句的问题？你有字典，还要写什么

    foreach (KeyValuePair<string, int> pair in name_id)
    {
        if (pair.Key.IndexOf(key) >= 0)

难道你不知道什么叫做hash？如果不知道，至少你可以知道对数据集合进行索引或者排序（然后二分查找）吧？！

不懂数据结构和算法，却把这种巨大的速度差别归结为什么“for语句”，我不知道是不是拿那些没有正规学过软件专业课的同学故意开涮啊？！

这样的标题党来误导别人可不好哦！

#40

忍不住给楼主提个方案

思路：通过建立单词索引，缩小搜索范围
算法：
S1.对标题分词，建立 关键词 到 标题集合 的映射（剔除那些集合过大的单词）
S2.对用户输入分词W[1..n]
S3.找出词频最小的词 Wmin ，（词频:关键词对应的集合大小)
   S3.1  在映射中找出 Wmin 对应的标题集合,调用楼主原有算法          
         return
   S3.2. 所有的词都不出现在关键词中
         调用楼主原有算法         
         return
分析：
    S1是预计算步骤，仅在初次加载标题时执行，若标题有变化，那么动态调整映射
    耗时可以平摊到后序查找过程中，于是代价忽略
    S2 分词可以快速完成，代价较小
    S3 如果大多数情况下能在S3.1处结束，极少数在S3.2结束，且S3.1比S3.2快出许多
    那么查找的平均性能会提高

#41

引用 39 楼  的回复:

难道你不知道什么叫做hash？如果不知道，至少你可以知道对数据集合进行索引或者排序（然后二分查找）吧？！

不懂数据结构和算法，却把这种巨大的速度差别归结为什么“for语句”，我不知道是不是拿那些没有正规学过软件专业课的同学故意开涮啊？！

这样的标题党来误导别人可不好哦！

楼主的问题没这么简单吧，不过可以判断楼主确属标题党

#42

境界太高了

#43

引用 34 楼  的回复:

引用 32 楼  的回复:

恩，通过IL查看明白了，还是基础知识不牢固

C# code
int i = 123;
Console.WriteLine((object)i.ToString());



Assembly code
.method private hidebysig static void  Main(string[] args) cil managed
……

恩，我也觉得是因为ToString的操作是针对基类做的优化。另外string也不是引用类型，所以不存在装箱，因为在赋值string的时候是拷贝了一份，如果是引用类型就直接赋值一个引用了。

#44

引用 39 楼  的回复:

引用 2 楼  的回复:
这种设计,要是被sp1234看到
肯定又是一顿喷

是啊！

这个也算是for语句的问题？你有字典，还要写什么
C# code
    foreach (KeyValuePair<string, int> pair in name_id)
    {
        if (pair.Key.IndexOf(key) >= 0)

难道你不知道什么叫做……

CSDN中热心的大牛。
可以展示点示例代码那就更完美了，毕竟像我这种菜鸟有时更需要简单的例子。

#45

该回复于2012-07-24 10:40:27被版主删除

#46

不知道你想干什么, 全文搜索?

你这个foreach对每篇文章都做了一次indexOf这个 复杂度是 O(文章数量*文章长度) 
我觉得不太可能比sql的算法还快

#47

why not using Lucene.NET?

#48

你的代码肯定没有问题，当数据量大的时候出了问题，就要掂量下你的思路是否需要改变了
你的代码其实做了两件事情，“查找”和“匹配”，如果你把他们分开，你确保你只要查找就是你想要的结果就可以了

#49

楼主的例子恰恰生动地说明了，单纯地抠语法而不注重大局的性能。

不管是Hash还是二分法都比你这种原始的循环效率高出几个数量级。

还一再提要用obj.Tostring()来代替obj.
那你试试这个吧。

obj =null;
obj.ToString();
结果会怎样？

#50

算法问题。SP1234没说错。
可以考虑NON SQL啊,IN MEMORY db a...