Структура данных для массивов, которые разделяют некоторые элементы - Python - программирование
Подтвердить что ты не робот

Структура данных для массивов, которые разделяют некоторые элементы - Python

У меня есть набор массивов, которые "перекрываются" над определенными элементами. Здесь изображен пример с участием 3 массивов символов:

  array0↓
       'A'      ↓array2
array1→'B' 'D' 'E'
       'C'     'F'

Важно то, что изменения в массивах должны уважать эту структуру. Так, например, если я изменил "B" в array0 на "X", "B" в массиве 1 также должен измениться на "X".

Мой вопрос - хороший и эффективный способ реализации этого в Python?

Есть две вещи, о которых я думал до сих пор:

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

Во-вторых, я мог бы сделать это, используя такие списки:

data = [['A'], ['B'], ['C'], ['D'], ['E'], ['F']]
array0 = [data[0], data[1], data[2]]
array1 = [data[1], data[3], data[4]]
array2 = [data[4], data[5]]

for array in array0, array1, array2:
     print(array)

>>> [['A'], ['B'], ['C']]
>>> [['B'], ['D'], ['E']]
>>> [['E'], ['F']]

array0[1][0] = 'X'

for array in array0, array1, array2:
     print(array)

>>> [['A'], ['X'], ['C']]
>>> [['X'], ['D'], ['E']]
>>> [['E'], ['F']]

Но я чувствую, что это может быть взломанным, а не лучшим способом. Спасибо за любые предложения.

4b9b3361

ОТВЕТЫ

Ответ 1

Мое предложение - это вариация, предложенная @a_guest. У вас может быть класс-оболочка, который помечает элементы как общие и структуру данных для обработки таких элементов:

class SharedElement:
    def __init__(self, val):
        self.val = val

    def update(self, val):
        self.val = val

    def __repr__(self):
        return "SharedElement({0})".format(self.val)

    def __str__(self):
        return str(self.val)


class SharedList:
    def __init__(self, lst):
        self._lst = lst

    def __getitem__(self, item):
        if isinstance(self._lst[item], SharedElement):
            return self._lst[item].val
        return self._lst[item]

    def __setitem__(self, key, value):
        if isinstance(self._lst[key], SharedElement):
            self._lst[key].update(value)


B = SharedElement('B')
E = SharedElement('E')

a = SharedList(['A', B, 'C'])
b = SharedList([B, 'D', E])
c = SharedList([E, 'F'])

b[0] = 'X'

print([val for val in a])
print([val for val in b])
print([val for val in c])

Выход

['A', 'X', 'C']
['X', 'D', 'E']
['E', 'F']

Ответ 2

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

arr = [[['A'], ['B'], ['C']], [['B'], ['D'], ['E']], [['E'], ['F']]]
class WrapArray:
  def __init__(self, _data):
    self.d = _data
  def __getitem__(self, _x):
    self.x = _x
    class _wrapper:
      def __init__(self, _inst):
         self.ref = _inst
      def __setitem__(self, _y, _val):
         _place = self.ref.d[self.ref.x][_y][0]
         self.ref.d[self.ref.x][_y][0] = _val
         for i in range(len(self.ref.d)):
           for b in range(len(self.ref.d[i])):
             if self.ref.d[i][b][0] == _place:
               self.ref.d[i][b] = [_val]
    return _wrapper(self)
  def __repr__(self):
    return str(self.d)

array = WrapArray(arr)
array[1][0] = 'X'

Выход:

[[['A'], ['X'], ['C']], [['X'], ['D'], ['E']], [['E'], ['F']]]

Ответ 3

Вы можете использовать выделенный класс, который обновляет другие пересекающиеся экземпляры соответствующим образом, как вы указали своей первой идеей. Я бы не рассматривал дублирование данных как проблему, так как для изменяемых данных вы все равно храните ссылки, и если вы используете большие неизменные данные, вы можете использовать выделенный класс оболочки (например, Python 3.7 представил декоратор @dataclass).

Вот пример реализации:

from collections import defaultdict

class List(list):
    def __init__(self, *args, **kwargs):
        super().__init__(*args, **kwargs)
        self._intersections = defaultdict(list)

    def __setitem__(self, index, value):
        super().__setitem__(index, value)
        for i, other in self._intersections[index]:
            other[i] = value

    def intersect(self, other, at):
        self._intersections[at[0]].append((at[1], other))

С этим вы можете пересечь списки, как в вашем примере:

a = List(['A', 'B', 'C'])
b = List(['B', 'D', 'E'])
c = List(['E', 'F'])

a.intersect(b, (1, 0))
b.intersect(c, (2, 0))

a[1] = 'X'
b[2] = 'Y'
print(a)
print(b)
print(c)

Что дает в качестве вывода:

['A', 'X', 'C']
['X', 'D', 'Y']
['Y', 'F']

Ответ 4

list подклассов можно использовать и использовать выделенный класс оболочки для прокси-контента общего доступа. Это не требует дублирования данных, поскольку он хранит только прокси-сервер для общих данных, который отправляет исходные данные. Он немного похож на ваш вложенный список, но поддерживает обычный интерфейс списка. Вот пример реализации:

class Intersection:
    def __init__(self, other, index):
        self.other = other
        self.index = index

    def __repr__(self):
        return repr(self.other[self.index])

    @property
    def value(self):
        return self.other[self.index]

    @value.setter
    def value(self, v):
        self.other[self.index] = v


class List(list):
    def __getitem__(self, index):
        item = super().__getitem__(index)
        return item.value if isinstance(item, Intersection) else item

    def __setitem__(self, index, value):
        item = super().__getitem__(index)
        if isinstance(item, Intersection):
            item.value = value
        else:
            super().__setitem__(index, value)

    def share(self, index):
        return Intersection(self, index)

Теперь вы можете делиться данными между списками по мере необходимости:

a = List(['A', 'B', 'C'])
b = List([a.share(1), 'D', 'E'])
c = List([b.share(2), 'F'])

a[1] = 'X'
b[2] = 'Y'
print(a)
print(b)
print(c)

Что дает в качестве вывода:

['A', 'X', 'C']
['X', 'D', 'Y']
['Y', 'F']

Ответ 5

Как вы указали в своем вопросе, соответствующая информация такова, что

array0ptr = [0, 1, 2]
array1ptr = [1, 3, 4]
array2ptr = [4, 5]

(Я добавляю суффикс ptr, потому что практически эти элементы являются указателями). Элемент списка - это указатель на объекты, которые должны храниться в отдельном списке

ol = ['A', 'B', 'C', 'D', 'E']

Реальные массивы могут быть получены во время выполнения функциями-членами, такими как

array0 = []
for i in range(len(array0ptr)):
    array0.append(ol[array0ptr[i]])

Теперь ваш вопрос: предположим, что список объектов становится

ol = ['A', 'B', 'intruder', 'C', 'D', 'E']

Как я автоматически отслеживаю это в своих массивах? Эти массивы должны стать:

array0ptr = [0, 1, 3]
array1ptr = [1, 4, 5]
array2ptr = [5, 6]

Я считаю, что самый простой ответ: сохранить список фиксированным !, и не разрешать вставку или изменение порядка элементов. Просто используйте другой хэш с позицией объекта. В приведенном выше случае вы будете иметь

sl = ['A', 'B', 'C', 'D', 'E', 'intruder']
slorder = [0, 1, 3, 4, 5, 2]

тогда можно написать функции-члены, которые выгружают обновленный список объектов, массив не изменится. Что может быть сложно, если вы хотите удалить объекты, но это сложно в любом случае, я боюсь.