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

 

(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;
}


[註] 事實上第二個 while 可以直接用 rnd 當 loop_index,會比上面方法還快。

 

* (6) Knuth Shuffle 

 

從 [1,100] 取 10 個不重覆亂數,以 Knuth Shuffle 而言是先產生 1~100 之陣列,

洗亂,再取前面 10個。另一種方式是用上述方法,先決定哪 10 個亂數,

唯瓶頸應是在 polling 結果那裡,建議改成雙層的 bitwise-hacker 

(見 * (4) 輸出結果部份 )

再對這 10 個亂數進行 Knuth Shuffle。

當 PICK / RANGE 較小時,這種方式之效率值得做為比較。

 

這部份可推廣,再深入研究的議題、想法並不少,此文便於此打住,有興趣可再自己鑽研。

arrow
arrow
    全站熱搜

    edisonx 發表在 痞客邦 留言(0) 人氣()