Двойной счетный цикл (n * n код производительности)

Question

В Python у меня есть такая таблица в виде списка списков

A: 8
B: 6
C: 8
D: 3
E: 4
F: 5
G: 7

Я пытаюсь получить для каждой строки количество «соседей», например количество строк, для которых это число либо одно и то же, либо -1, либо +1. Вот это было бы:

A: 3: 8
B: 3: 6
C: 3: 8
D: 2: 3
E: 3: 5
F: 3: 5
G: 4: 7

У меня есть код, который работает, состоящий из двойного цикла: для каждой строки, циклически перебирая все строки и считая все строки, соответствующие

Это работает, но для тысяч строк я сталкиваюсь с проблемой производительности n * n. Какой-нибудь общий способ улучшить это?

Answer 1

Таким образом, число соседей, которое имеет строка с «8», представляет собой сумму:

• Количество 7
• Количество 8
• Количество9's

Простое решение:

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

Пройдите через вашТаблица.Для каждой строки добавьте один к соответствующему значению счетчика словаря.Итак, когда вы видите строку «A», вы добавляете 1 к счету для ключа 8. Когда вы видите строку «B», вы добавляете 1 к счету для ключа 6 и т. Д. Когда вы закончите, счетдля ключа 8 будет 2. Ключ 6 будет иметь счет 1 и т. д.

Пройдите через таблицу снова.Для каждого элемента выведите ключ, его количество и суммы из трех значений словаря: dictionary[count] + dictionary[count-1] + dictionary[count+1].

Алгоритм O (n), с O (n) дополнительным пробелом (для словаря).