在JavaScript对象中查找最接近的较小“键”

Question

我正在处理一个JavaScript对象，虽然我已经有了解决方案，但我仍然认为它可以更有效地完成。

该对象是从一个ajax调用php脚本返回的。

r.price_array[1] = 39.99
r.price_array[5] = 24.99
r.price_array[10] = 19.99
and so on....

我现在正在搜索关键值（关键值表示数量）。

qty = $(this).val();

if (qty >= 1 && qty <= 4){
    price_set = 1;
}
else if (qty >= 5 && qty <= 9){
    price_set = 15;
}
else if (qty >= 10 && qty <= 14){
    price_set = 25;
}

//and so on...

console.log(r.price_array[price_set]); //this returns the value

有没有办法找到数量为3的下一个最低键匹配项，这将是1吗？ 或者数量为7，找到键5？

- Smith Smithy

---

循环两次遍历数组的所有元素？第一次获取最小值，第二次获取第二小的值？ - Jeroen Ingelbrecht

不是答案：如果最大数量“相当小”，则可以通过完全填充数组来进行速度/空间权衡，以便[1] [2] [3] [4]都包含39.99，然后if (quantity <= max) pricePerUnit = prices[quantity]。 - Stephen P

Answer 1

当然可以 - 只需使用循环：

var price_array = {
    1: 39.99,
    5: 24.99,
   10: 19.99,
   15: 15.99,
   20: 10.99,
   25:  5.99,
   30:  0.99
}
var qty = 12;

var maxKey = -1;
for (var key in price_array) {
    if (maxKey < 0 || key < qty) {
        maxKey = Math.max(maxKey, key);
    }
}
console.log(maxKey); //10
console.log(price_array[maxKey]); //19.99

- h2ooooooo

---

检查中...它几乎可以工作，但我正在动态元素上使用keyup触发，因此结果不稳定。正在重新设计触发器。 - Smith Smithy

线性搜索就可以了。不用担心循环遍历列表的问题。 - Scott Sauyet

@SmithSmithy，在循环中处理15个项目完全不需要时间-不用担心。我们不必缓存键、对其进行排序、查找并在键超过qty时立即停止（这只会用15个新项填满内存 - 除非它们一直存在）。 - h2ooooooo

感谢您的帮助。我不得不选择Fred的答案。由于某种原因，它给了我一个一致的返回结果。 - Smith Smithy

@SmithSmithy 没问题 - 很高兴你找到了答案。 - h2ooooooo

Answer 2

我这个版本已经测试过了，这是fiddle链接：http://jsfiddle.net/fred02138/UZTbJ/：

// assume keys in rprice object are sorted integers
function x(rprice, qty) {
    var prev = -1;
    var i;
    for (i in rprice) {
        var n = parseInt(i);
        if ((prev != -1) && (qty < n))
            return prev;
        else 
            prev = n;
    }    
}

var rprice = {
    1: 39.99,
    5: 24.99,
    10: 19.99
}

alert(x(rprice, 3));
alert(x(rprice, 7));

- fred02138

---

我在onkeyup事件中传递了值 - x(r.price_array, $(this).val())；不断地敲击数字键盘证明该函数按预期响应，并与下一个最低键具有一致的匹配。 - Smith Smithy

数组中的最后一个键是500。当用户输入500或更大的值时，我得到未定义的结果。我似乎无法弄清楚原因。 - Smith Smithy

我编辑了这个答案，但是编辑被删除了。如果输入大于最大键，则返回未定义。因此，alert(x(rprice, 11)); 将不起作用。 - Smith Smithy

Answer 3

另一种方法，在这个Fiddle中展示：

var lowerKeyFinder = function(prices) {
    var keys = Object.keys(prices);
    keys.sort(function(a, b) {return a - b;});

    return function(val) {
        var maxKey = -1;
        for (var i = 0, len = keys.length; i < len; i++) {
            if (maxKey < 0 || keys[i] < val) {
                maxKey = Math.max(maxKey, keys[i]);
            }
        }
        return maxKey;
    };
};

var lookup = lowerKeyFinder(r.price_array);

lookup(3);  //=> 1
lookup(7);  //=> 5

这并不要求键最初按顺序呈现，但会进行一次排序。它基于 @h2ooooooo 的答案，但工作方式略有不同，因为它最终只提供了一个通过数量查找的简单函数。

- Scott Sauyet

Answer 4

另一个解决方案是使用for-in循环。它的好处是一旦找到值就可以退出循环。

/**
 * @param {object} object - object with sorted integer keys
 * @param {number} index - index to look up
 */
function getValueForLowestKey(object, index) {
    let returned;

    for (const key in object) {
        if(key > index) break;
        returned = object[key];
    }

    return returned;
}

- Kentin

Answer 5

这是一个用于执行此操作的函数。它期望在具有数字键的对象上使用，就像您的数组一样：

function getClosestKey(arr, target, u){
  if(arr.hasOwnProperty(target))
    return target;

  var keys = Object.keys(arr);
  keys.sort(function(a,b){ return a-b; });

  // Can replace linear scan with Binary search for O(log n) search
  // If you have a lot of keys that may be worthwhile
  for(var i = 0, prev; i < keys.length; i++){
    if(keys[i] > target)
      return prev === u ? u : +prev;
    prev = keys[i];
  }
  return +keys[i - 1];
}

你需要在旧版浏览器中使用 SHIM Object.keys：

Object.keys = Object.keys || function(obj){
  var result = [];
  for(var key in obj)
    if(obj.hasOwnProperty(key)) result.push(key);
  return result;
}

使用方法：

var price_array = [];
price_array[1] = 39.99;
price_array[5] = 24.99;
price_array[10] = 19.99;

getClosestKey(price_array, 0); // undefined
getClosestKey(price_array, 1); // 1
getClosestKey(price_array, 3); // 1
getClosestKey(price_array, 4); // 1
getClosestKey(price_array, 5); // 5
getClosestKey(price_array, 7); // 5
getClosestKey(price_array, 9); // 5
getClosestKey(price_array, 10); // 10
getClosestKey(price_array, 100); // 10

- Paul

---

@SmithSmithy 这是“未定义”的意思。没有传递参数，所以它变成了“未定义”。这在旧浏览器中非常有用，因为“未定义”实际上可能被覆盖，也可以作为一种简写方式。 - Paul

@SmithSmithy 这只是一个方便的方式，当目标值低于最小键时返回 undefined。 - Paul

谢谢。由于某些原因，我得到了不一致的结果...我不知道是我用JQuery键盘抬起触发函数的方式有问题还是什么原因...我采用了Fred的答案...感谢您的帮助。 - Smith Smithy

@SmithSmithy 可能吧。在一些编辑之前可能存在这种情况。我对它进行了很多编辑，哈哈。我不断地注意到错误。现在应该是一致的了。 - Paul

Answer 6

您可以使用Math.round()和一些简单的除法来将数字四舍五入到最接近的5的倍数：

var price_array = {};
price_array[1] = 39.99;
price_array[5] = 24.99;
price_array[10] = 19.99;

function qty_round(qty) {
  // Math.max() is used to enforce a minimum quantity of 1
  return Math.max(1, 5 * Math.round(qty / 5));
}

console.log(price_array[qty_round(1)]);  // 39.99
console.log(price_array[qty_round(4)]);  // 24.99
console.log(price_array[qty_round(9)]);  // 19.99
console.log(price_array[qty_round(10)]); // 19.99

通过一些小的修改，你可以使用Math.floor而不是Math.round来向下舍入，或者强制设定一个最大数量。

- leepowers

---

你认为为什么保证所有的阈值都是五的倍数，而且所有的五的倍数都是阈值呢？为什么不是1、5、10、20、30、50、100、200、500、1000等呢？ - Scott Sauyet

因为这是问题中提供的数据？否则循环是解决方法。 - leepowers

它们不是5的倍数。在25之后，它跳到25的倍数，然后是50，在100之后...它可能是任何东西。 - Smith Smithy

我认为你需要使用循环。即使在原始数据中，只有两个是5的倍数。 - Scott Sauyet