iT邦幫忙

2

LeetCode的效能

Implement int sqrt(int x).

Compute and return the square root of x, where x is guaranteed to be a non-negative integer.

Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.
想請問leetcode上,請問是有宣告變數效能就會降低嗎?
解法1:
var mySqrt = function(x) {
return Math.pow(x,1/2).length>1?Math.pow(x,1/2):Math.floor(Math.pow(x,1/2));
};
Runtime: 92 ms
Memory Usage: 38.1 MB

解法2:
var mySqrt = function(x) {
var a= Math.pow(x,1/2);

return   a.length>1?a:Math.floor(a);

};
Runtime: 104 ms
Memory Usage: 38.3 MB

3
ShawnL
iT邦新手 4 級 ‧ 2020-09-09 17:50:24
最佳解答

2020/09/14 更新

從 Bytecode 角度上來看

以 V8 引擎而言,當你宣告變數並存入值時,他會做兩件事情:

  • 劃分一個記憶體位置
  • 將值存入到該記憶體位置

所以理論上來說自然會占用到記憶體的部分。

至於更加詳細解釋的部分,這裡推薦你閱讀這份系列文章,這系列文章透過 Node.js 中 --print-bytecode 指令來去查看最後產出的 Bytecode 藉以探討更底層的運作,但我想這可能會依不同引擎背後的實作而論。

從演算法角度上來看(請參閱樓下 Huli 解說)

看更多先前的回應...收起先前的回應...
kekeke iT邦新手 5 級 ‧ 2020-09-09 17:57:48 檢舉

所以是在宣告變數時,會再花時間在話分記憶體所以讓時間變多~謝謝

ShawnL iT邦新手 4 級 ‧ 2020-09-09 18:07:22 檢舉

但從實作上來說,JavaScript 比較要在意的應該會是物件上的 Memory Leak,因為記憶體如何分配並不是我們能控的,而基於瀏覽器的運作的話,瀏覽器也會幫忙做 Garbage Collection,所以比起這部分的 Memory Usage、Runtime,我會覺得可讀性會更重要 XD

huli iT邦新手 5 級 ‧ 2020-09-13 22:05:08 檢舉

原文這題其實要考慮到的點有很多,第一個是在很多 OJ 的系統上,那些時間如果沒有差太多(例如說 100ms 跟 200ms 的差距),可以視為是系統的計算誤差,有可能你多試幾次,秒數就變快或是變慢了

第二個是要考慮到 compiler,有些程式碼經過 compiler 優化以後會跟你想的不一樣,並不是光看程式碼本身就能夠推出來的。以原文的解法來說,第一種 Math.pow(x,1/2) 算了兩次,解法 2 只算了 1 次,我以常識去推論會認為第二種比較快,因為計算量較少

但結果秒數上面是第一種比較快,所以可以合理猜測可能是
(1) 系統誤差,差距太小可以視為一樣,可以把測資變大,看看差距是否一樣
(2) 編譯器做了一些神奇的事

kekeke iT邦新手 5 級 ‧ 2020-09-14 08:25:13 檢舉

huli謝謝尼的解說/images/emoticon/emoticon41.gif

2
海綿寶寶
iT邦大神 1 級 ‧ 2020-09-09 17:58:22

如果可以使用 Math 的 function 的話
不如直接給他 sqrt 算了

var mySqrt = function(x) {
   return parseInt(Math.sqrt(x)+"");
}
kekeke iT邦新手 5 級 ‧ 2020-09-10 08:28:57 檢舉

我也有想過~但題目有限制不得使用此函式~xd

1
淺水員
iT邦研究生 3 級 ‧ 2020-09-09 19:29:04

如果不使用內建函式
整數開方可以用二進位版本的直式開根號來做
人在外面,回家有空再補上

補上code

var mySqrt = function(x) {
    let r=0,
        q=0;
    for(let k=30;k>=0;k-=2) {
        r=r<<2|x>>>k&3;
        if((q<<2)<r) {
            r-=(q<<2|1);
            q=q<<1|1;
        } else {
            q=q<<1;
        }
    }
    return q;
};

Runtime: 84 ms, Memory Usage: 38.2 MB

淺水員 iT邦研究生 3 級 ‧ 2020-09-09 23:29:23 檢舉

一般內建函式幾乎是最快速的解法,但是當內建函式算的是浮點數,而我們只需要整數部分時,有時候自己寫的會比內建函式快。

kekeke iT邦新手 5 級 ‧ 2020-09-10 08:30:16 檢舉

/images/emoticon/emoticon41.gif謝謝~多上了一課

我要發表回答

立即登入回答