Я ищу более быстрый, чем грубый алгоритм, для нахождения наилучших коэффициентов (весов) в такой задаче:
Определите образец как серию N чисел. В этом случае, скажем, N = 10. Количество образцов, M , очень велико, скажем, M = 1000000. По сути это матрица из M строк X N столбцов. Итак, набор этих образцов выглядит так:
S_0_0 S_0_1 S_0_2 ... S_0_N
S_1_0 S_1_1 S_1_2 ... S_1_N
...
S_M_0 S_M_1 S_M_2 ... S_M_N
Кроме того, существует соответствующая серия из N весов. Число весовых рядов, P , также огромно, скажем, P = 2000000. Это еще одна матрица из P строк X N столбцов. Это похоже на выборку:
W_0_0 W_0_1 S_0_2 ... W_0_N
W_1_0 W_1_1 S_1_2 ... W_1_N
...
W_P_0 W_P_1 S_P_2 ... W_P_N
Я пытаюсь найти ряд весов (то есть правильный ряд из наборов весов), который максимизирует следующую сумму (то есть, какую строку x ):
W_x_0 * S_0_0 + W_x_1 * S_0_1 + ... + W_x_N * S_0_N +
W_x_0 * S_1_0 + W_x_1 * S_1_1 + ... + W_x_N * S_1_N +
...
W_x_0 * S_M_0 + W_x_1 * S_M_1 + ... + W_x_N * S_M_N
Оба файла данных ( W s и S s) загружаются из файла. S s - числа с плавающей запятой двойной точности во всем диапазоне, поддерживаемом процессорами x86 (от отрицательного к положительному). W s мы можем считать целыми числами.
Способ грубой силы сделать это очень прост: для каждой строки веса умножьте ее на каждую строку выборки в наборе выборок, сохраняя при этом промежуточную сумму. Следите за общими суммами для каждого весового ряда и выбирайте лучшее в конце.
Теперь, где, я думаю, есть место для более умного / более быстрого алгоритма в составе набора веса. Мы можем предположить только одно число в наборе веса изменений в строке. Таким образом, набор веса может выглядеть следующим образом (здесь краткость N = 5):
1 1 1 1 1
1 1 1 1 2
1 1 1 2 2
1 1 2 2 2
1 2 2 2 2
2 2 2 2 2
2 2 2 2 1
2 2 2 1 1
2 2 1 1 1
и т. Д.
Другими словами, в методе «грубой силы» явно будет много избыточных вычислений. Если наборы данных не были такими большими, одна мысль состоит в том, чтобы создать карту / кэш каждого продукта с весом выборки и проверить это перед вычислением. Но учитывая размер набора данных, я думаю, что использование памяти будет слишком высоким; также моя интуиция говорит, что поиск карты / кэша может быть медленнее, чем выполнение наивного умножения.
Кто-нибудь знает об алгоритме или библиотеке, которые здесь уместны?
Редактировать 1: У меня была опечатка в исходном сообщении: набор веса ошибочно показал два изменения от одного ряда к другому. Действительно, в каждой строке должно быть только одно изменение. Кроме того, не слишком читайте о «шаблоне» изменений: основная идея заключается в том, что в каждой строке есть только одно изменение, но как эти изменения могут быть изменены, чтобы соответствовать конкретному алгоритму.
Редактировать 2: Я думаю примерный набор веса теперь действительно показывает только одно изменение в строке.