Deduplicate data

Question

I currently have an implementation that helps us deduplicate data but I know it's slow.

Here's an example, note that I'm using OpenStruct here when really these are Mongoid objects pulled from the database.

require 'ostruct'

vendor_data = [
  OpenStruct.new(activity_id: "abc123"),
  OpenStruct.new(activity_id: "def456"),
  OpenStruct.new(activity_id: "ghi789"),
  OpenStruct.new(activity_id: "jkl012"),
]

existing_ids = ["abc123", "def456"]

def slow_method(vendor_data, existing_ids)
  vendor_data.each do |vendor|
    next if existing_ids.include? vendor.activity_id
    vendor.name = "A company"
    # in real life we'll call vendor.save or update here
  end
end

slow_method(vendor_data, existing_ids)

I know this is \$O(n^2)\$ but I'm struggling to figure out a faster way to do this.

I'm not sure on CodeReview if it's best practice to list out the 4 other variations I've tried, however, none of them seem to be any better (ie faster) or more readable than my first pass.

Answer 1

If existing_ids is an array, then existing_ids.include? vendor.activity_id takes O(n) time.

Turning existing_ids into a Set will make that lookup O(1), and thus the slow_method would be O(n).

require 'set'
existing_ids = Set.new["abc123", "def456"]

Answer 2

Without any knowledge of Ruby it seems you want to modify all Objects in vendor_data whose activity_id appears in existing_ids

First of all I think your algorithm is in O(n*m) with n being the length of vendor data and m the length of existing ids.

It seems you are using an array to store the vendors and existing ids. Is it possible to sort the vendors by activity id beforehand. Consider sorting the existing ids if m < n. You could then perform a binary search so performance would be in O(m*log(n))

Example in pseudo-code

foreach id in existing_ids do //performs at O(m)
   vendor = binarySearch(id, vendors) //performs at O(log(n))
   if vendor[id] != null then update vendor //performs at O(m*log(n))
next

Even better would be if could have constant access to every vendor by it's activity id. However this would work easily if the ids were 1,2,3,4....

Example in pseudo-code

foreach id in existing_ids do
  if vendor[id] != null then update vendor //performs at O(m)
next

Ok this would be the fastest approach though it's well possibly not possible