Алгоритм в Python для хранения и поиска ежедневных событий для тысяч пронумерованных событий? - PullRequest
Новая
       11

Алгоритм в Python для хранения и поиска ежедневных событий для тысяч пронумерованных событий?

5 голосов
/ 19 января 2011

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

Это упрощенный сценарий: я получаю ежедневный журнал 200 000 уличных фонарей (с пометкой от sl1 до sl200000), который показывает, работала ли лампа днем ​​или нет. Не имеет значения, как долго лампа находилась в эксплуатации, только то, что она была в данный календарный день.

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

class Streetlamp(object):
    """Class for streetlamp record"""
    def __init__(self, **args):
        self.location = args['location']
        self.power = args['power']
        self.inservice = ???

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

Запись может быть сохранена в виде потока битов, где каждый бит представляет день года, начиная с 1 января. Следовательно, если лампа работала первые три дня 2010 года, тогда запись могла бы быть: 

sl1000_up = dict('2010': '11100000000000...', '2011':'11111100100...')

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

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

Буду признателен за идеи или указатели на возможные решения. Чтобы добавить дополнительные детали, может быть интересно, что используемая внутренняя БД - это ZODB, и предпочтительны объекты Python, которые можно использовать для протравливания.

Ответы [ 2 ]

5 голосов
/ 19 января 2011

Создание 2D-массива в Numpy: 

import numpy as np

nbLamps = 200000
nbDays = 365

arr = np.array([nbLamps, nbDays], dtype=np.bool)

Это будет очень эффективно использовать память, и вы сможете легко объединять дни и лампы.

Для манипулирования даже днямилучше взгляните на scikits.timeseries .Они позволят вам получить доступ к датам с объектами datetime.

0 голосов
/ 19 января 2011

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

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

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

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

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

...