小是美丽的,但它也快吗？

Question

我和同事讨论过简单字符串解析器的实现.一个是"小",10行代码,使用c ++和流,另一个是70行代码,使用switch case并通过char迭代字符串char.我们测试了超过100万次迭代,并使用时间命令测量速度.似乎漫长而丑陋的方法平均快1秒.

问题:输入:字符串

"v=spf1 mx include:_spf-a.microsoft.com include:_spf-b.microsoft.com include:_spf-c.microsoft.com include:_spf-ssg-a.microsoft.com ip4:131.107.115.212 ip4:131.107.115.215 ip4:131.107.115.214 ip4:205.248.106.64 ip4:205.248.106.30 ip4:205.248.106.32 ~all a:1.2.3.4"

输出: map<string, list<string>>包含每个键的所有值,例如:ip4,include,a

上面给出的输入字符串上的一次迭代的示例输出:

关键:一

1.2.3.4,

关键:包括

_spf-a.microsoft.com,_spf-b.microsoft.com,_spf-c.microsoft.com,_spf-ssg-a.microsoft.com,

关键:IP4

131.107.115.212,131.107.115.215,131.107.115.214,205.248.106.64,205.248.106.30,205.248.106.32,

"小而美"的解析器:

        istringstream iss(input);
        map<string, list<string> > data;
        string item;
        string key;
        string value;

        size_t pos;
        while (iss.good()) {
                iss >> item;
                pos = item.find(":");
                key = item.substr(0,pos);
                data[key].push_back(item.substr(pos+1));
        }

第二种更快的方法:

  typedef enum {I,Include,IP,A,Other} State;
  State state = Other;
  string line = input;
  string value;
  map<string, list<string> > data;
  bool end = false;
  size_t pos = 0;
  while (pos < line.length()) {
   switch (state) {
    case Other:
     value.clear();
     switch (line[pos]) {
      case 'i':
       state = I;
       break;
      case 'a':
       state = A;
       break;
      default:
       while(line[pos]!=' ' && pos < line.length())
        pos++;
     }
     pos++;
     break;
    case I:
     switch (line[pos]) {
      case 'p':
       state = IP;
       break;
      case 'n':
       state = Include;
       break;
     }
     pos++;
     break;
    case IP:
     pos+=2;
     for (;line[pos]!=' ' && pos<line.length(); pos++) {
      value+=line[pos];
     }
     data["ip4"].push_back(value);
     state = Other;
     pos++;
     break;
    case Include:
     pos+=6;
     for (;line[pos]!=' ' && pos<line.length(); pos++) {
      value+=line[pos];
     }
     data["include"].push_back(value);
     state = Other;
     pos++;
     break;
    case A:
     if (line[pos]==' ')
      data["a"].push_back("a");
     else {
      pos++;
      for (;line[pos]!=' ' && pos<line.length(); pos++) {
       value+=line[pos];
      }
     }
     data["a"].push_back(value);
     state = Other;
     pos++;
     break;
   }
  }

我真的相信"小而美"是要走的路,我不喜欢这里提出的更长的代码,但是当代码运行得更快时,很难争论它.

您是否可以建议一种优化或完全重写小方法的方法,在这种方法中,它保持小巧美观但运行速度更快？

更新:添加状态定义和初始化.上下文:较长的方法在15.2秒内对同一个字符串完成100万次迭代,较小的代码平均在16.5秒内完成相同的操作.

两个版本都使用g ++ -O3,g ++ - 4.4编译,运行在Intel(R)Core(TM)2 Duo CPU E8200 @ 2.66GHz,Linux Mint 10上

好的方面已经赢得了这场战斗:)我在小程序中发现了小错误,它甚至在地图中添加了无效值,在字符串中没有":"冒号.添加"if"语句以检查是否存在冒号后,较小的代码运行得更快,速度更快.现在的时间是:"小而美":12.3又长又丑:15.2.

小很漂亮:)

Answer 1

较小可能不会更快.一个例子:冒泡排序很短,但它是O(n*n).QuickSort和MergeSort更长,看起来更复杂,但它是O(n log n).

但是说过......始终确保代码是可读的,或者如果逻辑很复杂,请添加好的注释,以便其他人可以关注.

Answer 2

减少代码行数; 更好.如果你真的不需要,不要添加60行.如果它很慢,简介.然后优化.在您需要之前不要进行优化.如果运行正常,请保持原样.添加更多代码会增加更多错误.你不希望这样.保持简短.真.

阅读此维基帖子.

"过早的优化是所有邪恶的根源" - 唐纳德克努特,一个非常聪明的家伙.

通过编写更少的代码,更智能地编写更快的代码是可能的.提高速度的一种方法:少做.

引用雷蒙德陈:

"我得到的一个问题是,"我的应用程序启动缓慢.你们在微软用来让你的应用程序更快启动的超级秘密邪恶伎俩是什么？"答案是,"超级恶魔的伎俩就是做更少的东西." - "每个Win32程序员需要知道的五件事"(2005年9月16日)

另外,看看为什么GNU grep很快.