• Post Reply Bookmark Topic Watch Topic
  • New Topic

Fastest algorithm to get a diff of two maps  RSS feed

 
Soren Skovsen
Greenhorn
Posts: 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Does anyone know a good and fast way to get added and deleted elements when comparing two maps?
The maps can be quite large and therefore the algorithm needs to be fast!
Regards
Soren
 
Stan James
(instanceof Sidekick)
Ranch Hand
Posts: 8791
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I'd probably start with the ole compare two ordered sets solution. If your maps are not already ordered, create new TreeMap( oldMap ). Then get the keys for each into a Set. And maybe turn each Set into an array. Call the two key sets A and B.

Say A was Monday's night's data and B was Tuesday's night's data. If KeyWasInAOnly, the key must have been deleted during the day Tuesday. If KeyWasInBOnly then somebody must have added the key during the day. If keys match, you might want to compare the actual data to see if it has been changed.
BTW: To keep the algorithm this clean, handle the end of one set by pretending it has an impossibly high key. Then the rest of the other set will all be less and will process properly through this loop. If that's not possible, add end tests: if A < B or BIsAtEnd
Ok, high performance. How fast is this? Exactly as fast as it is. Maybe try it and see if it is fast enough.
Hope that helps. Any other ideas?
[ August 06, 2003: Message edited by: Stan James ]
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!