multidimensional array - two dimensional lookup table -- how to store with headers in javascript - Stack Overflow

admin管理员组

文章数量:1379425

I have a requirement to calculate a result by looking it up in a table based on two values. The table is like this:

     Bar  <10   20   30   40   50   60
    Foo
   <1.0   .14  .17  .22  .29  .31  .45
    1.1   .16  .18  .25  .32  .37  .51
    1.2   .19  .20  .29  .37  .41  .53
    1.3   .21  .22  .32  .44  .49  .59
    1.4   .25  .26  .34  .51  .52  .68
    1.5   .29  .31  .39  .53  .54  .71

where the numbers along the top are ranges for the Bar value (where the number given is the top end of the range), and the numbers down the left side are ranges for the Foo value. If I'm given Bar = 24 and Foo=1.3, the lookup answer will be .32. (The numbers above are made up, of course, and the real table is about 25 X 25 in size.)

All of this has to be done in javascript, including storing the lookup values.

One possible approach is to store the values as a hash of hashes:

var lookup = { 1.0: {10:.14, 20: .17, 30:.22}); etc. etc.

where the outer value is the Foo value, and each Foo value maps to an object that maps Bar value to the answer. Messy and hard to read, but fairly explicit.

Another approach is to store the values as an array of arrays, and get the indexes from somewhere else. That is, I store the values across the top:

var BarColumns = [10, 20, 30, 50, 50, 60];

and down the side

var FooRows = [1.0, 1.1, 1.2, 1.3, 1.4, 1.5];

When given some values, I use the above lists to turn those into indexes, and then use those indexes to look things up in a two-dimensional array that holds the answer:

var lookup = [
  [.14, .17, .22, .29, .31, .45],
  [.16, .18, .25. .32, .37, .51],
  etc.
];

That corresponds a lot more closely with the original table, but without the headers, the table data is not very human-readable at all, and I think this is even harder to maintain -- particularly if the columns change.

Another option -- the super explicit, with the ranges repeated in each object:

var lookup = [{foo:1.0, bar:10, result:.14}, {foo:1.0, bar:20, result: .17}, etc.];

This is very explicit, but will presumably be enormous with 25 X 25 values.

So, my question is: what's the best way to store my original table in such as way that I can use it for lookups and also have it be human-readable and maintainable? One of my ideas above? Or something else entirely?

Important points I should have added: 1) the actual lookup won't happen that often, so I'm not terribly concerned about performance (within reason), and 2) I got the table data as an Excel spreadsheet from the client, but the best oute would be if I could turn the final javascript over to the client and have them maintain it - hence the concern about readability.

I have a requirement to calculate a result by looking it up in a table based on two values. The table is like this:

     Bar  <10   20   30   40   50   60
    Foo
   <1.0   .14  .17  .22  .29  .31  .45
    1.1   .16  .18  .25  .32  .37  .51
    1.2   .19  .20  .29  .37  .41  .53
    1.3   .21  .22  .32  .44  .49  .59
    1.4   .25  .26  .34  .51  .52  .68
    1.5   .29  .31  .39  .53  .54  .71

where the numbers along the top are ranges for the Bar value (where the number given is the top end of the range), and the numbers down the left side are ranges for the Foo value. If I'm given Bar = 24 and Foo=1.3, the lookup answer will be .32. (The numbers above are made up, of course, and the real table is about 25 X 25 in size.)

All of this has to be done in javascript, including storing the lookup values.

One possible approach is to store the values as a hash of hashes:

var lookup = { 1.0: {10:.14, 20: .17, 30:.22}); etc. etc.

where the outer value is the Foo value, and each Foo value maps to an object that maps Bar value to the answer. Messy and hard to read, but fairly explicit.

Another approach is to store the values as an array of arrays, and get the indexes from somewhere else. That is, I store the values across the top:

var BarColumns = [10, 20, 30, 50, 50, 60];

and down the side

var FooRows = [1.0, 1.1, 1.2, 1.3, 1.4, 1.5];

When given some values, I use the above lists to turn those into indexes, and then use those indexes to look things up in a two-dimensional array that holds the answer:

var lookup = [
  [.14, .17, .22, .29, .31, .45],
  [.16, .18, .25. .32, .37, .51],
  etc.
];

That corresponds a lot more closely with the original table, but without the headers, the table data is not very human-readable at all, and I think this is even harder to maintain -- particularly if the columns change.

Another option -- the super explicit, with the ranges repeated in each object:

var lookup = [{foo:1.0, bar:10, result:.14}, {foo:1.0, bar:20, result: .17}, etc.];

This is very explicit, but will presumably be enormous with 25 X 25 values.

So, my question is: what's the best way to store my original table in such as way that I can use it for lookups and also have it be human-readable and maintainable? One of my ideas above? Or something else entirely?

Important points I should have added: 1) the actual lookup won't happen that often, so I'm not terribly concerned about performance (within reason), and 2) I got the table data as an Excel spreadsheet from the client, but the best oute would be if I could turn the final javascript over to the client and have them maintain it - hence the concern about readability.

• javascript
• multidimensional-array

Share Improve this question Follow edited Jun 6, 2014 at 18:57 Jacob Mattison asked Jun 6, 2014 at 18:39 Jacob MattisonJacob Mattison 51.1k1111 gold badges108108 silver badges128128 bronze badges 4

• I think it depends how you plan to modify the values as time goes on. Would you be receiving them in tuples of foo/bar/result each time? Or in bulk? – jraede Commented Jun 6, 2014 at 18:49
• Edited to add a little more -- I get the original data as an Excel spreadsheet, and I'm hoping to have it in a format where the client can maintain the data going forward. – Jacob Mattison Commented Jun 6, 2014 at 19:06
• So question is really how it would make sense for them to maintain it. If they add one at a time it would probably make sense to do the array of object literals. But if they get it in bulk it may be easier to do the array of arrays. – jraede Commented Jun 6, 2014 at 19:11
• Yes, good point. I think it's fair to assume that they'll have it as a table/spreadsheet, so the conversion to array of arrays might be fairly straightforward. – Jacob Mattison Commented Jun 6, 2014 at 19:16

Add a ment  | 

4 Answers 4

Sorted by: Reset to default 2

jsFiddle Demo

I would suggest creating a data structure for this process. This would involve a LookUp "class" which will mediate a set of DataPoint objects which will be contain a range, a bar, and a value.

Data Structure

var Range = function(lower,upper){
 this.lower = lower;
 this.upper = upper;
};
var DataPoint = function(range,bar,value){
 this.range = range;
 this.bar = bar;
 this.value = value;
};
var LookUp = function(){
 this.DataPoints = [];   
};
LookUp.prototype.add = function(data){
 this.DataPoints.push(data);  
};

LookUp.prototype.load = function(BarColumns,FooRows,ValueColumns){
 ValueColumns = ValueColumns.split(" ").filter(Boolean);
 for( var n = 0; n < FooRows.length; n++ ){
  var range = 0;
  for( var i = 0 ; i < BarColumns.length; i++ ){
   var val = parseFloat(ValueColumns[(BarColumns.length * n) + i],10);
   var point = new DataPoint(new Range(range,BarColumns[i]),FooRows[n],val);
   this.add(point);
   range = BarColumns[i];
  }
 }   
};
LookUp.prototype.find = function(x,bar){
 for(var i = 0; i < this.DataPoints.length; i++){
  var point = this.DataPoints[i];
  if( x > point.range.lower && x < point.range.upper && point.bar == bar){
   return point.value;
  }
 }
};

Sample Data

Note: The valCols string is just a copy paste of your grid. However, this could easily be reproduced from Excel. Have a concatenation at the end of every row, and then at the bottom of the concat column, concat all of those and it will be the same as the valCols shown here.

var BarColumns = [10, 20, 30, 50, 50, 60];
var FooRows = [1.0, 1.1, 1.2, 1.3, 1.4, 1.5];
var valCols = ".14  .17  .22  .29  .31  .45 .16  .18  .25  .32  .37  .51 .19  .20  .29  .37  .41  .53 .21  .22  .32  .44  .49  .59 .25  .26  .34  .51  .52  .68 .29  .31  .39  .53  .54  .71";

Setup

var lookup = new LookUp();
lookup.load(BarColumns,FooRows,valCols);

Use

console.log(lookup.find(24,1.3));//3.2
alert(lookup.find(24,1.3));//3.2

I prefer to use array of array to store the lookup table, so the lookup can benefit from binary search.

var foo = [1, 2, 3, 4, 5];
var bar = [6, 7, 8, 9, 10];
var table = [];

// populate example table
for (var i = 0; i < bar.length; i++) {
    table[i] = [];

    for (var j = 0; j < foo.length; j++) {
        table[i][j] = foo[j] * bar[i];
    }
}
console.log(table);

var binarySearch = function (arr, x) {
    var a = 0;
    var b = arr.length - 1;
    var m;

    if (x > arr[b]) throw "Search key is too big";

    while (b > a) {
        m = Math.floor((a + b) / 2);
        if (arr[m] == x) return m;
        if (arr[m] > x) {
            if (m - 1 < 0) return 0;
            if (x > arr[m - 1]) return m;
            b = m - 1;
        } else {
            if (m + 1 < arr.length && x < arr[m + 1]) return m + 1;
            a = m + 1;
        }
    }

    return a;
}

console.assert(binarySearch(foo, 0.5) == 0);
console.assert(binarySearch(foo, 1) == 0);
console.assert(binarySearch(foo, 1.5) == 1);
console.assert(binarySearch(foo, 2) == 1);
console.assert(binarySearch(foo, 2.5) == 2);
//console.log(binarySearch(foo, 6));

var lookup = function (f, b) {
    var col = binarySearch(foo, f);
    var row = binarySearch(bar, b);
    return table[row][col];
}

console.assert(lookup(3, 8) == 24);
console.assert(lookup(2.5, 8) == 24);
console.assert(lookup(2.5, 7.5) == 24);
console.assert(lookup(4, 9) == 36);

fiddle: http://jsfiddle/3Lw5C/2/

Since non-technical people will be managing this, we can build an UI to manage the foobar ranges and lookup table values. Then all values can be serialized, and easily copied and pasted into js code in one place.

var columns = 3;
var rows = 3;

var html = '';
for (var i = 0; i < columns+1; i++) {
    html += '<tr>';
    for (var j = 0; j < rows+1; j++) {
        if (i == 0 && j == 0) {
            html += '<td></td>';
            continue;
        }

        var classname = '';        
        if (i == 0) {
            classname = 'foo';
        } else if (j == 0) {
            classname = 'bar';
        } else {
            classname = 'data';
        }

        html += '<td class="'+classname+'"><input type="text" value="0" /></td>';
    }
    html += '</tr>';
}

$('table').html(html);

var getFoo = function() {
    var foo = [];
    $('td.foo').each(function(i,td) {
        foo[i] = parseFloat($(td).children('input')[0].value);
    })
    return foo;
};

var getBar = function() {
    var bar = [];
    $('td.bar').each(function(i,td) {
        bar[i] = parseFloat($(td).children('input')[0].value);
    })
    return bar;
};

var getData = function() {
    var data = [];
    var j;
    $('td.data').each(function(i,td) {
        if (i%columns==0) {
            j = i/columns;
            data[j] = [];
        }
        data[j][i%columns] = parseFloat($(td).children('input')[0].value);
    })
    return data;
};

var config = {};
config['foo'] = getFoo();
config['bar'] = getBar();
config['data'] = getData();
$('div').text(JSON.stringify(config));

fiddle: http://jsfiddle/MLKsf/

Hashes are good for finding the identical value, but for values that are between the table values a two dimensional array should work better.

If Foo is an exact value and Bar isn't I would use a hash of one dimensional arrays.

For the lookup range values as well as the headers use a one dimensional array for each.

Do you actually need the underlying data to be human-readable? Or do you just need a developer-friendly way to access a given value?

If we set aside the human-readable question, this looks like a fairly standard memory-vs-performance tradeoff. You can use a tight representation (the 2-d array) and then offer a user-friendly function like lookup(foo, bar) that does a little bit of processing to get the value, or you can store the data in a more verbose format (the hash of hashes) and allow direct lookup[foo][bar] access. Note that a 2d array is also a hash of hashes in JS, so there might be little or no memory difference. I'd ditch the super-explicit idea, since it likely has a significantly slower lookup time than either of the other two, as you need to iterate though the whole list in the worst case to find the right value.

Some further considerations here:

• How important, really, is the human-readability of the underlying data? The hash of hashes probably has a small advantage here, but only a small one (e.g. it's less amenable to console.table() for debugging).

• Is the data always dense, or are you likely to have sparse tables where the 2d array would have a bunch of nulls? In this case the hash of hashes might be a more pact and usable representation.

• How does the data e to you, and which of these formats requires more pre-processing? If you're actually putting this directly in code, then either format could be made relatively readable with judicious tabbing.

• You almost certainly want to offer a lookup() function in either case, so that you don't hardcode the implementation as a 2d array everywhere and lock yourself into that.

• How easy is it to get the right range position for a given input value? This will change depending on whether you know the ranges are evenly spaced, always a given number of decimal places, etc, in which case you can determine the hash keys with math; if the range ticks are arbitrary, then the "header array" approach has merit, since you might need to iterate through the headers to find the right key.

本文标签： multidimensional arraytwo dimensional lookup tablehow to store with headers in javascriptStack Overflow