Quelle est la meilleure structure de données pour le stockage d'un ensemble de quatre (ou plus) des valeurs?

Il n'y a pas une seule structure de données construite en Python qui fait tout ce que vous voulez, mais il est assez facile d'utiliser une combinaison de ceux-la, il ne avoir à atteindre vos objectifs et de le faire assez rapidement.

Par exemple, disons que votre contribution a été les données suivantes dans un csv fichier appelé employees.csv avec des noms de champ définis comme indiqué par la première ligne:

name,age,weight,height
Bob Barker,25,175,6ft 2in
Ted Kingston,28,163,5ft 10in
Mary Manson,27,140,5ft 6in
Sue Sommers,27,132,5ft 8in
Alice Toklas,24,124,5ft 6in

Voici de travail code qui montre comment lire et stocker ces données dans une liste d'enregistrements, et de créer automatiquement de séparer les tables de recherche pour rechercher des enregistrements associés avec les valeurs contenues dans les champs de chacun de ces enregistrements.

Les enregistrements sont des instances d'une classe créée par namedtuple qui est une mémoire très efficace, car chaque on manque d'une __dict__ attribut que des instances de classe contiennent normalement. En les utilisant, il sera possible d'accéder aux champs de chaque nom en utilisant la syntaxe à point, comme record.fieldname.

Le look-up tables sont defaultdict(list) instances, qui fournissent un dictionnaire comme O(1) coup d'oeil de temps en moyenne, et également autoriser plusieurs valeurs associées à chacun. Donc, la clé est la valeur de la valeur du champ recherchées, et les données qui y sont associées seront une liste de l'entier des indices de la Person registres informatisés, conservés dans les employees liste avec que donc ils vont tous être relativement faible.

Noter que le code de la classe est entièrement piloté par les données, en ce qu'elle ne contient pas tout codé en dur noms de champs qui sont prises à partir de la première ligne de données au format csv, fichier d'entrée lorsqu'il est lu. Bien sûr, lors de l'utilisation d'une instance, tous les retrieve() les appels de méthode doit fournir les noms de champs valides.

Mise à jour

Modifié pour ne pas créer une table pour chaque valeur unique de chaque champ lorsque le fichier de données est d'abord lu. Maintenant, le retrieve() méthode "paresseusement" crée seulement lorsqu'il est nécessaire (et sauve/met le résultat en cache pour une utilisation future). Également modifié pour fonctionner dans Python 2.7+ 3 inclus.x.

from collections import defaultdict, namedtuple
import csv
class DataBase(object):
def __init__(self, csv_filename, recordname):
# Read data from csv format file into a list of namedtuples.
with open(csv_filename, 'r') as inputfile:
csv_reader = csv.reader(inputfile, delimiter=',')
self.fields = next(csv_reader)  # Read header row.
self.Record = namedtuple(recordname, self.fields)
self.records = [self.Record(*row) for row in csv_reader]
self.valid_fieldnames = set(self.fields)
# Create an empty table of lookup tables for each field name that maps
# each unique field value to a list of record-list indices of the ones
# that contain it.
self.lookup_tables = {}
def retrieve(self, **kwargs):
""" Fetch a list of records with a field name with the value supplied
as a keyword arg (or return None if there aren't any).
"""
if len(kwargs) != 1: raise ValueError(
'Exactly one fieldname keyword argument required for retrieve function '
'(%s specified)' % ', '.join([repr(k) for k in kwargs.keys()]))
field, value = kwargs.popitem()  # Keyword arg's name and value.
if field not in self.valid_fieldnames:
raise ValueError('keyword arg "%s" isn\'t a valid field name' % field)
if field not in self.lookup_tables:  # Need to create a lookup table?
lookup_table = self.lookup_tables[field] = defaultdict(list)
for index, record in enumerate(self.records):
field_value = getattr(record, field)
lookup_table[field_value].append(index)
# Return (possibly empty) sequence of matching records.
return tuple(self.records[index]
for index in self.lookup_tables[field].get(value, []))
if __name__ == '__main__':
empdb = DataBase('employees.csv', 'Person')
print("retrieve(name='Ted Kingston'): {}".format(empdb.retrieve(name='Ted Kingston')))
print("retrieve(age='27'): {}".format(empdb.retrieve(age='27')))
print("retrieve(weight='150'): {}".format(empdb.retrieve(weight='150')))
try:
print("retrieve(hight='5ft 6in'):".format(empdb.retrieve(hight='5ft 6in')))
except ValueError as e:
print("ValueError('{}') raised as expected".format(e))
else:
raise type('NoExceptionError', (Exception,), {})(
'No exception raised from "retrieve(hight=\'5ft\')" call.')

De sortie:

retrieve(name='Ted Kingston'): [Person(name='Ted Kingston', age='28', weight='163', height='5ft 10in')]
retrieve(age='27'): [Person(name='Mary Manson', age='27', weight='140', height='5ft 6in'),
Person(name='Sue Sommers', age='27', weight='132', height='5ft 8in')]
retrieve(weight='150'): None
retrieve(hight='5ft 6in'): ValueError('keyword arg "hight" is an invalid fieldname')
raised as expected

Donné http://wiki.python.org/moin/TimeComplexity comment à ce sujet:

• Disposer d'un dictionnaire pour chaque colonne que vous êtes intéressé à en - AGE, NAME, etc.
• Ont les clés de dictionnaires (AGE, NAME) possible des valeurs de la colonne (35 ou "m").
• Ont une liste de listes représentant les valeurs d'une "collection", par exemple VALUES = [ [35, "m"], ...]
• Ont la valeur de la colonne dictionnaires (AGE, NAME) être des listes d'indices à partir de la VALUES liste.
• Disposer d'un dictionnaire qui associe le nom de colonne d'indice dans les listes de VALUES de sorte que vous savez que la première colonne est l'âge et le deuxième, c'est le sexe (vous pouvez éviter cela et utiliser les dictionnaires, mais ils présentent une grande mémoire footrpint et avec plus de 100K objets cela peut ou ne pas être un problème).

Puis le retrieve fonction pourrait ressembler à ceci:

def retrieve(column_name, column_value):
if column_name == "age":
return [VALUES[index] for index in AGE[column_value]]      
elif ...: # repeat for other "columns"

Alors, c'est ce que vous obtenez

VALUES = [[35, "m"], [20, "f"]]
AGE = {35:[0], 20:[1]}
SEX = {"m":[0], "f":[1]}
KEYS = ["age", "sex"]
retrieve("age", 35)
# [[35, 'm']]

Si vous voulez un dictionnaire, vous pouvez effectuer les opérations suivantes:

[dict(zip(KEYS, values)) for values in retrieve("age", 35)]
# [{'age': 35, 'sex': 'm'}]

mais encore une fois, les dictionnaires sont un peu lourd sur le côté de la mémoire, donc si vous pouvez aller avec des listes de valeurs, il pourrait être mieux.

À la fois dictionnaire et la liste de récupération sont en O(1) en moyenne - pire des cas pour le dictionnaire est O(n) - ce qui devrait être assez rapide. Le maintien qui sera un peu de douleur, mais pas tellement. Pour "écrire", vous avez juste à ajouter à la VALUES liste, puis ajouter l'index dans VALUES à chacun des dictionnaires.

De cours, alors le mieux serait de tester les performances de votre mise en œuvre effective et à chercher d'éventuelles améliorations, mais j'espère que cela a du sens, et vous va 🙂

EDIT:

Veuillez noter que, comme @moooeeeep dit, cela ne fonctionnera que si vos valeurs sont hashable et, par conséquent, peuvent être utilisés comme clés de dictionnaire.