tablas - funciones panda python

¿Cuál es la mejor estructura de datos para almacenar un conjunto de cuatro(o más) valores?

Question

Supongamos que tengo las siguientes variables y sus values correspondientes values que representan un record .

name = ''abc''
age = 23
weight = 60
height = 174

Tenga en cuenta que el value podría ser de diferentes types ( string , integer , float , referencia a cualquier otro objeto, etc.).

Habrá muchos records (al menos> 100.000). Todos y cada uno de los record serán unique cuando se unique todas estas cuatro variables (en realidad sus values ). En otras palabras, no existe ningún record con los 4 values son iguales.

Estoy tratando de encontrar una estructura de datos eficiente en Python que me permita (almacenar y) recuperar records basados ​​en cualquiera de estas variables en la complejidad del tiempo de log(n) .

Por ejemplo:

def retrieve(name=None,age=None,weight=None,height=None) 
    if name is not None and age is None and weight is None and height is None:
        /* get all records with the given name */
    if name is None and age is not None and weight is None and height is None:
        /* get all records with the given age */
    ....
    return records

La forma en que debe llamarse la retrieve es la siguiente:

retrieve(name=''abc'') 

Lo anterior debe devolver [{name:''abc'', age:23, wight:50, height=175}, {name:''abc'', age:28, wight:55, height=170}, etc]

retrieve(age=23) 

Lo anterior debe devolver [{name:''abc'', age:23, wight:50, height=175}, {name:''def'', age:23, wight:65, height=180}, etc]

Y, puede que necesite agregar una o dos variables más a este registro en el futuro. Por ejemplo, digamos, sex = ''m'' . Entonces, la función de retrieve debe ser escalable.

En resumen: ¿hay una estructura de datos en Python que permita storing a record con n columns (nombre, edad, sexo, peso, altura, etc.) y retrieving records basados ​​en cualquier (uno) de la column en logarithmic ( o idealmente constant - O(1) búsqueda) complejidad?

Answer 1

¿Existe una estructura de datos en Python que permita almacenar un registro con n columnas (nombre, edad, sexo, peso, altura, etc.) y recuperar registros basados ​​en cualquier (uno) de la columna en logarítmico (o idealmente constante - O (1) tiempo de búsqueda) complejidad?

No, no hay ninguno. Pero podría intentar implementar uno sobre la base de un diccionario por dimensión de valor. Siempre y cuando tus valores sean manejables por supuesto. Si implementa una clase personalizada para sus registros, cada diccionario contendrá referencias a los mismos objetos. Esto te ahorrará algo de memoria.

Answer 2

Dado http://wiki.python.org/moin/TimeComplexity, ¿qué tal esto?

• Tenga un diccionario para cada columna que le interese: AGE , NAME , etc.
• Tener las claves de esos diccionarios ( AGE , NAME ) como valores posibles para una columna dada (35 o "m").
• Tener una lista de listas que representan los valores de una "colección", por ejemplo, VALUES = [ [35, "m"], ...]
• Haga que el valor de los diccionarios de columnas ( AGE , NAME ) sean listas de índices de la lista VALUES .
• Tenga un diccionario que mapee el nombre de la columna para indexar dentro de las listas en VALUES para que sepa que la primera columna es la edad y la segunda el sexo (puede evitar eso y usar diccionarios, pero introducen la memoria grande footrpint y con más de 100 K objetos esto puede o no ser un problema).

Entonces la función de retrieve podría verse así:

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

Entonces, esto es lo que obtienes

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

retrieve("age", 35)
# [[35, ''m'']]

Si quieres un diccionario, puedes hacer lo siguiente:

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

pero, una vez más, los diccionarios son un poco pesados ​​por el lado de la memoria, por lo que si puede ir con listas de valores, podría ser mejor.

Tanto la recuperación de diccionario como de la lista son O (1) en promedio; el peor caso para el diccionario es O (n), por lo que debería ser bastante rápido. Mantener eso será un poco doloroso, pero no tanto. Para "escribir", solo tiene que agregar a la lista VALUES y luego anexar el índice en VALUES a cada uno de los diccionarios.

Por supuesto, lo mejor sería comparar su implementación real y buscar mejoras potenciales, pero espero que esto tenga sentido y lo haga funcionar :)

EDITAR:

Tenga en cuenta que, como dijo @moooeeeep, esto solo funcionará si sus valores son manejables y, por lo tanto, pueden utilizarse como claves del diccionario.

Answer 3

Puede lograr la complejidad de tiempo logarítmico en una base de datos relacional usando índices ( O(log(n)**k) con índices de columna individual). Luego, para recuperar datos solo construye SQL apropiado:

names = {''name'', ''age'', ''weight'', ''height''}

def retrieve(c, **params):
    if not (params and names.issuperset(params)):
        raise ValueError(params)
    where = '' and ''.join(map(''{0}=:{0}''.format, params))
    return c.execute(''select * from records where '' + where, params)

Ejemplo:

import sqlite3

c = sqlite3.connect('':memory:'')
c.row_factory = sqlite3.Row # to provide key access

# create table
c.execute("""create table records
             (name text, age integer, weight real, height real)""")

# insert data
records = ((''abc'', 23, 60, 174+i) for i in range(2))
c.executemany(''insert into records VALUES (?,?,?,?)'', records)

# create indexes
for name in names:
    c.execute("create index idx_{0} on records ({0})".format(name))

try:
    retrieve(c, naame=''abc'')
except ValueError:
    pass
else:
    assert 0

for record in retrieve(c, name=''abc'', weight=60):
    print(record[''height''])

Salida:

174.0
175.0

Answer 4

No hay una sola estructura de datos integrada en Python que haga todo lo que quiera, pero es bastante fácil usar una combinación de las que tiene para lograr sus objetivos y hacerlo de manera bastante eficiente.

Por ejemplo, supongamos que su entrada fue la siguiente información en un archivo de valores separados por comas llamado employees.csv con nombres de campo definidos como se muestra en la primera línea:

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

El siguiente es un código de trabajo que ilustra cómo leer y almacenar estos datos en una lista de registros, y automáticamente crea tablas de búsqueda separadas para encontrar registros asociados con los valores de los campos contenidos en cada uno de estos registros.

Los registros son instancias de una clase creada por namedtuple que es muy eficiente en la memoria porque carece de un atributo __dict__ que las instancias de clase normalmente contienen. Al usarlos, será posible acceder a los campos de cada uno por nombre usando la sintaxis de punto, como record.fieldname .

Las tablas de búsqueda son instancias de defaultdict(list) , que proporcionan tiempos de búsqueda O (1) similares a los diccionarios en promedio, y también permiten que se asocien múltiples valores con cada uno. Entonces, la clave de búsqueda es el valor del valor de campo buscado y los datos asociados con él serán una lista de los índices enteros de los registros de Person almacenados en la lista de employees con ese valor, por lo que todos serán relativamente pequeños. .

Tenga en cuenta que el código para la clase está completamente basado en datos, ya que no contiene ningún nombre de campo codificado que, en cambio, se toma de la primera fila del archivo de entrada de datos csv cuando se lee. Cuando se utiliza una instancia, cualquier retrieve() llamadas al método de retrieve() deben, por supuesto, contener argumentos válidos de nombre de campo válido.

Actualizar

Modificado para no crear una tabla de búsqueda para cada valor único de cada campo cuando el archivo de datos se lee por primera vez. Ahora el método retrieve() crea solo según sea necesario (y guarda / almacena el resultado en caché para usarlo en el futuro).

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, ''rb'') as inputfile:
            csv_reader = csv.reader(inputfile, delimiter='','')
            self.fields = csv_reader.next()  # 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 = defaultdict(lambda: defaultdict(list))

    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 function ''
            ''(%s specified)'' % '', ''.join([repr(k) for k in kwargs.keys()]))
        field, value = kwargs.items()[0]  # get only keyword arg 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:  # must create field look up table
            for index, record in enumerate(self.records):
                value = getattr(record, field)
                self.lookup_tables[field][value].append(index)
        matches = [self.records[index]
                    for index in self.lookup_tables[field].get(value, [])]
        return matches if matches else None

if __name__ == ''__main__'':
    empdb = DataBase(''employees.csv'', ''Person'')
    print "retrieve(name=''Ted Kingston''):", empdb.retrieve(name=''Ted Kingston'')
    print "retrieve(age=''27''):", empdb.retrieve(age=''27'')
    print "retrieve(weight=''150''):", empdb.retrieve(weight=''150'')
    try:
        print "retrieve(hight=''5ft 6in''):", 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.'')

Salida:

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