質問
what is the best way to generate a cartesian product of some lists, not knowing in advance how many lists there are?
必要に応じて、ここで読むのをやめることができます。
バックグラウンド
私は学校にお金がないので、高速道路の料金所で夜勤をしている間、インターネットを使ってプログラミングを学ぼうとしています。演習として、いくつかの「プログラミングの課題」の問題を解決しようと決心しました。
プログラミングの割り当て
これが私が取り組もうとしている問題、TopCoderの特性です：
http://community.topcoder.com/stat?c=problem_statement&pm=3496
私は彼らの著作権表示を尊重するために完全な説明をコピーして貼り付けることはしませんが、逐語的に使用しない限り、要約できると思います（ただしIANAL）。
概要
過去の株価の「加重和」が、これらの価格のサブセットに同数の「加重」係数を掛けて得られる補遺の合計である場合、後者の合計が1.0になり、指定された有効な値のセットから選択されます。[-1.0、-0.9、...、0.9、1.0]、関数の引数として提供されたすべての履歴データでこの式を使用し、一度に5つの価格を調べ、次の価格を予測し、「重み係数」の順列を返します"これにより、平均予測誤差が最小になります。各実行で少なくとも6つの株価が存在するため、少なくとも1つの予測が保証され、最終結果は1E-9以内で正確である必要があります。
テストデータ
フォーマット：
- 入力データ用の1行（
list形式） - 期待される結果の1行
- スペーサーとしての1つの空の行
ダウンロード元：
私の解決策
import itertools
# For a permutation of factors to be used in a weighted sum, it should be chosen
# such than the sum of all factors is 1.
WEIGHTED_SUM_TOTAL = 1.0
FACTORS_CAN_BE_USED_IN_WEIGHTED_SUM = lambda x: sum(x) == WEIGHTED_SUM_TOTAL
# Historical stock price data should be examined using a sliding window of width
# 5 when making predictions about the next price.
N_RECENT_PRICES = 5
# Valid values for weighting factors are: [-1.0, -0.9, ..., 0.9, 1.0]
VALID_WEIGHTS = [x / 10. for x in range(-10, 11)]
# A pre-calculated list of valid weightings to consider. This is the cartesiant
# product of the set of valid weigths considering only the combinations which
# are valid as components of a weighted sum.
CARTESIAN_PRODUCT_FACTORS = [VALID_WEIGHTS] * N_RECENT_PRICES
ALL_PERMUTATIONS_OF_WEIGHTS = itertools.product(*CARTESIAN_PRODUCT_FACTORS)
WEIGHTED_SUM_WEIGHTS = filter(FACTORS_CAN_BE_USED_IN_WEIGHTED_SUM,
ALL_PERMUTATIONS_OF_WEIGHTS)
# Generator function to get sliding windows of a given width from a data set
def sliding_windows(data, window_width):
for i in range(len(data) - window_width):
yield data[i:i + window_width], data[i + window_width]
def avg_error(data):
# The supplied data will guarantee at least one iteration
n_iterations = len(data) - 5
best_average_error = None
# Consider each valid weighting (e.g. permutation of weights)
for weighting in WEIGHTED_SUM_WEIGHTS:
# Keep track of the prediction errors for this weighting
errors_for_this_weighting = []
for historical_data, next_to_predict in sliding_windows(data,
N_RECENT_PRICES):
prediction = sum([a * b for a, b in zip(weighting, historical_data)])
errors_for_this_weighting.append(abs(next_to_predict - prediction))
average_error = sum(errors_for_this_weighting) / n_iterations
if average_error == 0: return average_error
best_average_error = (average_error if not best_average_error else
min(average_error, best_average_error))
return best_average_error
def main():
with open('data.txt') as input_file:
while True:
data = eval(input_file.readline())
expected_result = eval(input_file.readline())
spacer = input_file.readline()
if not spacer:
break
result = avg_error(data)
print expected_result, result, (expected_result - result) < 1e-9
if __name__ == '__main__':
main()
私の質問
これはそのための間違ったStackExchangeフォーラムになるため、私は自分のソリューションのコードレビューを求めていません。その場合は、ソリューションを「コードレビュー」に投稿します。
代わりに私の質問は小さく、正確で明確で、このサイトのフォーマットに適合しています（うまくいけば）。
私のコードでは、itertoolsを使用してリストのデカルト積を生成します。本質的に、私は問題の核心を自分で解決するのではなく、解決策を私のためにそれを行うライブラリに委任します。これらの演習から学びたいのであれば、これは間違ったアプローチだと思います。私は自分で難しい部分をやるべきです、さもなければ、なぜ運動をするのですか？だから私はあなたに尋ねたいと思います：
what is the best way to generate a cartesian product of some lists, not knowing in advance how many lists there are?
私が知りたいのはそれだけです。必要に応じて、私のコードを批評することができます。すべてのテストに合格したとしても（特に私のような初心者の場合は、常により良い方法があります）、それは歓迎ですが、この質問がSOにとって「ちょうどいい」ものであるために、私は1つの側面だけに焦点を当てています。コードの、私が持っている具体的な問題と私が満足していない何か。もっとお話ししましょう、私はまた、標準的な「あなたはすでに何を試しましたか」を共有します...
明らかに、リストの数を知っていれば、この演習のトップソルバーが競争で行ったように、ネストされたforループを入力するだけで済みます。未知のものに対してこれを行う関数を書いてみましたリストの数ですが、どのアプローチを取るべきかわかりませんでした。最初のアプローチは、再帰関数を作成することでした。リスト1から、要素1を取得し、リスト2の要素1、次にリスト3の要素1などと組み合わせます。各「レイヤー」の要素をスタックにプッシュし、目的の深さに達したらポップします。到達可能な深度が妥当であるため、「スタックオーバーフロー」を恐れることはないと思います。次に、再帰呼び出しにあまりにも多くのパラメーターを渡さずに、可能な限り最も効率的な（メモリ/スペース）方法でこれを行うためのデータ構造を選択するのに苦労しました。データ構造は呼び出しの外部に存在する必要がありますか？呼び出しで渡されますか？任意のレベルの並列処理を実現できますか？どのように？非常に多くの質問と非常に少ない回答で、私はこの問題を解決するためにもっと知る必要があり、正しい方向にナッジを使用できることに気づきました。コードスニペットを提供していただければ、調査します。または、この種の問題を処理する正しい「コンピュータサイエンス」の方法を説明してください。私が考えていないことがあると確信しています。
最後に、上記のソリューションで検討したことは、ありがたいことに、ジェネレーターをフィルターフィルター処理することで、完全なデカルト積がメモリに保持されないようにすることです（コード内でいつでもリスト（ALL_PERMUTATIONS_OF_WEIGHTS）を実行した場合のように）。加重和として実際に使用できる組み合わせに対してのみ、メモリ内のスペースを占有しています。itertoolsを使用せずにデカルト積を生成できるシステムに適用すると、同様の注意が役立ちます。