Cấu trúc dữ liệu tốt nhất để lưu trữ một bộ bốn (hoặc nhiều hơn) giá trị là gì?

Question

Giả sử tôi có variables và số values tương ứng của nó đại diện cho record.

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

Xin lưu ý rằng value có thể là khác nhau types (string, integer, float, tài liệu tham khảo-to-bất kỳ-khác-đối tượng, vv).

Sẽ có nhiều records (ít nhất> 100.000). Mỗi và mọi record sẽ là unique khi tất cả bốn số variables này (thực sự là values) được đặt cùng nhau. Nói cách khác, không tồn tại record với tất cả 4 values giống nhau.

Tôi cố gắng để tìm thấy một cấu trúc dữ liệu hiệu quả trong Python mà sẽ cho phép tôi (cửa hàng và) lấy records dựa trên bất kỳ một trong những thời gian phức tạp variables trong log(n).

Ví dụ:

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 

Cách retrieve nên được gọi như sau:

retrieve(name='abc') 

Trên đây nên trở [{name:'abc', age:23, wight:50, height=175}, {name:'abc', age:28, wight:55, height=170}, etc]

retrieve(age=23) 

Trên đây nên trở [{name:'abc', age:23, wight:50, height=175}, {name:'def', age:23, wight:65, height=180}, etc]

Và, tôi có thể cần phải thêm một hoặc hai số variables vào hồ sơ này trong tương lai. Ví dụ: giả sử, sex = 'm'. Vì vậy, chức năng retrieve phải có khả năng mở rộng.

Vì vậy, trong ngắn: Có một cấu trúc dữ liệu trong Python mà sẽ cho phép storing a record với n số columns (tên, tuổi, giới tính, cân nặng, chiều cao, vv) và retrieving records dựa trên bất kỳ (một) của column trong logarithmic (hoặc lý tưởng là constant - O(1) thời gian tra cứu) phức tạp?

Answer 1

Không có một cấu trúc dữ liệu duy nhất được xây dựng vào Python mà làm mọi thứ bạn muốn , nhưng nó khá dễ dàng để sử dụng một sự kết hợp của những người nó phải đạt được mục tiêu của bạn và làm như vậy khá hiệu quả.

Ví dụ, nói đầu vào của bạn là dữ liệu sau đây trong một tập tin bằng dấu phẩy giá trị gọi là employees.csv với tên trường được định nghĩa như thể hiện bởi những dòng đầu tiên:

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 

Các mã sau đây được làm việc minh họa cách để đọc và lưu trữ dữ liệu này vào danh sách các bản ghi và tự động tạo các bảng tìm kiếm riêng biệt để tìm các bản ghi liên kết với các giá trị chứa trong các trường của mỗi bản ghi này.

Bản ghi là trường hợp của một lớp được tạo bởi namedtuple là bộ nhớ rất hiệu quả vì mỗi bản ghi thiếu thuộc tính __dict__ mà các cá thể lớp thường chứa. Sử dụng chúng sẽ làm cho nó có thể truy cập vào các lĩnh vực của từng tên bằng cách sử dụng cú pháp dấu chấm, như record.fieldname.

Các bảng nhìn lên là defaultdict(list) trường hợp, trong đó cung cấp từ điển giống như O (1) nhìn lên lần trên trung bình, và cũng cho phép nhiều giá trị có liên quan đến mỗi một. Vì vậy, khóa tìm kiếm là giá trị của giá trị trường được tìm kiếm và dữ liệu được liên kết với nó sẽ là danh sách các chỉ số nguyên của các bản ghi Person được lưu trữ trong danh sách employees với giá trị đó - vì vậy tất cả chúng sẽ tương đối nhỏ bé.

Lưu ý rằng mã cho lớp hoàn toàn hướng dữ liệu ở chỗ nó không chứa bất kỳ tên trường được mã hóa nào thay vào đó được lấy từ hàng đầu tiên của tệp nhập dữ liệu csv khi được đọc. được sử dụng, mọi cuộc gọi phương thức thực tế retrieve() phải, tất nhiên, chứa các đối số từ khóa tên trường hợp lệ.

Cập nhật

Modified để không tạo ra một bảng tra cứu cho mỗi giá trị duy nhất của tất cả các lĩnh vực khi các tập tin dữ liệu là đầu đọc. Bây giờ phương thức retrieve() chỉ tạo chúng khi cần (và lưu/lưu trữ kết quả để sử dụng sau này). Cũng được sửa đổi để làm việc trong Python 2.7+ bao gồm 3.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 = 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 = list(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'): {}".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.') 

Output:

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 

Answer 2

Với http://wiki.python.org/moin/TimeComplexity thế nào về điều này:

• Có một cuốn từ điển cho mỗi cột bạn quan tâm - AGE, NAME vv
• Có các phím điều đó từ điển (AGE, NAME) có thể các giá trị cho cột đã cho (35 hoặc "m").
• Có danh sách các danh sách đại diện cho các giá trị cho một "bộ sưu tập", ví dụ: VALUES = [ [35, "m"], ...]
• Có giá trị của từ điển cột (AGE, NAME) là danh sách các chỉ mục từ danh sách VALUES.
• Có một từ điển ánh xạ tên cột để lập chỉ mục trong các danh sách trong VALUES để bạn biết rằng cột đầu tiên là tuổi và thứ hai là giới tính (bạn có thể tránh điều đó và sử dụng từ điển, nhưng chúng giới thiệu footrpint bộ nhớ lớn và hơn 100K đối tượng này có thể hay không là một vấn đề).

Sau đó retrieve chức năng có thể trông như thế này:

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

Sau đó, đây là những gì bạn nhận

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

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

Nếu bạn muốn có một từ điển, bạn có thể làm như sau:

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

nhưng một lần nữa, từ điển là một chút háo hức ở phía bộ nhớ, vì vậy nếu bạn có thể đi với danh sách các giá trị, nó có thể tốt hơn.

Cả hai từ điển và danh sách truy xuất là O (1) trên trung bình - trường hợp xấu nhất cho từ điển là O (n) - vì vậy điều này nên được khá nhanh. Duy trì điều đó sẽ có một chút đau đớn, nhưng không quá nhiều. Để "viết", bạn chỉ cần thêm vào danh sách VALUES và sau đó nối chỉ mục trong VALUES vào mỗi từ điển.

Tất nhiên, sau đó tốt nhất là nên chuẩn thực hiện thực tế của bạn và tìm kiếm cải tiến tiềm năng, nhưng hy vọng này có ý nghĩa và sẽ giúp bạn đi :)

EDIT:

Xin lưu ý rằng như @moooeeeep cho biết, điều này sẽ chỉ hoạt động nếu giá trị của bạn có thể băm và do đó có thể được sử dụng làm khóa từ điển.

Answer 3

Có một cấu trúc dữ liệu bằng Python mà sẽ cho phép lưu thông tin với n số cột (tên, tuổi, giới tính, cân nặng, chiều cao, vv) và lấy hồ sơ dựa trên bất kỳ (một) của cột trong logarit (hoặc lý tưởng liên tục - O (1) thời gian tra cứu) phức tạp?

Không, không có. Nhưng bạn có thể thử triển khai một trên cơ sở một thứ nguyên từ điển cho mỗi giá trị. Miễn là giá trị của bạn có thể băm tất nhiên. Nếu bạn triển khai một lớp tùy chỉnh cho các bản ghi của bạn, mỗi từ điển sẽ chứa các tham chiếu đến cùng một đối tượng. Điều này sẽ giúp bạn tiết kiệm một số bộ nhớ.

Answer 4

Bạn có thể đạt được độ phức tạp về thời gian logarit trong cơ sở dữ liệu quan hệ bằng cách sử dụng chỉ mục (O(log(n)**k) với chỉ mục cột đơn). Sau đó, để lấy dữ liệu chỉ xây dựng SQL thích hợp:

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) 

Ví dụ:

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']) 

Output:

174.0 
175.0