Вставка элементов в список в зависимости от их появления

Скажем, я постоянно генерирую новые данные (например, целые числа) и хочу собрать их в список.

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 в каждой итерации, но это было бы очень неэффективно. Что я хочу сделать, так это вставить новые данные в правильную позицию списка, а не заменять их новым списком на каждой итерации.

Какие-либо предложения?

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

Не уверен, что понимаю... Как насчет dict с целочисленным ключом и целочисленным значением счетчика.

Fiddling Bits 07.10.2022 20:26

@FiddlingBits Это точно используется в моем коде

Shaun Han 07.10.2022 20:42

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

Alexander 07.10.2022 20:44

Чего вы пытаетесь достичь? Я думаю, вам может просто понадобиться Счетчик

Rodrigo Rodrigues 07.10.2022 20:46

@RodrigoRodrigues Я добавил пример. Надеюсь теперь понятно.

Shaun Han 07.10.2022 20:56

Если ваша цель состоит в том, чтобы иметь список, который смутно эффективно растет «на лету», обычный список вам не поможет. Подумайте: когда вы «вставляете» индекс, вы фактически перемещаете все после этого индекса. В худшем случае O(n). Вместо этого вам, вероятно, понадобится (двукратно) связанный список. Даже там, учитывая ваш алгоритм, трудно увидеть, как вы обновляете список, не выполняя полный проход по нему каждый раз, если только нет второй структуры данных, содержащей информацию - в этом случае реконструкция списка намного более неэффективна?

Nathaniel Ford 07.10.2022 21:04

Чем больше я думаю об этом, тем больше я убежден, что вам нужно: а) выполнить полный проход по списку, чтобы вы знали, есть ли в данном индексе какие-либо числа после этой точки, которых не было в списке (с правильной частотой появления) до этого момента, чтобы вы могли знать, может ли ваш новый номер быть вставлен в этот индекс на законных основаниях или б) хранить информацию в отдельной структуре, которая лучше «кэширует» эту информацию. И если вы используете базовый список, вы выполняете полный O(n) проход каждый раз, по крайней мере.

Nathaniel Ford 07.10.2022 21:11

@NathanielFord Другая структура данных (например, deque) подойдет, если она может работать.

Shaun Han 07.10.2022 21:22
Почему в Python есть оператор "pass"?
Почему в Python есть оператор "pass"?
Оператор pass в Python - это простая концепция, которую могут быстро освоить даже новички без опыта программирования.
Некоторые методы, о которых вы не знали, что они существуют в Python
Некоторые методы, о которых вы не знали, что они существуют в Python
Python - самый известный и самый простой в изучении язык в наши дни. Имея широкий спектр применения в области машинного обучения, Data Science,...
Основы Python Часть I
Основы Python Часть I
Вы когда-нибудь задумывались, почему в программах на Python вы видите приведенный ниже код?
LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа
LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа
Алиса и Боб имеют неориентированный граф из n узлов и трех типов ребер:
Оптимизация кода с помощью тернарного оператора Python
Оптимизация кода с помощью тернарного оператора Python
И последнее, что мы хотели бы показать вам, прежде чем двигаться дальше, это
Советы по эффективной веб-разработке с помощью Python
Советы по эффективной веб-разработке с помощью Python
Как веб-разработчик, Python может стать мощным инструментом для создания эффективных и масштабируемых веб-приложений.
0
8
65
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Я думаю, что структура данных, которая может лучше подойти для ваших целей, — это лес (в данном случае несвязное объединение списков).

Таким образом, вы сохраняете один внутренний список для каждого вхождения значений. Когда приходит новое значение, вы добавляете его в список сразу после того, которое вы добавили последним значением, которое пришел этот элемент.

Чтобы отслеживать количество вхождений, вы можете использовать встроенный Счетчик.

Вот пример реализации:

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]

Чтобы это работало лучше, ваш входной итеративный объект должен быть генератором (чтобы элементы можно было генерировать на лету).

Другие вопросы по теме