Структура данных для поддержания табличных данных в памяти?


мой сценарий выглядит следующим образом: у меня есть таблица данных (несколько полей, менее ста строк), которые я широко использую в своей программе. Мне также нужно, чтобы эти данные были постоянными, поэтому я сохраняю их как CSV и загружаю их при запуске. Я предпочитаю не использовать базу данных, потому что каждый вариант (даже SQLite) является излишним для моего скромного требования (также - я хотел бы иметь возможность редактировать значения в автономном режиме простым способом, и нет ничего проще, чем Блокнот).

предположим, что мои данные выглядят так далее следует (в файле это запятая без заголовков, это просто иллюстрация):

 Row  | Name     | Year   | Priority
------------------------------------
 1    | Cat      | 1998   | 1
 2    | Fish     | 1998   | 2
 3    | Dog      | 1999   | 1 
 4    | Aardvark | 2000   | 1
 5    | Wallaby  | 2000   | 1
 6    | Zebra    | 2001   | 3

Примечания:

  1. строка может быть" реальным " значением, записанным в файл, или просто автоматически сгенерированным значением, представляющим номер строки. В любом случае он существует в памяти.
  2. имена уникальны.

что я делаю с данными:

  1. поиск строки на основе идентификатора (итерации) или имени (прямой доступ.)
  2. отображение таблицы в разных порядках на основе нескольких полей: мне нужно отсортировать ее, например, по приоритету, а затем по году, или по году, а затем по приоритету и т. д.
  3. мне нужно подсчитать экземпляры на основе наборов параметров, например, сколько строк имеют свой год между 1997 и 2002 годами или сколько строк в 1998 году и приоритет > 2 и т. д.

Я знаю, что это "плачет" для SQL...

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

список списков строк:

a = []
a.append( [1, "Cat", 1998, 1] )
a.append( [2, "Fish", 1998, 2] )
a.append( [3, "Dog", 1999, 1] )
...

список списков столбцов (очевидно, будет API для add_row и т. д.):

a = []
a.append( [1, 2, 3, 4, 5, 6] )
a.append( ["Cat", "Fish", "Dog", "Aardvark", "Wallaby", "Zebra"] )
a.append( [1998, 1998, 1999, 2000, 2000, 2001] )
a.append( [1, 2, 1, 1, 1, 3] )

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

a = {}
a['ID'] = [1, 2, 3, 4, 5, 6]
a['Name'] = ["Cat", "Fish", "Dog", "Aardvark", "Wallaby", "Zebra"] 
a['Year'] = [1998, 1998, 1999, 2000, 2000, 2001] 
a['Priority'] = [1, 2, 1, 1, 1, 3] 

словарь с ключами, являющимися кортежами (строка, поле):

Create constants to avoid string searching
NAME=1
YEAR=2
PRIORITY=3

a={}
a[(1, NAME)] = "Cat"
a[(1, YEAR)] = 1998
a[(1, PRIORITY)] = 1
a[(2, NAME)] = "Fish"
a[(2, YEAR)] = 1998
a[(2, PRIORITY)] = 2
...

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

каков рекомендуемый подход?

EDIT:

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

6 61

6 ответов:

наличие "таблицы" в памяти, которая нуждается в поиске, сортировке и произвольной агрегации, действительно вызывает SQL. Вы сказали, что пробовали SQLite, но вы поняли, что SQLite может использовать базу данных только в памяти?

connection = sqlite3.connect(':memory:')

затем вы можете создавать/отбрасывать/запрашивать/обновлять таблицы в памяти со всеми функциями SQLite и без файлов, оставшихся после завершения. И по состоянию на Python 2.5,sqlite3 в стандартной библиотеке, так что это не "перебор" ИМО.

здесь образец того, как можно создать и заполнить базу данных:

import csv
import sqlite3

db = sqlite3.connect(':memory:')

def init_db(cur):
    cur.execute('''CREATE TABLE foo (
        Row INTEGER,
        Name TEXT,
        Year INTEGER,
        Priority INTEGER)''')

def populate_db(cur, csv_fp):
    rdr = csv.reader(csv_fp)
    cur.executemany('''
        INSERT INTO foo (Row, Name, Year, Priority)
        VALUES (?,?,?,?)''', rdr)

cur = db.cursor()
init_db(cur)
populate_db(cur, open('my_csv_input_file.csv'))
db.commit()

если вы действительно предпочитаете не использовать SQL, вы, вероятно, должны использовать список словарей:

lod = [ ] # "list of dicts"

def populate_lod(lod, csv_fp):
    rdr = csv.DictReader(csv_fp, ['Row', 'Name', 'Year', 'Priority'])
    lod.extend(rdr)

def query_lod(lod, filter=None, sort_keys=None):
    if filter is not None:
        lod = (r for r in lod if filter(r))
    if sort_keys is not None:
        lod = sorted(lod, key=lambda r:[r[k] for k in sort_keys])
    else:
        lod = list(lod)
    return lod

def lookup_lod(lod, **kw):
    for row in lod:
        for k,v in kw.iteritems():
            if row[k] != str(v): break
        else:
            return row
    return None

тестирование тогда дает:

>>> lod = []
>>> populate_lod(lod, csv_fp)
>>> 
>>> pprint(lookup_lod(lod, Row=1))
{'Name': 'Cat', 'Priority': '1', 'Row': '1', 'Year': '1998'}
>>> pprint(lookup_lod(lod, Name='Aardvark'))
{'Name': 'Aardvark', 'Priority': '1', 'Row': '4', 'Year': '2000'}
>>> pprint(query_lod(lod, sort_keys=('Priority', 'Year')))
[{'Name': 'Cat', 'Priority': '1', 'Row': '1', 'Year': '1998'},
 {'Name': 'Dog', 'Priority': '1', 'Row': '3', 'Year': '1999'},
 {'Name': 'Aardvark', 'Priority': '1', 'Row': '4', 'Year': '2000'},
 {'Name': 'Wallaby', 'Priority': '1', 'Row': '5', 'Year': '2000'},
 {'Name': 'Fish', 'Priority': '2', 'Row': '2', 'Year': '1998'},
 {'Name': 'Zebra', 'Priority': '3', 'Row': '6', 'Year': '2001'}]
>>> pprint(query_lod(lod, sort_keys=('Year', 'Priority')))
[{'Name': 'Cat', 'Priority': '1', 'Row': '1', 'Year': '1998'},
 {'Name': 'Fish', 'Priority': '2', 'Row': '2', 'Year': '1998'},
 {'Name': 'Dog', 'Priority': '1', 'Row': '3', 'Year': '1999'},
 {'Name': 'Aardvark', 'Priority': '1', 'Row': '4', 'Year': '2000'},
 {'Name': 'Wallaby', 'Priority': '1', 'Row': '5', 'Year': '2000'},
 {'Name': 'Zebra', 'Priority': '3', 'Row': '6', 'Year': '2001'}]
>>> print len(query_lod(lod, lambda r:1997 <= int(r['Year']) <= 2002))
6
>>> print len(query_lod(lod, lambda r:int(r['Year'])==1998 and int(r['Priority']) > 2))
0

лично мне больше нравится версия SQLite, так как она лучше сохраняет ваши типы (без дополнительного кода преобразования в Python) и легко растет, чтобы соответствовать будущим требованиям. Но опять же, мне вполне комфортно с SQL, так что YMMV.

очень старый вопрос, который я знаю, но...

Панда DataFrame, кажется, идеальный вариант здесь.

http://pandas.pydata.org/pandas-docs/version/0.13.1/generated/pandas.DataFrame.html

из аннотации

двумерный размер-изменяемые, потенциально гетерогенные табличные данные структура с маркированными осями (строки и столбцы). Арифметические операции выравнивание по меткам строк и столбцов. Можно рассматривать как дикт-как контейнер для объектов серии. Первичная структура данных панды

http://pandas.pydata.org/

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

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

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

rows = []
rows.append({"ID":"1", "name":"Cat", "year":"1998", "priority":"1"})

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

есть класс таблицы, строки которого представляют собой список объектов dict или better row

в таблице не добавляйте строки напрямую, но есть метод, который обновляет несколько карт поиска, например, для имени если вы не добавляете строки по порядку или id не являются последовательными, вы также можете иметь idMap например,

class Table(object):
    def __init__(self):
        self.rows =  []# list of row objects, we assume if order of id
        self.nameMap = {} # for faster direct lookup for row by name

    def addRow(self, row):
        self.rows.append(row)
        self.nameMap[row['name']] = row

    def getRow(self, name):
        return self.nameMap[name]


table = Table()
table.addRow({'ID':1,'name':'a'})

во-первых, учитывая, что у вас есть сложный сценарий извлечения данных, вы уверены, что даже SQLite является излишним?

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

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

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

я лично написал lib для довольно много, что совсем недавно, он называется BD_XML

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

она написана на испанском языке (если это имеет значение в языке программирования), но это очень просто.

from BD_XML import Tabla

он определяет объект под названием Tabla (таблица), он может быть создан с именем для идентификации a предварительно созданный объект подключения совместимого интерфейса базы данных pep-246.

Table = Tabla('Animals') 

тогда вам нужно добавить столбцы с agregar_columna (add_column) метод, С может принимать различные ключевые аргументы слова:

  • campo (поле): имя поля

  • tipo (тип): тип хранимых данных может быть такими вещами, как "varchar" и "double" или имя объектов python, если вы не заинтересованы в экспорте в базу данных последний.

  • defecto (по умолчанию): установите значение по умолчанию для столбца, если его нет при добавлении строки

  • есть и другие 3, но только там для базы данных tings и на самом деле не функциональны

как:

Table.agregar_columna(campo='Name', tipo='str')
Table.agregar_columna(campo='Year', tipo='date')
#declaring it date, time, datetime or timestamp is important for being able to store it as a time object and not only as a number, But you can always put it as a int if you don't care for dates
Table.agregar_columna(campo='Priority', tipo='int')

затем вы добавляете строки с оператором + = (или +, если вы хотите создать копию с дополнительной строкой)

Table += ('Cat', date(1998,1,1), 1)
Table += {'Year':date(1998,1,1), 'Priority':2, Name:'Fish'}
#…
#The condition for adding is that is a container accessible with either the column name or the position of the column in the table

затем вы можете создать XML и записать его в a файл с exportar_XML (export_XML) и escribir_XML (write_XML):

file = os.path.abspath(os.path.join(os.path.dirname(__file__), 'Animals.xml'))
Table.exportar_xml()
Table.escribir_xml(file)

и затем импортировать его обратно с importar_XML (import_XML) с именем файла и указанием, что вы используете файл, а не строковый литерал:

Table.importar_xml(file, tipo='archivo')
#archivo means file

Advanced

это способы использования объекта Tabla в SQL-режиме.

#UPDATE <Table> SET Name = CONCAT(Name,' ',Priority), Priority = NULL WHERE id = 2
for row in Table:
    if row['id'] == 2:
        row['Name'] += ' ' + row['Priority']
        row['Priority'] = None
print(Table)

#DELETE FROM <Table> WHERE MOD(id,2) = 0 LIMIT 1
n = 0
nmax = 1
for row in Table:
    if row['id'] % 2 == 0:
        del Table[row]
        n += 1
        if n >= nmax: break
print(Table)

в этом примере предполагается столбец с именем 'id' но можно заменить ширину ряда.pos для вашего примера.

if row.pos == 2:

в файл можно скачать с:

https://bitbucket.org/WolfangT/librerias