How to optimize search algorithm

Question

I have 4 dropdown multi-select filters in row.

Which need to render and on every selected option. I need to add that selected option in new array and update that current array -> object.property.selected = false/true.

I am searching trough array of objects, and one property of every object have array of objects.

You can found code example on this code-pen: https://codepen.io/nikolatrajkovicits/pen/JqpWOX?editors=0012

Here is how that array looks:

export const getFiltersList = () => [
  {
    title: 'Taxonomy',
    options: [
      {
        id: 0,
        name: 'Competitions',
        selected: false,
        key: 'Taxonomy'
      },
      {
        id: 1,
        name: 'Events',
        selected: false,
        key: 'Taxonomy'
      },
      {
        id: 2,
        name: 'Data',
        selected: false,
        key: 'Taxonomy'
      },
      {
        id: 3,
        name: 'Organisations',
        selected: false,
        key: 'Taxonomy'
      },
      {
        id: 4,
        name: 'Players',
        selected: false,
        key: 'Taxonomy'
      },
      {
        id: 5,
        name: 'Teams',
        selected: false,
        key: 'Taxonomy'
      }
    ]
  },
  {
    title: 'Source',
    options: [
      {
        id: 0,
        name: 'Facebook',
        selected: false,
        key: 'Source'
      },
      {
        id: 1,
        name: 'Twitter',
        selected: false,
        key: 'Source'
      },
      {
        id: 2,
        name: 'Instagram',
        selected: false,
        key: 'Source'
      },
      {
        id: 3,
        name: 'Websites',
        selected: false,
        key: 'Source'
      }
    ]
  },
  {
    title: 'Timeframe',
    options: [
      {
        id: 0,
        name: 'Past hour',
        selected: false,
        key: 'Timeframe'
      },
      {
        id: 1,
        name: 'Past 24 hours',
        selected: false,
        key: 'Timeframe'
      },
      {
        id: 2,
        name: 'Past week',
        selected: false,
        key: 'Timeframe'
      },
      {
        id: 3,
        name: 'Past month',
        selected: false,
        key: 'Timeframe'
      },
      {
        id: 4,
        name: 'Past year',
        selected: false,
        key: 'Timeframe'
      }
    ]
  },
  {
    title: 'Location',
    options: [
      {
        id: 0,
        name: 'Location 1',
        selected: false,
        key: 'Location'
      },
      {
        id: 1,
        name: 'Location 2',
        selected: false,
        key: 'Location'
      },
      {
        id: 2,
        name: 'Location 3',
        selected: false,
        key: 'Location'
      },
      {
        id: 3,
        name: 'Location 4',
        selected: false,
        key: 'Location'
      }
    ]
  }
];

Here is algorithm:

selectFilter = ({ id, key }) => {
    const { filtersList, selectedFilters } = this.state;
    const tempFilters = filtersList;
    const tempSelected = selectedFilters;
    const i = tempSelected.length;

    tempFilters.forEach((filter) => {
      if (filter.title === key) {
        filter.options.forEach((option) => {
          if (option.id === id) {
            option.selected = !option.selected;
            const isFilterExist = tempSelected.filter(
              (selectedFilter) => selectedFilter.name === option.name
            );
            if (!isFilterExist.length) {
              const selectedItem = { name: option.name, key, id };
              tempSelected[i] = selectedItem;
            }
          }
        });
      }
    });
    this.setState({
      filtersList: tempFilters,
      selectedFilters: tempSelected
    });
  };

On code pen you can found version which is in pure javascript code.

How to make better cleaner faster search algo?

Any advice article, tutorial, comment?

Not sure I agree on how you are trying to manage selected, I have solution below. — Neil, Jun 01 '19 at 14:25

VLAZ · Accepted Answer · 2019-06-01T15:39:38.307

First of all these two are unnecessary:

const tempFilters = filtersList;
const tempSelected = selectedFilters;

The variables are references to the exact same objects and you already have variables for those. You can simply use filtersList and selectedFilters instead of tempFilters and tempSelected respectively.

tempFilters.forEach((filter) => {
      if (filter.title === key) {`

Since the entirety of the .forEach is the if, then this suggests you need to use .filter instead.

tempFilters.filter((filter) => filter.title === key)`

Same here, when you get inside the if

filter.options.forEach((option) => {
  if (option.id === id) {

you can simplify to

filter.options.filter((option) => option.id === id)

Continuing on, this line is a waste

const isFilterExist = tempSelected.filter(
    (selectedFilter) => selectedFilter.name === option.name
);

No need to run .filter on the entire array, when all you're interested in is if there are any items that match the predicate or not. Use .some instead which directly gives you a boolean:

const isFilterExist = tempSelected.some(
    (selectedFilter) => selectedFilter.name === option.name
);

Also, since you are always inverting the boolean, it's a bit simpler to just find the opposite - if a filter doesn't exist - invert the predicate and use .every to get that. The reasoning is that some of the element match but you want the opposite which is logically that every of the elements match the exact opposite of the predicate. Finally, I've changed the name to use has to sound a bit more natural.

const hasNoFilter = tempSelected.every(
    (selectedFilter) => selectedFilter.name !== option.name
);

So, as a start, the code can be re-written into the following:

selectFilter = ({ id, key }) => {
  const { filtersList, selectedFilters } = this.state;
  const i = selectedFilters.length;

  filtersList
    .filter((filter) => filter.title === key)
    .forEach(filter => {
      filter.options
        .filter((option) => option.id === id)
        .forEach(option => {
          option.selected = !option.selected;
          const hasNoFilter = tempSelected.every(
            (selectedFilter) => selectedFilter.name !== option.name
          );

          if (hasNoFilter) {
            const selectedItem = { name: option.name, key, id };
            selectedFilters[i] = selectedItem;
          }
        });
    });
  this.setState({
    filtersList,
    selectedFilters
  });
};

This makes it a bit easier to reason about the code.

It seems like you have filters with unique titles and options with unique IDs within those, which means that the combination of title + ID would also be unique.

With that in mind, you are interested in a single value not, any number of them, thus you don't need to do all the looping. You can use .find to fetch the values you are interested in which then makes the entire code easier to read:

selectFilter = ({ id, key }) => {
    const { filtersList, selectedFilters } = this.state;

    const filter = filtersList.find((filter) => filter.title === key);

    const option = filter.options.find((option) => option.id === id)

    option.selected = !option.selected;
    const hasNoFilter = tempSelected.every(
      (selectedFilter) => selectedFilter.name !== option.name
    );
    if (hasNoFilter) {
      const selectedItem = { name: option.name, key, id };
      selectedFilters.push(selectedItem);
    }

    this.setState({
      filtersList,
      selectedFilters
    });
  };
}

As a consequence of this code only working with a single item, you don't need the line const i = selectedFilters.length; because you are going to make a single insertion in the array. Previously, the line selectedFilters[i] = selectedItem; enclosed in a all the loops suggested you would insert multiple values but all in the same position, so as to leave only the last one. A simple .push is enough to append to the end.

score 1 · Answer 2 · answered Jun 01 '19 at 12:21

If I were you, I would change the structure of the Json object before I use it. For example: If the Json became a key, value pair where the key is the title and the value is the array that represents options. This will make you get rid of the first loop and you will get the list of option in o(1) like the complexity of a hash table. Note: I assumed that the title here is unique. Second Change I would make:you want to search by ID and from the example you mentioned the options array is sorted by id meaning first element has id =0 and it is at index 0 etc. so if the value of the new representation is an array the access of elements at index i is also o(1) by this you will get rid of the second loop too. Note: if the title is not unique or the options ids are not sorted you need to update the example in order to get a better solution.

@Soha great advice, really thank you. I will combine your suggest with VLAZ suggest. This is really helpful. — Mark James, Jun 01 '19 at 15:37

Neil · Answer 3 · 2019-06-01T14:35:34.470

So I have a react implementation, as you tagged it.

In a nutshell, I took the two concerns (data & state) and split them out from your inbound data. In addition your data coming in had 2 properties which were unnecessary (selected & key).

key - This is react implementation that you add during the return function. I used your title as it was unique across each object.

selected - Data should contain the important properties coming into the app, this is classed as application state more than data. If you took this approach you would add more more computing overhead. You would have to update every other instance to false when you select an item. I lifted this state up to the main app.

Here is the code I wrote:

dropdown-data.json:

[
  {
    "title": "Taxonomy",
    "options": [
      {
        "id": 0,
        "name": "Competitions"
      },
      {
        "id": 1,
        "name": "Events"
      },
      {
        "id": 2,
        "name": "Data"
      },
      {
        "id": 3,
        "name": "Organisations"
      },
      {
        "id": 4,
        "name": "Players"
      },
      {
        "id": 5,
        "name": "Teams"
      }
    ]
  },
  {
    "title": "Source",
    "options": [
      {
        "id": 0,
        "name": "Facebook"
      },
      {
        "id": 1,
        "name": "Twitter"
      },
      {
        "id": 2,
        "name": "Instagram"
      },
      {
        "id": 3,
        "name": "Websites"
      }
    ]
  },
  {
    "title": "Timeframe",
    "options": [
      {
        "id": 0,
        "name": "Past hour"
      },
      {
        "id": 1,
        "name": "Past 24 hours"
      },
      {
        "id": 2,
        "name": "Past week"
      },
      {
        "id": 3,
        "name": "Past month"
      },
      {
        "id": 4,
        "name": "Past year"
      }
    ]
  },
  {
    "title": "Location",
    "options": [
      {
        "id": 0,
        "name": "Location 1"
      },
      {
        "id": 1,
        "name": "Location 2"
      },
      {
        "id": 2,
        "name": "Location 3"
      },
      {
        "id": 3,
        "name": "Location 4"
      }
    ]
  }
]

<App />:

import React from "react";

import dropdownData from "./dropdown-data.json";

const Dropdown = ({ options = [], ...props }) => (
  <select {...props}>
    {options.map(({ id, ...option }) => (
      <option key={id}>{option.name}</option>
    ))}
  </select>
);

const App = () => {
  const [data, setData] = React.useState({});

  return (
    <>
      {/* A debugging helper :) */}
      <pre>{JSON.stringify(data, null, 2)}</pre>

      {dropdownData.map(({ title, options }) => (
        <Dropdown
          key={title}
          {...{ options }}
          onChange={({ target }) =>
            setData({
              ...data,
              [title.toLowerCase()]: target.value
            })
          }
        />
      ))}
    </>
  );
};

export default App;

The pre tag shows the data being returned below. Since there was an empty object for the initial state, your state does not get populated with untouched / unneeded data.

Let me know how this helps, this was 2 files inside a create-react-app.

Did you find it useful? Do you have any question on the implementation? — Neil, Jun 01 '19 at 15:47
Yes, it is totally new and different approach to the problem, it is inspirative and I will use it in the future for sure. So far I didn't had in mind idea of that solution. Very useful! — Mark James, Jun 01 '19 at 15:51

How to optimize search algorithm

3 Answers3