デカルト積を指数化する方法

Question

変数xとthetaは、それぞれ[0, 1, 2]と[0, 1, 2, 3]の可能な値をとることができるとします。

具体的には、x = 1とtheta = 3としましょう。これを表現する自然な方法は、タプル(1,3)です。しかし、代わりに単一のインデックスで状態(1,3)にラベルを付けたいと思います。

が

import numpy as np 
import itertools 

N_x = 3 
N_theta = 4 

np.random.seed(seed = 1) 
x = np.random.choice(range(N_x)) 
theta = np.random.choice(range(N_theta)) 

def get_box(x, N_x, theta, N_theta): 
    states = list(itertools.product(range(N_x),range(N_theta))) 
    inds = [i for i in range(len(states)) if states[i]==(x,theta)] 
    return inds[0] 

print (x, theta) 
box = get_box(x, N_x, theta, N_theta) 
print box 

これは、我々がそれを見れば理にかなって(x, theta) = (1,3)とbox = 7与える：これを行うための「ブルートフォース」メソッドは、すべての可能な順序対(x,theta)のデカルト積を形成し、それをルックアップするためにありますstatesリストは：それを見ずに、事前にインデックスを決定することが可能でなければなりませんよう

[(0, 0), (0, 1), (0, 2), (0, 3), (1, 0), (1, 1), (1, 2), (1, 3), (2, 0), (2, 1), (2, 2), (2, 3)]

しかし、この「ブルートフォース」アプローチは、非効率です。これを行う一般的な方法はありますか？ （N_xとN_thetaの状態の数は、実際のアプリケーションによって異なる場合があり、デカルト積にはより多くの変数が存在する可能性があります）。

Answer 1

あなたは常に辞書順あなたstatesを保存し、あなたの例が示すようにxとthetaの可能な値は、常に0からいくつかの最大の完全な範囲であれば、あなたは、以下の式を使用することができます(x, theta)が1である

index = x * N_theta + theta 

あなたのタプルの。

これは、より高い次元のタプルに対して、以下のように一般化：N変数の範囲を表すリストまたはタプルである場合には（そうN[0]等、最初の変数の可能な値の数である）とpタプルであります、あなたは、次のスニペットを使用して、すべての可能なタプルの辞書順ソートされたリストにインデックスを取得：

index = 0 
skip = 1 
for dimension in reversed(range(len(N))): 
    index += skip * p[dimension] 
    skip *= N[dimension] 

これはそれを行うには、ほとんどのPython的な方法ではないかもしれませんが、それは何が起こっているかを示しています。あなたはあなたのタプルを考えますあなたが1つの次元だけに進むことができるハイパーキューブですが、もしあなたが端に達すると、「次の」次元の座標が増加し、あなたの移動座標リセット。読者は絵を描くように勧められます。 ;）

Answer 2

私はそれがあなたが持っているデータによって異なると思います。それらがまばらである場合、最良の解決策は辞書である。任意のタプルの次元に対応します。

import itertools 
import random 

n = 100 
m = 100 
l1 = [i for i in range(n)] 
l2 = [i for i in range(m)] 

a = {} 
prod = [element for element in itertools.product(l1, l2)] 
for i in prod: 
    a[i] = random.randint(1, 100) 

パフォーマンスについては非常に良い情報源はthis discutionです。

Answer 3

私は、元の実装のわずか適応バージョンで、get_box3、get_box2をジュリアンKniephoffのソリューションの私の実装が含まれます完全を期すために：

# 'Brute-force' method 
def get_box2(p, N): 
    states = list(itertools.product(*[range(n) for n in N])) 
    return states.index(p) 

# 'Analytic' method 
def get_box3(p, N): 
    index = 0 
    skip = 1 
    for dimension in reversed(range(len(N))): 
     index += skip * p[dimension] 
     skip *= N[dimension] 
    return index 

p = (1,3,2)   # Tuple characterizing the total state of the system 
N = [3,4,3]   # List of the number of possible values for each state variable 

print "Brute-force method yields %s" % get_box2(p, N) 
print "Analytical method yields %s" % get_box3(p, N) 

どちらも「ブルートフォース」と '分析的方法は同じ結果をもたらす：

Brute-force method yields 23 
Analytical method yields 23 

しかし、私は '解析的な'方法がより速くなると期待している。 Julianの示唆に基づき、表現をpとNに変更しました。