조건에서 복수 a <= b <= c를 테스트하는 가장 효율적인 방법

-2

나는 하한값과 상한값으로 얻은 범위에 대해 각각 테스트하기 위해 여러 개의 숫자 (적어도 3 개)를 가지고 있습니다 (나는 lower <= upper 조건이 항상 만족). 이제조건에서 복수 a <= b <= c를 테스트하는 가장 효율적인 방법

낮은 ... 1 N]가, X [1 ... N]와 위 [1 ... N] 여기 내 목표는 내가 ...

성능을 최적화하고자하는 내가 this other Q&A here on StackOverflow에보고 한 후, 나는 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])); 
}

내가 1,363,210

또는를 할 수있는 :

// 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.

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

하지만

그것은 나를 더 적은 코드를 작성시키는 경우에만 편리 할 것입니다하지만이 두 번째 코드 접근 방식에 뭔가 매우 아날로그입니다 : 나는 다음과 같은 방법으로 for 루프와 함께 할 수있는 알고 결국, 안돼?
모든 값이 하나의 분리 된 매개 변수로 전달 될 수 있기 때문에이 양식을 사용하고 싶지 않습니다 (실제 사례 인 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- to-unsigned하지만 내 생각에 함수 호출 자체가 비교보다 큰 오버 헤드를 갖습니다. – 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.

을 따라서 ... 자바 스크립트를 사용하는 가장 좋은 방법은 "고전적인"형식이며, 특히 "장황한"방법은 루프보다 훨씬 좋습니다 :

모든 코드를 작성하는 대신 어쨌든 공연에 약간의 이득 가치가 없어 루프의 활용의 노력 ... 배열에서 테스트 할 수 많은 이미 모든 것을 가진 경우 195,680,083,210

글쎄, 내 생각

출처

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를 테스트하는 가장 효율적인 방법

답변

관련 문제