Nishutosh Sharma Nishutosh Sharma - 1 month ago 8
Ruby Question

Efficient to delete all substrings of other elements within an array in Ruby

I have a complex problem of in-place editing of an array at hand.
I have an array in which some of the elements are sub-strings of other elements.I want to delete all the sub-strings and keep the supersets/strings only.
i.e. Array =>

['1', '1 1', '1 1 1', '1 1 1 2', '1 2 3 1', '1 2', '2 3']

After operation I should have a sanitized array =>
['1 1 1 2', '1 2 3 1']


Is there an efficient algorithm to achieve the same ?

Answer

It uses less memory, performs less computations. This one will delete substrings both ways, looping will be less. Brought

             user       system     total       real
    First    0.000000   0.000000   0.000000 (  0.000076)
    Second   0.010000   0.000000   0.010000 (  0.000037)
    Third    0.000000   0.000000   0.000000 (  0.000019)

Above mentioned is the benchmark results for the 2 algos mentioned above(First and Second) and this one(Third).

array = ['1 1 1', '1', '1 1', '1 1 1 2', '1 2 3 1', '1 2', '2 3', '1 2 3', '1 1 1']

i1 = 0
arr_len = array.length
last_index = arr_len - 1

while i1 <= last_index
  w1 = array[i1]
  i2 = i1 + 1
  while i2 <= last_index
    w2 = array[i2]
    # If w2 is a subset of w1
    if w1.include? w2
      # Delete from index i2
      array.delete_at(i2)
      # Decrement the array_length as one element is deleted
      arr_len -= 1
      # Decrement last index, as one element is deleted
      last_index -= 1
      next
    end
    # If w1 comes out to be a subset of w2
    if w2.include? w1
      # Delete the value from that index
      array.delete_at(i1)
      # Decrement the array_length as one element is deleted
      arr_len -= 1
      # Decrement last index, as one element is deleted
      last_index -= 1
      # Reset value of w1 as it is deleted in this operation
      w1 = array[i1]
      # Reset index of 2nd loop to start matching again
      i2 = i1 + 1
      # Move next from here only
      next
    end
    i2 += 1
  end
  i1 += 1
end
Comments