Entry

What is the best algorithm for matching key B to key A and applying value B to value A from list B to list A where B > A (many : 1)

Jun 14th, 2000 10:14
Matt Gregory,

This is my best attempt at the proper solutions (steps/pseudo-code)
1.) Create Comparator for Key: Compare(Key1, Key2) (<:-1),(=:0),(>:1) 
2.) QuickSort List A and List B with Comparator. (A*log(A))+(B*log(B))
3.) Iterate through shortest list.
4.) Search for solution in largest list.
5.) Since search cannot be guaranteed to be first matching record in 
smaller list, start at point found and walk both up and down the list 
until the first and last match are found.
6.) Apply Value(s) in Application List to Value(s) in destination list.
for all items in short list
  search for match in larger list (see best search algorhythims)
  walk up and down from match until you find the first and last match
  from first match to last match apply values from/to matches
  **** If you know that you will not have multiple matches drop matched 
keys from search list.
end looping