Ruby Beginner - Fuzzy matching / string manipulation

Question

There is no intended end use for this. It is for learning and development only.

I got carried away following an example and ended up with a miniaturised vehicle registration system. You can bulk generate records, each of which is given a unique registration number in keeping with British registration format. I've written a script that compares and lists all registration numbers that fall afoul of the criteria.

It does work, but it is incredibly slow. (over an hour to check 1 mil records). I am looking for critique on the logic and any optimisation I may have missed.

Example string: AA99AAA

Example criteria: A?9?AAA

 def full_search(offensive_list)
    p 'Full check:'
    p "Comparing #{$all_vehicles.count} records against #{offensive_list.count} banned combinations"
    p 'This will take a few minutes'
    vrm_array, example_array = [], []
    vrm_list = $all_vehicles.keys.sort
    vrm_list.each do |vrm|
        vrm_array << vrm.split("") #We split each reg into an array of characters
    end
    offensive_list.each do |example|
        example.strip!
        example_array << example.split("") #and the same with our banned combinations
    end

        vrm_array.each do |vrm|
            example_array.each do |example| #itterate through vrms x examples
                @formatted_vrm = vrm.dup
                if example.length == vrm.length
                    example.each_index do |index|
                        if example[index] == "?" #for each wildcard we add a wildcard to the vrm for comparison
                            @formatted_vrm[index] = "?"
                        end
                    end
                    if @formatted_vrm == example then offensive_found(vrm, example) end
                end
            end
        end
end

def offensive_found(vrm, example)
    built_vrm = ""
    built_example = ""
    if vrm.class == Array #clean up formatting so we can store it
    vrm.each do |character|
            built_vrm << character
        end
        example.each do |character|
            built_example << character
        end
    else
        built_example = example #clearly redundant, but it works so...
        built_vrm = vrm
    end

    if $bad_vrms[built_example] # if we already have a record
        prev_matched = $bad_vrms[built_example] #just add to the array
        prev_matched << built_vrm
        $bad_vrms.store(built_example, prev_matched)
    else
        new_match = [built_vrm]        # or create a new hash key 
        $bad_vrms.store(built_example, new_match)
    end
    #p "#{built_vrm} - matched with #{built_example}"
end

If you'd prefer you can clone the full thing on github. https://github.com/Niall47/RubySomDemo

Answer 1

You could consider using Regex to speed up the search. The cleanest way to do so would be to change your full_search.txt to be Regex expressions. For example A?9?AAA would need to be changed to A.9.AAA (in Regex the . means any single character).

Then you could change your full_search method to look like this:

def full_search(offensive_list)
  vrm_list = $all_vehicles.keys.sort
  offensive_examples = offensive_list.map(&:strip)

  offensive_examples.each do |offensive_example|
    vrm_list.grep(/^#{offensive_example}$/).each do |offensive_vrm|
      offensive_found(offensive_vrm, offensive_example)
    end
  end
end

In the Regex the ^ means start of string and the $ means end of string; this basically ensures that substrings are not matched e.g.) abcd matches with the regex .c but not with ^.c$

If you don't want to modify your list, you could so something that dynamically creates the regex in Ruby. For example: offensive_example.gsub("?", ".") this would replace all ? with ..

---

A couple unrelated pointers...

• Ruby has a String#chars method that is (arguably) more readable and might have some minor performance improvements over string.split("").
• Instead of assigning an initial empty value and building it in an each, consider using Array#map to reduce the amount of variable reassignments.

# before
vrm_array = []
vrm_list.each do |vrm|
  vrm_array << vrm.split("")
end
vrm_array.each do |vrm|
    # do stuff
end

# after
vrm_array = vrm_list.map { |vrm| vrm.split("") } # this calls `split` on each element in `vrm_list`
vrm_array.each do |vrm|
    # do stuff
end

• If you need to take an array of characters and join them together into a single string, consider using Array#join.

irb(main):001:0> ['a', 'b', 'c'].join
=> "abc"

• If you have a Hash and you want an empty array if a key doesn't exist, consider using a default value (but be careful with some gotchas related to mutable defaults)

$bad_vrms = Hash.new { |h, k| h[k] = [] } # the argument is the default value which in this case is a block that initializes the key's value to a new instance of an empty array

# now we don't need to check if a key exists and can simply push to it
$bad_vrms[example] << vrm