2

I am creating a ReactJS app. The app has over 100,000 entities on screen which I am plotting using WebGL. The properties of these entirties are stored in a JSON/Dict type object. Whenever a user applies a filter, I need to go through the values, compare the properties, and select the ID (type UUID4) of those not matching the filter, so that I can turn their Visibility to False in the WebGL container.

I am presently using an Array of the following type :-

spriteProps = [ {id: xxxx-...-xxxx, color: Blue, Length: 10, points:50}, {id: yyyy-...-yyyy, color:Red, Length:25, points:112}, ..... ]

The user may want to see all entities which are Blue in color and have a length less than 100. So I have to iterate through each value and check which values match the filter. However, this is very slow.

What is the best data structure to use in this situation to get the best performance? Is there any JS library I can use to improve performance?

Thanks.

user3367601
  • 73
  • 5
  • Have you looked into third party libraries like ag-grid? It provides a large amount of the functionality you are looking to implement. – Souritra Das Gupta Nov 06 '19 at 04:42
  • 1
    I am using ag-grid for the filtering and sorting in the frontend. However, I need to still search through the data using JS code in the React App for displaying/hiding the sprites. I was looking for the most suitable ata structure for that. – user3367601 Nov 06 '19 at 05:03
  • Ah I understand what you mean. But for backend filtering, I would say it is better to write your own JS code. The way you represented your data seems fine. JS array and object prototype methods are pretty versatile and you can control how much data the frontend actually renders. If you absolutely want to use a library, look into ArrowJs by apache. I haven’t used it personally but hope it helps. – Souritra Das Gupta Nov 06 '19 at 05:22
  • Yes, I am ok with using vanilla JS code. I want to know what is better for this use case - Array, Map, Object, etc / ForEach, etc. – user3367601 Nov 06 '19 at 05:30
  • @user3367601 - Use [forEach()](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/forEach) to iterate over the array and `if` condition to check the length and color. Turn visibility off for elements which don't satisfy the criteria. See my [answer](https://stackoverflow.com/a/58723624/2924577) for more info. Before settling on any suggested library, test it on your data, compare the performance by yourself, and then make a decision. – Nikhil Nov 06 '19 at 05:48
  • You could use the map data structure but it requires more memory. And No major performance benefit over objects. If you need to manipulate individual elements prefer objects. If you might manipulate keys at runtime and need to keep track of size, use a map. – Souritra Das Gupta Nov 06 '19 at 05:49
  • I forgot to mention maps are ordered though if iterating in order matters to you, use a map. – Souritra Das Gupta Nov 06 '19 at 05:52

3 Answers3

0

https://www.ag-grid.com/react-getting-started/

Ag-grid is a good library that will help you implement what you are looking for. I have used it with data that was an array of objects and the dataset was very large. It should fit your needs perfectly. Sorting and searching works seamlessly. Your properties will be the column headings and you can sort and filter based on columns. Selecting rows and pinning specific rows is also possible.

Souritra Das Gupta
  • 120
  • 7
0

Basically in this use case you need to filter from large set of data. Cross filter is very good option. Crossfilter is a JavaScript library for exploring large multivariate datasets in the browser.

https://github.com/crossfilter/crossfilter

J L P J
  • 442
  • 3
  • 8
0

You can try the following binary search approach.

Choose any property likely to be used in the filtering criteria. I'm choosinglength here. When user applies filters and if length isn't used as a filter, then fallback to simply iterating the array in sequence.

  1. When data is available, sort the array in ascending or descending order based on length property.

  2. When user applies filters, perform a binary search to find the index above or below which all elements are within the given length.

  3. Iterate on the section of the array containing elements within given length and turn visibility off for elements with different color property.

  4. Then iterate on other section of the array containing elements greater than given length and turn visibility off for all these elements.

We can see that we are visiting every element in the array. So, this approach isn't any better than visiting each element in the array sequentially.

If all the elements have visibility off at the beginning and if we have to turn visibility on for selected elements, then we can avoid visiting the second section of the array (point 4), and this binary search approach will be useful in such case.

But since it isn't the case, we have to visit every element in the array and therefore time complexity couldn't get better than linear time O(n).

Nikhil
  • 6,493
  • 10
  • 31
  • 68
  • The order will only matter if use filters by length. And in that case, a map should be used as sorting have to be done manually. In majority of cases, we have to traverse the entire structure for filtering. So unfortunately, there isn’t any data structure that will reduce time complexity much. – Souritra Das Gupta Nov 06 '19 at 06:30
  • 1
    @SouritraDasGupta - Yes, but when not filtering by length we can fallback to simply iterating in sequence. Maps wouldn't give any extra performance gain here. Arrays maintain insertion order and can be sorted in-place, whereas a map maintains insertion order but cannot be sorted in-place — a new map must be created for [sorting a map](https://stackoverflow.com/a/31159284/2924577). We are comparing array vs map here, not object vs map. – Nikhil Nov 06 '19 at 13:52
  • yes that's what I told him. Can't beat classic objects and arrays. – Souritra Das Gupta Nov 06 '19 at 18:20