Getting the value from key in a dictionary that is nearest to a given number using JavaScript
I have a dictionary (keys are integers, values are float). I would now ask the dictionary for the value of the key that is > than the given numb开发者_开发问答er but < than the next greater key.
Example:
dict = {100: 0.0035, 150: 0.0024, 200: 0.0019}.
i give 122, it should give me 0.0035
i give 333, it should give me 0.0019
i give 200, it should give me 0.0024
Thanks!
This is a perfect use-case for a binary tree. The topic is a little broad for a stack overflow answer, but here goes anyway.
function addValueToNode(tree, nodeidx, value) {
var left = 2*nodeidx + 1;
var right = 2*nodeidx + 2;
if(value > tree[nodeidx]) {
if(!tree[right])
tree[right] = value;
else
addValueToNode(tree, right, value);
} else {
if(!tree[left])
tree[left] = value;
else
addValueToNode(tree, left, value);
}
}
function addValueToTree(tree, value) {
if(tree.length == 0)
tree.push(value)
else
addValueToNode(tree, 0, value);
}
function addValuesToTree(tree, values) {
for(var i = 0; i < values.length; i++)
addValueToTree(tree, values[i]);
}
function addDictionaryToTree(tree, dict) {
var values = [];
for(var key in dict) {
values.push(key);
}
values.sort();
addValuesToTree(tree, values);
}
function findClosestValue(tree, nodeidx, value) {
var left = 2*nodeidx + 1;
var right = 2*nodeidx + 2;
if(value > tree[nodeidx]) {
if(!tree[right] || tree[right] == value)
return tree[nodeidx];
else
return findClosestValue(tree, right, value);
} else {
if(!tree[left])
return tree[nodeidx];
else
return findClosestValue(tree, left, value);
}
}
var tree = [];
var dict = {100: 0.0035, 150: 0.0024, 200: 0.0019};
addDictionaryToTree(tree, dict);
var closest = findClosestValue(tree, 0, 175);
var dictValue = dict[closest];
alert( closest + " : " + dictValue);
Working example (tested under Firefox 3.6):
<html>
<head>
<script type="text/javascript" src="jquery-1.3.2.min.js"></script>
<script type="text/javascript">
var dict = {100: 0.0035, 150: 0.0024, 200: 0.0019};
function r(aNum) {
var result;
for (var key in dict) {
var dist = key - aNum
if ((dist < 0 && dist < result) || result === undefined) {
result = key;
}
}
return dict[result];
}
$(document).ready(function() {
$('li').each(function() {
var id = $(this).attr('id').replace('n', '')
$(this).html(id + ": " + r(id));
});
});
</script>
</head>
<body>
<ul>
<li id="n122"></li>
<li id="n333"></li>
<li id="n200"></li>
</ul>
</body>
</html>
var value = 122;
var min = null;
var minkey = null;
for ( var key : dict ) {
if (min==null || abs(value-key)<min) {
min=abs(value-key);
minkey = key;
}
}
return dict[minkey]
You can try this. Sorry if smth, i have no chance to test it.
The following function matchs your requirements:
function getNumber(dict, value) {
var key, found;
for (key in dict) {
if (value - key > 0) {
found = key;
}
}
return dict[found];
}
var dict = {100: 0.0035, 150: 0.0024, 200: 0.0019};
// Firebug assertions
console.assert(getNumber(dict, 122) == 0.0035);
console.assert(getNumber(dict, 333) == 0.0019);
console.assert(getNumber(dict, 200) == 0.0024);
Binary search, using a modified (stable) algorithm that searches for the least element meeting the comparison criteria.
If your dictionary is not huge, you could try to cycle from, for example, (122-1). If it's undefined, subtract 1 and try again, until you find something :)
加载中,请稍侯......
精彩评论