[面試] "盡可能小且快"－Edison.X. Blog

有一系列之面試題目，要求使用記憶體使用量要小，且程式速度要快。如下面兩個問題

(1) 依序輸出 [10, 200] 之所有整數，但，若假設有一陣列 A[] = {-1, 124, 2, 72, 7, 453, 25, 68}，如果 A 陣列裡面出現之元素，則不進行輸出。以此例而言，最後會從 10 輸出到 200，除了 25, 68, 72, 124 不輸出。

(2) 欲從 [-100, +100] 中，從中隨機取出不同之 20 個數字，最後再依大小輸出這 20 個數字。

這裡將焦點放在問題 2，問題 1 之解法也可以探討很久，

但筆者對於這兩個問題解法是大同小異的，故放在一起討論。

這裡做的前提假設為：CHAR_BIT = 8， sizeof(unsigned) = 4。

關於問題二，這裡再把問題重修正一下

欲從 [LOW, UP] 中，從中隨機取出不同之 PICK 個數字 (其中 PICK < UP - LOW) ，最後再依大小輸出這 PICK 個數字。

為說明方便起見，令 RANGE = UP - LOW + 1。一般大致上跑不出二種想法

想法一 - Force + Sort

做一個 int list[20]，每次取出來的亂數去查 list 中是否存在，

如果不存在的話才加到 list 裡面去，最後加完後再對 list 做排序。

所以需要 int list[20]、int loop_counter、int rnd、int tmp ( 排序時做 swap 用 )

空間：23 * 4 = 92 bytes

速度： ??? ，可確定的是當 PICK / RANGE 愈接近於 1 時，速度愈慢，但相對在 PICK / RANGE 愈接近 0 時，使用此法速度快！

想法二 - Knuth + Sort

這問題實際上可轉換成 Knuth Shuffle，一開始產生 RANGE 個大小之陣列，進行 shuffle 後，取出前 PICK 個，再對此做排序。所以需要 int poker[201] 、int loop_counter、int rnd、int tmp ( 做 swap 用 )

空間：(201+3) * 4 = 816 bytes

速度：洗牌O(n) + 排序 O(nlog(n) / n )

想法三 - Knuth + Force + Sort

想法三源自於 STL 使用之 sort : intro-sort，這裡非常粗略的做演算法之切換。

假設 PICK / RANGE 大於等於 0.7 (想法二) 時，就用 Knuth Shuffle；若小於 0.7 時就用暴力法(想法一)。

至於上述的 0.7 這數值怎來的？這是筆者亂猜的，實際上最佳切換點要推得應不是件容易之事。

空間與速度參考上述。

想法四 - 筆者解法

這方法概念不難，但說明冗長。優點是 cache hit 甚高。

(1) 資料型態 - Array

我們已知要從 [-100, 100] 取出 20 個不同數字出來，

如果 -100~+100 各以 1 個 bit 表示該數字，則只需要 201 個 bits 即可。如，

若取出之亂數為 -100，則設第 (-100 - (-100) ) = 0 個 bits 為 1；

若取出之亂數為 -10，則設第 (-10 - (-100) ) = 90 個 bits 為 1；

若取出之亂數為 72，則設第 (72 - (-100) ) = 28 個 bits 為 1，依此類推，

故使用的資料型態是 unsigned array[SIZE]，至於 SIZE 要多大，

後面會講怎麼算。

(2) 其他之變數

在這問題裡，若用 int loop_index ，直接吃了 4 bytes，但細思，

我們在用 loop_index 會有些情況？

第一種是計數，是否已產生相異的 20 (PICK) 個亂數，

這種計數只需要 5 個 bits 即可完成；

第二種計數 (其實第二種計數可因設計模式而異，筆者的方法並不是最省的) ，

是從 bit0 ~ bit200 , 0~200 之計數，

這種計數需要 8 個 bits 方可完成。

所以這支程式，最省約為 201 + 8 = 209 bits，但實際上我們不會配 209 bits 出來。

由於決定是 unsigned array[SIZE] 紀錄 bit0~bit200，

第bit200 時，是在 array[7] 的第 8 個 bit ( 6 * 32 + 9 = 201 )，

意思是 array[7] 本身 bit9~bit31 ，有 23 個 bit 還沒用，這 bit 數足夠拿來當計數器，

故這份程式碼實際上不會再使用 int loop_index、tmp 這二個變數，

但 int rnd 變數應是跑不掉的。

(3) SIZE 計算

ˇ 紀錄數字：100 - -100 + 1 = 201 bits ；

ˇ 計數器：ceil ( log2(201) ) = 8，注意，若 log2(201) 本身是整數的話，這個值要再加 1 ，避免計數器溢位。

ˇ 共使用 bits 數：201 + 8 = 209

ˇ unsigned array[SIZE]： size = ceil ( 209 / ( sizeof(unsigned) * CHAR_BIT) )

size = ceil ( 209 / 32 ) = 7

故 SIZE 算出來，是 7。

* (4) 輸出結果部份

這部份是筆者自認為還有待加強的部份，有兩種處理方式。

當已產生完後，剩下的也不需排序，一種簡單的方式是直接從 bit0 ~ bit200，

逐一 polling，當 bit(n) 為 1 時就輸出 n，筆者用的是這種方式。

另一種方式是再用 bitwise-hacker 找到 right most 1，

但求得的是 2^n，這裡必需再從用另一個 bitwise-hacker 從 2^n 轉到 n，

才可進行輸出。

( 或說，只用一個 bitwise-hacker，求 2^n <= x 之最大 n 值 )

注意到，這裡用的雖然也是暴力法，但卻沒有想法一暴力法上的缺點，

當 PICK / RANGE 接近於 1 時，如 98 / 100 的時候，

事實上我們可以視作 2 / 100 ，取到的那二個亂數就不去輸出，

其他的 98 個亂數一律輸出 ( 疑！這不就是此文開頭的問題一了嗎！)。

* (5) 程式碼參考

這份程式碼是基於想法四較簡單版本去做的，用了大量的 macro，

同時有些 macro 之結果可以先存下來 (多使用了4bytes) 讓速度更快，

這裡並沒有這麼做。也由於用了大量 macro，展開後可能還可以再化簡，

這裡沒再進一步展開化簡，參考如下。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
// 
#define LOW (-100)
#define UP (+100)
#define PICK 20

#define CHK_BIT(arr, x)((arr[x>>5]&(1U <<(x&31)))!=0U)
#define SET_BIT(arr, x)((arr[x>>5]|=(1U<<(x&31))))

#define GET_H8_VAL(x)(x>>24)
#define CMP_H8_VAL(x, val)(GET_H8_VAL(x)==val)
#define INC_H8_VAL(x)(x+=0x01000000)

#define RNDI(low,up) \
    (int)((up-low+1.0)*rand()/(RAND_MAX+1.0)+low)

int main()
{
    // (1) 100-(-100)+1=201
    // (2) ceil( log2(201) ) = 8
    // (3) 201 + 8 = 209 (bits)
    // (4) if log2(201) is integer, plus 1.
    // (5) size = ceil (209 / 32) = 7

#define SIZE 7 
    unsigned arr[SIZE] = {0U};
    int rnd; 
    srand((unsigned)time(NULL));
    while(!CMP_H8_VAL(arr[SIZE-1],PICK)){
        rnd = RNDI(0, UP-LOW);        
        if(!CHK_BIT(arr, rnd)) {
            SET_BIT(arr, rnd);
            INC_H8_VAL(arr[SIZE-1]);
        }
        printf("%d", rnd + LOW);
    }
puts("");
    arr[SIZE-1]&=0x00ffffff; // set high eight bits to zero.
    while(!CMP_H8_VAL(arr[SIZE-1], (UP-LOW+1))) { // check equ. upper bound
        if(CHK_BIT( arr, GET_H8_VAL(arr[SIZE-1]) )) {
            printf("%d", GET_H8_VAL(arr[SIZE-1]) + LOW);
        }
        INC_H8_VAL(arr[SIZE-1]);
    }
getchar();
    return 0;
}