Эффективный способ сдвига 2D-матриц в python в обоих направлениях

Учитывая двумерную матрицу, например

l = [[1,1,1], [2,5,2], [3,3,3]]) 

что является наиболее эффективным способом реализации операции сдвига по столбцам и строкам?

Например

 shift('up', l) [[2, 5, 2], [3, 3, 3], [1, 1, 1]] 

но

 shift('left', l) [[1, 1, 1], [5, 2, 2], [3, 3, 3]] 

Я использую collections.deque на обеих глубинах из-за этого ответа, но в то время как «вверх» или «вниз» требуется только 1 смену, «левый» или «правый» требует N сдвигов (моя реализация использует цикл for для каждого ряд).

В CI думаю, что это можно улучшить, используя арифметику указателя (см., Например, этот ответ ).

Есть ли лучший питонический путь?

РЕДАКТИРОВАТЬ:

  • Эффективным я имею в виду, если есть способ избежать N сдвигов.
  • Мы можем предположить, что матрица квадратична.
  • Смещение может быть на месте.

Спасибо Мартино за то, что он указал на эти важные вопросы. Мне жаль, что я не указал их раньше.

Вот один довольно эффективный способ сделать это, который будет работать с неквадратичными матрицами:

 UP, DOWN, LEFT, RIGHT = 'up', 'down', 'left', 'right' def shift(direction, number, matrix): ''' shift given 2D matrix in-place the given number of rows or columns in the specified (UP, DOWN, LEFT, RIGHT) direction and return it ''' if direction in (UP, DOWN): n = (number % len(matrix) if direction == UP else -(number % len(matrix))) h = matrix[:n] del matrix[:n] matrix.extend(h) return matrix elif direction in (LEFT, RIGHT): n = (number % len(matrix[0]) if direction == LEFT else -(number % len(matrix[0]))) temp = zip(*matrix) h = temp[:n] del temp[:n] temp.extend(h) matrix[:] = map(list, zip(*temp)) return matrix else: return matrix if __name__ == '__main__': def print_shifted_matrix(direction, number, matrix): print(direction + ': ' + (10-2-len(direction))*' ' + ('\n' + 10*' ').join(str(row) for row in shift(direction, number, matrix))) print matrix1 = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]] matrix2 = [[1, 2, 3], [4, 5, 6], [7, 8, 9], [10, 11, 12]] for matrix in matrix1, matrix2: print_shifted_matrix('original', 0, matrix) print_shifted_matrix(UP, 1, matrix) print_shifted_matrix(DOWN, 1, matrix) print_shifted_matrix(LEFT, 1, matrix) print_shifted_matrix(RIGHT, 1, matrix) 

Выход (обратите внимание, что результаты являются кумулятивными, поскольку операции выполняются на месте):

 original: [1, 2, 3, 4] [5, 6, 7, 8] [9, 10, 11, 12] up: [5, 6, 7, 8] [9, 10, 11, 12] [1, 2, 3, 4] down: [1, 2, 3, 4] [5, 6, 7, 8] [9, 10, 11, 12] left: [2, 3, 4, 1] [6, 7, 8, 5] [10, 11, 12, 9] right: [1, 2, 3, 4] [5, 6, 7, 8] [9, 10, 11, 12] original: [1, 2, 3] [4, 5, 6] [7, 8, 9] [10, 11, 12] up: [4, 5, 6] [7, 8, 9] [10, 11, 12] [1, 2, 3] down: [1, 2, 3] [4, 5, 6] [7, 8, 9] [10, 11, 12] left: [2, 3, 1] [5, 6, 4] [8, 9, 7] [11, 12, 10] right: [1, 2, 3] [4, 5, 6] [7, 8, 9] [10, 11, 12] 

Numpy предоставляет метод roll () для сдвига записей.

 >>> import numpy as np >>> x = np.arange(9) >>> x = x.reshape(3, 3) >>> print(x) [[0 1 2] [3 4 5] [6 7 8]] >>> x = np.roll(x, -1, axis=0) # up >>> print(x) [[3 4 5] [6 7 8] [0 1 2]] >>> x = np.roll(x, 1, axis=0) # down >>> print(x) [[0 1 2] [3 4 5] [6 7 8]] >>> x = np.roll(x, 2, axis=1) # right >>> print(x) [[1 2 0] [4 5 3] [7 8 6]] >>> x = np.roll(x, -2, axis=1) # left >>> print(x) [[0 1 2] [3 4 5] [6 7 8]] 

Я думаю, что Numpy будет довольно эффективным по сравнению с большинством решений
в терминах матричных операций, и вы не будете привязаны к двумерной матрице.

Это универсальная версия, которую вы можете вращать во всех четырех направлениях, любое количество раз

 l = [[1,1,1], [2,5,2], [3,3,3]] def shift(direction, count, myList): myLen = len(myList) if direction == "up": return [myList[i % myLen] for i in range(count, count + myLen)] elif direction == "down": return [myList[-i] for i in range(count, count - myLen, -1)] elif direction == "left": tlist = zip(*myList) return map(list, zip(*[tlist[i % myLen] for i in range(count, count + myLen)])) elif direction == "right": tlist = zip(*myList) return map(list, zip(*[tlist[-i] for i in range(count, count - myLen, -1)])) print shift("up", 1, l) print shift("up", 2, l) print shift("down", 2, l) print shift("down", 1, l) print shift("left", 1, l) print shift("right", 1, l) 

Вывод

 [[2, 5, 2], [3, 3, 3], [1, 1, 1]] [[3, 3, 3], [1, 1, 1], [2, 5, 2]] [[2, 5, 2], [3, 3, 3], [1, 1, 1]] [[3, 3, 3], [1, 1, 1], [2, 5, 2]] [[1, 1, 1], [5, 2, 2], [3, 3, 3]] [[1, 1, 1], [2, 2, 5], [3, 3, 3]] 

Возможно, что-то вроде этого с помощью numpy :

 def shift(x, direction='up'): if direction == 'up': temp = range(x.shape[0]) indicies = temp[1:] + [temp[0]] return x[indicies] elif direction == 'left': temp = range(x.shape[1]) indicies = temp[1:] + [temp[0]] return x[:, indicies] else: print 'Error direction not known' 

Результат:

 >>> shift(l, direction='up') array([[2, 5, 2], [3, 3, 3], [1, 1, 1]]) >>> shift(l, direction='left') array([[1, 1, 1], [5, 2, 2], [3, 3, 3]]) >>> shift(l, direction='to the moon') Error direction not known