ネコナゾ娘 (・∀・)

      今天在写代码的时候，要用到动态数组，我就很自然的选择了 MFC 的 CArray ，就这样写，中间有一个地方不熟悉，于是就向另一个同事询问了一下，他说 你用 CArray 的什么函数怎么干就好了啊。于是我试了一下， CArray 没有那样的成员函数，= =，于是，我就翻出 VC 开发宝典，查了一下。没想到恰好被那个同事给看到了，就随口问了一句，你在查什么呢，我说 CArray 的函数呗。没想到他居然惊奇了，VC里面有 CArray 么 .....
      原来我们公司的代码库里面已经有一个动态数组了，CAry ，他一直用的是那个，然后越用越 happy ，自然就不知道MFC里面也有一个了。我于是很好奇了，去看了下 CAry 的头文件，果然是很好用，成员函数比 CArray 封装的多，我就很好奇了。尤其是知道 CArray索引元素的访问时间是不变的，与数组大小无关 的特性之后，更想知道公司代码库的CAry 性能怎么样。
     于是我对 CArray 和 CAry 分别作了下面的测试      然后记录下结果
     名字             插入用时   插入时CPU            访问用时          内存占用
     CArray         60s            ~50%              0.906ms            > 4M
     CAry            78s            ~50%              1.375s              < 60M
 从中可以看出 双方在插入时 都占了 50% 的 CPU( E4500 双核中的一个被完全占用)，而且插入时要比访问时更费时，CArray 应该是 O(1) ， CAry至少也是 O(logN)，也有可能是 O(1)，不过我对O(1)表示怀疑(因为CAry的源码似乎使用了树，只是撇了一下)。而且说内存，CArray 存储 1M 个 int (至少占有 1M * 4) 居然只占用了 4M多一点 ，利用效率意外的高。而且从插入时的内存变化来看(内存成块增长，有时伴随着内存的释放)可以猜测，CArray 使用了类似 realloc 的方法合并了小内存块(指分配一块更大的内存，并释放先前分配的小内存块，所以，它是 O(1) 访问的)。 
    最后又用 lua 做了同样的测试，代码如下        结果是相当惊人的，插入元素居然没有花什么时间!!!! Very Surprise!! 至于访问时，则花了 4.36s，考虑到脚本的效率，也是令人很满意的了，lua使用的 hash table 查找效率显然是 O(1) 的。然后我从新跑了一下，这下发现了，看见内存直接涨了 16M多一点(注，lua内部数字使用 double类型，而且hash table 内存利用率为 50% ， 1M * 8 * 2)，我就怀疑也许lua在编译的时候，把它给简化了，然后就直接分配了那么多内存，也就是说只分配了一次内存就完事了。