Какова лучшая структура данных для хранения 2-кортежей (a, b), которые поддерживают добавление, удаление кортежей и сравнение (либо на a, либо на b))

Question

Итак, вот моя проблема. Я хочу сохранить 2-кортеж (ключ, val) и хочу выполнить следующие операции:

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

Хэш, кажется, является очевидным выбором для обновления значения ключа, но тогда поиск по значениям займет больше времени (O (n)). Другой вариант - сбалансированное двоичное дерево поиска с переключенным ключом и значением. Так что теперь поиск по значениям будет быстрым (O (lg (n))), но обновление ключа займет (O (n)). Так есть ли какая-либо структура данных, которая может быть использована для решения этих проблем?

Спасибо.

Answer 1

Я бы использовал 2 структуры данных, хеш-таблицу из ключей к значениям и дерево поиска, упорядоченное по значениям, а затем по ключам. При вставке вставьте пару в обе структуры, при удалении по ключу найдите значение из хеша, а затем удалите пару из дерева. Обновление в основном удалить + вставить. Вставьте, удалите и обновите O (log n). Для получения всех ключей, меньших значения, ищите значение в дереве поиска и выполняйте итерацию в обратном направлении. Это O (log n + k).

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

Answer 2

Вы можете создать собственную структуру данных, которая содержит два словаря.

т.е. хеш-таблица от keys->values и другая хеш-таблица от values->lists of keys.

class Foo:
    def __init__(self):
        self.keys = {} # (KEY=key,VALUE=value)
        self.values = {} # (KEY=value,VALUE=list of keys)

    def add_tuple(self,kd,vd):
        self.keys[kd] = vd
        if self.values.has_key(vd):
           self.values[vd].append(kd)
        else:
            self.values[vd] = [kd]

f = Foo()
f.add_tuple('a',1)
f.add_tuple('b',2)
f.add_tuple('c',3)
f.add_tuple('d',3)

print f.keys
print f.values

print f.keys['a']
print f.values[3]

print [f.values[v] for v in f.values.keys() if v > 1]

ВЫВОД:

{'a': 1, 'c': 3, 'b': 2, 'd': 3}

{1: ['a'], 2: ['b'], 3: ['c', 'd']}

1

['c', 'd']

[['b'], ['c', 'd']]

Answer 3

Словарь или типы карт, как правило, основаны на одной из двух структур.

• Сбалансированное дерево (гарантия O (log n)).
• На основе хеша (лучший случай - O (1), но плохая хеш-функция для данных может привести к O (n) поискам).

Любая книга по алгоритмам должна охватывать оба вопроса очень подробно.

Чтобы обеспечить операции как с ключами, так и со значениями, существуют также коллекции на основе нескольких индексов (со всей дополнительной сложностью), которые поддерживают несколько структур (так же, как таблица RDBMS может иметь несколько индексов). Если у вас нет большого количества поисков в большой коллекции, дополнительные издержки могут быть дороже, чем несколько линейных поисков.

Answer 4

Для двоичного дерева поиска вставка - это O (logN) операция в среднем и O (n) в худшем случае. То же самое для операции поиска. Так что это должен быть твой выбор, я верю.