Go语言代码树状结构 golang 树

GO文件中的注释信息是如何得到的

一直很好奇GO注释文件中的信息是如何得到的，终于在《The Gene Ontology Handbook》中找到了答案。

目前创新互联公司已为上千家的企业提供了网站建设、域名、网页空间、网站托管、企业网站设计、商丘网站维护等服务，公司将坚持客户导向、应用为本的策略，正道将秉承"和谐、参与、激情"的文化，与客户和合作伙伴齐心协力一起成长，共同发展。

GO的原始文件可以分为两部分：ontology和association files。

该文件以obo格式储存，每个词条都以树状结构表示着和其他词条的关系，具体内容可以从 GO网站 中找到，其中的元素和逻辑关系可以简单参考上几篇文章。主要编辑工具有go-basic、go和go-plus三个。

这部分文件主要是关于GO词条的具体功能信息，以及相关的支撑信息，以GAF或GPAD格式储存。

目前对基因的注释主要有两种手段：人工注释和机器注释。

人工注释由专业人士(biocurators)通过阅读，提取和转化文献中的实验结果来对基因进行注释。人工注释费时费力，但他们的努力非常重要，因为人工注释的准确性是其他注释的基石，目前有20个团队为GO的人工注释贡献力量。

机器注释主要两大类方法：根据序列进行注释和文本挖掘的方法注释。

1、根据序列信息进行注释：

annotation transfers from Homologous proteins

annotation transfers from Orthologous proteins

annotation transfers from Protein families

2、文本挖掘注释

Automatic text categorization

Lexical approaches

k-Nearest neighbors

Properties of Lexical and k-NN categorizers

Inter-annotator agreement

每种方法的具体解释参考《The Gene Ontology Handbook》的相关章节。

如何构造内核源代码树

Linux内核的配置系统由三个部分组成，分别是：

Makefile：分布在 Linux 内核源代码中的 Makefile，定义 Linux 内核的编译规则；

配置文件（config.in）：给用户提供配置选择的功能；

配置工具：包括配置命令解释器（对配置脚本中使用的配置命令进行解释）和配置用户界面（提供基于字符界面、基于 Ncurses 图形界面以及基于 Xwindows 图形界面的用户配置界面，各自对应于 Make config、Make menuconfig 和 make xconfig）。

这些配置工具都是使用脚本语言，如 Tcl/TK、Perl 编写的（也包含一些用 C 编写的代码）。本文并不是对配置系统本身进行分析，而是介绍如何使用配置系统。所以，除非是配置系统的维护者，一般的内核开发者无须了解它们的原理，只需要知道如何编写 Makefile 和配置文件就可以。所以，在本文中，我们只对 Makefile 和配置文件进行讨论。另外，凡是涉及到与具体 CPU 体系结构相关的内容，我们都以 ARM 为例，这样不仅可以将讨论的问题明确化，而且对内容本身不产生影响。

2． Makefile

2.1 Makefile 概述

Makefile 的作用是根据配置的情况，构造出需要编译的源文件列表，然后分别编译，并把目标代码链接到一起，最终形成 Linux 内核二进制文件。

由于 Linux 内核源代码是按照树形结构组织的，所以 Makefile 也被分布在目录树中。Linux 内核中的 Makefile 以及与 Makefile 直接相关的文件有：

Makefile：顶层 Makefile，是整个内核配置、编译的总体控制文件。

.config：内核配置文件，包含由用户选择的配置选项，用来存放内核配置后的结果（如 make config）。

arch/*/Makefile：位于各种 CPU 体系目录下的 Makefile，如 arch/arm/Makefile，是针对特定平台的 Makefile。

各个子目录下的 Makefile：比如 drivers/Makefile，负责所在子目录下源代码的管理。

Rules.make：规则文件，被所有的 Makefile 使用。

用户通过 make config 配置后，产生了 .config。顶层 Makefile 读入 .config 中的配置选择。顶层 Makefile 有两个主要的任务：产生 vmlinux 文件和内核模块（module）。为了达到此目的，顶层 Makefile 递归的进入到内核的各个子目录中，分别调用位于这些子目录中的 Makefile。至于到底进入哪些子目录，取决于内核的配置。在顶层 Makefile 中，有一句：include arch/$(ARCH)/Makefile，包含了特定 CPU 体系结构下的 Makefile，这个 Makefile 中包含了平台相关的信息。

位于各个子目录下的 Makefile 同样也根据 .config 给出的配置信息，构造出当前配置下需要的源文件列表，并在文件的最后有 include $(TOPDIR)/Rules.make。

Rules.make 文件起着非常重要的作用，它定义了所有 Makefile 共用的编译规则。比如，如果需要将本目录下所有的 c 程序编译成汇编代码，需要在 Makefile 中有以下的编译规则：

%.s: %.c

$(CC) $(CFLAGS) -S $ -o $@

有很多子目录下都有同样的要求，就需要在各自的 Makefile 中包含此编译规则，这会比较麻烦。而 Linux 内核中则把此类的编译规则统一放置到 Rules.make 中，并在各自的 Makefile 中包含进了 Rules.make（include Rules.make），这样就避免了在多个 Makefile 中重复同样的规则。对于上面的例子，在 Rules.make 中对应的规则为：

%.s: %.c

$(CC) $(CFLAGS) $(EXTRA_CFLAGS) $(CFLAGS_$(*F)) $(CFLAGS_$@) -S $ -o $@

2.2 Makefile 中的变量

顶层 Makefile 定义并向环境中输出了许多变量，为各个子目录下的 Makefile 传递一些信息。有些变量，比如 SUBDIRS，不仅在顶层 Makefile 中定义并且赋初值，而且在 arch/*/Makefile 还作了扩充。

常用的变量有以下几类：

1） 版本信息

版本信息有：VERSION，PATCHLEVEL, SUBLEVEL, EXTRAVERSION，KERNELRELEASE。版本信息定义了当前内核的版本，比如 VERSION=2，PATCHLEVEL=4，SUBLEVEL=18，EXATAVERSION=-rmk7，它们共同构成内核的发行版本KERNELRELEASE：2.4.18-rmk7

2） CPU 体系结构：ARCH

在顶层 Makefile 的开头，用 ARCH 定义目标 CPU 的体系结构，比如 ARCH:=arm 等。许多子目录的 Makefile 中，要根据 ARCH 的定义选择编译源文件的列表。

3） 路径信息：TOPDIR, SUBDIRS

TOPDIR 定义了 Linux 内核源代码所在的根目录。例如，各个子目录下的 Makefile 通过 $(TOPDIR)/Rules.make 就可以找到 Rules.make 的位置。

SUBDIRS 定义了一个目录列表，在编译内核或模块时，顶层 Makefile 就是根据 SUBDIRS 来决定进入哪些子目录。SUBDIRS 的值取决于内核的配置，在顶层 Makefile 中 SUBDIRS 赋值为 kernel drivers mm fs net ipc lib；根据内核的配置情况，在 arch/*/Makefile 中扩充了 SUBDIRS 的值，参见4）中的例子。

4） 内核组成信息：HEAD, CORE_FILES, NETWORKS, DRIVERS, LIBS

Linux 内核文件 vmlinux 是由以下规则产生的：

vmlinux: $(CONFIGURATION) init/main.o init/version.o linuxsubdirs

$(LD) $(LINKFLAGS) $(HEAD) init/main.o init/version.o

--start-group

$(CORE_FILES)

$(DRIVERS)

$(NETWORKS)

$(LIBS)

--end-group

-o vmlinux

可以看出，vmlinux 是由 HEAD、main.o、version.o、CORE_FILES、DRIVERS、NETWORKS 和 LIBS 组成的。这些变量（如 HEAD）都是用来定义连接生成 vmlinux 的目标文件和库文件列表。其中，HEAD在arch/*/Makefile 中定义，用来确定被最先链接进 vmlinux 的文件列表。比如，对于 ARM 系列的 CPU，HEAD 定义为：

HEAD := arch/arm/kernel/head-$(PROCESSOR).o

arch/arm/kernel/init_task.o

表明 head-$(PROCESSOR).o 和 init_task.o 需要最先被链接到 vmlinux 中。PROCESSOR 为 armv 或 armo，取决于目标 CPU。 CORE_FILES，NETWORK，DRIVERS 和 LIBS 在顶层 Makefile 中定义，并且由 arch/*/Makefile 根据需要进行扩充。 CORE_FILES 对应着内核的核心文件，有 kernel/kernel.o，mm/mm.o，fs/fs.o，ipc/ipc.o，可以看出，这些是组成内核最为重要的文件。同时，arch/arm/Makefile 对 CORE_FILES 进行了扩充：

# arch/arm/Makefile

# If we have a machine-specific directory, then include it in the build.

MACHDIR := arch/arm/mach-$(MACHINE)

ifeq ($(MACHDIR),$(wildcard $(MACHDIR)))

SUBDIRS += $(MACHDIR)

CORE_FILES := $(MACHDIR)/$(MACHINE).o $(CORE_FILES)

endif

HEAD := arch/arm/kernel/head-$(PROCESSOR).o

arch/arm/kernel/init_task.o

SUBDIRS += arch/arm/kernel arch/arm/mm arch/arm/lib arch/arm/nwfpe

CORE_FILES := arch/arm/kernel/kernel.o arch/arm/mm/mm.o $(CORE_FILES)

LIBS := arch/arm/lib/lib.a $(LIBS)

5） 编译信息：CPP, CC, AS, LD, AR，CFLAGS，LINKFLAGS

在 Rules.make 中定义的是编译的通用规则，具体到特定的场合，需要明确给出编译环境，编译环境就是在以上的变量中定义的。针对交叉编译的要求，定义了 CROSS_COMPILE。比如：

CROSS_COMPILE = arm-linux-

CC = $(CROSS_COMPILE)gcc

LD = $(CROSS_COMPILE)ld

......

CROSS_COMPILE 定义了交叉编译器前缀 arm-linux-，表明所有的交叉编译工具都是以 arm-linux- 开头的，所以在各个交叉编译器工具之前，都加入了 $(CROSS_COMPILE)，以组成一个完整的交叉编译工具文件名，比如 arm-linux-gcc。

CFLAGS 定义了传递给 C 编译器的参数。

LINKFLAGS 是链接生成 vmlinux 时，由链接器使用的参数。LINKFLAGS 在 arm/*/Makefile 中定义，比如：

# arch/arm/Makefile

LINKFLAGS :=-p -X -T arch/arm/vmlinux.lds

6） 配置变量CONFIG_*

.config 文件中有许多的配置变量等式，用来说明用户配置的结果。例如 CONFIG_MODULES=y 表明用户选择了 Linux 内核的模块功能。

.config 被顶层 Makefile 包含后，就形成许多的配置变量，每个配置变量具有确定的值：y 表示本编译选项对应的内核代码被静态编译进 Linux 内核；m 表示本编译选项对应的内核代码被编译成模块；n 表示不选择此编译选项；如果根本就没有选择，那么配置变量的值为空。

2.3 Rules.make 变量

前面讲过，Rules.make 是编译规则文件，所有的 Makefile 中都会包括 Rules.make。Rules.make 文件定义了许多变量，最为重要是那些编译、链接列表变量。

O_OBJS，L_OBJS，OX_OBJS，LX_OBJS：本目录下需要编译进 Linux 内核 vmlinux 的目标文件列表，其中 OX_OBJS 和 LX_OBJS 中的 "X" 表明目标文件使用了 EXPORT_SYMBOL 输出符号。

M_OBJS，MX_OBJS：本目录下需要被编译成可装载模块的目标文件列表。同样，MX_OBJS 中的 "X" 表明目标文件使用了 EXPORT_SYMBOL 输出符号。

O_TARGET，L_TARGET：每个子目录下都有一个 O_TARGET 或 L_TARGET，Rules.make 首先从源代码编译生成 O_OBJS 和 OX_OBJS 中所有的目标文件，然后使用 $(LD) -r 把它们链接成一个 O_TARGET 或 L_TARGET。O_TARGET 以 .o 结尾，而 L_TARGET 以 .a 结尾。

决策树结构

1、决策树结构

import numpy as np

from matplotlib import pyplot as plt

from sklearn.model_selection import train_test_split

from sklearn.datasets import load_iris

from sklearn.tree import DecisionTreeClassifier

from sklearn import tree

plt.rcParams['font.sans-serif'] = ['SimHei']

plt.rcParams['axes.unicode_minus'] = False

#用iris数据集拟合训练树分类器

iris = load_iris()

X = iris.data

y = iris.target

X_train, X_test, y_train, y_test = train_test_split(X, y, random_state=0)

clf = DecisionTreeClassifier(max_leaf_nodes=3, random_state=0)

clf.fit(X_train, y_train)

#树状结构

n_nodes = clf.tree_.node_count

children_left = clf.tree_.children_left

children_right = clf.tree_.children_right

feature = clf.tree_.feature

threshold = clf.tree_.threshold

node_depth = np.zeros(shape=n_nodes, dtype=np.int64)

is_leaves = np.zeros(shape=n_nodes, dtype=bool)

stack = [(0, 0)]  # 从根节点id(0)及其深度（0）开始

while len(stack) 0:

#POP确保每个节点只访问一次

node_id, depth = stack.pop()

node_depth[node_id] = depth

# 如果一个节点的左子节点和右子节点不相同，将进行拆分

is_split_node = children_left[node_id] != children_right[node_id]

# 如果是拆分节点，将左子节点和右子节点以及深度追加到'Stack'

# 这样就可以遍历它们

if is_split_node:

    stack.append((children_left[node_id], depth + 1))

    stack.append((children_right[node_id], depth + 1))

else:

    is_leaves[node_id] = True

print(

"The binary tree structure has {n} nodes and has "

"the following tree structure:\n".format(n=n_nodes)

)

for i in range(n_nodes):

if is_leaves[i]:

    print(

        "{space}node={node} is a leaf node.".format(

            space=node_depth[i] * "\t", node=i

        )

    )

else:

    print(

        "{space}node={node} is a split node: "

        "go to node {left} if X[:, {feature}] = {threshold} "

        "else to node {right}.".format(

            space=node_depth[i] * "\t",

            node=i,

            left=children_left[i],

            feature=feature[i],

            threshold=threshold[i],

            right=children_right[i],

        )

    )

tree.plot_tree(clf)

plt.title("决策树结构")

plt.show()