Schnellste Möglichkeit, mehrere Indexierungsoperationen für Python-Listen zu verketten

Question

Ich möchte einige Daten klassifizieren, die ich habe und für die ich arbeiten möchte Ich möchte die Indexierung von Python-Listen verketten. Vereinfachte Ich habe eine verschachtelte Liste:

lst = [[[1], [2]], [[3, 3], [4]], [[5], [6,6,6]]] 

und ich möchte über das Produkt der ersten beiden Indizes wiederholen, aber der dritte die gleiche halten:

from itertools import product 

for index1, index2 in product(range(3), range(2)): 
    print(lst[index1][index2][0]) 

Allerdings möchte ich diese allgemeinere machen ohne vorher zu wissen, wie viele Substrukturen tief gehen muss (ich möchte die Zahl range an itertools.product Variable übergeben).

Ich kämpfe ein bisschen wie ich die [index1][index2][0] verallgemeinern kann eine willkürliche Anzahl von indices zu akzeptieren, das Beste, was ich functools.reduce mit war einfiel:

from functools import reduce 

for indices in product(range(3), range(2)): 
    print(reduce(list.__getitem__, indices, lst)[0]) 

Das furchtbar kompliziert erscheint (und deutlich langsamer ist als die manuelle Indizierung), also habe ich mich gefragt, ob es einen besseren und schnelleren Weg gibt, das zu tun. Ich benutze sowohl Python 2.x und 3.x und externe Bibliotheken sind in Ordnung (aber es sollte nicht NumPy oder Pakete basierend auf NumPy erfordern). Verwenden Sie einfach die Python-builtin reduce für diese

Answer 1

Ich würde, und es scheint nicht, dass komplexe und es war nicht so viel langsamer in meinem Test:

from itertools import product 

for x in product(range(3), range(2)): 
    rg = reduce(lambda result, index: result[index], x, lst) 
    value = rg[0] 

Wenn Sie sich über die sich Sorgen machen Zeitstrafe von reduce, können Sie einfach stattdessen eine for Schleife verwenden:

for x in product(range(3), range(2)): 
    value = lst 
    for index in x: 
     value = value[index] 
    value = value[0] 

Dies wird in allen Fällen als manuelle Indexierung langsamer sein, da ein for Schleife zusätzliche Operationen für herauszufinden, den Stop condi benötigt tion. Die Frage ist wie immer, ob sich die Geschwindigkeitsoptimierung für die Flexibilität einer beliebigen Tiefenspezifikation lohnt.

Was, warum Sie reduce vs. for, es verwenden würde, ist eine laufende stilistische Debatte innerhalb der Gemeinschaft JavaScript, ob Sie die verwenden sollten reduce, map, filter Funktionen auf Array s oder tun, um die for Schleife Version statt, weil es ist schneller, und Sie können sich auf diese Debatte beziehen, um auszuwählen, auf welche Seite Sie fallen.

---

TIMING mit for-Schleife:

In [22]: stmt = ''' 
    ...: from itertools import product 
    ...: def go(): 
    ...: lst = [[[1], [2]], [[3, 3], [4]], [[5], [6,6,6]]] 
    ...: for x in product(range(3), range(2)): 
    ...:  # rg = reduce(lambda result, index: result[index], x, lst) 
    ...:  value = lst 
    ...:  for index in x: 
    ...:   value = value[index] 
    ...:  value = value[0] 
    ...:  # value = lst[x[0]][x[1]][0] 
    ...: ''' 

In [23]: timeit(setup=stmt, stmt='go()', number=1000000) 
Out[23]: 4.003296852111816 

TIMING mit reduce:

In [18]: stmt = ''' 
    ...: from itertools import product 
    ...: def go(): 
    ...: lst = [[[1], [2]], [[3, 3], [4]], [[5], [6,6,6]]] 
    ...: for x in product(range(3), range(2)): 
    ...:  rg = reduce(lambda result, index: result[index], x, lst) 
    ...:  value = rg[0] 
    ...:  # value = lst[x[0]][x[1]][0] 
    ...: ''' 

In [19]: timeit(setup=stmt, stmt='go()', number=1000000) 
Out[19]: 6.164631128311157 

TIMING mit manuellen Indexierungs:

In [16]: stmt = ''' 
    ...: from itertools import product 
    ...: def go(): 
    ...: lst = [[[1], [2]], [[3, 3], [4]], [[5], [6,6,6]]] 
    ...: for x in product(range(3), range(2)): 
    ...:  # rg = reduce(lambda result, index: result[index], x, lst) 
    ...:  value = lst[x[0]][x[1]][0] 
    ...: ''' 

In [17]: timeit(setup=stmt, stmt='go()', number=1000000) 
Out[17]: 3.633723020553589 

Answer 2

Ich schlage eine rekursive Art und Weise.

def theshape(lst): 
    l=lst 
    shape=[] 
    while isinstance(l,list): 
       shape.append(len(l)) 
       l=l[0] 
    return shape 

Diese Funktion soll die Form Ihrer Struktur finden, die bis zur letzten Dimension regelmäßig ist.

def browse(lst): 
    shape=theshape(lst) 
    ndim=len(shape) 
    def level(l,k): 
     if k==ndim: 
      print(l) 
     else: 
      for i in range(shape[k]): 
       level(l[i],k+1) 
    level(lst,0) 

Dieser durchsuchen rekursiv alle Ebenen. Es minimiert Zeigeränderungen.

Ein einfaches Beispiel:

u=arange(2**6).reshape(4,2,1,2,2,1,1,2).tolist() 
browse(u) 
0 
2 
. 
. 
. 
62 

Einige Tests auf große Strukturen (mit Druck von print = lambda _ : None verworfen):

def go(lst): 
for x in product(*[range(k) for k in theshape(lst)]): 
    print(reduce(lambda result, index: result[index], x, lst)) 

In [1]: u=arange(2**21).reshape([2]*21).tolist() 

In [2]: %time go(u) 
Wall time: 14.8 s 

In [3]: %time browse(u) 
Wall time: 3.5 s 

In [5]: u=arange(2**21).reshape([1]*30+[2**21]+[1]).tolist() 

In [6]: %time go(u) 
Wall time: 18 s 

In [7]: %time browse(u) 
Wall time: 3.48 s 

In [8]: u=arange(2**21).reshape([1]+[2**21]+[1]*30).tolist() 

In [9]: %time go(u) 
Wall time: 14 s 

In [10]: %time browse(u) 
Wall time: 58.1 s 

Dies zeigt, dass die Leistung sehr Datenstruktur abhängt.

EDIT:

Schließlich einfachste ist am schnellsten. theshape ist nicht erforderlich.

def browse2(lst): 
     if isinstance(lst,list): 
      for l in lst: 
       browse2(l) 
     else: print(lst) 

es ist oft 30% schneller als durchsuchen. Und es funktioniert unabhängig von der Struktur der Liste.

Answer 3

Wie wäre es mit der dynamischen Indexerstellung?

lst = [[[1], [2]], [[3, 3], [4]], [[5], [6,6,6]]] 

from itertools import product 

for index1, index2 in product(range(3), range(2)): 
    print(lst[index1][index2][0]) 


# need depth info from somewhere to create hard coded indexing 

prod_gen = product(range(3), range(2)) 

first = next(prod_gen) 

indx_depth = len(first) + 1 

exec(('def IndexThisList(lst, indxl):\n' + 
     '  return lst' + ''.join(('[indxl[' + str(i) + ']]' 
              for i in range(indx_depth))))) 

# just to see what it exec'd: 
print(("def IndexThisList(lst, indx_itrbl):\n" + 
     "  return lst" + ''.join(('[indx_itrbl[' + str(i) + ']]' 
             for i in range(indx_depth))))) 
# the exec is only invoked again when changing the indexing depth 
# for accessing the list with its currently instantiated depth of indexing 
# just use the current instance of the generated function 

print(IndexThisList(lst, first + (0,))) 
for itpl in prod_gen: 
    print (IndexThisList(lst, itpl + (0,))) 

1 
2 
3 
4 
5 
6 
def IndexThisList(lst, indx_itrbl): 
     return lst[indx_itrbl[0]][indx_itrbl[1]][indx_itrbl[2]] 
1 
2 
3 
4 
5 
6 

nur ein Anfänger in diesem, scheint wie meine exec mit einer anderen Funktion eingewickelt werden sollte, die index_depth passieren aber die mich für eluding jetzt