Переназначить значения словаря

Question

У меня есть словарь типа

{'A': 0, 'B': 1, 'C': 2, 'D': 3, etc}

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

Пример:

У меня есть большая матрица, где строки представляют слова, а столбцы представляют документы, в которых встречаются эти слова.Я храню слова и соответствующие им индексы как словарь.Например, для этой матрицы

2 0 0
1 0 3
0 5 1
4 1 2

словарь будет выглядеть следующим образом:

words = {'apple': 0, 'orange': 1, 'banana': 2, 'pear': 3}

Если я уберу слова 'apple' и 'banana', матрица будет содержать только две строки.Таким образом, значение 'orange' в словаре теперь должно равняться 0, а не 1, а значение 'pear' должно составлять 1 вместо 3.

В Python 3.6+ словари упорядочены, поэтому я могу просто написать что-то вроде этого, чтобы переназначить значения:

i = 0
for k, v in words.items():
  v = i
  i += 1

или, альтернативно

words = dict(zip(terms.keys(), range(0, matrix.shape[0])))

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

Answer 1

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

words = {'apple': 0, 'orange': 1, 'banana': 2, 'pear': 3}

# reverse dict for index -> word mappings
inverted = {i: word for word, i in words.items()}

remove = {'apple', 'banana'}

# sort/remove the words
new_words = [inverted[i] for i in range(len(inverted)) if inverted[i] not in remove]

# rebuild new dictionary
new_dict = {word: i for i, word in enumerate(new_words)}

print(new_dict)

Какие выходы:

{'orange': 0, 'pear': 1}

Примечание: Как и принятый ответ, это такжеO(n).

Answer 2

Превратите dict в отсортированный список, а затем создайте новый dict без слов, которые вы хотите удалить:

import itertools

to_remove = {'apple', 'banana'}

# Step 1: sort the words
ordered_words = [None] * len(words)
for word, index in words.items():
    ordered_words[index] = word
# ordered_words: ['apple', 'orange', 'banana', 'pear']

# Step 2: Remove unwanted words and create a new dict
counter = itertools.count()
words = {word: next(counter) for word in ordered_words if word not in to_remove}
# result: {'orange': 0, 'pear': 1}

Время выполнения O (n), поскольку упорядочивание списка вручную с помощью операций индексированияявляется линейной операцией, в отличие от sorted, которая будет O (n log n).

См. также документацию для itertools.count и next.

Answer 3

Изначально у нас есть

words = {'apple': 0, 'orange': 1, 'banana': 2, 'pear': 3}

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

std = sorted(words, key=lambda x: words[x])

newwords = { word : std.index(word) for word in std }

Это нормально ..?

Answer 4

Вы используете неправильный инструмент (dict) для работы, вы должны использовать list

class vocabulary:
    def __init__(self, *words):
        self.words=list(words)
    def __getitem__(self, key):
        try:
             return self.words.index(key)
        except ValueError:
            print (key + " is not in vocabulary")
    def remove(self, word):
        if type(word)==int:
           del self.words[word]
           return
        return self.remove(self[word])

words = vocabulary("apple" ,"banana", "orange")
print (words["banana"]) # outputs 1
words.remove("apple")
print (words["banana"]) # outputs 0

Заметка о сложности

У меня было несколько комментариев, в которых упоминалось, чтоdict более эффективен, потому что время поиска составляет O(1), а время поиска list равно O(n).

В данном случае это просто не так .

Гарантия O(1) хеш-таблицы (dict в python) является результатом амортизированной сложности, что означает, что вы усредняете обычное использование справочной таблицы, которая генерируется один раз , при условии, что ваша хеш-функция сбалансирована.

В этом амортизированном вычислении не учитывается удаление всего словаря и его восстановление каждый раз при удалении элемента, как предполагают некоторые другие ответы.

Реализация list и реализация dict имеют одинаковую сложность наихудшего случая: O(n).

Тем не менее, реализация list может быть оптимизирована с двумя строками Python (* 1032)*) иметь худшее-кейс сложность O(log(n))

Answer 5

Вы можете использовать существующую логику, используя отсортированное словарь:

import operator

words = {'apple': 0, 'orange': 1, 'banana': 2, 'pear': 3}
sorted_words = sorted(words.items(), key=operator.itemgetter(1))

for i, (k, v) in enumerate(sorted_words):
    words[k] = i