relativity 20.1.0

字典到列表

想象一下在没有哈希表的情况下编程。例如，假设我们有一个Restaurant对象和City对象列表，我们想要知道每个City中有多少Restaurant。

通常这很简单

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())

相对论最基本的数据结构是多对多映射（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替换list那样替换dict。相反，它是一个新的抽象层，可以极大地简化一大类问题。

是否可以更进一步？是否存在更高层次的抽象，可以用更少的数据结构和更少的代码行以及中间值来表示更复杂的关系？

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的值相同的池中提取。

构建链的一个简单方法是使用chain辅助函数。

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

classmates = chain(students2clases, students2classes.inv)

通过将学生:课程映射与自身链式连接，我们可以轻松查询哪些学生有共同课程。

>>> 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仅具有网络功能。数据以无任何数据模型的不可见数据包形式存储在临时形式中。没有更新原子的性：没有方法来确保两次写入要么都成功，要么都失败。

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

相对性：关系型按需

在这个设计空间中，相对性提供关系型功能集，其他什么都没有。相对性允许你构建表示任意Python对象之间关系的内存数据结构，然后通过非常自然和Pythonic的API对这些对象和关系执行查询。

M2MChain和M2MStar：关系的行

M2MChain和M2MStar被实现为list中M2M的薄包装。它们带来的主要功能是提供“行迭代”。它们之间的区别在于它们定义行的方式。M2MChain表示连接端到端的关系。M2MStar表示指向同一基础对象的关联，类似于星型模式。

共享的M2M

所有高级数据结构都关注M2M之间和其中的结构。特定M2M内的内容不需要保持任何不变性。也就是说，如果一个高级数据结构中的一个M2M中的所有内容都打乱了，高级数据结构仍然有效。

（与，如果你打乱了M2M中的键集和值集，将会完全不一致。）

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

例如，M2MGraph.chain(*cols) 将构建并返回一个新的跨传递列的 M2MChain。实际上这里发生的事情是，M2MGraph 被查询以获取底层的 M2M，然后 M2M 列表传递给 M2MChain 构造函数，它仅仅持有它们的引用。

将 M2MGraph、M2MChain 和 M2MStar 视为对底层 M2M 的低廉视图的另一种思考方式。无论底层 M2M 中有多少数据，在这些高级数据结构之上组装的成本是固定且低的。

Pandas

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

这听起来像相对性和 Pandas 应该是竞争对手；但实际上，它们是互补的。虽然 Pandas 在表示表格数据的行和列方面非常出色，但相对性在表示连接不同表的行之间的外键关系方面表现出色。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

NetworkX

NetworkX 是 Python 的“图论库”

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

NetworkX 在表示节点组之间的任意连接方面非常出色。相对性具有以关系为中心的 API 和数据结构，其中 M2M 代表单一关系，而 M2MChain、M2MStar 和 M2MGraph 构建更高阶的连接。

在底层，它们都由 dict 支持。