2D Dict с быстрым удалением столбцов и строк? - PullRequest
Новая
       98

2D Dict с быстрым удалением столбцов и строк?

1 голос
/ 13 июля 2020

Мне нужна двумерная структура, подобная диктовке, которая позволяет выполнять быструю операцию удаления. Fe 

    x['a']['b'] = 1
    x['a']['c'] = 1
    x['a']['d'] = 1
    x['b']['a'] = 1
    x['b']['f'] = 1
    x['e']['b'] = 1
    x['f']['c'] = 1
    ...

т.е. клавиши a, b, c, e, f, c, ... могут использоваться в обоих измерениях

Быстро удалить первое измерение, т.е. 

   del x[a]

, но если вы хотите удалить по второму измерению, вам нужно сначала перечислить элементы, что происходит медленно.

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

Каким было бы ваше решение?

PS> Можно было бы сохранить Списки ключей от 2 до 1 измерений, но это займет слишком много памяти и сохранит данные для строк / столбцов, которые не будут удалены!

Будет ли использование Pandas фрейма данных быстрее? 

  key1, key2, data

1 Ответ

1 голос
/ 13 июля 2020

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

from collections import defaultdict

class Table2D:

    def __init__(self, *args, **kwargs):
        self._row_to_cols = defaultdict(dict)
        self._col_to_rows = defaultdict(dict)

    def add(self, c, r):
        self._col_to_rows[c][r] = 1
        self._row_to_cols[r][c] = 1

    def get_row(self, r):
        return self._row_to_cols[r]

    def get_col(self, c):
        return self._col_to_rows[c]

    def rem_row(self, r):
        for c in self._row_to_cols[r]:
            del self._col_to_rows[c][r]
        del self._row_to_cols[r]

    def rem_col(self, c):
        for r in self._col_to_rows[c]:
            del self._row_to_cols[r][c]
        del self._col_to_rows[c]

t2d = Table2D()
t2d.add('a', 'c')
t2d.rem_col('a')
print(t2d.get_col('a')
...