Как индексировать декартово произведение

Question

Предположим, что переменные x и theta могут принимать возможные значения [0, 1, 2] и [0, 1, 2, 3], соответственно.

Предположим, что в одной реализации, x = 1 и theta = 3. Естественным способом представления этого является кортеж (1,3). Однако я хотел бы вместо этого пометить состояние (1,3) одним индексом. А «грубой силы» метод делает это, чтобы сформировать декартово произведение всех возможных упорядоченных пар (x,theta) и посмотреть его:

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, что имеет смысл, если мы посмотрим его в 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 до некоторого максимума, как говорит ваш пример, вы можете использовать формулу

index = x * N_theta + theta 

где (x, theta) это один ваших кортежей.

Это обобщает следующим образом к более высокой размерности кортежей: Если N список или кортеж, представляющий диапазоны величин (так N[0] есть число возможных значений для первой переменной, и т.д.) и p является кортежем , вы получите индекс в лексикографически отсортированный список всех возможных кортежей, используя следующий фрагмент кода:

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

Это может быть не самый Pythonic способ сделать это, но это показывает, что происходит: вы думаете о своих кортежей как гиперкуб, где вы можете идти только по одному измерению, но если вы достигаете края, ваша координата в «следующем» измерении увеличивается, и ваши путешествия сбрасывание координат. Читателю рекомендуется сделать несколько снимков. ;)

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

Для полноты картины я включу моя реализация решения Джулиана Kniephoff в, get_box3, с немного адаптированной версией оригинальной реализации, get_box2:

# '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 

, но я ожидаю, что «аналитический» метод будет быстрее. Я изменил представление на p и N, как было предложено Джулианом.