Преобразование матрицы

Question

Задача

Преобразовать матрицу, чтобы она была срезана по y координате. Пример:

x = [[1, 2, 3],
     [4, 5, 6]]
#Нужно срезать до 1 индекса включительно у обоих и получить массив вида:
x = [[2, 3],
     [5, 6]]
--------------------
x = [[1, 2, 3],
     [4, 5, 6]]
#Нужно срезать до 2 индекса включительно у обоих и получить массив вида:
x = [[3],
     [6]]

Не обращайте внимания на отступы, они сделаны для наглядности. Массивы в матрице всегда равны друг другу.

Моё решение

def cut(n: int, x: list[list]) -> list[list]:
    new_massive = []
    for i in range(len(x)):
        massive = []
        for j in range(n, len(x[0])):
            massive.append(x[i][j])
        new_massive.append(massive)
    return new_massive
#Где n - это индекс, до которого нужно сразать. x - матрица.

Проблема

Моя функция работает за O(n^2). Как сделать её работу за O(n) и, если возможно, за O(1)?

Answer 1

Используйте срезы

def slice_n(matrix, n):
    return [x[n:] for x in matrix]

x = [[1, 2, 3],
     [4, 5, 6]]
print(slice_n(x, 1))

[[2, 3], [5, 6]]

Answer 2

Использовать массивы numpy вместо нативных списков.

import numpy as np

a = np.array([[1,2,3], [4,5,6]])
print(a[:, 1:])
print(a[:, 2:])

[[2 3]
 [5 6]]
[[3]
 [6]]

В них срезы бесплатные, потому, что ничего не копируют, а ссылаются на существующие данные

import timeit

a = np.random.random((10000, 10000))
print(timeit.timeit(lambda: a[:, 1:], number=1000000))    # 0.302562693999789
print(timeit.timeit(lambda: a[:, 9999:], number=1000000)) # 0.2967891000007512

a = np.random.random((10, 10))
print(timeit.timeit(lambda: a[:, 1:], number=1000000))    # 0.2955629850002879
print(timeit.timeit(lambda: a[:, 9:], number=1000000))    # 0.301412505999906

При любом копировании, будь то явном или срезами списков – сложность будет O(количество скопированных элементов), просто с разными скрытыми коэффициентами (срезы в разы быстрее).

import random
import timeit

a = random.sample(range(1000000), k=1000)
print(timeit.timeit(lambda: a[1:], number=1000000))   # 3.0076194629982638
print(timeit.timeit(lambda: a[999:], number=1000000)) # 0.23986860099830665

БЛОГ НА HUSL

Преобразование матрицы

Ответы (2 шт):