relativity 20.1.0

字典列表

想象一下没有哈希图的编程。例如，假设我们有一个Restaurant对象和City对象的列表，我们想要获取每个City中有多少餐馆。

通常这很简单：

restaurants_in_city = {}

for restaurant in restaurants:
    city = restaurant.city
    restaurants_in_city[city] = restaurants_in_city.get(city, 0) + 1

def get_restaurant_count(city):
    return restaurants_in_city.get(city, 0)

但是，想象一下如果唯一可用的数据结构是一个列表，你将如何解决这个问题。

cities = []
restaurants_in_city = []

for restaurant in restaurants:
    missing = True
    for idx, city in enumerate(cities):
        if city == restaurant.city:
            restaurants_in_city[idx] += 1
            missing = False
    if missing:
        cities.append(restaurant.city)
        restaurants_in_city.append(1)

def get_restaurant_count(city):
    for idx, city2 in enumerate(cities):
        if city == city2:
            return restaurants_in_city[idx]
    return 0

比较这两个示例，有几个关键区别：

• 有更多低价值的本地价值（idx）

• 单个数据结构拆分为多个，然后必须保持同步

• 代码更长，因此更难阅读、修改和调试

让我们暂时把这个反乌托邦的数据结构荒地抛在脑后，回到常规的 python。

字典到 M2M

在将使用单索引哈希图的编程与相对论多索引哈希图进行比较时，使用和不使用哈希图进行编程时出现的相同差异将再次出现。

回到餐馆和城市的例子，如果一家餐馆可以有多个地点，我们需要跟踪每家餐馆在哪些城市，以及每个城市有哪些餐馆。

请注意，我们允许一家餐厅在同一个城市内拥有多个地点，因此必须使用集合以避免重复计算。

restaurants_in_city = {}
cities_of_restaurant = {}

for restaurant in restaurants:
    for location in restaurant.locations:
        restaurants_in_city.setdefault(location.city, set()).add(restaurant)
        cities_of_restaurant.setdefault(restaurant, set()).add(location.city)

def get_restaurants_in_city(city):
    return restaurants_in_city.get(city, set())

def get_cities_of_restaurant(restaurant):
    return cities_of_restaurant.get(restaurant, set())

Relativity 最基本的数据结构是多对多映射M2M。 M2M是将每个键与一组值相关联以及将每个值与一组键相关联的系统抽象。了解M2M如何简化问题：

restaurant_city_m2m = M2M()

for restaurant in restaurants:
    for location in restaurant.locations:
        restaurant_city_m2m.add(restaurant, location.city)

get_restaurants_in_city = restaurant_city_m2m.inv.get
get_cities_of_restaurant = restaurant_city_m2m.get

回想一下，使用单索引哈希图的优点是代码更短，寿命更长的数据结构更少，本地值更少。 M2M不会替换dict ，就像 dict替换list一样。相反，它是一个新的抽象层，可以大大简化一大类问题。

有没有可能走得更远？是否有更高级别的抽象可以在更少的数据结构中表示更复杂的关系，并且可以用更少的代码行和中间值进行操作？

M2M 到 M2MGraph

相对论真正闪耀的地方是减轻程序员保持数据结构与更新一致的负担。如果我们需要能够一次添加和删除一个位置并且仍然能够查询，让我们考虑我们的餐厅示例。

使用M2M对象，问题是可行的，但实现起来很繁琐：

restaurant_location = M2M()
location_city = M2M()

def add_location(location):
    restaurant_location.add(location.restaurant, location)
    location_city.add(location, location.city)

def remove_location(location):
    del location_city[location]
    del restaurant_location.inv[location]

def restaurants_in_city(city):
    restaurants = set()
    for location in location_city.inv[city]:
        for restaurant in restaurant_location.inv[location]:
            restaurants.add(restaurant)
    return restaurants

def cities_of_restaurant(restaurant):
    cities = set()
    for location in restaurant_location[restaurant]:
        for city in location_city[location]:
            cities.add(city)
    return cities

这个问题可以通过提高抽象级别来简化。其中M2M是键和值的数据结构，M2MGraph 是M2M的更高级别的数据结构。使用M2MGraph，这个问题变得简单直观：

data = M2MGraph([('restaurant', 'location'), ('location', 'city')])

def add_location(location):
    data['restaurant', 'location', 'city'].add(
        location.restaurant, location, location.city)

def remove_location(location):
    data.remove('location', location)

def restaurants_in_city(city):
    return data.pairs('city', 'restaurant').get(city)

def cities_of_restaurant(restaurant):
    return data.pairs('restaurant', 'city').get(restaurant)

介绍链

图表可以很好地表示任意数据集，但它们难以查询过度。 M2MChain的`` M2M``序列，其中 ``M2M n 的键与M2M n - 1的值来自同一个池。

构造链的一种简单方法是使用链辅助函数。

students2classes = M2M([
    ('alice', 'math'),
    ('alice', 'english'),
    ('bob', 'english'),
    ('carol', 'math'),
    ('doug', 'chemistry')])

classmates = chain(students2clases, students2classes.inv)

通过将 student:class 映射链接到自身，我们可以轻松查询哪些学生一起上课。

>>> classmates.only('alice')
M2MChain([M2M([('alice', 'math'), ('alice', 'english')]), M2M([('math', 'carol'), ('math', 'alice'), ('english', 'bob'), ('english', 'alice')])])

>>> classmates.only('alice').m2ms[1]
M2M([('math', 'carol'), ('math', 'alice'), ('english', 'bob'), ('english', 'alice')])

>>> classmates.only('alice').m2ms[1].inv.keys()
['bob', 'carol', 'alice']

M2M + ORM

让我们从 Django 的一个例子开始。

from django.db import models

class Student(models.model):
    name = models.StringField()

class Course(models.model):
    name = models.StringField()
    students = models.ManyToMany(Student)

学生上很多课，每门课都有很多学生。

在这些关系上构建M2M非常自然：

from relativity import M2M
StudentCourse = Course.students.through

enrollments = M2M(
    StudentCourse.objects.all().values_list('student', 'course'))

数据库功能集

典型的 SQL 数据库，如 PostGres、MySQL、SQLServer、Oracle 或 DB2 提供了许多功能，可分为四类：

• 关系数据模型和查询

• 网络协议和多个并发连接

• 事务、原子更新和MVCC

• 持久存储、备份和只读副本

我们将这些称为“关系”、“网络”、“事务”和“持久性”特征集。

“替代”数据库

最广泛使用的替代方案可能是SQLite。SQLite 具有关系、事务和持久性功能集，但没有网络协议。相反，它必须 作为库嵌入到另一个应用程序中。

另一个例子是古老的ZODB。ZODB 具有网络、事务和持久性功能集，但用对象数据模型代替了关系数据模型。

作为一个关于少即是多的极端例子，memcached只有网络功能。数据以不透明 blob 的形式临时存储，没有任何数据模型。更新没有原子性：无法确保两次写入都成功或都失败。

所谓的“NoSQL”数据库（cassandra、couchdb、mongodb等）通常提供网络和持久性功能，但缺乏关系数据模型和事务性。

相对论：关系单点

在这个设计空间中，Relativity 提供了一个关系功能集，仅此而已。Relativity 允许您构建表示任意 Python 对象之间关系的内存数据结构，然后通过非常自然和 Python 化的 API 对这些对象和关系执行查询。

M2MChain和M2MStar : 关系行

M2MChain和M2MStar被实现为M2M列表 的瘦包装器。他们带来的主要功能提供了“行迭代”。它们之间的区别在于它们如何定义一行。 M2MChain代表端到端连接的关系。 M2MStar表示都指向同一个基础对象的关系，类似于星型模式。

共享M2M s

所有高阶数据结构都与M2M之间的结构有关。特定M2M中的内容不需要维护任何不变量。也就是说，如果高阶数据结构之一内的所有M2M都被加扰，则高阶数据结构仍然有效。

（相比之下，如果您要在M2M中打乱 key 集和 val 集，那将是完全不一致的。）

这具有重要的后果，因为这意味着M2MGraph、M2MChain和M2MStar的各种实例可以共享它们的底层 M2M，并继续更新它们。这意味着所有这些高阶数据结构都可以被视为廉价和短暂的。

例如，M2MGraph.chain(*cols)将在连接传递的列的M2M上构造并返回一个新的 M2MChain 。这里实际发生的只是查询M2MGraph以获取底层 M2M，然后将M2M的列表传递给M2MChain 构造函数，该构造函数仅包含对它们的引用。

考虑M2MGraph、M2MChain和M2MStar的另一种方式是对底层M2M的廉价视图。无论底层M2M中有多少数据，在顶部组装这些高阶数据结构之一具有固定的低成本。

熊猫

Relativity 和 Pandas 都可以将数据从 SQL 数据库中干净地提取到内存中的数据结构中，该结构可以进一步处理。这两个库都提供了可以轻松表达对内存数据集的查询的数据结构，否则这些查询将非常困难，并且会诱使开发人员多次返回数据库。

这听起来像 Relativity 和 Pandas 应该竞争；但是，实际上它们是互补的。Pandas 擅长以行和列的形式表示表格数据，而 Relativity 擅长表示连接不同表中行的外键关系。Pandas 可以轻松获取 SQL 结果集，并通过过滤行和添加列来进一步细化它。相对论可以很容易地提取许多表之间的外键关系，并通过按连通性过滤和添加额外的关系来进一步细化它们。

class Enrollment(models.Model):
     student = models.ForeignKey(Student)
     class = models.ForeignKey(Class)
     grade = models.FloatField()  # 0.0 - 5.0

# Pandas is great at determining each students GPA
enrollments_data_frame.group_by(['student']).mean()

>>> import pandas
>>> import relativity
>>> s = pandas.Series(data=[1, 2, 2], index=['a', 'a', 'b'])
>>> s
a    1
a    2
b    2
dtype: int64
>>> m2m = relativity.M2M(s.items())
>>> m2m
M2M([('a', 1L), ('a', 2L), ('b', 2L)])
>>> keys, vals = zip(*m2m.iteritems())
>>> s2 = pandas.Series(data=vals, index=keys)
>>> s2
a    1
a    2
b    2
dtype: int64

网络X

NetworkX是 Python 的“图论库”：

“NetworkX 是一个 Python 包，用于创建、操作和研究复杂网络的结构、动力学和功能。”

NetworkX 擅长表示一组节点之间的任意连接。Relativity 具有以关系为中心的 API 和数据结构，其中M2M表示单个关系，而M2MChain、 M2MStar和M2MGraph构建更高阶的连接。

在下面，两者都由dict支持。