条件で複数のa <= b <= cをテストする最も効率的な方法

-2

私は下限と上限で得られた範囲に対して複数の数値（3つ以上）をテストしています（lower <= upperの条件がいつも満足している）。今ここに私の目的は、私は、パフォーマンスを最適化したいと思います下[1 ... n]を持つ、X [1 ... n]と上位[1 ... n]は条件で複数のa <= b <= cをテストする最も効率的な方法

...

私はthis other Q&A here on StackOverflowを見ていた後、私はこの機会にJavaScriptで行く必要がある、と私は「古典」lower[n] <= x[n] && x[n] <= upper[n]

上

(unsigned)(x[n]-lower[n]) <= (upper[n]-lower[n])フォーム

で行くことができる、知っています私はそれを得ることができることを知っているこの言語は使用して「トリック」：

JavaScript >>> bitwise operator
または私は第二の方法は非常にパフォーマンス上の最悪の影響を与えるだろう、かなり確信しているJavaScript Uint32Array object

を使用することによって、除きます出発時に、最初のものだけを考えれば、私はできます：

// Example 1 
function everything_is_in_range(lower, x, upper) { 
    return (((x[0]-lower[0]) >>> 0) <= (upper[0]-lower[0]) && 
      ((x[1]-lower[1]) >>> 0) <= (upper[1]-lower[1]) && 
      ... 
      ((x[n-1]-lower[n-1]) >>> 0) <= (upper[n-1]-lower[n-1])); 
}

私は何ができる

または：

// Example 2 
function everything_is_in_range(lower, x, upper) { 
    if (((x[0]-lower[0]) >>> 0) > (upper[0]-lower[0])) return false; 
    if (((x[1]-lower[1]) >>> 0) > (upper[1]-lower[1])) return false; 
    ... 
    return (((x[n-1]-lower[n-1]) >>> 0) <= (upper[n-1]-lower[n-1])); 
}

私の質問は以下のとおりです。私は目的のために、「古典的」lower[n] <= x[n] && x[n] <= upper[n]フォームに滞在する必要がありますように

符号なしシフトは、一般的なパフォーマンスに便利ではないでしょう？
私の最初の答えに対する答えがいいえでない場合、どちらの方法が最も効率的でしょうか？しかし、もっと重要なこと：あなたがおそらくあなたが提案できるより良いものを知っていますか？

P.S.私は次のようにforループを行うことができます知っている：

// Loop example 
function everything_is_in_range(lower, x, upper) { 
    for (i=0; i<n; ++i) if (((x[i]-lower[i]) >>> 0) > (upper[i]-lower[i])) return false; 
    return true; 
}

しかし

それは私が少ないコードを書くせるためだけ便利だろうが、それは2番目のコードのアプローチに非常にアナログなものです結局、いいえ？
すべての値が単一の区切りパラメータとして渡される可能性があるため、このフォームを使用したくない（これは私の実際のケースで、3または4の数値+範囲の変数セットこれを変更することはできません）、値の配列としては使用できません（この例のように）。

出典

2017-11-09 danicotra

Javascriptには符号なし数値の概念がないため、その特定のトリックを利用することはできません – Hamms

'function withinRange（num、begin、end）{if（num> = begin && num <= end）{trueを返します。 } else {return false; }} ' – PHPglue

を" unsigned "にすると、追加の変換ステップのために少し遅くなる可能性が高くなります。https://stackoverflow.com/questions/14890994/javascript-c-style-type-cast-from-signed-私の推測では、関数呼び出し自体が比較よりも大きなオーバーヘッドを持つことになります。 – Slai

私はこの作られた：私はそれに "トリッキー" と（ループを含む） "クラシック" フォームの両方を入れて、私はこれを取得

<html> 
    <head> 
     <meta charset="utf-8"/> 
    </head> 
<body> 
<script> 

// Loop example 
function everything_is_in_range(lower, x, upper) { 
    for (i=0; i<3; ++i) if (((x[i]-lower[i]) >>> 0) > (upper[i]-lower[i])) return false; 
    return true; 
} 

// E.2 
function everything_is_in_range_2(lower, x, upper) { 
    if (((x[0]-lower[0]) >>> 0) > (upper[0]-lower[0])) return false; 
    if (((x[1]-lower[1]) >>> 0) > (upper[1]-lower[1])) return false; 
    return (((x[2]-lower[2]) >>> 0) <= (upper[2]-lower[2])); 
} 

// E.1 
function everything_is_in_range_1(lower, x, upper) { 
    return (((x[0]-lower[0]) >>> 0) <= (upper[0]-lower[0]) && 
      ((x[1]-lower[1]) >>> 0) <= (upper[1]-lower[1]) && 
      ((x[2]-lower[2]) >>> 0) <= (upper[2]-lower[2])); 
} 

// Loop C example 
function everything_is_in_range_C(lower, x, upper) { 
    for (i=0; i<3; ++i) if (lower[i] > x[i] || x[i] > upper[i]) return false; 
    return true; 
} 

// E.C2 
function everything_is_in_range_C2(lower, x, upper) { 
    if (lower[0] > x[0] || x[0] > upper[0]) return false; 
    if (lower[1] > x[1] || x[1] > upper[1]) return false; 
    return (lower[2] <= x[2] && x[2] <= upper[2]); 
} 

// E.C1 
function everything_is_in_range_C1(lower, x, upper) { 
    return (lower[0] <= x[0] && x[0] <= upper[0] && 
      lower[1] <= x[1] && x[1] <= upper[1] && 
      lower[2] <= x[2] && x[2] <= upper[2]); 
} 

let u = [50, 100, 150], 
    x = [100, 100, 100], 
    l = [25, 100, 125]; 

var t0, t1, m, m1, m2, mc, mc1, mc2, r; 
m = m1 = m2 = mc = mc1 = mc2 = 0; 
for (r=0; r < 100; ++r) { 
//console.log("Round " + (r+1) + ":"); 

t0 = performance.now(); 
everything_is_in_range_1(l, x, u); 
t1 = performance.now(); 
//console.log("Call 1 " + (t1 - t0) + " ms."); 
m1 += (t1 - t0); 

t0 = performance.now(); 
everything_is_in_range_2(l, x, u); 
t1 = performance.now(); 
//console.log("Call 2 " + (t1 - t0) + " ms."); 
m2 += (t1 - t0); 

t0 = performance.now(); 
everything_is_in_range(l, x, u); 
t1 = performance.now(); 
//console.log("Call loop " + (t1 - t0) + " ms."); 
m += (t1 - t0); 

t0 = performance.now(); 
everything_is_in_range_C1(l, x, u); 
t1 = performance.now(); 
//console.log("Call C1 " + (t1 - t0) + " ms."); 
mc1 += (t1 - t0); 

t0 = performance.now(); 
everything_is_in_range_C2(l, x, u); 
t1 = performance.now(); 
//console.log("Call C2 " + (t1 - t0) + " ms."); 
mc2 += (t1 - t0); 

t0 = performance.now(); 
everything_is_in_range_C(l, x, u); 
t1 = performance.now(); 
//console.log("Call loop C " + (t1 - t0) + " ms."); 
mc += (t1 - t0); 
} 

console.log("------------- AVERAGE RESULTS (after " + r + " rounds)-------------"); 
console.log("1: " + (m1/r) + " ms."); 
console.log("2: " + (m2/r) + " ms."); 
console.log("Loop: " + (m/r) + " ms."); 
console.log("C1: " + (mc1/r) + " ms."); 
console.log("C2: " + (mc2/r) + " ms."); 
console.log("Loop C: " + (mc/r) + " ms."); 

</script> 
</body> 
</html>

を：

ので

------------- AVERAGE RESULTS (after 100 rounds)------------- 
1: 0.0017500000000001137 ms. 
2: 0.0014500000000009549 ms. 
Loop: 0.002749999999998636 ms. 
C1: 0.0014500000000003865 ms. 
C2: 0.001150000000000091 ms. 
Loop C: 0.0019000000000011141 ms.

JavaScriptを使用する最良の方法は「古典的な」形式であり、特にこの「冗長」な方法はループよりも優れているようです：

function everything_is_in_range_C2(lower, x, upper) { 
    if (lower[0] > x[0] || x[0] > upper[0]) return false; 
    if (lower[1] > x[1] || x[1] > upper[1]) return false; 
    return (lower[2] <= x[2] && x[2] <= upper[2]); 
}

ループを利用する代わりに、テストする数字がたくさんあり、配列内のすべてのコードがすべてのコードを書くときには、パフォーマンスにはあまり価値がありません。

出典

2017-11-10 20:13:57 danicotra

最適化の主なポイントは、unsignedの部分ではなく、分岐予測ミスを最小限に抑えることです。万が一、あなたがまだスタックオーバーフロー上で最もアップ投票質問と回答を見ていない場合は

：
Why is it faster to process a sorted array than an unsorted array?

function f1(l, x, u) { if (l[0] > x[0] || x[0] > u[0]) return false; 
 
         if (l[1] > x[1] || x[1] > u[1]) return false; 
 
         return (l[2] <= x[2] && x[2] <= u[2]); } 
 

 
function f2(l, x, u) { return !!((x[0] - u[0]^x[0] - l[0]) & 
 
            (x[1] - u[1]^x[1] - l[1]) & 
 
            (x[2] - u[2]^x[2] - l[2])) } 
 

 
let l = [1, 1, 1], x = [2, 2, 2], u = [3, 3, 3], t, b, p = performance, c = 12345678 
 
t = p.now(); for (let i = c; i--;) b = f1(l, x, u); t = p.now() - t; console.log(1, t|0, b) 
 
t = p.now(); for (let i = c; i--;) b = f2(l, x, u); t = p.now() - t; console.log(2, t|0, b) 
 

 
l = [1, 2, 3], x = [2, 2, 2], u = [3, 3, 3] 
 
t = p.now(); for (let i = c; i--;) b = f1(l, x, u); t = p.now() - t; console.log(1, t|0, b) 
 
t = p.now(); for (let i = c; i--;) b = f2(l, x, u); t = p.now() - t; console.log(2, t|0, b) 
 

 
l = [3, 3, 3], x = [2, 2, 2], u = [3, 3, 3] 
 
t = p.now(); for (let i = c; i--;) b = f1(l, x, u); t = p.now() - t; console.log(1, t|0, b) 
 
t = p.now(); for (let i = c; i--;) b = f2(l, x, u); t = p.now() - t; console.log(2, t|0, b)

あなたはおそらく気づくことができたように、無店舗比較をしないバージョンは平均で少し速く見えますが、比較バージョンが早期に終了すると遅くなります。

ブランチレスバージョンは、おそらく試行錯誤の結果であり、広範なテストを行っていないため、間違っている可能性があります（負の数は間違いがあります）。

どちらのバージョンもSIMD命令で最適化できますが、few browsersでのみサポートされています。

出典

2017-11-11 17:18:34 Slai

条件で複数のa <= b <= cをテストする最も効率的な方法

答えて

関連する問題