This script works but keeps timing out with longer inputs. How can I improve its speed? [Ruby]

The script takes a string such as this: (15, 176) (65, 97) (72, 43) (102, 6) (191, 189) (90, 163) (44, 168) (39, 47) (123, 37) and breaks it into an array of arrays. It then computes the largest possible number of choices, with the guideline that each selected array has to have both numbers smaller than the previous selection. For the above string, the right output would be 4.

people = File.read(ARGV[0])
people = people.sub("$$", '').sub(/$$$/, '').split("\) $$") people.map! { |p| p.split(', ') } count = 0 test = people.permutation.to_a test.each do |perm| test_count = 0 perm.each_with_index do |item, i| test_case = perm[i+1] unless test_case == nil test_count += 1 if item[0] > test_case[0] && item[1] > test_case[1] end count = [count, test_count].max end end p count  Anyways, it works but is sloooow, especially with longer strings. How can I speed this up? I know the nested loops can be problematic and as the string grows the number of permutations grows. Any advice would be much appreciated. Edit: I am running this on Ruby 1.8.7. Edit: New attempt at the problem/script: people = '(15, 176) (65, 97) (72, 43) (102, 6) (191, 189) (90, 163) (44, 168) (39, 47) (123, 37)' #people = File.read(ARGV[0]).chomp people = people.sub("\(", '').sub(/$$$/, '').split("\) \(")
people.map! { |p| p.split(', ').map {|a| a.to_i } }

ht = people.sort_by { |h| h[0] }
wt = people.sort_by { |w| w[1] }
a_i = []

ht.each do |item|
a_i << wt.index(item)
end

def subgen( array, count=1, t=(array.length+1) )
if array.length == 1
return count
end
without = subgen(array[0..-2], count, t)
if array[0] > array[-1] || array[-1] > t
return without
else
with = subgen(array[0..-2], count+=1, t = array[-1])
return [with, without].max
end
end

current = 0
a_i.each_with_index do |item, j|
test = a_i[j..-1]
current = [current, subgen(test)].max
end

p current


This has been thoroughly tested and works, but there has to be a way to make it faster. Any ideas?

• On my machine, the first code takes 10.776s while the second one takes 0.005s. That's 2000x faster ! – barjak Dec 18 '11 at 22:01
• @barjak It is incredibly faster! but I think it can still be made faster. For long lists subgen gets called a lot and I wonder if there is a way to reduce that some how. I've been reading about memoization but I can't figure out how to apply it to my new script. – Sean Lerner Dec 19 '11 at 3:31
• I realized that your problem seems to be somewhat similar to the longest common subsequence problem. – barjak Feb 17 '12 at 10:49

So, you are generating every possible permutations of the array, which is a O(n!) operation. This is huge.

I think this can be done with an O(n²) algorithm. I would do :

• create an array containing the pairs, ordered by the first value
• create another one containing the pairs, ordered by the second value
• create a third array containing, for each index of the first array, the index in the second array where we can find the corresponding value.
• find every subset of this third array whose values are in ascending order.

The result is the length of the biggest subset.

Example

first array | second array | third array
------------+--------------+------------
15,176      | 102,6        | 7
39,47       | 123,37       | 3
44,168      | 72,43        | 6
65,97       | 39,47        | 4
72,43       | 65,97        | 2
90,163      | 90,163       | 5
102,6       | 44,168       | 0
123,37      | 15,176       | 1
191,189     | 191,189      | 8


The ascending subsets are :

• 7 8
• 3 6 8
• 3 4 5 8
• 6 8
• 4 5 8
• 2 5 8
• 5 8
• 0 1 8
• 1 8
• 8

The biggest subset is (3 4 5 8), and its size is 4.

Complexity

The sorts can be done with O(n log n) The creation of the third array is O(n²) To find the subset, I think we can do that with O(n²) (I'm not sure about that)

So, the whole thing should be O(n²).

The algorithm for finding the ascending subsets is not trivial. I'm sure it will be fun to implement !

The code below follows the known rule: use the simplest possible algorithm, unless some code-probing bottleneck analysis (with your particular data) proves it insufficiently fast.

So, it basically uses the algorithm you first gave, plus @barjak's indices, and his insights both into what you are doing, and into the fact that combinations are as good as permutations, after they are both sorted. Also:

• Since finding the largest is the goal, it starts with the largest and works smaller so it can stop as soon as it finds the first one.
• It converts the numbers so it can work with the faster binary instead of strings.
• It doesn't convert the huge enumerable (of combinations or even permutations) into an array, which stores everything in memory and could cause a paging slowdown, but individually checks its entries.
• Using Ruby library methods when possible (mostly written in C), rather than our own Ruby code, speeds up execution.

The Ruby library 'makes no guarantees about the order in which the combinations are yielded', so at first I didn't trust it to keep the order of the indices when giving combinations of them, but I put in such a further algorithmic optimization to avoid sorting by height for every combination.

Also, I bail out as soon as I find the weights out of order, rather than sort the entire combination's worth. But still it will be O(n!) because, almost n times, it checks almost n!/(n-k)!k! combinations, each of length k. And, it still takes a long time: 16 seconds at just 22 pairs (with my setup). 19 pairs takes 2 seconds.

I found your description, 'the largest possible number of choices with the guidelines that each selected array has to have both numbers smaller than the previous selection' somewhat hard to interpret. So, I read your code instead, and came up with:

Problem: drawing from a set of integer 2-tuples, find the length of the longest subset which can strictly increase in both variables.

For your test data, I got 4 also.

def print_time
p Time.new.sec
end

def increasing?(array, indices)
f = array.at indices.first
skip_first = 1
(skip_first...indices.length).reduce(f) do |memo,i|
each = array.at indices.at i
return false unless memo < each # Bail out quickly.
each # Slide the pair.
end
true
end

def search
# Get filename.
##fn = ARGV.at 0

# Read string containing parenthesized pairs of numbers.
# Or, use test string.
##paren = '(15, 176) (65, 97) (72, 43) (102, 6) (191, 189) (90, 163) (44, 168) (39, 47) (123, 37)'
# Or, generate repeatable random numbers.
srand 0
n, max = 22, 100000
paren=(0...n).map{(0..1).map{rand max}}.map{|a,b| "(#{a}, #{b})"}.join ' '
print_time

# Translate to array syntax.
commas = paren.gsub ') (', '),('

# Convert parentheses to brackets.
brack = commas.tr '()', '[]'
s = "[ #{brack} ]"

# Convert into pairs of numbers in binary.
people = eval s

# Pre-sort people by height then weight, which may speed sorting the combinations.
people = people.sort

# Remove duplicates, which could reduce the length considerably, depending on the data.
people = people.uniq

# Get single numbers in binary.
ht = people.map{|e| e.first} # Height.
wt = people.map{|e| e.last } # Weight.

# Set up indices.
pl = people.length
p "N after removing duplicates is #{pl}."
indices = (0...pl).to_a

result = 0 # Preserve the result after the block.

# Start from the largest size of subset and go downward.
decreasing_sizes = (1..pl).to_a.reverse
decreasing_sizes.each do |size|

# Use combinations instead of permutations.
# Don't produce a big array of combinations, because
# it could be causing slow virtual-memory paging.
# Instead, check each combination when it is supplied.

indices.combination(size).each do |comb|

# Each combination is sorted already in increasing order by height.
## comb = comb.sort{|i,k| (ht.at i) <=> (ht.at k)}

# Check whether the weights are also in increasing order.
next unless increasing? wt, comb
w = wt.values_at *comb # Double check.
next unless w.sort==w

# We have found our first subset, which is increasing in both
# height and weight.
# Therefore, its size is the largest good subset size.
# Report this size and stop.
result = [size, comb.map{|i| people.at i}]
throw :result, result
end
end
end

length, pairs = catch(:result){ search}
p "One of the longest subsets has length #{length}: #{pairs.inspect}, length #{length}."
print_time


Best for this is an algorithm similar to Patience sorting. I wrote some Ruby code that processes tens of thousands of pairs in something like a few seconds. You're welcome to write me if you're still interested.