Каков наилучший способ хранения данных набора в Python?

Question

У меня есть список данных в следующей форме:

[(id\__1_, description, id\_type), (id\__2_, description, id\_type), ... , (id\__n_, description, id\_type))

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

Иногда для одного и того же идентификатора описания могут незначительно отличаться, как показано ниже:

IPI00110753

• Тубулин альфа-1А цепь
• Тубулин альфа-1 цепь
• Альфа-тубулин 1
• Альфа-тубулин, изотип М-альфа-1

(Обратите внимание, что этот пример взят из базы данных uniprot белка .)

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

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

У меня действительно два вопроса. Во-первых, получу ли я для этого меньший объем памяти, используя для этого тип Set (по типу словаря), или мне следует использовать отсортированный список, в котором я проверяю каждый раз, когда вставляю в список, чтобы увидеть, существует ли идентификатор или есть ли третье решение, о котором я не думал? Во-вторых, если тип «Set» является лучшим ответом, как мне указать его, чтобы он смотрел только на первый элемент кортежа вместо всего этого?

Спасибо, что прочитали мой вопрос,
Тим

Обновление

на основе некоторых комментариев, которые я получил, позвольте мне немного уточнить. Большая часть того, что я делаю со структурой данных, это вставка в нее. Я только прочитал это дважды, один раз, чтобы аннотировать это дополнительной информацией, * и один раз, чтобы сделать, чтобы быть вставленным в базу данных. Однако в дальнейшем может появиться дополнительная аннотация, которая делается до того, как я вставлю ее в базу данных. К сожалению, я не знаю, произойдет ли это в это время.

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

* Информация представляет собой список идентификаторов белков Swiss-Prot, которые я получаю, запрашивая uniprot.

Answer 1

Наборы не имеют ключей. Элемент является ключом.

Если вы думаете, что хотите ключи, у вас есть отображение. Более или менее по определению.

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

Вы говорите о таком словаре?

{ 'id1': [ ('description1a', 'type1'), ('description1b','type1') ], 
  'id2': [ ('description2', 'type2') ],
...
}

Это конечно кажется минимальным. Идентификаторы представлены только один раз.

Возможно, у вас есть что-то подобное?

{ 'id1': ( ('description1a', 'description1b' ), 'type1' ),
  'id2': ( ('description2',), 'type2' ),
...
}

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

Answer 2

Если вы выполняете n-way merge с удалением дубликатов, вам может понадобиться следующее:

Этот генератор объединит любое количество источников. Каждый источник должен быть последовательностью. Ключ должен быть в позиции 0. Он дает объединенную последовательность по одному элементу за раз.

def merge( *sources ):
    keyPos= 0
    for s in sources:
        s.sort()
    while any( [len(s)>0 for s in sources] ):
        topEnum= enumerate([ s[0][keyPos] if len(s) > 0 else None for s in sources ])
        top= [ t for t in topEnum if t[1] is not None ]
        top.sort( key=lambda a:a[1] )
        src, key = top[0]
        #print src, key
        yield sources[ src ].pop(0)

Этот генератор удаляет дубликаты из последовательности.

def unique( sequence ):
    keyPos= 0
    seqIter= iter(sequence)
    curr= seqIter.next()
    for next in seqIter:
        if next[keyPos] == curr[keyPos]:
            # might want to create a sub-list of matches
            continue
        yield curr
        curr= next
    yield curr

Вот скрипт, который использует эти функции для создания результирующей последовательности, которая представляет собой объединение всех источников с удаленными дубликатами.

for u in unique( merge( source1, source2, source3, ... ) ):
    print u

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

Answer 3

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

Использовать меньше структур, кроме строк (str)

Вопрос, который вы задаете, состоит в том, как структурировать ваши данные в одном процессе, чтобы использовать меньше памяти. Единственный канонический ответ на этот вопрос (если вам все еще нужны ассоциативные поиски), используйте как можно меньше других структур, чем строки Python (str, а не unicode). Хэш (словарь) Python хранит ссылки на ваши строки довольно эффективно (это не реализация b-дерева).

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

Альтернативное решение

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

• Разделите вашу информацию на несколько процессов, каждый из которых содержит любую структуру данных, удобную для этого.
• Реализация межпроцессного взаимодействия с сокетами, чтобы процессы могли находиться на других компьютерах в целом.
• Попытайтесь разделить ваши данные, чтобы минимизировать межпроцессное взаимодействие (ввод / вывод медленнее по сравнению с циклами процессора).

Преимущество подхода, который я обрисовал, состоит в том, что

• Вы можете использовать два или более ядер на машине полностью для производительности
• Вы не ограничены адресным пространством одного процесса или даже физической памятью одного компьютера

Существует множество пакетов и подходов к распределенной обработке, некоторые из которых

• * 1033 Линды *
• обработка

Answer 4

Это все еще мутно, но, похоже, у вас есть несколько списков [(id, description, type) ...]

Идентификаторы уникальны в списке и согласованы между списками.

Вы хотите создать UNION: единый список, в котором каждый идентификатор встречается один раз, возможно, с несколькими описаниями.

По некоторым причинам, вы думаете, что отображение может быть слишком большим. У вас есть доказательства этого? Не переусердствуйте без реальных измерений.

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

source1.sort()
source2.sort()
result= []
while len(source1) > 0 or len(source2) > 0:
    if len(source1) == 0:
        result.append( source2.pop(0) )
    elif len(source2) == 0:
        result.append( source1.pop(0) )
    elif source1[0][0] < source2[0][0]:
        result.append( source1.pop(0) )
    elif source2[0][0] < source1[0][0]:
        result.append( source2.pop(0) )
    else:
        # keys are equal
        result.append( source1.pop(0) )
        # check for source2, to see if the description is different.

Это объединяет объединение двух списков путем сортировки и объединения. Нет отображения, нет хэша.

Answer 5

Наборы в Python реализованы с использованием хеш-таблиц. В более ранних версиях они фактически были реализованы с использованием наборов, но это изменило AFAIK. Единственное, что вы сохраните, используя набор, - это размер указателя для каждой записи (указатель на значение).

Чтобы использовать только часть кортежа для хеш-кода, вам нужно создать подкласс кортежа и переопределить метод хеш-кода:

class ProteinTuple(tuple):
     def __new__(cls, m1, m2, m3):
         return tuple.__new__(cls, (m1, m2, m3))

     def __hash__(self):
         return hash(self[0])

Имейте в виду, что в этом случае вы платите за дополнительный вызов функции на __hash__, потому что в противном случае это был бы метод C.

Я бы пошел за рекомендациями Константина, вынул идентификатор из кортежа и посмотрел, насколько это помогает.

Answer 6

Как насчет использования словаря {id: (description, id_type)}? Или {(id, id_type): description} словарь, если (id, id_type) является ключом.