Что такое эффективный контейнер для одной ссылки?

Question

У меня есть список, содержащий произвольные объекты одинакового типа:

items = ['a', 'b', 'c', 'x', 'y', 'z']

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

for i in range(len(items)):
    if i % 2:
        items[i] = (items[i],)

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

items = [x[0] for x in items if isinstance(x, tuple)]

Этот код является в основном функциональным. Однако для очень больших массивов пометка увеличивает использование памяти и, естественно, требует времени.

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

Answer 1

Я рекомендую булевский список или кортеж для маркировки. При необходимости вы можете сжать это до растрового изображения.

flag = [i%2 for i in range(len(items))]

На втором проходе извлеките необходимые элементы из items:

new_items = [x for x, wanted in zip(items, flag) if wanted]

Будет ли это вас продвигать?

Answer 2

Использование объектов-оболочек для этого по своей природе неэффективно, поскольку каждая оболочка занимает не менее 40 байт в 64-разрядной системе - 8 байт каждый для

• указателя типа,
• refcount,
• указатель содержимого и
• два указателя, необходимые для системы CPython G C.

Этот минимум 40 байтов может быть достигнут с помощью пользовательского контейнера:

class Wrapper(object):
    __slots__ = ('content',)
    def __init__(self, content):
        self.content = content

или types.CellType на Python 3.8 +:

import types
wrapper = types.CellType(wrapped)
extracted_content = wrapper.cell_contents

или с менее прямым способом создания закрывающие ячейки в Python версиях ниже 3.8:

def make_wrapper(x):
    return (lambda: x).__closure__[0]

wrapper = make_wrapper(wrapped)
extracted_content = wrapper.cell_contents

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