在數組中，如何找到給定浮點值的最接近的鍵？

Question

我在做一個「加速度」數組是這樣的：

acc["0100"] = 1; 
acc["0300"] = 2; 
acc["0600"] = 4; 
acc["0900"] = 8; 
acc["2000"] = 16; 
acc["5000"] = 32; 

而且，當用戶按下一個鍵，我啓動一個定時器：this._startTick = (new Date()).getTime();

現在我如果該鍵，檢查計時器仍然被按下。如果是這樣，那麼我這樣做：

this._delay = (new Date()).getTime() - this._startTick; 

而現在，基於this._delay，我想找到以前的一個值（1，2，4或8個）。你會怎麼做？

注意：如果該值大於「5.0」，則結果應始終爲32。

NOTA：我的目標是，根據經過的時間，找出哪個值最好。我以我剛剛解釋的方式開始，但如果您有其他解決方案，我會接受！

Answer 1

它更容易數組不是一個對象上進行操作：

var accArr = []; 
for (time in acc) { 
    accArr.push({time: time, value: acc[time]}); 
} 

假設你有一個rray，你可以這樣做：

function getValue(delay) { 
    var diffs = accArr.map(function (e) { return Math.abs(e.time - delay); }); 
    return accArr[diffs.indexOf(Math.min.apply(null, diffs))].value; 
} 

編輯：

好了，你沒有提到這是一個性能關鍵的功能。在這種情況下，我建議採摘粒度（例如0.05，所以對於延遲乘數是20）和預先計算的所有值從0到MAX_DELAY：

var multiplier = 20, 
    granularity = 1/multiplier; 

var delayValues = (function() { 
    var result = []; 
    for (var delay = 0; delay <= MAX_DELAY; delay += granularity) { 
     result.push(getValue(delay)); 
    } 
    return result; 
})(); 

在動畫，取的值將是一個簡單的查找在一個相對較小的表：

function getValueFast(delay) { 
    return (delayValues[Math.round(delay * multiplier)] || 
      delayValues[delayValues.length - 1]) 
} 

JSPerf comparison這個解決方案和簡單的if語句之間顯示他們執行同樣快圍繞中間值搜索。

Answer 2

如果0.1是的秒數，並且要舍入到1位小數，你可以做一些這樣的：

// 0.42332 * 10 = 4.2332 
// Math.round() will be 4 
// 4/10 = 0.4 
acc[ (Math.round(this._delay * 10)/10).toString() ] 

Answer 3

var seconds = this._delay.toString().substring(0,2) 

console.log(acc[seconds]); 

這是你的問題的一個直接的方法：首先，我將float轉換爲一個字符串，其次我切斷了第三個字符後的所有內容。

Answer 4

Here是jsfiddle測試頁面。

var getAccForDelay = (function() { 
    var acc = { 
     0.1: 1, 
     0.3: 2, 
     0.6: 4, 
     0.9: 8, 
     2.0: 16, 
     5.0: 32 
    }; 

    return function(delay) { 
     var key, 
      bestKey = undefined, 
      absDiff, 
      absDiffMin = Number.MAX_VALUE; 

     for (key in acc) { 
      if (acc.hasOwnProperty(key)) { 
       absDiff = Math.abs(delay - key); 
       if (absDiffMin > absDiff) { 
        absDiffMin = absDiff; 
        bestKey = key; 
       } 
      } 
     } 
     return bestKey === undefined ? undefined : acc[bestKey]; 
    }; 
}()); 

測試：

console.clear(); 
console.log(getAccForDelay(0)); 
console.log(getAccForDelay(0.33)); 
console.log(getAccForDelay(3.14)); 
console.log(getAccForDelay(123456.789)); 

輸出：

1 
2 
16 
32 

=== UPDATE ===

將上述溶液未利用的事實，即acc按鍵排序。我通過用binary search代替線性搜索來優化代碼，這在長陣列上要快得多。 Here是測試頁面。

var getAccForDelay = (function() { 
    var accKey = [ 0.1, 0.3, 0.6, 0.9, 2.0, 5.0 ], 
     accValue = [ 1, 2, 4, 8, 16, 32 ], 
     accLength = accKey.length; 

    return function(delay) { 
     var iLeft, iMiddle, iRight; 

     iLeft = 0; 
     if (delay <= accKey[iLeft]) 
      return accValue[iLeft]; 
     iRight = accLength - 1; 
     if (accKey[iRight] <= delay) 
      return accValue[iRight];   
     while (true) { 
      if (iRight - iLeft === 1) 
       return delay - accKey[iLeft] < accKey[iRight] - delay ? accValue[iLeft] : accValue[iRight]; 
      iMiddle = ~~((iLeft + iRight)/2); 
      if (delay < accKey[iMiddle]) 
       iRight = iMiddle; 
      else if (accKey[iMiddle] < delay) 
       iLeft = iMiddle; 
      else 
       return accValue[iMiddle]; 
     } 
    }; 
}()); 

Answer 5

你使用什麼單位？

this._startTick = (new Date()).getTime(); 
//  ms  =     ms 

this._delay = (new Date()).getTime() - this._startTick; 
//  ms =     ms  -  ms 

所以去"0.1" /等從毫秒我假設你正在做的

(Math.floor(ms/100)/10).toString(); 

爲什麼不剛在ms/100一切，所以你可以使用整數？

var acc = []; 
acc[ 1] = 1; 
acc[ 3] = 2; 
acc[ 6] = 4; 
acc[ 9] = 8; 
acc[20] = 16; 
acc[50] = 32; 

然後你可以創建一個這樣

function find(x) { 
    var i = 0; 
    x = x | 0; // The | 0 will cause a cast to int 
    if (x < 0) x = 0; 
    if (acc[x] !== undefined) return acc[x]; 
    if (x > acc.length) return acc[acc.length - 1]; 
    while (++i < acc.length) { 
     if (acc[x - i] !== undefined) return acc[x - i]; 
     if (acc[x + i] !== undefined) return acc[x + i]; 
    } 
} 
find(this._delay/100); 

一個「最近」查找功能現在的例子是

find(30); // 16 
find(100.5); // 32 
find(0);  // 1 

Answer 6

在我的愚見，我認爲這個問題最好的解決辦法是寫一個挑選基於使用if語句如下的時候最好加速功能：

function getAcceleration(time) { 
    if (time < 0.20) return 1; 
    if (time < 0.45) return 2; 
    if (time < 0.75) return 4; 
    if (time < 1.45) return 8; 
    if (time < 3.50) return 16; 
    return 32; 
} 

然而，這是一個靜態的解決方案。如果你沒有問題，我建議你使用這種方法。在另一方面，如果你需要一個動態的解決方案，然後用這個來代替：

var getAcceleration = createAccelerationMap(0.1, 0.3, 0.6, 0.9, 2.0, 5.0); 

function createAccelerationMap(previous) { 
    var length = arguments.length, limits = []; 

    for (var i = 1; i < length;) { 
     var current = arguments[i++]; 
     limits.push((previous + current)/2); 
     previous = current; 
    } 

    return function (time) { 
     var length = limits.length, acceleration = 1; 

     for (var i = 0; i < length;) { 
      if (time < limits[i++]) return acceleration; 
      acceleration *= 2; 
     } 

     return acceleration; 
    }; 
} 

無論哪種方式，你可以再使用getAcceleration如下：

console.log(getAcceleration(0));   // 1 
console.log(getAcceleration(0.33));  // 2 
console.log(getAcceleration(0.64));  // 4 
console.log(getAcceleration(1.42));  // 8 
console.log(getAcceleration(3.14));  // 16 
console.log(getAcceleration(123456.789)); // 32 

觀看演示：http://jsfiddle.net/QepT7/