CODEWITHSUNDEEP
javaalgorithmoptimization
Rohan
Rohan

Reputation: 21

Comparing two lists and fetching child objects

I have 2 lists. One, with just the parent Objects and the other which may have its child objects.

Since these lists can be huge, I needed a way to fetch just the child objects by comparing the two lists in something better than O(n^2)

The condition for an object to be a child object is it should have its parent objects name as its base. eg: 'abcd' would be a child object of 'abc'.

List<String> childList=new ArrayList<>();
for(String parent: parentList){
  for(String child: childList){
    if(child.matches(parent + "(.*)"))
      childList.add(child)
  }
}

With like 14k objects, this was taking like 10 seconds. Can someone help me optimize this

Upvotes: 2

Views: 241

Answers (2)

MrSmith42
MrSmith42

Reputation: 10151

Depending on the length of your names you could create a map of all prefixes of the child-names in the first pass. (Costs O(n*nameLength) time)

Than you can lookup for each parent in O(1) (if you use a HashMap) which children have the parents-name as prefix.

You should definitely try to avoid RegExp for matching. these are not cheap!

P.s. You could also google for "prefix-trees", if it's only about detecting prefixes.

Upvotes: 1

m.raynal
m.raynal

Reputation: 3113

If I understood your problem well, you have 2 lists of strings, A and B. The goal is to determine which strings in B are a prefix of a string in A.
Then, there exists a data structure, called trie, which does exactly that.
First, you need to insert each string of A into your trie.
Then for each string of B, you can do the following: traverse the trie by reading the current string (or word). If you cannot go till the end of the word because a node is missing, then the current word is not the 'child' of any object'.
On the other hand, if you finish the current word and are still on the trie, then you word is a prefix of a word stored beforehand. You should find implementations of java tries (or ideas on how to implement them) here.

Upvotes: 1

Related Questions