[討論] 面試題 - 陣列輸出.矩陣乘法

[EdisonX (閉上眼的魚)]

小弟平時會 "挖" 一些面試題，< 有新的也有舊的 >
這個月有幾題覺得還不錯，< 其實重點是覺得自己解不好 >
讓人蠻感興趣，於此想與各位版友一起探討，也懇請不吝賜教。

提到一些演算法的東西, 但盡量附上 code 。

為留有思考空間，題目與小弟的想法分上下段分開寫。
也由於題目範圍會跳 tone 些，故若對於其中任意一題有想法，
請不吝提出，感激不盡。


Q1 假設一陣列 a[] = {4,15,21,17,6,1,99}，
   如何輸出 1~100 ，而 a 陣列出現之數字即不輸出？
   ( 記憶體使用量盡可能少，程式執行速度盡可能快 )

Q2 假設已知二陣列 double a[p][q], b[q][r], 
   現欲求 double c[p][r] = a[p][q] * b[q][r]，
   已知 500 < p, q, r < 1000 , 請試完成 c。
   ( as soon as possible. )

* Q3 就你所知，能否簡述 AutoRun.inf 病毒防護機制或原理？
   或直接提示一想法去防護 ? 
   ( 很抱歉這題我竟沒太多想法 )

－－－－－－－－－－－－－－－－－－－－－－－－－－

A1 : 這題小弟解法 :  http://ppt.cc/rS@8
     < 上面廢話跳過，拉到最下面看 code >

A2 : 最有得討論的大概是這題。

(1) 傳統 < 略 >

    簡單的說是 rst[i][j] += a[i][k] * b[k][j] ;
    0 < i < p ; 0 < j < r ; 0 < k < q

(2) 轉置

    先將 b[q][r] 轉置成為 b'[r][q]
    變成 rst[i][j] += a[i][k] * b[j][k]
    0 < i < p ; 0 < j < r ; 0 < k < q

        for(i=0; i<p; ++i){
                for(j=0; j<r; ++j){
                        sum = 0.0;
                        for(k=0; k<q; ++k)
                                sum += a[i][k] * b[j][k];
                        rst[i][j] = sum;
                }
        }

　 測試出來 ( wall time testing ) 約比傳統快 6～7 倍

* (3) Div Block

   這裡會用到 6 個 for-loop, 前面 3 個是限制 block, 後 3 個是計算 rst,
   同時利用到 (2) 的技巧，也就是先將 b[q][r] 先轉置成 b'[r][q]，
   實測跑出來下面這段 code 結果會出包 < 結果是錯的 >
   不知是否我哪段有誤？

   const size_t BLOCK = 64;
   for(ci=0; ci< p; ci+=BLOCK)
      for(cj=0; cj< r; cj+=BLOCK)
        for(ck=0; ck< q; ck+=BLOCK)

            for(i=ci; i<min(ci+BLOCK, p); ++i)
                for(j=cj; j<min(cj+BLOCK, r); ++j) {
                   sum = 0.0;
                   for(k=ck; k<min(ck+BLOCK, q); ++k)
                       sum += a[i][k] * b[j][k];
                   rst[i][j] = sum;
                }

   小弟驗證答案是錯的，不知是否哪裡有誤？
   < wall time 大概比上一個方法快 10%~20%, 不過取決於 Block Size>

   完整測試碼 http://codepad.org/X81ymBjQ

* (4) Q

  下面三個其他想法有問題, 苦找不到方向 ：

　(a) Div Block , 有辦法推出較佳的 Block ”大概”　是多少嗎？

  (b) 有種演算法叫 Strassen algorithm, 目前看的 code 都有一前提在
      matrix 為 nxn , 且 n = 2^k ( k 為整數 )，
      使用此演算法必定需符合此前提嗎 ?

      < 另我較好奇的是，這種演算法使用分而治之，大多用遞迴手法完成，
        如此下來是不是真的比 (3) 還快倒讓人蠻懷疑的 >

  (c) " 目前 "， matrix multiple 是否可以 multi-thread 完成？
      ( 或說，multi-thread 對於 matrix multiple 是否有較佳設計模式？
        目前我試是較慢的，所以想說應該是我沒設計好 )

  我知道最快的方法躺在 I2A 裡面，不過實在沒興趣 K 它實作 Orz。

A3 :

   這問題可能跳 tone 許多，也是一個 open problem，
   縮小範圍，下面就當笑話看看吧..

   (1) 我知道一些單位，電腦裡面會放一支 serv,
       當 usb 插入後會讀到 pid , 於是在 Win32 API 抓到
       WM_DEVICE_CHANGE 時去確認 pid, 不是符合的就自動斷掉
       但不知道病毒的動作會不會比這個還快，
       不過這並不能算是「防毒軟體」Orz

   (2) 另一種方式大概只能做 trace API,
       但難度在於監看 process API 之調用,
       如何監控哪些 process 用到了
       FindWindow、SendMessage、Read/WriteProcessMemory... etc，
       這點卻完全摸不著頭緒。

       若真有辦法控監的話，誤判機率應該蠻大的，
       目前能想到的修正大概是：
       CreateProcess -> ReadProcessMemroy -> WriteProcessMemory,
       要判斷是否為「某一系列 API 之連續調用」，再判斷是否為病毒。
       < 所以應該會用到 FSM >

－－－－－－－－－－－－－－－－－－－－－－－－－－

以上，請各位版友不吝解惑與賜教，小弟感激不盡！

--
 「自從我學了 C#   , 人都變聰明 , 考試都考一百分」
 「自從我學了 VB   , 皮膚都變好 , 人也變漂亮了  」
 「自從我學了 Java , 明顯變壯   , 個子也變高了  」
 「自從我學了 C++  , 內分泌失調 , 頭都禿了...   」

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 180.177.76.161
推 BombCat:A2.2應該是cache locality所以變快了
推 purpose:打個醬油閒扯幾句，研究難題最怕的就是重新發明輪子，我雖
→ purpose:非專業，但也知道問題(3)這類的漏洞利用方式跟解決方案，
→ purpose:早就充斥到炸了，短時間很難有心的創舉，與其苦想不如
→ purpose:去找已經存在的技術文章，其實這題不值得你關注
→ EdisonX:@BombCat: 我能想到的就是用 cache locality 去做.
→ EdisonX:@p大 : autorun.inf 技術文是否有推薦可概閱 ?
→ BombCat:A2.3會變更快是cache locality變更好，因為那個區塊的資料
→ BombCat:都在附近然後又一直重複使用(?
→ EdisonX:@B 大:A2.2/A2.3 是我寫的 sample code,所以我知道原因 :)
→ EdisonX:原因簡單而言，就正如您所說的沒錯 :)
→ BombCat:其實我是亂猜的 XD
推 purpose:抱歉，我沒特地收集，你只能重找一遍了
→ EdisonX:嗯嗯, 謝謝 p 大 :)
→ BombCat:要multi-thread不就一個thread負責一個區塊就好?
→ BombCat:這樣也不用同步拉
→ BombCat:不過好像本來就不用同步 Orz
→ erotic:標題的effective是指什麼? @@
→ EdisonX:已修改。<原本的effective指的是前兩題都要求效能>
→ linotwo:A1 : http://codepad.org/WlgbIySu
→ linotwo:將 a[] 排序後作為 1~100 的分隔點
→ EdisonX:疑!我的作法是開 array[low:up] 出來,直接紀錄,只是用的是
→ EdisonX:bitwise array.
A2.3 也解出來了, 效能似乎與轉置沒太大差異。
※ 編輯: EdisonX         來自: 180.177.76.161       (05/27 09:34)