Сохранение иерархически отсортированных списков в python

Question

Я не уверен, что «иерархический» является правильным способом помечать эту проблему, но у меня есть серия списков целых чисел, которые я намерен хранить в массиве 2D numpy, который мне нужен держать отсортированный следующим образом:

array[0,:] = [1, 1, 1, 1, 2, 2, 2, 2, ...] 
array[1,:] = [1, 1, 2, 2, 1, 1, 2, 2, ...] 
array[2,:] = [1, 2, 1, 2, 1, 2, 1, 2, ...] 
    ... 
    ... 
array[n,:] = [...] 

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

Первоначально каждый список будет содержать только одно целое число, и я получу новые столбцы, которые мне нужно вставить в массив таким образом, чтобы он оставался отсортированным, как обсуждалось выше.

Цель хранения списков в этом порядке состоит в том, что если мне задан новый столбец целых чисел, мне нужно проверить, существует ли точная копия этого столбца в массиве или нет, насколько это возможно, и я предполагаю этот порядок поможет мне это сделать. Может быть, есть лучший способ сделать эту проверку, чем хранить списки, подобные этому, - если у вас есть мысли об этом, пожалуйста, укажите их!

Я предполагаю, что правильная позиция для нового столбца может быть найдена рядом бинарных поисков, но мои попытки были беспорядочными - любые мысли о том, чтобы делать это аккуратно и эффективно?

спасибо!

Answer 1

Если я правильно понимаю вашу проблему, у вас есть куча последовательностей чисел, которые вам нужно обработать, но вы должны быть в состоянии определить, является ли последний дубликат одной из последовательностей, которые вы обработали до , В настоящее время вы пытаетесь вставить новые последовательности в виде столбцов в массив numpy, но это неудобно, поскольку numpy действительно лучше всего с массивами фиксированного размера (конкатенация или вставка вещей всегда будет медленной).

Для удобства пользователей гораздо лучшая структура данных. set. Тесты на членство и добавление новых элементов на set являются очень быстрыми (с учетом сложности времени O (1)). Единственное ограничение состоит в том, что элементы set должны быть хешируемыми (что верно для tuple с, но не для или массивов numpy).

Вот набросок некоторого кода, который вы могли бы использовать:

seen = set() 
for seq in sequences: 
    tup = tuple(sequence) # you only need to make a tuple if seq is not already hashable 
    if tup not in seen: 
     seen.add(tup) 

     # do whatever you want with seq here, it has not been seen before 

    else: 
     pass # if you want to do something with duplicated sequences, do it here 

Вы также можете посмотреть на unique_everseen рецепт в the itertools documentation, который делает в основном то же самое, что и выше, но, как хорошо оптимизированный функция генератора.