Javascript sortable array/object structure and performance

Question

In javascript we can't use key/value pairs in objects if they should keep their sort order. Instead we need an array with something like ES6 map for it.

It seems like the below could be one way to structure it. I put id and wrap all the items into an array. The same idea for the col blocks.

[
  {
    id: 21,
    items: [
      {
        col: 'name',
        data: {
          data1: 'hello',
          data2: 'world'
        }
      },
      {
        col: 'slug',
        data: {
          data1: 'hello',
          data2: 'world'
        }
      }
    ]
  },
  {
    id: 44,
    items: [
      {
        col: 'name',
        data: {
          data1: 'hello',
          data2: 'world'
        }
      },
      {
        col: 'slug',
        data: {
          data1: 'hello',
          data2: 'world'
        }
      }
    ]
  },
]

The problem

The problem with this approach is that when it can't use key/value pairs, then it needs to go through the whole array to find id 44 for example. In real life there are not just two groups, there can be a 100. The same thing with the cols. It may be 20 cols in each items group. It needs to walk through all of the items to find for example the column slug.

Dreamcode

let result = get(44, 'slug', 'data2');

Question(s)

• Is the structure above a good and performant one?
• How can I step in this without performace hits?

Answer 1

While the @VLAZ answer can be good in many cases, here is an alternative.

function lookup(items) {
    let results = {};

    items.forEach((rows, y) => {
        if (!(rows['id'] in results)) {
            results[rows['id']] = {
                y: y,
                cols: {}
            };
        }

        rows.items.forEach((cols, x) => {
            results[rows['id']].cols[cols['col']] = x;
        });
    });

    return results;
}

It will generate a lookup object that looks like this:

21: {
  y: 0,      
  cols: {
    data1: 0
    data2: 1
  }
},
44: {
  y: 1,      
  cols: {
    data1: 0
    data2: 1
  }
}

Then with another function I can use x and y to get the correct data from the original array.

Update

To get data, I now use this:

function getData(items, lookup, row, col) {
  const x = lookup[row]['cols'][col];
  const y = lookup[row]['y'];

  return items[y]['items'][x];
}

let final = getData(data.rows, test, 28, 'meta_title');

console.log(final['data']);

Answer 2

Your structure will not be terribly slow to lookup anything. With a linear scan through each item and its sub-fields, you'll get a O(m*n) complexity because you need to go over each group, then check each of its columns and finally grab the data by name (assuming it has complexity of O(1)). With 100 groups and 20 columns, that's still 2000 operations at most, if you grab the very last item. That should be reasonably fast, as you'll just be doing a check to see if that's the correct item and discarding the rest.

Still, if that's too slow, and you need to do a lot of lookups, you can drop the complexity of fetching data to O(1) by generating a lookup table from your data that will essentially work like this:

+----------+-------------+----------+-------+
| group id | column name | data key | value |
+----------+-------------+----------+-------+
|       21 | name        | data1    | hello |
|       21 | name        | data2    | world |
|       21 | slug        | data1    | hello |
|       21 | slug        | data2    | world |
|  etc...  |    etc...   |  etc...  | etc...|
+----------+-------------+----------+-------+

You can use nested Maps to represent that:

const data = [ { id: 21, items: [ { col: 'name', data: { data1: 'hello', data2: 'world' } }, { col: 'slug', data: { data1: 'hello', data2: 'world' } } ] }, { id: 44, items: [ { col: 'name', data: { data1: 'hello', data2: 'world' } }, { col: 'slug', data: { data1: 'hello', data2: 'world' } } ] }, ];

const lookupTable = new Map();

data.forEach(group => {
  if (!lookupTable.has(group.id)) {
    lookupTable.set(group.id, new Map());
  }
  
  const groupLookupTable = lookupTable.get(group.id);
  
  group.items.forEach(column => {
    //only set the `data` object
    groupLookupTable.set(column.col, column.data);
  })
})

function get(id, col, data) {
  const group = lookupTable.get(id);
  
  if (!group) return;
  
  const columnData = group.get(col);
  
  if (!columnData) return;
    
  return columnData[data];
}


let result = get(44, 'slug', 'data2');

console.log(result)

You can just assign the object belonging to data last because it's cheaper than turning it into a Map and holding another object in memory for the same data. At the same time, the lookup speed of a key in an object should be the same as looking it up from a Map. In fact, you can implement this using plain objects instead of Maps but it's at the very least, a Map ensures the key stays the same type.