vector與map...怎麼選擇

平常我們在寫程式時,經常可以用很多方法來解決
不過寫到後來,可能會因為客戶要求, 程式品質, 或者挑戰自己
而想要用比較有效率的方法
這時候,什麼是有效率的,沒比較過是不會知道的
我們在寫C++程式時,一定都知道STL,常用的排序與尋找的方法
就是vector 搭配binary_search 以及map這二個較多了

以下的程式碼(BCB5),就把這2個做了一個比較(200萬筆)
//---------------------------------------------------------------------------

#include < vcl.h >
#pragma hdrstop
#include < iostream >
#include < vector >
#include < list >
#include < map >
#include < ctime >
#include < stdio.h >
#include < time.h >
//---------------------------------------------------------------------------
#pragma argsused

using namespace std;

int main(int argc, char* argv[])
{

//vector
        vector  v;
        vector ::iterator it;

        v.push_back( 10 );

        cout << "vector container " << endl << "================" << endl << endl;
        time_t t1; time(&t1);
        for(int i=0;i<2000000;i++)
                v.push_back(i);
//            v.insert( v.begin( ) , i );
        time_t t2; time(&t2);
        cout<<" vcetor insert data , the time it takes is " << t2-t1 << " sec." << endl;

        sort(v.begin(),v.end());

        int a;
        time_t t5; time(&t5);
        for(int i=0;i<2000000;i++)
        {
            srand(time(NULL));
            a=(rand() % 2000000) +1;
            bool b1 = binary_search(v.begin(),v.end(),a);
        }
        time_t t6; time(&t6);
        cout<<" vcetor search data , the time it takes is " << t6-t5 << " sec." << endl;


        time_t t3; time(&t3);
        v.erase (v.begin(),v.begin()+2000000);
        time_t t4; time(&t4);
        cout <<" vcetor erase data , the time it takes is " << t4-t3 << " sec." << endl ;
//map
      map< int,int > mymap;
      map< int,int >::iterator map_it;
      pair< map< int,int >::iterator,bool > ret;


      mymap.insert ( pair< int,int >(0,100) );

      cout << endl << "map container " << endl << "================"  << endl;
      time_t map_t1; time(&map_t1);
      for(int i=1;i<2000000;i++)
          mymap.insert ( pair(i,2000000+i) );
      time_t map_t2; time(&map_t2);
      cout << endl <<" map insert data , the time it takes is " << map_t2-map_t1 << " sec." << endl;


      int c;
      time_t map_t5; time(&map_t5);
      for(int i=0;i<2000000;i++)
      {
          srand(time(NULL));
          c=(rand() % 2000000) +1;
          map_it=mymap.find(c);
      }
      time_t map_t6; time(&map_t6);
      cout<<" map search data , the time it takes is " << map_t6-map_t5 << " sec." << endl;



      time_t map_t3; time(&map_t3);
      mymap.erase(mymap.begin(),mymap.end());
      time_t map_t4; time(&map_t4);
      cout  <<" map erase data , the time it takes is " << map_t4-map_t3 << " sec." << endl << endl;

      system("pause");
      return 0;
}
//---------------------------------------------------------------------------

以下是執行結果,可以明顯看出,vector與binary_search的組合是比較有效率的
你不禁會懷疑,是不是巧合(因為random),執行幾次後,還是一樣

vector container
================

 vcetor insert data , the time it takes is 0 sec.
 vcetor search data , the time it takes is 4 sec.
 vcetor erase data , the time it takes is 0 sec.

list container
================

 list insert data , the time it takes is 0 sec.

 list erase data , the time it takes is 1 sec.

map container
================

 map insert data , the time it takes is 8 sec.
 map search data , the time it takes is 5 sec.
 map erase data , the time it takes is 1 sec.

請按任意鍵繼續 . . .

從上面的比較可以得知,vector與binary_search的合作似乎都比較好
那為什麼還要用到map,答案隱藏在上面vector程式碼裡用雙斜線mark掉那行
如果我vector都一直insert在第1筆,那效率就很慘了(可以打開來試看看)
況且,如果你的情況,是要一邊insert , 排序, search
那猜測這樣的結果可能不見得會是vector跟binary_search會比較好了(因為不是push_back)
筆者試過,每push_back 1筆就排序一次,只要2萬筆,...就慢到不行

所以建議:
(1)如果資料一剛開始就確定範圍,可以用vector 與binary_search來處理
(2)如果資料使用中不斷變化,簡單方法可以用map
(3)承(2),如果一定要用vector,比較常遇到的解法是
   1)不要用sort,改用lower_bound或upper_bound來決定插入資料的位置
   2)因為sort資料會花時間,尤其是資料量大時,如果還是要用sort,那就原始資料一律用vector.push_back,
     另外建一個vector來與原始資料對應序號(KEY),針對這個KEY的vector進行SORT
     會有效率得多,不過在做erase時,請記得2方都要刪除
      (當然KEY的vector也可運用1)的技巧)

以下補充:以下參考(http://hi.baidu.com/litinglong2010/blog/item/6b55d23962cbabca9f3d6215.html)

vector中存儲資料 標準關聯容器(map)
概要：在有序vector中存儲資料很有可能比在標準關聯容器中保存相同的資料消耗更少的記憶體；
當頁面錯誤值得重視的時候，在有序vector中通過二分法查找可能比在一個標準關聯容器中查找更快。 

當然，有序vector的大缺點是它必須保持有序！當一個新元素插入時，大於這個新元素的所有東西都必須向上移一位。
它和聽起來一樣昂貴，如果vector必須重新分配它的內在記憶體（參見條款14），則會更昂貴，
因為vector中所有的元素都必須拷貝。同樣的，如果一個元素從vector中被刪除，所有大於它的元素都要向下移動。
vector的插入和刪除都很昂貴，但是關聯容器的插入和刪除則很輕量。這就是為什麼只有當你知道
你的資料結構使用的時候查找幾乎不和插入和刪除混合時，使用有序vector代替關聯容器才有意義。 

本條款有很多文字，但不幸的是只有很少的例子，所以我們來看看一個使用有序vector代替set的代碼骨架： 

vector < Widget > vw; // 代替set < Widget > 
... // 建立階段：很多插入， 
// 幾乎沒有查找 
sort(vw.begin(), vw.end()); // 結束建立階段。（當 
// 模擬一個multiset時，你 
// 可能更喜歡用stable_sort 
// 來代替；參見條款31。） 
Widget w; // 用於查找的值的對象 
... // 開始查找階段 
if (binary_search(vw.begin(), vw.end(), w))... // 通過binary_search查找 
vector < Widget > ::iterator i = 
lower_bound(vw.begin(), vw.end(), w); // 通過lower_bound查找 
if (i != vw.end() && !(w < *i))... // 條款19解釋了 
// “!(w < *i)”測試 
pair < vector < Widget > ::iterator, 
vector < Widget > ::iterator > range = 
equal_range(vw.begin(), vw.end(), w); // 通過equal_range查找 
if (range.first != range.second)... 
... // 結束查找階段，開始 
// 重組階段 
sort(vw.begin(), vw.end()); // 開始新的查找階段... 

就像你可以看到的，這非常直截了當。裏面最難的東西就是怎麼在搜索演算法中做出選擇（比如，binary_search、lower_bound等），條款45可以幫你做出選擇。 

當你決定用vector代替map或multimap時，事情會變得更有趣，因為vector必須容納pair物件。
畢竟，那是map和multimap所容納的。但是要注意，如果你聲明一個map < K, V > 的物件
（或者等價的multimap），保存在map中的元素類型是pair < const K, V > 。
如果要用vector模擬map或者multimap，你必須去掉const，因為當你對vector排序時，
它的元素的值將會通過賦值移動，那意味著pair的兩個元件都必須是可賦值的。
當使用vector來模擬map < K, V > 時，保存在vector中資料的類型將是pair < K, V > ，
而不是pair < const K, V > 。 

map和multimap以順序的方式保存他們的元素，但用於排序目的時它們只作用於元素的key部分
（pair的第一個元件），所以當排序vector時你必須做一樣的事情。你需要為你的pair寫一個
自定義比較函數，因為pair的operator < 作用於pair的兩個組件。 

有趣的是，你會需要第二個比較函數來進行查找。用來排序的比較函數將作用於兩個pair物件，
但是查找只用到key值。必須傳給用於查找的比較函數一個key類型的物件（要查找的值）和一個pair
（存儲在vector中的一個pair）——兩個不同的類型。還有一個附加的麻煩，你不會知道key還是pair
是作為第一個實參傳遞的，所以你真的需要兩個用於查找的比較函數：一個key值先傳遞，一個pair先傳遞。 

這個例子演示了怎麼把這些東西合在一起： 

typedef pair < string, int > Data; // 在這個例子裏 
// "map "容納的類型 
class DataCompare { // 用於比較的類 
public: 
bool operator()(const Data& lhs, // 用於排序的比較函數 
const Data& rhs) const 
{ 
return keyLess(lhs.first, rhs.first); // keyLess在下麵 
} 

bool operator()(const Data& Ihs, // 用於查找的比較函數 
const Data::first_type& k) const // （形式1） 
{ 
return keyLess(lhs.first, k); 
} 

bool operator()(const Data::first_type& k, // 用於查找的比較函數 
const Data& rhs) const // （形式2） 
{ 
return keyLessfk, rhs.first); 
} 

private: 
bool keyLess(const Data::first_type& k1, // “真的” 
const Data::first_type& k2) const // 比較函數 
{ 
return k1 < k2; 
} 
}; 

在這個例子中，我們假設有序vector將模擬map < string, int > 。
這段代碼幾乎是上面討論的字面轉換，除了存在成員函數keyLess。
那個函數的存在是用來保證幾個不同的operator()函數之間的一致性。
每個這樣的函數只是簡單地比較兩個key的值，所以我們把這個測試放在keyLess中並讓operator()
函數返回keyLess所做的事情，這比複製那個邏輯要好。
這個軟體工程中絕妙的動作增強了DataCompare的可維護性，但有一個小缺點，
它提供了有不同參數類型的operator()函數，這將導致函數物件無法適配（看見條款40）。
噢，好了。 

把有序vector用作map本質上和用作set一樣。唯一大的區別是必須把DataCompare物件用作比較函數： 

vector < Data > vd; // 代替map < string, int > 
... // 建立階段：很多插入， 
// 幾乎沒有查找 
sort(vd.begin(), vd.end(), DataCompare()); // 結束建立階段。（當 
// 模擬multimap時，你 
// 可能更喜歡用stable_sort 
// 來代替；參見條款31。） 
string s; // 用於查找的值的對象 
... // 開始查找階段 
if (binary_search(vd.begin(), vd.end(), s, 
DataCompare()))... // 通過binary_search查找 
vector  ::iterator i = 
lower_bound(vd.begin(), vd.end(), s, 
DataCompare()); // 在次通過lower_bound查找， 
if (i != vd.end() && !DataCompare()(s, *i))... // 條款45解釋了 
// “!DataCompare()(s, *i)”測試 
pair < vector < Data > ::iterator, 
vector < Data > ::iterator > range = 
equal_range(vd.begin(), vd.end(), s, 
DataCompare()); // 通過equal_range查找 
if (range.first != range.second)... 
... // 結束查找階段，開始 
// 重組階段 
sort(vd.begin(), vd.end(), DataCompare()); // 開始新的查找階段... 

正如你所見，一旦你寫了DataCompare，東西都很好的依序排列了。而一旦位置合適了，
只要你的程式按照101頁描述的階段方式使用資料結構，它們往往比相應的使用真的map的設計
運行得更快而且使用更少記憶體。如果你的程式不是按照階段的方式操作資料結構，
那麼使用有序vector代替標準關聯容器幾乎可以確定是在浪費時間。

free -- cached and buffers(2)

一般程式在執行，與進入CPU大致上會有幾個資料搬移的作業

Disk(code) <--> RAM <--> L2 Cache <--> L1 Cache(inside CPU)

當程式要執行時會愈往右邊走，執行完畢時，會慢慢走回左邊，如果都用不到，始終回到只剩DISK

以上的Cache跟主題要講的Cached有些類似，但不是指同一件事

一支程式要執行時，會有需要將使用的資料從File(Disk)讀起來使用的時候

讀起來就會進入RAM，但結束時理當要釋放這個RAM給其他程式使用

Linux考量到其他的程式可能也會用到，所以會先Cache住，如果有要用到，可以馬上反應使用

這是指在DRAM充裕的狀況下，如此運作對效能有幫助

但如果因為導致實體記憶體被吃光，而使用到Swap空間時，就輪到CPU倒楣

使用上應特別注意

其中的 Cached Memory 會依據系統的使用狀況做動態調整,借此以提高系統效能. /proc/sys/vm/drop_caches 的預設值為 0,也就是啟動 cache 的功能.如果你不喜歡這些功能或者覺得它不夠Smart的話,可以把他取消掉.在 Kernel 2.6.16 之後的本版可以透過 /proc/sys/vm/drop_caches 來釋放 Cached Memory

釋放 pagecache 所使用的 Cached Memory.

[root@localhost]# echo 1 > /proc/sys/vm/drop_caches

釋放 dentries,inodes 所使用的 Cached Memory.

[root@localhost]# echo 2 > /proc/sys/vm/drop_caches

釋放 pagecache,dentry,inode 所使用的 Cached Memory.

[root@localhost]# echo 3 > /proc/sys/vm/drop_caches

以下參考自: http://ssorc.tw/rewrite.php/read-599.html

其他說明可見：http://forums.gentoo.org/viewtopic.php?p=1155852

free

total used free shared buffers cached

Mem: 1023916 975816 48100 0 26376 465844

-/+ buffers/cache: 483596 540320

Swap: 2096440 105564 1990876

計算方式

total used free shared buffers cached

Mem: a b c d e f

-/+ buffers/cache: g h

Swap: i j ka = 總記憶體大小

b = 配給 buffers 與 cache 的記憶體大小(包含未用的 buffers 與 cache)

c = 剩下的記憶體大小

e = 配給 buffers 但未用的記憶體大小

f = 配給 cache 但未用的記憶體大小

g = buffers 與 cache 被使用掉的記憶體大小，也就是實際被應用程式用走的

h = 那這個就是實際剩下的記憶體大小

a = b + c

a = g + h

g = b - e - f

h = c + e + f

buffer 與 cache 的區別:

A buffer is something that has yet to be "written" to disk.

A cache is something that has been "read" from the disk and stored for later use.

一般情況下，Linux kernel 會盡可能多地利用 RAM 的空閑空間作為 cache/buffer 以最大幅度地提高系統性能。當系統中運行的應用程序占用的 RAM 增加時，則將 cache/buffer 所占用的空間釋放出來，讓渡給應用程序使用。

Mem: 那一行顯示了實際記憶體的使用率；

Swap: 顯示的是系統 swap 空間的使用率；

-/+ buffers/cache: 則是目前撥給系統緩衝區的實體記憶體數量。

記憶體管理的概觀

當系統開機一段時間後，像是「top」這種傳統的 Unix 工具常常回報少的可憐的可用記憶體數值，在我寫這篇文章的系統中，就算我總共有 512 MB 的記憶體在我的系統裡，但約開機m後三個小時，我只剩下 60 MB 的可用記憶體，那些記憶體到底跑到那裡去了？

用掉最多記憶體的地方是磁碟快取 (disk cache)，目前它總共用了超過 290 MB 的記憶 (在 top 裡的「cached」項目中)，快取記憶體 (cached memory) 基本上是空閒的，當有新/執行中的程式需要記憶體的話，它會快速的被取回來。

為什麼 Linux 使用這麼多的記憶體來當作磁碟快取 (disk cache) 呢？主要的原因便是：假如 RAM 沒有被使用的話，它便是閒放在那邊浪費著不用。如果把資料放在用 RAM 組成的磁碟上，它的存取速度比直接從硬碟上存取還要快上 1000 倍。假如在快取裡找不到該資料，當然還是得直接從磁碟裡存取，但就如同上面說的，您將可以節省些微的存取時間。

Out of Memory

more /var/log/messages

kernel: Mem-info:

kernel: Zone:DMA freepages: 2916 min: 0 low: 0 high: 0

kernel: Zone:Normal freepages: 758 min: 766 low: 4031 high: 5791

kernel: Zone:HighMem freepages: 125 min: 253 low: 506 high: 759

kernel: Free pages: 3799 ( 125 HighMem)

kernel: ( Active: 237940/1195, inactive_laundry: 1, inactive_clean: 0, free: 3799 )

kernel: aa:0 ac:0 id:0 il:0 ic:0 fr:2916

kernel: aa:209592 ac:2087 id:1190 il:1 ic:0 fr:758

kernel: aa:26033 ac:232 id:0 il:0 ic:0 fr:125

kernel: 0*4kB 2*8kB 4*16kB 2*32kB 4*64kB 2*128kB 1*256kB 1*512kB 0*1024kB 1*2048kB 2*4096kB = 11664kB)

kernel: 8*4kB 1*8kB 175*16kB 6*32kB 0*64kB 0*128kB 0*256kB 0*512kB 0*1024kB 0*2048kB 0*4096kB = 3032kB)

kernel: 1*4kB 0*8kB 1*16kB 1*32kB 1*64kB 1*128kB 1*256kB 0*512kB 0*1024kB 0*2048kB 0*4096kB = 500kB)

kernel: Swap cache: add 5156731, delete 5156620, find 19439534/21006374, race 0+19

kernel: 4115 pages of slabcache

kernel: 1566 pages of kernel stacks

kernel: 13 lowmem pagetables, 5378 highmem pagetables

kernel: 32 bounce buffer pages, 32 are on the emergency list

kernel: Free swap: 0kB

kernel: 261760 pages of RAM

kernel: 32384 pages of HIGHMEM

kernel: 5781 reserved pages

kernel: 14591 pages shared

kernel: 116 pages swap cached

kernel: Out of Memory: Killed process 25580 (java).

free -- cached and buffers(1)

以下參考自:http://egloo.wordpress.com/2008/10/29/linux-cached-memory/
In Linux, reading from a disk is very slow compared to accessing real memory. In addition, it is common to read the same part of a disk several times during relatively short periods of time. For example, one might first read an e-mail message, then read the letter into an editor when replying to it, then make the mail program read it again when copying it to a folder. Or, consider how often the command ls might be run on a system with many users. By reading the information from disk only once and then keeping it in memory until no longer needed, one can speed up all but the first read. This is called disk buffering, and the memory used for the purpose is called the buffer cache.

Unlike (Windows) other operating systems, Linux administers memory the smartest way it can.

Since unused memory is next to worthless, the filesystem takes whatever memory is left and caches it in order to speed up disk access. When the cache fills up, the data that has been unused for the longest time is discarded and the memory thus freed is used for the new data.

Whenever an application needs memory, the kernel makes the cache smaller; You do not need to do anything to make use of the cache, it happens completely automatically.

Freeing memory buffer does not make your programs faster… Actually it makes disk access slower.

BUT if for some reason (kernel debugging for example) you want to force the buffer to be freed, you need to set the drop_caches value to 1:

$ echo 1 > /proc/sys/vm/drop_caches
Issuing this command will release all the cached memory and also will stop collecting I/O buffer blocks. Let’s see an example of the effect:




Under normal situations, most of the memory is already cached by the system. But if we force the system to free the memory, you can see in the graph how the memory is suddenly dropped.

The technical details of how this works are explained on the Linux API