Fastest way to search through nested lists-CodePudding

So we have a list of objects where every object(restaurant) contains a list of object(items). And I’m trying to implement a search items method where the user will be able to directly search through items .

I already thought about going through all the restaurants and add every restaurant’s items to a list of items and search through that list . But this solution doesn’t seem scalable especially if we will have a lot of restaurants with a lot of items .

class Restaurant {
String name,
List<Item> items
…
}
class Item{
String name,
… }

CodePudding user response：

For the performance and time optimization, you have to look for the solution from the prespective of Algorithms and Data Structure.

But if you are looking for a simnple soution for the problem you can just do a nested loop for the search like the following:

String? searchItem(String searchQuery){
  for(Restaurant restaurant in restaurants){
    for(Item item in restaurant.items)
    {
      if(item.name.contains(searchQuery))
      {
        return item.name;
      }
    }
  }
  return null; // No Item Found!
}

NOTE: This implementation will do early return once it find an item, so the Best Case would be if the item is first one in first restaurant Ω(1), and the Worst Case would be it the item is the last one in the last restaurant O(n^2).

CodePudding user response：

There is a lot of possible solutions, many of which would require a DS&A knowledge. Though the simplest one would be to use a Map data structure. You can have a List of restaurants that contains a Map of items instead of a list. With this simple change, you can achieve O(n) complexity by only iterating through the restaurants.