Complexity

branches.jpg

The issue of managing complexity has been coming up in my Project Euler problems the best optimized solutions don't set up your CPU to double as an electric blanket.

Complexity, in a nutshell, is about how requirements to find a solution scale in relationship to the problem. For example, the difficulty of assigning two variables is just twice as demanding as assigning one variable, so it's not a very complex task. In contrast, the complexity of finding multiple pairs of numbers with nested iteration expands as a square. Every additional cycle of the external iteration requires a whole series of nested cycles.

Let me use a concrete example of a problem involving large numbers. I solved it two ways: once quite naively and once with reduced complexity.

The question involved locating the optimal times in one day to purchase and then sell a single stock, when the stock value is saved in an array every minute after midnight.

My first solution to find the optimal times of purchase and sale had a wheel within a wheel system. The stock could only be sold after it was purchased (I assumed one minute of latency), so as I progressed through the day to analyze the potential purchase times, I compared that with all future times a sale could be made. The best optimization I could do was to analyze only times of sale that came after the purchase, but that just cuts the processing by half.

Note that this program will not recommend a purchase or sale time on days in which the stock price only declined.

class ProfitFinderOne
attr_accessor :purchase_time, :sale_time, :best_profit

PRICES = []

def initialize
@best_profit = 0
@purchase_time
@sale_time
scan
end

def scan
purchase_index = 0
while purchase_index < PRICES.length
purchase_price = PRICES[purchase_index]
sale_index = purchase_index + 1
while sale_index < PRICES.length
sale_price = PRICES[sale_index]
if sale_price - purchase_price > best_profit
best_profit = sale_price - purchase_price
purchase_time = purchase_index
sale_time = sale_index
end
end
purchase_index += 1
end

end

To reduce the complexity however, I can remove that wheel inside the other wheel. Now I have chosen to pre-process information about optimal future sale prices and the time that price is available. Now, as the program progresses through the day, each comparison is only to one other element in the parallel array. Thus reducing the complexity from a square to linear growth pattern.

class ProfitFinderTwo
attr_accessor :purchase_time, :sale_time, :best_profit

PURCHASE_PRICE = []
BEST_FUTURE_SALE = []

def initialize
@best_profit = 0
@purchase_time
@sale_time
populate_sale_array
scan
end

def populate_sale_array
temp_array = PURCHASE_PRICE.reverse
last_best = [PURCHASE_PRICE[-1], PURCHASE_PRICE.length - 1]
temp_array.each_with_index do |value, index|
if value > last_best[0]
last_best[0] = value
last_best[1] = index
end
BEST_FUTURE_SALE << last_best
end
BEST_FUTURE_SALE.reverse!
end

def scan
PRICES.each_with_index do |purchase_price, index|
profit = BEST_FUTURE_SALE[index][0] - purchase_price
if profit > best_profit
best_profit = profit
purchase_time = index
sale_time = BEST_FUTURE_SALE[index][1]
end
end
end

end