Enhancing the performance of sortable array and object structures in Javascript

Question

Enhancing the performance of sortable array and object structures in Javascript

When working with objects in javascript and needing to maintain a specific sort order, key/value pairs cannot be used. Instead, utilizing an array with features like ES6 map is more suitable.

An example structure that could be used is shown below. The id is specified and all the items are enclosed within an array. This concept applies to the col blocks as well.

[
  {
    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 Challenge

An issue arises with this method when it becomes necessary to search for specific identifiers such as finding id 44. In real scenarios, there could be numerous groups instead of just two, adding complexity. Similarly, there may be several columns within each group of items, requiring extensive searching.

Desired Code Structure

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

Regarding Performance

Does the provided structure ensure good performance?
How can efficiency be maintained without compromising performance?

javascript arrays performance object

Answer 1

Answer №1

Your method of retrieving data will not lead to significant delays. By scanning through each item and its sub-fields in a linear manner, you will encounter a complexity of O(m*n). This means that for every group, you need to check each column and extract the data by name (assuming this operation has an O(1) complexity). With 100 groups and 20 columns, the maximum number of operations is 2000, if you are accessing the very last item. This process should be reasonably fast, as it involves verifying if it's the correct item and discarding the rest.

If you find this approach too slow and require frequent lookups, you can enhance the efficiency of fetching data to O(1) by creating a lookup table from your data structure. This entails setting up a table with group IDs, column names, data keys, and corresponding values.

+----------+-------------+----------+-------+
| 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...|
+----------+-------------+----------+-------+

This can be represented using nested Maps:

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)

When assigning the object to data, consider doing so at the end since it is more cost-effective than converting it into a Map or storing another object's memory for the same data. Additionally, the speed of looking up a key in an object should be equivalent to searching for it in a Map. Although plain objects can be used instead of Maps, a Map ensures consistency in key types at the very least.

Answer 2

Your method of retrieving data will not lead to significant delays. By scanning through each item and its sub-fields in a linear manner, you will encounter a complexity of O(m*n). This means that for every group, you need to check each column and extract the data by name (assuming this operation has an O(1) complexity). With 100 groups and 20 columns, the maximum number of operations is 2000, if you are accessing the very last item. This process should be reasonably fast, as it involves verifying if it's the correct item and discarding the rest.

If you find this approach too slow and require frequent lookups, you can enhance the efficiency of fetching data to O(1) by creating a lookup table from your data structure. This entails setting up a table with group IDs, column names, data keys, and corresponding values.

+----------+-------------+----------+-------+
| 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...|
+----------+-------------+----------+-------+

This can be represented using nested Maps:

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)

When assigning the object to data, consider doing so at the end since it is more cost-effective than converting it into a Map or storing another object's memory for the same data. Additionally, the speed of looking up a key in an object should be equivalent to searching for it in a Map. Although plain objects can be used instead of Maps, a Map ensures consistency in key types at the very least.

Answer 3

Answer №2

Although the solution provided by @VLAZ may work well in various scenarios, here is an alternative approach.

function createLookup(items) {
    let lookupTable = {};

    items.forEach((row, y) => {
        if (!(row['id'] in lookupTable)) {
            lookupTable[row['id']] = {
                y: y,
                columns: {}
            };
        }

        row.items.forEach((col, x) => {
            lookupTable[row['id']].columns[col['column']] = x;
        });
    });

    return lookupTable;
}

This function will produce a lookup object structured like this:

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

Subsequently, another function can be utilized to retrieve the correct data from the original array based on x and y coordinates.

Update

The following method is now employed to fetch data:

function fetchItemData(items, lookupTable, rowId, column) {
  const columnIndex = lookupTable[rowId]['columns'][column];
  const rowIndex = lookupTable[rowId]['y'];

  return items[rowIndex]['items'][columnIndex];
}

let result = fetchItemData(data.rows, test, 28, 'meta_title');

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

Answer 4

Although the solution provided by @VLAZ may work well in various scenarios, here is an alternative approach.

function createLookup(items) {
    let lookupTable = {};

    items.forEach((row, y) => {
        if (!(row['id'] in lookupTable)) {
            lookupTable[row['id']] = {
                y: y,
                columns: {}
            };
        }

        row.items.forEach((col, x) => {
            lookupTable[row['id']].columns[col['column']] = x;
        });
    });

    return lookupTable;
}

This function will produce a lookup object structured like this:

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

Subsequently, another function can be utilized to retrieve the correct data from the original array based on x and y coordinates.

Update

The following method is now employed to fetch data:

function fetchItemData(items, lookupTable, rowId, column) {
  const columnIndex = lookupTable[rowId]['columns'][column];
  const rowIndex = lookupTable[rowId]['y'];

  return items[rowIndex]['items'][columnIndex];
}

let result = fetchItemData(data.rows, test, 28, 'meta_title');

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

Enhancing the performance of sortable array and object structures in Javascript

The Challenge

Desired Code Structure

Regarding Performance

Answer №1

Answer №2

Update

Similar questions

Do Firefox and Chrome yield different results when using navigator.geolocation.getCurrentPosition()?

Table borders disappear when loading PHP echoed tables with jQuery and Ajax

Is it possible to provide an offset to the raycaster in three.js?

How can I merge my two custom filters into a single, more efficient custom filter?

Dealing with mixed data types when parsing JSON using PHP's array and

How can I use VB codebehind in ASP to display a dialog box to the user asking for a yes or no response?

What is the best method to access nested objects in react-native when working with this.state?

When working with JavaScript, it's important to note that any reference used outside of the catch block

"Unleashing the Power of AngularJS: Implementing a Global Error Handler to Display and

Is there a way to conceal a div that holds a full table when the table consists of only one row?

Loading a Threejs model: "The CORS policy has blocked access to XMLHttpRequest from origin 'null' - How can I test this locally? Or should I simply upload it?"

What is the best way to incorporate an array of objects into the React state hook?

ajax with names that are alike

`Populating fields in Firebase``

Issue with v-model not updating data correctly when using switch and select dropdown in VueJS

Issue encountered while attempting to save a value in localStorage

Error in typescript: The property 'exact' is not found in the type 'IntrinsicAttributes & RouteProps'

A guide to translating the centroid of an object in three.js during panning操作

Configuring the port number of the socketio connection in Heroku

Add several additional views following an element within a View in Backbone