Pull to refresh

Проблема «maximum-subarray» на примере курса доллара

Algorithms *

В чём суть


В статье предлагается найти промежуток дат, за который можно было заработать больше всего на разнице в курсе доллара к рублю за последние 5 лет.
image
На русском языке наименование проблемы будет звучать примерно как максимальная сумма элементов подмассива в массиве. В статье приведен алгоритм вычислений, а так же результат его работы.

image
Как я к этому пришёл

Недавно начал читать отличную книгу CLRS (Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein. Introduction to Algorithms, Third Edition.). Как не трудно догадаться, в книге изложены фундаментальные знания computer science.
Один из разделов книги как раз приводит реализацию алгоритма для решения этой проблемы. Для закрепления знаний и удовлетворения собственного интереса, я решил применить его на данных о курсе доллара к рублю за последние 5 лет.

Суть проблемы

Как видно из графика за последние 5 лет курс доллара менялся очень сильно. И было бы разумно предположить, что наверняка самой выгодной сделкой было бы купить в абсолютный минимум и продать в последующий локальный максимум (который порой не так легко обнаружить «на глаз»).

image

Давайте проверим это утверждение.

Решение

Самым простым решением было бы «пойти в лоб» и перебором найти суммы всех комбинаций субмассивов и сравнить их на поиск максимального, однако это решение займёт по времени O(n^2) не очень нас устраивает, так как есть уверенность, что можно сделать это оптимальнее.

Решением будем рекурсивно разбивать входной массив на 2 подмассива через середину и искать максимальную сумму в каждой и частей, а так же на их пересечении. Данный процесс будет требовать у нас O(n lg n), что вполне эффективно.

Давайте распишем пример:

Данные мы получим из www.oanda.com/currency/historical-rates в .csv файле в формате
"2011-10-02","32.1914",,,,
"2011-10-01","32.0809",,,,
"2011-09-30","31.9086",,,,
"2011-09-29","31.7294",,,,
"2011-09-28","32.0421",,,,
"2011-09-27","32.2233",,,,
"2011-09-26","32.0980",,,,
"2011-09-25","32.0673",,,,
...


Далее нам надо считать данные и подготовить их для обработки:

	courses = []
	
	reader = csv.reader(open('data.csv', 'rb'), delimiter=',', quotechar='"')
	prev = 0
	
	for row in reader:
		#получить текущий элемент
		cur = float(row[1])
		#в самом начале разницы в курсе не должно быть
		if prev == 0:
			prev = cur 
		#сохраним разницу в списке
		value = [row[0], prev - cur, row[1]]
		prev = cur
		courses.insert(0, value)


Данные в файле в обратном порядке относительно времени, поэтому вставляем их инверсно. Во время обработки данных мы ищем разницу в ежедневном курсе previous — current. Нашей задачей как раз и будет поиск максимальной суммы этих разностей.

def find_max_subarray(a, low, high):
	#выход из рекурсии
	if high == low:
		return low, high, a[low][1]
	else:
		#разбиваем массив на 2 части 
		mid = (low + high) / 2

		#находим максимум в левой части
		left_low, left_high, left_sum = find_max_subarray(a, low, mid)
		#находим максимум в правой части
		right_low, right_high, right_sum = find_max_subarray(a, mid + 1, high)
		#находим кросс-максимум
		cross_low, cross_high, cross_sum = find_crossing(a, low, mid, high)

		if (left_sum >= right_sum) & (left_sum >= cross_sum):
			return left_low, left_high, left_sum
		elif (right_sum >= left_sum) & (right_sum >= cross_sum):
			return right_low, right_high, right_sum
		else:
			return cross_low, cross_high, cross_sum



И функция поиска кросс-максимума (проходящего через mid — середину деления).

def find_crossing(a, low, mid, high):
	max_left = 0
	max_right = 0

	left_sum = -1e308
	sum = 0
	#уходим влево от центра
	for i in range(mid, low, -1):
		sum = sum + a[i][1]
		if sum > left_sum:
			left_sum = sum
			max_left = i
			max_right = 0

	right_sum = -1e308
	sum = 0
	#уходим вправо от центра
	for j in range(mid + 1, high):
		sum = sum + a[j][1]
		if sum > right_sum:
			right_sum = sum
			max_right = j

	return max_left, max_right, left_sum + right_sum



Ну и выведем результат, который нас интересует


min, max, sum = find_max_subarray(courses, 0, len(courses)-1)

print courses[min]
print courses[max]
print sum
 


В результате я получил

['2008-07-16', 0.07420000000000115, '23.1269']
['2009-02-05', 0.12059999999999604, '36.1257']
13.1194


И немного поигрался, сдвинув нижнюю дату на 2011 год

['2011-05-05', 0.006199999999999761, '27.2657']
['2011-09-26', 0.12530000000000285, '32.0980']
4.9576


Весь код можно найти на gist.github.com/1257729

Спасибо за внимание!
Tags:
Hubs:
Total votes 70: ↑40 and ↓30 +10
Views 6.6K
Comments 31
Comments Comments 31

Posts