Какой хороший способ получить доступ к 2D списку с "плоским" индексом?

Question

Предположим, у нас есть список 2D, 3x3:

list = [[1, 2, 3],
        [4, 5, 6],
        [7, 8, 9]]

Каков рекомендуемый способ доступа к list элементам с "плоским" индексом?

Я имею в виду, яиметь только число от 0 до 9. Как получить доступ к соответствующему элементу list[i][j]?

Answer 1

вы можете использовать деление и по модулю для вычисления 2D координат (работает, только если все подсписки имеют одинаковый размер)

def get_item(lst,i):    
    return(lst[i//len(lst[0])][i%len(lst[0])])

обратите внимание, что уплощение списка для доступа к элементам O(n**2) сложность, тогда как этот метод O(1).

Если у вас переменная длина подсписка, вы должны сначала найти подсписок, и вы не можете использовать деление. Но как только правильный подсписок найден, у вас есть O(1) доступ:

lst = [[1, 2, 3, 4],
        [5, 6],
        [7,8,9,10]]

def get_item(lst,i):
    current = 0
    for sublist in lst:
        index = i - current
        if 0 <= index < len(sublist):
            return sublist[index]
        current += len(sublist)
    raise Exception("index out of range {}".format(i))

print(get_item(lst,0),get_item(lst,6),get_item(lst,9))

отпечатки: 1 7 10

Answer 2

Вот короткая команда, но менее эффективная:

lst = [[1, 2, 3],
        [4, 5, 6],
        [7, 8, 9]]

#Get the index no. 5 from 2d list
sum(lst, [])[5]

Вывод:

6

Answer 3

Для прямоугольной матрицы вы можете использовать divmod для получения индексов строк и столбцов Сложность доступа: O (1) :

matrix = [[1, 2, 3,],
          [10,11,12],
          [21,22,23]]

r,c = divmod(6,len(matrix[0]))
value = matrix[r][c]
print(value) # 21

Для нерегулярного списка списков, пока не изменяется ни один из размеров, вы можете создать список косвенного обращения и использовать его для преобразования плоской позиции в индексы строк и столбцов Сложность доступа: O (1) Сложность индексации O (N) (N = общее количество элементов) :

matrix = [[1, 2, 3, 4 ,5],
          [10,11,12],
          [21,22,23,24]]

indx = [ (r,c) for r,row in enumerate(matrix) for c in range(len(row)) ]
pos   = 8
r,c   = indx[pos]
value = matrix[r][c]

print(value) # 21

После создания списка indx доступ к элементам будет практически таким же быстрым, как метод прямоугольной матрицы (целочисленное деление и по модулю).

Обратите внимание, что вам придется воссоздавать список косвенных сообщений (indx) каждый раз, когда вы изменяете размер списка или какие-либо его строки.

Если ваша матрица изменяется (по размеру) чаще, чем вы обращаетесь к ней с помощью плоских позиций, вы можете создать функцию для возврата индексов Сложность доступа: O (R) :

def rowCol(m,p):
    for r,row in enumerate(m):
        if p<len(row): return r,p
        p-=len(row)

r,c = rowCol(matrix,8)
value = matrix[r][c]
print(value) 

Это будет намного медленнее, чем готовая переменная indx, поэтому вы можете использовать гибридный подход, при котором индекс очищается после каждого изменения и перестраивается только по требованию (при вызове функции).

Другой альтернативой, которая будет создавать индекс быстрее, но доступ к нему будет немного медленнее, будет создание индекса только с совокупными размерами строк матрицы. Затем вы можете использовать алгоритм двоичного поиска для поиска строки и простого вычитания для поиска столбца Сложность доступа: O (log (R)) Сложность индексирования: O ( R)

matrix = [[1, 2, 3,],
          [10,11,12,13,14],
          [21,22,23,24]]

from itertools import accumulate
from bisect import bisect_left
indx = [0]+list(accumulate(map(len,matrix)))

pos   = 8
r     = bisect_left(indx,pos+1)-1
c     = pos - indx[r]
value = matrix[r][c]
print(pos,r,c,value) # 21

Доступ к нему медленнее, чем полное индексирование координат, но он будет занимать меньше памяти и все равно будет намного быстрее, чем итеративная функция (которая, по сути, делает то же самое последовательно)

Answer 4

Вы можете использовать numpy.reshape для генерации одномерного массива из двумерного массива.

import numpy

in_list = [[1,2,3],[4,5,6],[7,8,9]]
out_list = numpy.reshape(in_list, 9).tolist()

print(in_list)
#[[1,2,3],[4,5,6],[7,8,9]]

print(out_list)
#[1,2,3,4,5,6,7,8,9]

Тогда вы можете просто получить доступ к массиву с измененным размером как к массиву 1D

print(out_list[2])
#2

Answer 5

Вы можете использовать itertools.chain:

from itertools import chain

lst = [[1, 2, 3],
         [4, 5, 6],
         [7, 8, 9]]

for i, x in enumerate(chain(*lst)):
    print(i, x)

0 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9

Таким образом, чтобы использовать свой уплощенный индекс:

# you can just match the index explicitly
for i, x in enumerate(chain(*lst)):
    if i==5:
        break

x
# 6

# or you can store in a list 
flattened = list(chain(*lst))

flattened[5]
# 6