Скажем, я постоянно генерирую новые данные (например, целые числа) и хочу собрать их в список.
import random
lst = []
for _ in range(50):
num = random.randint(0, 10)
lst.append(num)
Когда создается новое значение, я хочу, чтобы оно располагалось в списке на основе количества вхождений этого значения, поэтому данные с более низким «текущим вхождением» должны быть помещены перед данными с более высоким «текущим вхождением».
«Текущее появление» означает «количество дубликатов этих данных, которые уже были собраны на данный момент, вплоть до этой итерации». Для данных, которые имеют одно и то же вхождение, они должны следовать порядку, в котором они генерируются.
Например, если на итерации 10 текущим списком является [1,2,3,4,2,3,4,3,4]
, скажем, генерируется новое значение 1
, то его нужно вставить в индекс 7, в результате чего получится [1,2,3,4,2,3,4,1,3,4]
. Поскольку это второе вхождение 1
, его следует поместить после всех значений, которые встречаются только один раз, но после всех других существующих элементов, которые встречаются дважды: 2
, 3
и 4
(следовательно, сохраняя порядок).
Это мой текущий код, который может изменить порядок списка:
from collections import defaultdict
def rearrange(lst):
d = defaultdict(list)
count = defaultdict(int)
for x in lst:
count[x] += 1
d[count[x]].append(x)
res = []
for k in sorted(d.keys()):
res += d[k]
return res
lst = rearrange(lst)
Однако это не дает ожидаемого результата.
Я написал отдельный алгоритм, который продолжает генерировать новые данные до тех пор, пока не будет выполнен некоторый критерий сходимости, где список может стать чрезвычайно большим.
Поэтому я хочу переупорядочивать сгенерированные значения на лету, т.е. постоянно вставлять данные в список "на месте". Конечно, я могу использовать свою функцию rearrage
в каждой итерации, но это было бы очень неэффективно. Что я хочу сделать, так это вставить новые данные в правильную позицию списка, а не заменять их новым списком на каждой итерации.
Какие-либо предложения?
Обновлено: структура данных не обязательно должна быть списком, но она должна быть упорядочена и не требует другой структуры данных для хранения информации.
@FiddlingBits Это точно используется в моем коде
Таким образом, каждый раз, когда вы добавляете элемент в список и его количество изменяется, ваш алгоритм должен будет извлекать и вставлять каждый соответствующий элемент и перемещать его. Это то, о чем вы просите?
Чего вы пытаетесь достичь? Я думаю, вам может просто понадобиться Счетчик
@RodrigoRodrigues Я добавил пример. Надеюсь теперь понятно.
Если ваша цель состоит в том, чтобы иметь список, который смутно эффективно растет «на лету», обычный список вам не поможет. Подумайте: когда вы «вставляете» индекс, вы фактически перемещаете все после этого индекса. В худшем случае O(n). Вместо этого вам, вероятно, понадобится (двукратно) связанный список. Даже там, учитывая ваш алгоритм, трудно увидеть, как вы обновляете список, не выполняя полный проход по нему каждый раз, если только нет второй структуры данных, содержащей информацию - в этом случае реконструкция списка намного более неэффективна?
Чем больше я думаю об этом, тем больше я убежден, что вам нужно: а) выполнить полный проход по списку, чтобы вы знали, есть ли в данном индексе какие-либо числа после этой точки, которых не было в списке (с правильной частотой появления) до этого момента, чтобы вы могли знать, может ли ваш новый номер быть вставлен в этот индекс на законных основаниях или б) хранить информацию в отдельной структуре, которая лучше «кэширует» эту информацию. И если вы используете базовый список, вы выполняете полный O(n)
проход каждый раз, по крайней мере.
@NathanielFord Другая структура данных (например, deque) подойдет, если она может работать.
Я думаю, что структура данных, которая может лучше подойти для ваших целей, — это лес (в данном случае несвязное объединение списков).
Таким образом, вы сохраняете один внутренний список для каждого вхождения значений. Когда приходит новое значение, вы добавляете его в список сразу после того, которое вы добавили последним значением, которое пришел этот элемент.
Чтобы отслеживать количество вхождений, вы можете использовать встроенный Счетчик.
Вот пример реализации:
from collections import Counter
def rearranged(iterable):
forest, counter = list(), Counter()
for x in iterable:
c = counter[x]
if c == len(forest):
forest.append([x])
else:
forest[c] += [x]
counter[x] += 1
return [x for lst in forest for x in lst]
rearranged([1,2,3,4,2,3,4,3,4,1])
# [1, 2, 3, 4, 2, 3, 4, 1, 3, 4]
Чтобы это работало лучше, ваш входной итеративный объект должен быть генератором (чтобы элементы можно было генерировать на лету).
Не уверен, что понимаю... Как насчет
dict
с целочисленным ключом и целочисленным значением счетчика.