Удалить все ключи в словаре Python больше x за постоянное время
Если у вас есть словарь:
d = {1: True, 2: False, 3: False, 4: True, 5: False, 6: True, 7: False, 8: False}
и вы хотите, чтобы все ключи больше 3 были удалены, чтобы словарь стал:
{1: True, 2: False, 3: False}
вы можете сделать это в постоянное время, если ключи отсортированы?
Нет, он будет масштабироваться по количеству клавиш.
Можете ли вы описать сценарий и причину этого необычного запроса? Это определит, возможно ли какое-либо обходное решение или нет.
Ответы 2
Нет, мы не можем сделать это за постоянное время.
Чтобы удалить все ключи больше 3, мы можем просто сделать:
{k:v for k,v in d.items() if k<=3}
#{1: True, 2: False, 3: False}
У нас есть for-loop в приведенном выше понимании словаря. Его временная сложность O(n).
Однако вы можете получить доступ к отдельным элементам в постоянное время, например:
d[3]
#False constant Time complexity O(1)
если вы всегда хотите перейти к фиксированному номеру, скажите k; это может быть хорошим решением:
new_dict = {}
for i in range(1,k+1):
new_dict[i] = old_dict[i]
Поскольку k фиксировано, его постоянная временная сложность
Согласно этому ответу, доступ к словарю — это практически постоянное время.
Вы пробовали что-нибудь?