Эффективный способ проверить уникальность записей в Python / PyTables

Question

У меня есть таблица в PyTables с ~ 50 миллионами записей. Комбинация двух полей (в частности, userID и date) должна быть уникальной (то есть пользователь должен иметь не более одной записи в день), но мне нужно убедиться, что это действительно так.

В качестве иллюстрации мой стол выглядит так:

userID |   date
A      |    1
A      |    2
B      |    1
B      |    2
B      |    2   <- bad! Problem with the data!

Дополнительные детали:

• Таблица в настоящее время «в основном» отсортирована.
• Я едва могу вытащить одну колонку в память как массив, но я не может вытащить двоих в память на в то же время.
• ИД пользователя, и дата являются целыми числами

Answer 1

Кажется, что индексы в PyTables ограничены отдельными столбцами.

Я бы предложил добавить хеш-столбец и добавить к нему индекс. Ваши уникальные данные определяются как объединение других столбцов в БД. Разделители гарантируют, что не будет двух разных строк, которые дают одинаковые уникальные данные. Хеш-столбец может быть просто этой уникальной строкой, но если ваши данные длинные, вы захотите использовать хеш-функцию. Быстрая хеш-функция, такая как md5 или sha1, отлично подходит для этого приложения.

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

Answer 2

Так что спустя годы у меня все еще остается тот же вопрос, но с помощью индексации и запросов эта проблема является лишь незначительной, в зависимости от размера вашей таблицы. С использованием readWhere или getListWhere я думаю, что проблема составляет примерно O (n)

Вот что я сделал ... 1. Я создал таблицу, в которой было два индикатора. Вы можете использовать несколько индикаторов в PyTables:

http://pytables.github.com/usersguide/optimization.html#indexed-searches

Когда ваша таблица проиндексирована , я также использую LZO-сжатие, вы можете сделать следующее:

import tables
h5f = tables.openFile('filename.h5')
tbl = h5f.getNode('/data','data_table') # assumes group data and table data_table
counter += 0

for row in tbl:
    ts = row['date'] # timestamp (ts) or date
    uid = row['userID']
    query = '(date == %d) & (userID == "%s")' % (ts, uid)
    result = tbl.readWhere(query)
    if len(result) > 1:
        # Do something here
        pass
    counter += 1
    if counter % 1000 == 0: print '%d rows processed'

Теперь код, который я здесь написал, на самом деле довольно медленный. Я уверен, что есть некоторые гуру PyTables, которые могли бы дать вам лучший ответ. Но вот мои мысли о производительности:

Если вы знаете, что начинаете с чистых данных, т. Е. (Без дубликатов), то все, что вам нужно сделать, это один раз запросить у таблицы ключи, которые вы хотите найти, что означает, что вам нужно только сделать:

ts = row['date'] # timestamp (ts) or date
uid = row['userID']
query = '(date == %d) & (userID == "%s")' % (ts, uid)
result = tbl.getListWhere(query)
if len(result) == 0:
    # key pair is not in table
    # do what you were going to do
    pass
elif len(result) > 1:
    # Do something here, like get a handle to the row and update instead of append.
    pass

Если у вас достаточно времени, чтобы проверить наличие дубликатов, создайте фоновый процесс, который просматривает каталог с вашими файлами и ищет дубликаты.

Я надеюсь, что это поможет кому-то еще.

Answer 3

Я не знаю много о PyTables, но я бы попробовал этот подход

1. Для каждого идентификатора пользователя получить все (userID, date) пары
2. assert len(rows)==len(set(rows)) - это утверждение верно, если все (userID, date) кортежи, содержащиеся в списке rows, являются уникальными