CODEWITHSUNDEEP
pythonalgorithm
Takkun
Takkun

Reputation: 6361

Fastest Search Through Random Nested Data

[
   [
      [2,33,64,276,1],
      [234,5,234,7,34,36,7,2],
      []
   ]
   [
      [2,4,5]
   ]
   .
   .
   .
   etc
]

I'm not looking for an exact solution to this, as the structure above is just an example. I'm trying to search for an ID that can be nested several levels deep within a group of IDs ordered randomly.

Currently I'm just doing a linear search which takes a few minutes to get a result when each of the deepest levels has a couple hundred of IDs. I was wondering if anyone could suggest a faster algorithm for searching through multiple levels of random data? I am doing this in Python if that matters.

Note: The IDs are always at the deepest level and the number of levels is consistent for each branch down. Not sure if that matters or not.

Also to clarify the data points are unique and cannot be repeated. My example has some repeats because I was just smashing the keyboard.

Upvotes: 1

Views: 193

Answers (1)

dbkaplun
dbkaplun

Reputation: 3647

The fastest search through random data is linear. Pretending your data isn't nested, it's still random, so even flattening it won't help.

To decrease the time complexity, you can increase the space complexity -- keep a dict containing IDs as keys and whatever information you want (possibly a list of indices pointing to the list containing the ID at each level), and update it every time you create/update/delete an element.

Upvotes: 3

Related Questions