В курсе по алгоритмам попалась интересная задача - как очистить массив за O(1)?

На автомате обычно предлагают решение - удалить и создать заново. Но оно работает не за константу O(1), а за линию O(n) - при создании массива надо проинициализировать все элементы дефолтным значением (обычно None). Собственно, то же самое происходит и при очистке массива.

Решение неожиданное и красивое - храним в массиве в каждой ячейке две переменные. Первая - собственно само значение value, вторая - версия записи version. Плюс где то отдельно хранится текущая версия current_version. Пусть version во всех ячейках равна 2, current_version также равна 2. Тогда при записи в ячейку, например, 1, мы записываем первую переменную value, а во вторую переменную сохраним current_version. При чтении из ячейки, мы сравниваем version и current_version и если они равны, то возвращаем value. Если же version < current_version, мы возвращаем дефолтное значение None. Т.е. если нам надо очистить массив - мы увеличиваем значение current_version, и тогда при попытке чтения из любой ячейки будет возвращаться None.

class Array:
    def __init__(self, capacity):
        self.__current_version = 0
        self.__capacity = capacity
        self.__array = [(None, self.__current_version)] * self.__capacity

    def set_item(self, index, value):
        self.__array[index] = (value, self.__current_version)

    def get_item(self, index):
        value, version = self.__array[index]
        if version == self.__current_version:
            return value
        return None

    def clear(self):
        self.__current_version += 1

Первая мысль - так вот как работает TRUNCATE в Greenplum! Но нет, он работает не так. В отличии от массива в оперативной памяти, таблицам на диске не нужно инициализировать пустые строки дефолтным значением. Пустых строк просто нет. Соответственно, TRUNCATE просто меняет ссылку файла данных на новый пустой файл. Возможно DELETE без условий в некоторых mvcc СУБД так работает, но это неточно :)