c++|动手打造深度学习框架(基本数据结构与算法)

我们要实现的元程序库要包含哪些内容呢?这个元程序库并不需要包含非常复杂的数据结构与算法,但应该具有足够的通用性,能够为我们的深度学习框架实现提供有力的支持。STL就是此类通用函数库中的一个典范:它包含的大部分数据结构与算法都比较简单,但被广泛地应用于各种C++程序的开发过程中。当然,C++标准模板库主要被应用于运行期,而我们要实现的元程序库则会在编译期大显身手。应用场景虽有所区别,但这并不妨碍我们借鉴STL的优秀设计。
1 数据结构的表示方法 STL中的主要数据结构可以划分为两类:顺序容器与关联容器。前者通过位置来访问数据,后者通过特定类型的键来访问数据。在运行期可以使用的工具相对较多,相应的数据表示形式也多种多样。以顺序容器为例,在STL中常用的顺序容器就包括vector、list等。这些数据结构各有优劣,用户可以根据具体场景进行选择。
相比之下,在编译期我们能使用的工具就不是那么多了:编译期所处理的是常量——无法修改数据的值将对我们的工具选择造成很大限制;编译期对指针等概念的支持相对较弱,我们也无法在编译期进行动态内存分配并以类似指针的形式保存分配的空间,用于后续访问。这些都限制了我们在构造数据结构时可以选择的工具。如第1章所讨论的那样,在编译期表示容器较方便的方法就是使用变长参数模板。我们会将其作为数据结构的载体,以表示在编译期使用的顺序容器与关联容器。

  • 顺序表:一个变长参数模板实例中的元素是天然有序的。按照C++的惯例,我们将变长参数模板中的元素按照从前到后的顺序赋予相应的索引值,索引值从0开始。比如对于tuple来说,int、double、char所对应的索引值分别为012。
  • 集合:变长参数模板实例也可以表示集合。比如tuple同样可以视为一个包含了3个元素的集合。集合中的元素没有顺序性,也即tuple 所表示的集合与tuple所表示的等价。另外,通常来说集合中的元素具有互异性,即相同的元素在集合中不会出现多次。因此,对于像tuple这样的变长参数模板实例来说,是否可以将其视为集合呢?显然,这个实例中存在相同的元素。我们可以拒绝将其视为一个集合,也可以采用其他的方式来解释该实例,比如:无论容器中相同的元素出现多少次,都视为仅出现了一次。采用这种解释时,上述实例也可视为一个集合。要怎么解释容器中的元素是一个选择问题。我们将会在本章的后面讨论不同的选择,以及每种选择所带来的性能差异。
  • 映射:STL中的映射容器采用键-值对存储元素,可以通过键来获取相应的值,我们的元程序库中也将引入类似的构造。我们会使用KVBinder模板来存储键-值对。KVBinder的定义如下[2]:
1template 2struct KVBinder 3{ 4using KeyType = TK; 5using ValueType = TV; 6static TV apply(TK*); 7};

KVBinder提供了元数据域来获取键与值的类型。在此基础上,我们可以使用变长参数模板容器来表示映射,比如tuple, KVBinder>——这个映射将一些类型与其指针类型关联了起来。
与集合类似,映射中的键有互异性,因此这里也存在是否将具有相同键的容器视为映射的问题。我们将会在讨论映射实现时分析不同选择所带来的性能差异。
  • 多重映射(multimap):STL提供了multimap来表示多重映射,也即键可以重复的映射。在我们的深度学习框架中,某些地方需要在编译期使用多重映射,因此我们的元程序库中也引入了多重映射。我们使用如下的结构来表示多重映射中的键值关系:
1KVBinder>

ValueSequence是一个变长参数模板,用于存储某个键所对应的值序列。变长参数模板同时还会作为多重映射的容器使用。一个典型的多重映射实例形如:
1tuple>, 2KVBinder>>

它包含了3个键-值对:int-char、double-int与double-bool。
  • 数值容器:细心的读者可能发现了,前面所列出的容器中存储的元素都是类型。这是因为在我们将要实现的深度学习框架中,类型处理占据元程序的主要部分。除此之外,我们也会在某些地方用到与数值相关的元数据结构与算法。但它们与类型容器的处理方式非常相似,因此本章也就不详细讨论了。
可以看出,变长参数模板在我们的元程序库中占据了重要的地位,所有的元数据结构都是以它为载体来实现的。这种设计的缺点在于:给定一个变长参数模板容器,我们很难判断出它所表示的具体含义(序列、集合,还是映射……)。但它也有优点:容器的实例可以自由转换其角色,选择适当的算法。比如,映射可以看成集合(只需要将键-值对看成一个键),因此可以将集合相关的算法应用到映射上;集合又可以看成序列,因此可以将序列相关的算法应用到集合上。我们可以灵活地选择算法达到目的。
还有一点要说明的是:我们使用变长参数模板作为元数据结构的载体,但并不限制变长参数模板的具体类型。在前文中,我们使用了tuple作为示例,但我们也可以采用其他的变长参数模板。比如完全可以自定义一个变长参数模板容器,并使用它来表示序列、集合或映射。
以上就是我们所使用的元数据结构。在此基础上就可以引入一些算法来实现相关的操作了。让我们首先从一些简单的算法开始讨论。
2 基本算法 很多算法都是非常基础且易于实现的。比如获取顺序表尺寸(其中包含的元素个数)的算法:
1template 2struct Size_; 3 4template