Поворот массива (списка) в линейном времени и постоянной памяти - PullRequest
Новая
       2

Поворот массива (списка) в линейном времени и постоянной памяти

2 голосов
/ 12 февраля 2020

Как я могу быть уверен, что этот Python алгоритм использует постоянную память? Теоретическое доказательство в порядке.

Учебное пособие * имеет следующее упражнение: написать алгоритм для "поворота" списка из n целых чисел, другими словами, чтобы сместить значения списка на k индексы каждый. Суть в том, что алгоритм должен занимать линейное время (пропорциональное n ) и постоянную память (одинаковое количество для любого n ). Поворот можно выполнить с помощью нарезки: 

>>> n = 5
>>> k = 3
>>> a = [i for i in range(n)]
>>> a = a[k:] + a[:k]
>>> a
[3, 4, 0, 1, 2]

Я проверил, что удвоение n удваивает время, необходимое, и поэтому этот алгоритм требует линейного времени. Однако я не уверен, что это требует постоянной памяти. Я предполагаю, что Python создает новый массив, который является объединением двух срезов, а затем переназначает переменную a этому массиву. Если так, то я думаю, что используемая память пропорциональна n . Но как я могу это проверить?

Упражнение также дает мне подсказку, которая является крипти c: «Подсказка: поменять местами три подрешетки». Зачем нужно создавать три подмассива и зачем их менять? Это трюк с использованием постоянной памяти? Я понимаю, что вы можете изменить порядок элементов от 0 до k-1 , изменить порядок элементов k до n-1 затем измените порядок всех элементов в обратном порядке, но это похоже на большее количество операций, а не на меньшее.

* Книга Седжвика, Уэйна и Дондеро «Введение в программирование в Python». Я учу себя, а не беру курс за кредит.

Ответы [ 3 ]

3 голосов
/ 12 февраля 2020

Подсказка, на которую ссылается подсказка, такова:

Чтобы повернуть последовательность из N элементов, оставленных M:

  • полностью изменить всю последовательность
  • перевернуть последние M элементов
  • инвертируют первые элементы NM

выполнено

например, оставлено 2: 1234567 -> 7654321 -> 7654312 -> 3456712

Да, это хитрость при использовании постоянной памяти, потому что обращение к разделу массива легко сделать на месте. Я не думаю, что есть встроенный метод для реверсирования подмассивов, поэтому вам придется сделать что-то вроде: 

i=0
j=n-m-1
while i<j:
    temp = a[i]
    a[i] = a[j]
    a[j] = temp
    i+=1
    j-=1

В python, это, вероятно, будет медленнее, чем вы изначально написали , но это все еще линейное время.

1 голос
/ 14 февраля 2020

Вместо того чтобы выполнять свопы, вы можете носить с собой один элемент и сдвигать его в следующую позицию: 

def rotate(array,offset): # positive offset rotates left to right
    index = base = 0
    value = array[0]
    size  = len(array)
    for _ in range(size):
        index = (index+offset)%size
        value,array[index] = array[index],value
        if index == base:
            index = base = index + 1
            value = array[index]

A = [1,2,3,4,5,6,7]
rotate(A,3)
print(A)

# [5, 6, 7, 1, 2, 3, 4]

Из-за способности Python использовать негативы для индексации с конца массив, функция также будет работать, чтобы вращаться справа налево, давая ему отрицательное смещение: 

A = [1,2,3,4,5,6,7]
rotate(A,-3)
print(A)

# [4, 5, 6, 7, 1, 2, 3]
0 голосов
/ 12 февраля 2020

Мне известно, что это решение возвращает итератор, а не список, но это может быть полезно для других людей, ищущих этот вопрос.

Мы можем использовать itertools для выполнения объединения в "лени" "

import os
import psutil
import itertools


process = psutil.Process(os.getpid())
print(f"initial memory: {process.memory_info().rss}")

n = 10000
k = n // 2
a = [i for i in range(n)]

print(f"memory after creating the array: {process.memory_info().rss}")

res = itertools.chain(itertools.islice(a, k, None), itertools.islice(a, k))

print(f"memory after reordering the array: {process.memory_info().rss}")

for a in res:
    print(a)
print()

print(f"memory at the end: {process.memory_info().rss}")

Результатом будет:

начальная память: 13025280
память после создания массива: 13328384
память после переупорядочения массива: 13328384
5000
5001 ...
память в конце: 13385728

При исходном решении память будет выше ...

Опять же, этот результат будет верните итератор.

Интересный факт: печать всего списка за раз увеличит объем памяти процессов из-за буфера вывода.

...