What is an efficient container for a single reference?

user_2988730 0
Viewed 109

I have a list containing arbitrary objects of uniform type:

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

I'm scanning through the list and marking the objects by placing them in a container based on some unimportant condition. Let's say it's odd indices:

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

A second pass will filter the list to unwrap the flagged items and remove everything else:

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

This code is fundamentally functional. However, for very large arrays, the flagging is increasing memory usage and naturally taking time.

What is the most efficient container to use for something like this? I'm using tuple because it has the smallest footprint of all the container classes I looked at. Is there a better way to wrap a single reference?

list python
2 Answers

I recommend a Boolean list or tuple for the marking. If needed, you could compress this to a bitmap.

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

On the second pass extract the needed elements from items:

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

Will that move you along?

user_47851850

Using wrapper objects for this is inherently memory-inefficient, since each wrapper will take at least 40 bytes on a 64-bit system - 8 bytes each for

  • the type pointer,
  • the refcount,
  • the content pointer, and
  • two pointers needed for CPython's GC system.

This 40-byte minimum is achievable with a custom container:

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

or with types.CellType on Python 3.8+:

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

or with a less direct means of creating closure cells on Python versions below 3.8:

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

wrapper = make_wrapper(wrapped)
extracted_content = wrapper.cell_contents

but techniques that don't involve a wrapper will be able to achieve much lower memory overhead.

user_23571120
Related