STL Map的用處

這是練習leetcode時所看到的範例

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

看到這個大部分人都很直覺地會想到透過兩個for loop
把所有組合窮舉出來
這樣做法的時間複雜度是O(n)，空間複雜度O(1)

public int[] twoSum(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[j] == target - nums[i]) {
                return new int[] { i, j };
            }
        }
    }
    throw new IllegalArgumentException("No two sum solution");
}

那麼如果使用了Map呢(Map<key, value>)
Map是透過雜湊表(hash table)把我們所input的key轉換為value
我把他簡化理解成查表(look-up table)的意思
反正今天給我一個key我可以找到一個對應的value
也因為這樣類似查表的特性，他找尋的速度是O(1)
所以剛剛的問題利用Map可以在O(n)裡解出
不過付出的代價就是要有儲存map的空間，複雜度是O(n)

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        map.put(nums[i], i);
    }
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement) && map.get(complement) != i) {
            return new int[] { i, map.get(complement) };
        }
    }
    throw new IllegalArgumentException("No two sum solution");
}

C++ vector 複製

在C++的stl::vector 裡

如果想要複製一個vector到另一個vector的話有太多種方法

1.使用for 直接複製(速度最慢)

for(int i = 0; i < original.size(); ++i)
    new_vector[i] = original[i];

2.使用vector.assign()

new_vector.assign(original.begin(), original.end());

個人覺得這是最佳解，速度比起上一個快很多

3.使用vector.insert()

new_vector.reserve(original.size());
new_vector.insert(new_vector.end(), original.begin(), original.end())

insert也可以使用在把兩個vector合併(append)
用法就與上面類似了，就是reserve的時候也要加上new_vector的大小

4.使用copy constructor

new_vector = vector(original);

這個方法稍微測試了一下，好像不是真正的去複製
只是把new_vector指向了original的記憶體位置
也就是說new_vector跟original是同一個物件
動了其中一個兩個都會改變
也就是彼此是彼此的別名(我在說啥XD)

存取記憶體影響效能

最近在寫論文的程式時有些發現

在我的程式裡有這麼一段

deque<int> new_crossing(y2 - y1 + 1);
for (int i = 0; i <= y2 - y1; i++)
{
 int parent_crossing, child_crossing;

 if (bound.y > i + y1 || bound.br().y - 1 < i + y1)
  parent_crossing = 0;
 else
  parent_crossing = crossings[i + y1 -bound.y];

 if (child->bound.y > i + y1 || child->bound.br().y - 1 < i + y1)
  child_crossing = 0;
 else
  child_crossing = child->crossings[i + y1 - child->bound.y];

 new_crossing[i] = parent_crossing + child_crossing;
}

crossings = new_crossing;

內容就是要把parent_crossing與child_crossing 對齊地合起來(依照它們的y座標) 總之我偷懶的直接創了一個最可容納parent_crossing與child_crossing的deque

這樣的作法會不斷地創造新的deque，並且再把舊的deque給丟棄

一開始也只是先求有再求好，就不是這麼注重效能了

沒想到最近我發現了Visual Studio裡面有效能分析的工具

一分析下去...原來我在這一小段程式碼耗了將近2/3的時間

再來就是這一段了

vector<bool> pixel_accessible(height*width, false);
vector<bool> pixel_accumulated(height*width, false);

這是一個與影像大小相同的mask

用來檢查每個pixel的狀態

我發現用vector來存boolean，然後用operator[]存取這個mask也是極度地沒有效率

原因就不是很清楚了

後來把它改為用int存，而且記憶體是自己向作業系統要，效能又在提升一倍

只能說沒有效率的資料結構或是記憶體使用

把程式速度拖累個好幾倍是很常見的~

STL心得

對我來說

C++比起C最大的好處

不是物件導向的開發方式(雖說這也是其中之一)

而是它有很多模板可以使用(STL)

提供了vector, queue, stack, list...

很多厲害的演算法一定脫離不了這些資料結構

而在github上看了很多高手的程式

觀察到大部分實作stack的時候不使用stack而改用vector

於是我深入研究一下

stack其實更偏向於container adapter

也就是說他是拿來裝其他container(vector, list, deque...)較多

而且他少了vector能隨機存取的優點，讓debug更不方便

因此如果我們使用vector並只在尾端增減的話就能完美地取代stack

但用stack也不是全沒好處

一來是可以很明確地告訴開發者這變數LIFO的機制

二來是我自己測試，stack在push & pop的時候比vector快一咪咪

OpenCV Mat取值

參考以下OpenCV這一篇解說
Opencv影像掃描


1. 提到效率當然還是使用純C風格的 [] 取值最快
使用Mat::data來存取，不過我試過似乎只在Mat型態為uchar的時候可以使用
速度理所當然是最快的
可以用以下的形式來掃描影像

uchar* p = img.data;
for(int i = 0; i < img.total(); i++)
    p[i] = 0;

2. iterator是個效率差一點但相對安全許多的方式.
iterator的方式比純C風格慢一些
但多了邊界檢查安全許多

3. at最慢
隨機存取是他的優點，但速度確實是偏慢，
OpenCV的文件也不建議使用at來進行掃描，
at在debug下肯定輸iterator與ptr，而release下有則有可能稍慢或是打平

for(int i = 0; i < img.rows; i++)
{
    for (int j = 0; j < img.cols; j++)
    {
        img.at<uchar>(i,j) = 0;
    }
}

at也可以使用一維的方式存取，
方法就像是純C的那樣，不再贅述

4. ptr比at快
ptr的方式是我現在比較偏好的
因為在掃描影像或是做convolution時常常需要去考慮邊界的問題
而ptr可以讓我選擇在特定的row開始
再加上一個位移選擇到特定的col
比起純C與iterator方式多了彈性
速度也不會慢多少，快上at許多
以下範例是可以略過最外圈的掃描方法

for(int i = 1; i < img.rows-1; i++)
{
    uchar* ptr = img.ptr<uchar>(i);
    for (int j = 1; j < img.cols-1; j++)
    {
        ptr[j] = 0;
    }
}

5.LUT最快
若要將某個特定值換成另一個值，
使用OpenCV提供的core function LUT是最快的，甚至比純C還要快

    Mat lookUpTable(1, 256, CV_8U);
    uchar* p = lookUpTable.data;
    for( int i = 0; i < 256; ++i)
        p[i] = table[i];

先將LUT表給建好
然後輸入A影像，給定一個look up table
輸出的B影像則會依照look up table來替換成你要的值

LUT(A, lookUpTable, B);