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

Question

前一帖子参考：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的执行时间想起了一句话：勿以善而不为。不要以为性能改善极其微小，就按自己的想法去做

Answer 1

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

Answer 2

设计的问题由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>
这样就不用装箱了
别喷我,我知道这是错误的

Answer 3

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

Answer 4

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

Answer 5

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

Answer 6

写这个帖子的目的，也有等大师来喷的意思
因为个人水平的确有限等待SP1234或Cao中
指点下小弟，就标题这个应用 如何设计，效率最高？

Answer 7

    
没有抠语句的性能
只在外面多加了一个精确缓存
可能性能会更差/// <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;
        }
    }

Answer 8

答复楼上：“最好能从标题里提取关键字填充这个缓存”这个就是SqlServer或一些开源的全文检索做的事情，这个对中文分词的支持，始终不是很好，百度的效果都做的不是很好，所以我才一直使用类似SQL的 like '%关键词%' 方案目前我的核心代码就是一楼写的那样，然后外层对一些常见关键字做HttpRuntimeCache的缓存
再就是多台机器用lvs做负载均衡了真心希望有好算法，我个人是想不到更好的方案了

Answer 9

修改成下面这样
性能继续提升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()

Answer 10

你这个把装箱放到索引生成里去了
但是sb.AppendFormat("{0},", object);
最终还是调用了Int.ToString(string format, IFormatProvider provider)跟我在一楼写的方法没有区别

Answer 11

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，将排序结果生成检索结果的最终列表，提供给检索用户。 
如果这是事实，那么谷歌也是全文分词？？那连“的都”这样的非词组也分？那它的索引得多大？这么大的索引，如何快速搜索？
有没有人了解？或者指点下小弟，如果改善我那简单的搜索接口

Answer 12

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

Answer 13

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

Answer 14

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

Answer 15

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

Answer 16

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

Answer 17

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

Answer 18

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

Answer 19

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

Answer 20

恩，通过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()就转成了字符串，但不发生装箱操作。

Answer 21

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

Answer 22

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

Answer 23

是啊！这个也算是for语句的问题？你有字典，还要写什么
    foreach (KeyValuePair<string, int> pair in name_id)
    {
        if (pair.Key.IndexOf(key) >= 0)
难道你不知道什么叫做hash？如果不知道，至少你可以知道对数据集合进行索引或者排序（然后二分查找）吧？！不懂数据结构和算法，却把这种巨大的速度差别归结为什么“for语句”，我不知道是不是拿那些没有正规学过软件专业课的同学故意开涮啊？！这样的标题党来误导别人可不好哦！

Answer 24

忍不住给楼主提个方案思路：通过建立单词索引，缩小搜索范围
算法：
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快出许多
    那么查找的平均性能会提高

Answer 25

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

Answer 26

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

Answer 27

不知道你想干什么, 全文搜索?你这个foreach对每篇文章都做了一次indexOf这个 复杂度是 O(文章数量*文章长度) 
我觉得不太可能比sql的算法还快

Answer 28

why not using Lucene.NET?

Answer 29

楼主的例子恰恰生动地说明了，单纯地抠语法而不注重大局的性能。不管是Hash还是二分法都比你这种原始的循环效率高出几个数量级。还一再提要用obj.Tostring()来代替obj.
那你试试这个吧。obj =null;
obj.ToString();
结果会怎样？

Answer 30

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

Answer 31

别的不想说，
就光看你写这个， 敢说比sqlserver自己处理的好？

Answer 32

sql啥的咱是白痴,不扯那个,就代码看起来LZ是想实现在标题中查找指定关键字.
同时标题却又作为hash的key了.于是干脆就遍历这种情况其实用SortedDictionary更好吧?hash的存储可不保证给你按序排放啊.
按key排序后再二分查找如sp1234所说比你现在的方式效率高了不是一点半点啊..放下这个不说,那
sb.AppendFormat("{0},", pair.Value);
明显不如
sb.Append(pair.Value.ToString());
sb.Append(',');至于后面那个
sb.AppendFormat("{0},", pair.Value.ToString());
LZ你是在卖萌吧?既然效率都那么差了你还弄个格式字符串去让它解析一下,完了还让它判断下参数类
型后给你copy到指定位置?最后:
hash表和stringbuilder真心不是这么用的...

Answer 33

你这问题与for有什么关系啊？你对一个dictionary进行遍历（我从来没见过），功能退化为vector，性能和所占内存以及构造还不如vector。楼主的问题是一个非常复杂的算法问题。我也没想到好的办法，所以就不说了。我很想知道的是，楼主修改代码之后，性能提高了吗？我不太信。
就算提高了一点点，那也是因为你for循环太多的问题，如果你的for循环占用了90%的cpu（夸张一点，明白我的意思即可），那么在for循环里面稍微优化一下，的确是提高不少性能，但这是建立在你设计错误的基础之上的（比如你举的例子）——为什么for循环要占用这么多的cpu？

Answer 34

当然，如果什么算法都非要让for循环占用很高的CPU（新算法还没发明），那么仅仅在这种情况下，楼主你说对了，的确应该在for循环里面疯狂优化而不注重可读性。可是，这种例子有多少呢？除了楼主举的这个严重设计错误的例子。

Answer 35

至于循环，摘录一句其他地方的话吧：
Prefer while and foreach over other available looping constructs when applicable. They are logically simpler and easier to code and debug.

Answer 36

弱弱的说一下。。Dictionary<K,V>的TryGetValue方法比先判断ContainsKey再GetValue的做法效率更佳

Answer 37

严重同意。
程序=数据结构+算法。不是if else new;

Answer 38

至于为什么，只有自己做了实际的测试才知道。
微软的MVC框架里的源代码，也是这么用的

Answer 39

我知道TryGetValue效率高
我9楼的代码也是使用TryGetValue
我就是问你为什么嘛?
为什么呢?

Answer 40

引用#1楼:这段代码上线后，执行效率不是很好，后来通过性能工具测试，发现问题比较大的一个地方，就是
IndexOf(key)和AppendFormat("{0},", pair.Value)占用了大约30%的执行时间-----
这怎么看都是因为IndexOf()占的时间长啊.  
怎么会想到去pair.Value.ToString()的? 加了之后估计也没效果的吧. 也许快个0.1%?真正的问题怎么看都是IndexOf()

Answer 41

在平时，有人经常跟那些连涉及“for”语句简单逻辑程序的人共事的么？我遇到这样的人，会非常可怜自己“怎么会遇到这种事儿？”。但是你遇到了一个号称“负责日访问千万次，几十万条数据的简单查找”的人，只会写个for语句，此时我的心情更加沉重。如果程序员说“hash查找、而分查找、索引树查找的概念，是高深和复杂的，我想都不会想到”，那么我已经没有必要去讨论程序改进问题了，这时候已经打破了开发的底线——应该赶紧想到如何体面地结束的问题了。

Answer 42

那些连涉及“for”语句简单逻辑程序的人   -->  那些都会组织涉及“for”语句简单逻辑程序的人
好容易经过公司“培养”一些人会写for语句了，但是离公司的要求可能还是差的冤，我们还是要明白这种差距啊。公司起码要用一个懂得使用基本《数据结构》（或者《算法》）知识的人啊。怎么能动不动就说基本数据结构知识是什么“高深、复杂”的知识呢？难道吃饭、挣工资不复杂么？