2024年10月


pandas是具有非常直观且容易操作的索引数据的python第三方软件包。pandas主要有两种数据结构,分别是Series和DataFrame,其广泛用于金融、统计、社会科学等领域的数据分析工作。

1.pandas的特点

  1. 数据结构

    • DataFrame
      :类似于 Excel 表格,可以存储不同类型的数据列。
    • Series
      :一维数组,可以存储任何数据类型(整数、字符串、浮点数、Python 对象等)。
  2. 数据操作

    • 支持大量的数据操作,包括数据清洗、处理缺失数据、重采样时间序列数据等。
    • 提供了丰富的数据对齐和集成处理功能。
  3. 数据索引

    • 支持多种索引方式,包括时间戳、整数索引、标签索引等。
    • 可以对数据进行高效的切片、筛选和分组。
  4. 时间序列功能

    • 强大的时间序列功能,可以轻松处理和分析时间序列数据。
  5. 数据合并

    • 提供了多种数据合并和连接工具,如
      merge

      join

      concat
  6. 数据分组

    • 通过
      groupby
      功能,可以对数据进行分组,并应用聚合函数。
  7. 数据重塑

    • 支持
      pivot

      melt
      等操作,可以轻松地重塑数据结构。
  8. 处理大数据

    • 虽然 Pandas 不是为处理大规模数据集而设计的,但它可以与 Dask 等库结合使用,以处理超出内存限制的大型数据集。
  9. 集成性

    • 可以与 NumPy、SciPy、Matplotlib、Scikit-learn 等其他 Python 数据科学库无缝集成。
  10. 性能

    • 底层使用 Cython 和 C 语言编写,提供了快速的数据操作性能。
  11. 易用性

    • 提供了直观的 API,使得数据操作和分析变得简单直观。
  12. 文档和社区

    • 拥有详细的官方文档和活跃的社区,用户可以轻松找到帮助和资源。

2.Series

在 Pandas 库中,
Series
是一种一维数组结构,可以存储任何数据类型(整数、字符串、浮点数、Python 对象等)。它类似于 Python 中的列表(list)或 NumPy 的一维数组,但
Series
更加强大,因为它可以存储不同的数据类型,并且每个元素都有一个标签(称为索引)。

2.1新建Seriws

可以使用pandas.Series类来新建Series,第一个参数可以带入(列表、元组、字典、numpy.ndarry)等数据。

ser = pd.Series([1,2,3,4,5],index=list('abcde'))  
ser

如果省略index的话会默认从0开始创建索引

pd.Series([1,2,3,4,5])

2.2使用标签来选择数据

使用loc方法可以根据标签来选择数据

#指定标签  
print(ser.loc['b'])  
  
#不使用loc  
print(ser['b'])  
  
#指定标签范围  
print(ser.loc['a':'c'])

你已经很好地概述了 Pandas 中
Series
的创建和基本访问方法。下面我将补充一些细节和额外的操作,以帮助你更好地理解
Series
的使用。

2.3 通过指定位置选择数据

在 Pandas 中,除了使用标签(索引)来选择数据外,还可以通过位置(整数索引)来选择数据。这与 Python 列表的索引类似。以下是一些示例:

import pandas as pd

# 创建 Series
ser = pd.Series([1, 2, 3, 4, 5], index=list('abcde'))

# 使用位置选择第一个元素
print(ser.iloc[0])  # 输出: 1

# 使用位置选择多个元素
print(ser.iloc[0:3])  # 输出: a    1, b    2, c    3

# 使用位置选择最后一个元素
print(ser.iloc[-1])  # 输出: 5

2.4 使用布尔值选择数据

布尔索引是 Pandas 中非常强大的一个功能,它允许你根据条件选择数据。以下是一些示例:

import pandas as pd

# 创建 Series
ser = pd.Series([1, 2, 3, 4, 5], index=list('abcde'))

# 使用布尔索引选择大于2的元素
print(ser[ser > 2])

# 使用布尔索引选择小于等于3的元素
print(ser[ser <= 3])

2.5 其他操作

2.5.1 修改数据

你可以直接通过索引来修改
Series
中的数据:

ser['a'] = 10  # 修改索引为 'a' 的元素
print(ser)

2.5.2 统计操作

Series
提供了许多内置的统计方法,如
sum()
,
mean()
,
max()
,
min()
,
std()
,
var()
等:

print(ser.sum())  # 求和
print(ser.mean())  # 求平均值
print(ser.max())  # 求最大值
print(ser.min())  # 求最小值
print(ser.std())  # 标准差
print(ser.var())  # 方差

2.5.3 缺失数据处理

如果
Series
中包含缺失值(
NaN
),Pandas 提供了多种处理方法,如
dropna()
,
fillna()
等:

ser = pd.Series([1, 2, None, 4, 5])
print(ser.dropna())  # 删除缺失值

ser.fillna(0, inplace=True)  # 将缺失值填充为0
print(ser)

这些操作使得
Series
成为一个非常灵活和强大的数据结构,适用于各种数据分析任务。

3.DataFrame

DataFrame
是 Pandas 中的另一个核心数据结构,它是一个二维表格型数据结构,可以被看作是由多个
Series
组成的(每个
Series
作为
DataFrame
的一列),所有
Series
共享一个索引。

3.1 新建 DataFrame

DataFrame
可以通过多种方式创建,例如从字典、列表、NumPy 数组、已有的
DataFrame
或者直接从数据文件(如 CSV)中读取。

import pandas as pd

# 从字典创建 DataFrame
data = {'Name': ['John', 'Anna', 'Peter', 'Linda'],
        'Age': [28, 23, 34, 29],
        'City': ['New York', 'Paris', 'Berlin', 'London']}
df = pd.DataFrame(data)
print(df)

# 从列表创建 DataFrame
data = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
df = pd.DataFrame(data, columns=['A', 'B', 'C'])
print(df)

# 从 NumPy 数组创建 DataFrame
import numpy as np
data = np.array([[1, 2, 3], [4, 5, 6], [7, 8, 9]])
df = pd.DataFrame(data, columns=['A', 'B', 'C'])
print(df)

3.2 选择数据

3.2.1 使用标签选择数据

使用
.loc
可以基于标签选择数据。它允许你选择行和列。

# 选择行标签为 'John' 的行
print(df.loc[df['Name'] == 'John'])

# 选择列 'Age' 和 'City'
print(df.loc[:, ['Age', 'City']])

3.2.2 使用 iloc 选择数据

使用
.iloc
可以基于整数位置选择数据。它允许你选择行和列。

# 选择第一行
print(df.iloc[0])

# 选择前两行和前两列
print(df.iloc[:2, :2])

3.2.3 使用指定列名选择数据

直接使用列名可以快速选择列。

# 选择 'Age' 列
print(df['Age'])

3.2.4 使用布尔值选择数据

布尔索引允许你根据条件选择行。

# 选择 'Age' 大于 25 的行
print(df[df['Age'] > 25])

3.3 修改数据

修改
DataFrame
中的数据与
Series
类似,可以直接通过标签或位置进行修改。

# 修改 'John' 的 'City' 为 'Los Angeles'
df.loc[df['Name'] == 'John', 'City'] = 'Los Angeles'
print(df)

3.4 统计操作

DataFrame
提供了丰富的统计方法,可以对整个数据框或特定的列进行操作。

# 计算每列的描述性统计
print(df.describe())

# 计算 'Age' 列的平均值
print(df['Age'].mean())

3.5 处理缺失数据


Series
类似,
DataFrame
也支持多种处理缺失数据的方法。

# 添加缺失值
df.loc[3, 'Age'] = None

# 删除包含缺失值的行
print(df.dropna())

# 填充缺失值
df.fillna(value=30, inplace=True)
print(df)

DataFrame
是进行数据科学和分析工作时非常强大的工具,它提供了灵活的数据操作和分析功能。

4.读取格式各样的数据

Pandas 提供了多种函数来读取不同格式的数据文件,这些函数使得数据导入变得非常简单和直接。以下是一些常用的数据读取方法:

4.1 读取 CSV 格式文件

CSV(逗号分隔值)文件是一种常见的数据交换格式。Pandas 的
read_csv
函数可以轻松读取 CSV 文件。

import pandas as pd

# 读取 CSV 文件
df = pd.read_csv('path_to_file.csv')

# 显示前几行数据
print(df.head())

read_csv
函数提供了许多参数来处理不同的 CSV 格式,例如指定分隔符、处理缺失值、选择特定的列等。

4.2 读取 Excel 文件

Excel 文件是一种广泛使用的电子表格格式。Pandas 的
read_excel
函数可以用来读取 Excel 文件。

# 读取 Excel 文件
df = pd.read_excel('path_to_file.xlsx')

# 显示前几行数据
print(df.head())

read_excel
函数允许你指定工作表、读取特定的单元格范围等。

4.3 读取 SQL 文件

Pandas 可以通过 SQL Alchemy 连接到数据库,并使用
read_sql

read_sql_query
函数读取 SQL 数据。

from sqlalchemy import create_engine
import pandas as pd

# 创建数据库连接引擎
engine = create_engine('database_connection_string')

# 读取 SQL 查询结果
df = pd.read_sql_query('SELECT * FROM table_name', con=engine)

# 显示前几行数据
print(df.head())

这里需要一个有效的数据库连接字符串,以及对应的数据库驱动。

4.4 读取 HTML 文件

Pandas 的
read_html
函数可以解析 HTML 中的
<table>
标签,并将其转换为
DataFrame
对象。

# 读取 HTML 文件
df = pd.read_html('path_to_file.html')

# df 是一个 DataFrame 列表,选择第一个 DataFrame
df = df[0]

# 显示前几行数据
print(df.head())

read_html
函数会尝试找到 HTML 文件中所有的
<table>
标签,并返回一个包含所有表格数据的
DataFrame
列表。

在读取这些文件时,Pandas 允许你指定各种参数来处理文件中的特定格式,例如编码、列名、数据类型等。这些函数大大简化了从不同数据源导入数据的过程。

5.数据预处理

数据预处理是数据分析和机器学习项目中的关键步骤,Pandas 提供了多种工具来帮助我们完成这些任务。以下是一些常见的数据预处理技术:

5.1 使用布尔值筛选数据

布尔索引允许我们根据条件筛选数据。我们可以对
DataFrame

Series
使用布尔表达式来选择满足条件的行或列。

import pandas as pd

# 假设我们有以下 DataFrame
df = pd.DataFrame({
    'Age': [25, 30, 35, 40, 45],
    'Name': ['John', 'Anna', 'Peter', 'Linda', 'Michael']
})

# 使用布尔值筛选年龄大于 30 的人
filtered_df = df[df['Age'] > 30]
print(filtered_df)

5.2 使用 where 方法筛选数据

where
方法可以根据一个条件表达式来过滤数据,返回一个满足条件的布尔型
DataFrame

Series

# 使用 where 方法筛选年龄大于 30 的人
filtered_df = df.where(df['Age'] > 30)
print(filtered_df)

where
方法返回的结果是对原始数据的布尔型掩码,如果需要替换不满足条件的值,可以结合
fillna

mask
方法使用。

5.3 修改数据

直接通过标签或位置修改数据。

# 修改特定行的数据
df.loc[df['Name'] == 'John', 'Age'] = 28

# 修改特定列的数据
df['Age'] = df['Age'] + 1
print(df)

5.4 缺失值处理

缺失值处理是数据预处理中的一个重要部分。Pandas 提供了多种方法来处理缺失值。

# 删除包含缺失值的行
df_cleaned = df.dropna()

# 填充缺失值
df_filled = df.fillna(value=0)
print(df_filled)

还可以使用
interpolate
方法来进行插值填充。

5.5 排序

排序是数据分析中的常见操作,Pandas 提供了
sort_values
方法来对数据进行排序。

# 按年龄升序排序
sorted_df = df.sort_values(by='Age')

# 按年龄降序排序
sorted_df_desc = df.sort_values(by='Age', ascending=False)
print(sorted_df)
print(sorted_df_desc)

排序时可以指定多个列,并设置是否升序或降序。

这些是数据预处理中常用的一些操作,Pandas 提供的这些功能使得数据清洗和准备变得非常高效和方便。

6.统计计算

统计计算是数据分析中的核心部分,Pandas 提供了丰富的函数来进行描述性统计分析。以下是一些常用的统计计算方法:

6.1 常见的统计函数

描述性统计

  • count()
    : 计算非NA/null值的数量。
  • mean()
    : 计算平均值。
  • median()
    : 计算中位数。
  • min()

    max()
    : 计算最小值和最大值。
  • std()

    var()
    : 计算标准差和方差。
  • sum()
    : 计算总和。
  • size()
    : 返回数据的总大小。
import pandas as pd

# 创建一个简单的 DataFrame
df = pd.DataFrame({
    'A': [1, 2, 3, 4, 5],
    'B': [10, 20, 30, 40, 50]
})

# 计算描述性统计
print(df.describe())

分布和形状

  • skew()
    : 计算偏度(数据分布的不对称性)。
  • kurt()
    : 计算峰度(数据分布的“尾部”程度)。
print(df.skew())
print(df.kurt())

相关性

  • corr()
    : 计算列之间的相关系数。
print(df.corr())

自定义统计

  • agg()
    : 允许应用多个统计函数。
print(df.agg(['mean', 'max', 'min']))

6.2 快速统计汇总

Pandas 的
describe()
方法可以快速提供一个数据框的汇总统计,包括平均值、标准差、最小值、最大值等。

# 对整个 DataFrame 进行描述性统计
print(df.describe())

# 对指定列进行描述性统计
print(df[['A', 'B']].describe())

describe()
方法默认计算数值列的统计信息,但也可以用于字符串类型的列,此时会显示计数、唯一值数量、最常见值等信息。

对于分类数据,可以使用
value_counts()
方法来查看每个类别的频率。

# 假设我们有一个分类列
df['Category'] = ['A', 'B', 'A', 'C', 'B']
print(df['Category'].value_counts())

统计计算是数据分析的基础,Pandas 提供的这些功能使得从数据中提取有意义的统计信息变得非常简单。通过这些统计函数,我们可以快速了解数据的分布、中心趋势和离散程度。

7.交叉统计

在 Pandas 中,
groupby()

pivot_table()
是两个非常强大的工具,它们可以帮助我们对数据进行分组和汇总统计。

7.1 使用 groupby() 统计

groupby()
方法允许我们根据一个或多个键将数据分组,然后对每个组应用聚合函数,如
sum()

mean()

count()
等。

import pandas as pd

# 创建一个示例 DataFrame
df = pd.DataFrame({
    'Category': ['A', 'B', 'A', 'B', 'C', 'A', 'B', 'C'],
    'Values': [10, 20, 30, 40, 50, 60, 70, 80]
})

# 根据 'Category' 列分组,并计算每个组的总和
grouped_sum = df.groupby('Category')['Values'].sum()
print(grouped_sum)

# 可以同时应用多个聚合函数
grouped_stats = df.groupby('Category')['Values'].agg(['sum', 'mean', 'count'])
print(grouped_stats)

groupby()
也可以用于多级分组,即根据多个列进行分组。

# 假设我们有另一个列 'Subcategory'
df['Subcategory'] = ['X', 'X', 'Y', 'Y', 'X', 'Y', 'X', 'Y']
grouped_multi = df.groupby(['Category', 'Subcategory'])['Values'].sum()
print(grouped_multi)

7.2 使用 pivot_table() 统计

pivot_table()
方法类似于
groupby()
,但它提供了更多的灵活性,允许我们重新排列数据,创建一个透视表,其中指定的列成为行和列索引,而其他列则用于计算值。

# 创建透视表,以 'Category' 为行索引,'Subcategory' 为列索引,计算 'Values' 的总和
pivot_table = df.pivot_table(index='Category', columns='Subcategory', values='Values', aggfunc='sum')
print(pivot_table)

pivot_table()
方法非常灵活,可以处理多个聚合函数,并且可以填充缺失值,处理缺失的组合等。

# 创建透视表,并填充缺失值
pivot_table_filled = df.pivot_table(index='Category', columns='Subcategory', values='Values', aggfunc='sum', fill_value=0)
print(pivot_table_filled)

pivot_table()
还允许我们指定多个聚合函数,并对结果进行进一步的处理。

# 创建透视表,并应用多个聚合函数
pivot_table_multi = df.pivot_table(index='Category', columns='Subcategory', values='Values', aggfunc=['sum', 'mean'])
print(pivot_table_multi)

这些工具在数据分析中非常有用,特别是当你需要对数据进行分组分析或创建复杂的汇总报表时。通过
groupby()

pivot_table()
,我们可以轻松地对数据进行多维度的探索和分析。

8.时间序列的数据处理

时间序列数据是一系列按照时间顺序排列的数据点。在金融、气象、经济和其他许多领域中,时间序列分析是一个重要的分析工具。Pandas 提供了强大的工具来处理时间序列数据。

8.1 使用时间序列数据的函数

Pandas 提供了一系列专门用于处理时间序列数据的函数。这些函数可以帮助我们对时间序列数据进行索引、重采样、移动窗口统计等操作。

import pandas as pd
import datetime as dt

# 创建时间序列数据
dates = pd.date_range('20230101', periods=6)
values = [10, 20, 25, 30, 40, 50]
ts = pd.Series(values, index=dates)

# 访问时间序列数据
print(ts)

# 时间序列的日期偏移
ts_1day_later = ts.shift(1)
print(ts_1day_later)

# 时间序列的滚动统计
rolling_mean = ts.rolling(window=3).mean()
print(rolling_mean)

8.2 DatetimeIndex

DatetimeIndex
是 Pandas 中专门用于时间序列的索引对象。它能够处理日期和时间数据,并提供丰富的时间序列功能。

# 创建 DatetimeIndex
index = pd.DatetimeIndex(['2023-01-01', '2023-01-02', '2023-01-03'])

# 将 DatetimeIndex 设置为范围
date_range = pd.date_range(start='2023-01-01', end='2023-01-10', freq='D')

# 创建时间序列数据
ts_with_range = pd.Series(range(10), index=date_range)
print(ts_with_range)

8.3 筛选时间序列数据

可以使用
DatetimeIndex
来筛选时间序列数据。

# 筛选特定时间段的数据
selected_ts = ts['2023-01-02':'2023-01-04']
print(selected_ts)

8.4 采样

时间序列数据的采样是指从时间序列中提取特定时间点的数据。Pandas 允许我们使用
resample
方法对时间序列数据进行采样。

# 重采样时间序列数据
resampled_ts = ts.resample('D').mean()  # 每日平均值
print(resampled_ts)

# 可以指定不同的频率
resampled_ts_monthly = ts.resample('M').mean()  # 每月平均值
print(resampled_ts_monthly)

在处理时间序列数据时,Pandas 提供的这些工具可以帮助我们有效地管理和分析数据。通过时间序列分析,我们可以识别数据中的模式、趋势和季节性变化,这对于预测和决策制定非常有价值。

一、关于注解

1.1 简介

Java 注解(Annotation)是一种特殊的语法结构,可以在代码中嵌入元数据。它们不直接影响代码的运行,但可以通过工具和框架提供额外的信息,帮助在编译、部署或运行时进行处理。

bfdc3304-b731-443f-bb1c-2bb8a00a90be

初学者可以这样理解注解:想像代码具有生命,注解就是对于代码中某些鲜活个体的贴上去的一张标签。简化来讲,注解如同一张
标签

1.2 发展

Java注解的发展可以追溯到Java 5.0的发布,引入了注解这一特性,为开发者提供了一种新的元数据形式,允许在代码中添加类型信息而不改变程序的逻辑。以下是Java注解发展的一些关键里程碑:

  1. Java 5.0 (2004)
    : 引入了注解的概念,包括
    @Override
    ​,
    @Deprecated
    ​,
    @SuppressWarnings
    ​等内置注解。
  2. Java 6.0 (2006)
    : 增加了对注解的元注解支持,例如
    @Retention
    ​,
    @Target
    ​,
    @Documented
    ​,这些元注解可以用来定义其他注解的元数据。
  3. Java 7.0 (2011)
    : 引入了
    @SafeVarargs
    ​和
    @FunctionalInterface
    ​注解,用于提供关于可变参数和函数式接口的编译时检查。
  4. Java 8.0 (2014)
    : 引入了
    @Repeatable
    ​注解,允许在一个元素上使用同一个注解类型多次。同时,Java 8也是Spring框架开始广泛使用注解的时期,例如
    @Autowired
    ​,
    @RestController
    ​等。
  5. Java 11.0 (2018)
    : 在这个版本中,Java模块系统(Jigsaw项目)正式成为Java的一部分,引入了
    @Module
    ​,
    @Requires
    ​,
    @Exports
    ​等模块相关的注解。
  6. Spring框架的发展
    : 从Spring 1.x的
    @Transactional
    ​和
    @ManagedResource
    ​开始,Spring框架逐渐引入了更多的注解来简化配置和提高开发效率。到了Spring 3.x,引入了
    @Configuration
    ​,
    @ComponentScan
    ​,
    @EnableAutoConfiguration
    ​等注解,进一步推动了注解编程的普及。
  7. Spring 4.x (2013)
    : 引入了
    @Conditional
    ​注解,允许基于条件创建Bean,这是Spring Boot中自动配置的核心。
  8. Spring 5.x (2017)
    : 引入了
    @Indexed
    ​注解,用于提高注解驱动的组件扫描性能。

Java注解的发展不仅提高了代码的可读性和可维护性,也为框架和库的开发者提供了强大的工具,使得他们能够创建更加灵活和强大的API。随着Java语言和相关框架的不断进步,注解将继续在软件开发中扮演重要角色。

1.3 特点

Java注解是一种强大的工具,它使得代码更加清晰、模块化,并且可以与编译器、开发工具和运行时环境紧密协作,提高开发效率和代码质量。

优点

  1. 增强代码可读性


    • 注解提供了清晰的元数据,使代码更易于理解,特别是在使用框架时,可以减少对 XML 配置的依赖。
  2. 减少样板代码


    • 使用注解可以减少大量的样板代码,简化配置。例如,在 Spring 框架中,可以通过注解来代替繁琐的 XML 配置。
  3. 编译时检查


    • 通过注解处理器,可以在编译时检查注解的使用,帮助开发者及早发现问题,提升代码质量。
  4. 灵活性


    • 注解可以与各种编程范式结合使用,如面向对象编程、面向切面编程等,为开发者提供了灵活的编程方式。
  5. 支持元编程


    • 注解与反射机制结合,可以在运行时动态地处理元数据,适用于许多框架和库的设计,如 ORM 和依赖注入。
  6. 自定义能力


    • 开发者可以根据需要创建自定义注解,灵活地定义元数据,满足特定的需求。

缺点

  1. 性能开销


    • 使用反射机制读取注解可能会带来性能开销,尤其是在大规模应用中,频繁的反射调用会影响运行效率。
  2. 调试困难


    • 注解的使用可能使得调试过程变得复杂,尤其是在错误信息中不明确标识出注解的影响,可能导致追踪问题时的困惑。
  3. 学习曲线


    • 对于初学者而言,理解注解及其用法可能需要一定的学习成本,特别是在注解与反射结合使用时。
  4. 过度使用


    • 过度使用注解可能导致代码难以维护和理解,尤其是当多个注解叠加在同一元素上时,可能使得逻辑变得复杂。
  5. 编译器支持


    • 并非所有的 IDE 和工具都完全支持注解的编写和使用,可能会导致一些兼容性问题。
  6. 不适用于所有场景


    • 在一些简单的场景中,使用注解可能显得过于复杂,反而增加了开发和维护的成本。

1.4 使用场景

Java 注解在很多场景下都有应用,例如:

  • 代码分析工具
    :例如使用
    @Deprecated
    ​ 标记方法过时,帮助开发者识别风险和改进代码。
  • 编译时处理
    :例如通过自定义注解,在编译时生成辅助代码,如 Lombok 库。
  • 运行时处理
    :通过反射机制,可以在运行时获取和处理注解信息,实现动态的行为。

二、基本语法

Java 注解的语法主要包括定义注解、使用注解以及元注解。以下是具体的语法示例和解释:

2.1 定义注解

使用
@interface
​ 关键字定义一个注解。可以定义元素(属性)和默认值。

public @interface MyAnnotation {
    // 定义一个字符串类型的元素,带有默认值
    String value() default "default value";

    // 定义一个整型元素,带有默认值
    int count() default 0;
}

2.2 注解的元注解

元注解是用来注解其他注解的注解。Java 提供了以下元注解:

  • @Retention
    :定义注解的生命周期。
  • @Target
    :定义注解可以应用于哪些 Java 元素(类、方法、字段等)。
  • @Documented
    :表示该注解应该被 javadoc 工具记录。
  • @Inherited
    :表示该注解可以被子类继承。
import java.lang.annotation.ElementType;
import java.lang.annotation.Retention;
import java.lang.annotation.RetentionPolicy;
import java.lang.annotation.Target;

@Retention(RetentionPolicy.RUNTIME) // 注解在运行时可用
@Target(ElementType.METHOD) // 注解可以用于方法
public @interface MyMethodAnnotation {
    String description();
}

2.3 使用注解

使用自定义注解时,直接在需要的元素上加上注解即可。

public class MyClass {

    @MyMethodAnnotation(description = "This is a custom method annotation")
    public void myAnnotatedMethod() {
        // 方法实现
    }
}

2.4 访问注解

使用反射机制在运行时访问注解信息。

import java.lang.reflect.Method;

public class AnnotationExample {
    public static void main(String[] args) throws Exception {
        Method method = MyClass.class.getMethod("myAnnotatedMethod");

        if (method.isAnnotationPresent(MyMethodAnnotation.class)) {
            MyMethodAnnotation annotation = method.getAnnotation(MyMethodAnnotation.class);
            System.out.println("Description: " + annotation.description());
        }
    }
}

2.5 组合注解

可以将多个注解组合在一起使用。

@MyAnnotation
@AnotherAnnotation
public class AnotherClass {
    // 类实现
}

三、Java 预置的注解

Java 提供了一些预置的注解,这些注解在 Java 开发中非常常用。以下是一些主要的预置注解及其用途:

1.
@Override
  • 用途
    :用于指示一个方法重写了超类的方法。

  • 示例

    @Override
    public String toString() {
        return "This is my object";
    }
    
2.
@Deprecated
  • 用途
    :标记一个元素(类、方法或字段)为不推荐使用,可能在将来的版本中被删除。

  • 示例

    @Deprecated
    public void oldMethod() {
        // 不推荐使用
    }
    
3.
@SuppressWarnings
  • 用途
    :抑制编译器发出的特定警告。可以指定警告类型,如未使用的变量、未检查的转换等。

  • 示例

    @SuppressWarnings("unchecked")
    public void myMethod() {
        List list = new ArrayList(); // 编译器可能会发出未检查的转换警告
    }
    
4.
@FunctionalInterface
  • 用途
    :用于指示一个接口是函数式接口,即该接口只包含一个抽象方法。

  • 示例

    @FunctionalInterface
    public interface MyFunctionalInterface {
        void execute();
    }
    
5.
@SafeVarargs
  • 用途
    :用于指示可变参数方法是类型安全的,适用于不可变的泛型。

  • 示例

    @SafeVarargs
    public static <T> void safeMethod(T... elements) {
        // 处理元素
    }
    
6.
@Native
  • 用途
    :标记一个字段为本地常量,通常用于与 C/C++ 代码交互。

  • 示例

    @Native
    public static final int NATIVE_CONSTANT = 100;
    

四、示例

示例1—使用注解(标记过时的方法)

在 Java 中,使用
@Deprecated
​ 注解可以标记一个方法或类已经过时,鼓励开发者使用新的实现或方法。

class DeprecatedExample {

    @Deprecated
    public void oldMethod() {
        System.out.println("This method is deprecated.");
    }

    public void newMethod() {
        System.out.println("This is the new method.");
    }

    public static void main(String[] args) {
        DeprecatedExample obj = new DeprecatedExample();

        // 调用过时的方法
        obj.oldMethod();

        // 调用新方法
        obj.newMethod();
    }
}

在这个示例中,
oldMethod
​ 被标记为过时的,当我们调用它时会得到编译器警告,提醒我们不要继续使用这个方法。

image

示例2—自定义注解

1.定义注解

image

image

//自定义注解必须的元注解target,指明注解的作用域(此处指明的是在类和方法上起作用)
@Target({ElementType.TYPE, ElementType.METHOD})
//元注解retention声明该注解在何时起作用(此处指明的是在运行时起作用)
@Retention(RetentionPolicy.RUNTIME)
public @interface MyAnnotation {

    //注解中需声明参数,格式为:参数类型 + 参数名();
    String value() default "";

}

2.使用注解

image

public class CustomAnnotation {

    @MyAnnotation(value = "这是一个测试方法")
    public void test() {
        System.out.println("执行 test 方法");
    }

}

3.获取和使用注解信息

image

public class AnnotationDemo {

    public static void main(String[] args) {

        try {
            // 获取 CustomAnnotation 类的 Class 对象
            Class<CustomAnnotation> clazz = CustomAnnotation.class;

            // 获取 test 方法
            Method method = clazz.getMethod("test");

            // 检查该方法是否有 MyAnnotation 注解
            if (method.isAnnotationPresent(MyAnnotation.class)) {
                // 获取 MyAnnotation 注解
                MyAnnotation annotation = method.getAnnotation(MyAnnotation.class);
                // 打印注解的 value 值
                System.out.println("注解的值: " + annotation.value());
            }

            // 调用 test 方法
            CustomAnnotation customAnnotation = new CustomAnnotation();
            customAnnotation.test();

        } catch (NoSuchMethodException e) {
            throw new RuntimeException(e);
        }

    }
}

1. 相关工作

CNN
的的卷积核窗口大小有限,每次只能看比较短的部分序列,但是它的多通道机制被认为可以去识别多模式,
transformer
论文参考这个机制,在
attention
的机制进一步引出了
Muti-Head Attention
,来模拟卷积层的多输出通道效果。

Self-attention

transformer
论文之前已经有人提出,但
transformer
是第一个只依赖自注意力机制(self-attnetion)来实现
encoder-decoder
架构的模型。

2. 模型架构

(直到 GPT 出来之前)大多数有竞争力的神经序列转换模型都是采用编码器-解码器结构,transformer 模型也不例外。

编码器将输入的符号表示序列 (
\(x_1,x_2,…,x_n\)
) 映射为一个连续表示序列 (
\(z_1,z_2,…, z_n\)
)。得到编码器输出序列
\(z\)
后,解码器逐个元素的生成符号的输出序列 (
\(y_1,y_2…,y_m\)
)。解码器输出是自回归的,将当前轮的输出和输入拼接,作为下一轮的输入。

Transformer
的基本组件是:
point-wise

self-attention

add & norm

feed forward

linear

softmax

为了方便残差连接,模型中的所有子层
Sub Layer
以及嵌入层
Embedding Layer
都生成维度为
\(d_{model} = 512\)
的输出向量。

3. 如何理解 Layer Norm

NLP/Transformer
模型的输入是
三维向量

batch
、句子序列长度
\(n\)
、单词映射为
embedding vector
都分别表示为一个维度。

Batch norm

layer norm
的区别一句话总结就是
bn
是切特征,
ln
是切样本。

  • BN
    : 对于每个特征维度,计算它在整个批次中的均值和标准差,然后对该特征进行归一化。
  • LN
    : 对每个样本单独计算其所有特征的均值和标准差,然后在该样本内进行归一化。

BN 和 LN 的区别

Layer Norm 层的计算可视化如下图所示:

Layer Norm

4. Encoder 和 Decoder 结构

Decoder
同样由
\(N = 6\)
个相同的层组成。
Decoder

attention
是带掩码的,确保位置
\(i\)
的预测只能依赖于小于
\(i\)
的已知输出。

5. 从 attention 到 Scaled Dot-Product Attention

标准自注意力的数学表达式如下:

\[\text{Attention}(Q, K, V) = \text{softmax}\left(\frac{QK^T}{\sqrt{d_k}}\right)V
\]

1,首先,注意力函数可以描述为将一个查询(query)和一组键-值对(key-value pairs)映射到一个输出 output,
\(q\)

\(k\)

\(v\)
都是向量。输出都是对
value
进行加权求和得到的,每个 value 对应的权重
weight
是通过
\(q\)

\(k\)
之间的相似度计算得到。

2,将 q 和 k 的内积作为相似度(Dot-Product),然后除以向量的长度
\(\sqrt{d_k}\)
(Scaled),结果再应用
softmax
函数,就会得到
\(n\)
个非负且相加求和等于
\(1\)
的权重向量,最后将权重应用于 value,就得到了最终输出 output。

余弦相似度常用来比较两个向量的相似度(距离)
,伪代码如下:

CosineSimilarity = sum(x[i]*y[i])/(sqrt(sum(x[i]*x[i]))*sqrt(sum(y[i]*y[i])))。

实际中,为了方便计算,会同时对一组查询(queries)计算注意力函数,将 q、k、v 都是构建成矩阵
\(Q\)

\(K\)

\(V\)
( 维度相等),涉及到两个矩阵乘法。

作者提到当向量维度变大的时候,softmax 函数会造成梯度消失问题,所以设置了一个 softmax 的 temperature 来缓解这个问题。这里 temperature 被设置为了
\(\sqrt{d_k}\)

作者提出的注意力机制算法跟之前的 Dot-Product Attention 相比就是单纯多了 Scaled(除以
\(\sqrt{d_k}\)
)。

另外 decoder 模块的 attention 多了一个
Mask
,实际是第
\(t\)
时刻的
\(q\)
只能看前面阶段的对应的
\((k, v)\)
对,计算当中表现就是对于
\(q_t\)

\(k_t\)
及其之后的那些权重值都替换成一个极大的负数,这样经过
softmax
后(做指数
\(e^{w_t}\)
),对应位置的
\(v\)
就变成了 0。

6. Multi-Head Attention

Scaled Dot-Product Attention
是不带任何参数的!

与其做单个的注意力函数,不如将
\(Q\)

\(K\)

\(V\)
投影到一个
低维度
、投影
\(h\)
次,然后再做
\(h\)
次的自注意力函数,并将这
\(h\)
个函数的输出拼接在一起,最后再次进行线性投影回来。

\[\text{Multi-Head Attention} = Concat(head_1,….,head_h) W^o \\
\text{Where} \ \text{head}_i = Attention (QW_i^Q, KW_i^K, VW_i^V)\]

\(Q\)

\(K\)
的线性(映射)层的权重维度是
\([d_\text{model}, d_k]\)

\(V\)
的线性(映射)层的权重维度是
\([d_{model}, d_v]\)
,输出线性(映射)层权重维度是
\([h*d_v, d_{model}]\)

作用:
多头注意力机制可以注意到不同子空间的信息,捕捉到更加丰富的特征信息,实现类似卷积核的多通道机制的效果

从 scaled dot producted attention 到 multi-head attention

7. Transformer 的三个 multi-head attention 的原理和作用

三个 multi-head attention

原理

  1. 解码器中的第二个注意力层,其查询
    \(q\)
    来自前一层的解码器层,但
    \(k\)

    \(v\)
    来自于编码器最后一层的输出。
  2. 编码器第一个注意力层:不考虑多头和线性投影层的情况,三个输入
    \(q\)
    \(k\)
    \(v\)
    本质上都是一个东西,三个输入都是原始输入本身自己,输出就是输入本身的加权和,而权重又来源自己本身跟跟各个向量的相似度函数,所以也叫自注意力层(self-attention)。
  3. 解码器的第一个注意力层:编码器的最终输出作为 key value 输入进来,解码器下一层的输出作为 query 输入进来。

作用

  1. Self-Attention
    (自注意力):对于每个位置上的 token,Self-Attention 将其与序列中的所有其他位置进行关联,从而使模型能捕捉到句子内部的语义关系。
  2. Encoder-Decoder Attention
    (编码器-解码器注意力):允许解码器在生成下一个词时参考编码器的输出。这种机制实现了输入和输出序列之间的联系,是实现翻译等任务的关键所在。
  3. Masked Self-Attention
    (掩码自注意力):过掩码机制屏蔽掉序列中未来位置的 tokens,从而确保模型预测生成的每个 token 仅依赖于当前生成位置之前的 tokens。

从 nlp 角度理解 Attention + MLP: Attention 负责从全局的角度把整个序列的信息聚合起来(捕捉上下文信息 + 信息聚合),然后用 MLP 做语义的转换。

8. Embedding 和 Softmax 层

Embedding
层的作用学习一个长为
\(d_{model}\)
的向量来表示
token

,编码器和解码器的输入都需要
embedding
层,两个嵌入层和
softmax
之前的线性变换之间共享相同的权重矩阵重(维度都是一样的),并且将权重值乘以
\(\sqrt{d_{model}}\)

学习 embedding 时,可能会把每个向量的
\(\text{L2\ norm}\)
学得相对较小(维度越大权重值越小),乘以
\(\sqrt{d_{model}}\)
后放大,使得和 PE 相加时在
scale
上匹配。

L2 归一化(L2 Norm)是一种将向量缩放到单位长度的操作,使得向量的模为1。对于一个给定向量
\(\mathbf{v}\)
,L2 归一化后的向量
\(\mathbf{\hat{v}}\)
,计算公式如下:

\[\mathbf{\hat{v}} = \frac{\mathbf{v}}{\|\mathbf{v}\|_2}
\]

9. Positional Encoding

Attention
层的输出本身是不具备时序信息的,因为其本质是
value
向量的一个加权和,而权重是
query

key
的距离,跟序列信息无关。把输入
tokens
位置打乱,
attention
的输出向量的所有元素的值大小不会变化,只有元素位置的变化,这显然不符合直觉。

而 Position encoding 层的作用是使得生成的 embedding vectors 值跟位置相关(加入时序信息),更符合人类文字的意义(文字的位置打乱,相应语义肯定会变化)。它的做法是将位置信息编码为向量,并将这些向量加到输入的嵌入向量中。Positional Encoding 通常通过以下公式计算:

\[PE(pos, 2i) = \sin \left(pos/10000^{2i/d}\right) \\
PE(pos, 2i+1) = \cos \left(pos/10000^{2i/d}\right)\]

10. 为什么使用 self-attention!

比较了四种不同的层: self-attention、rnn、cnn、self-attention (restricted),分别比较了计算复杂度FLOPs、顺序操作(并行度)、最大路径长度。

参考资料

今天我们继续学习新的数据结构-散列表。

01
、定义

我们先来了解一些常见概念名词解释。

散列
:散列表的实现叫做散列,是一种实现以常数级时间复杂度执行查找、插入和删除的技术;

散列值
:通过散列函数对输入值(key)计算出来的结果,用来表示key的唯一性,它通常是一个长度固定的值,即无论key多大,散列值的长度都是固定的;

散列地址
:通过散列值计算出来的存储位置,即存储value的位置,通常使用散列值和散列表的大小取模得到散列地址。

碰撞
:也叫
冲突
,指两个不同的key,经过散列函数计算后得到相同的散列值;

负载系数
:也叫
负载因子
,用来衡量散列表填充程度,通过散列表已存储的元素个数除以散列表的大小计算可得;

散列函数
:也叫
哈希函数
,指将key映射为散列值的函数;

散列表又称哈希表,是以「key-value」形式存储数据的数据结构。可以理解为任意的key都可以唯一对应到内存中的某个地址,而这个地址就存放着value,通过key快速查找到value。也可以把散列表理解为一种高级的数组,其中key就相当于数组下标,此数组下标不但可以是整数,还可以是浮点数、字符串、结构体等,其中value就相当于数组元素值。

通过前面的数据结构学习,我们知道数组是查找容易、插入和删除困难;链表是查找困难、插入和删除容易;而散列表是集两者之大成,做大查找、插入、删除都容易的一种数据结构。

本质上来说散列表就是一个数组。虽然上面把key比作数组下标,但是key并不真的是数组下标。因此这中间就需要一个转换工具把key转换为数组下标,而这个工具就是散列函数。

如下图,展示了在散列表中如何通用key获取到value的过程。输入key4通过散列函数计算得到数组索引3,最后通过数组下标取出value4。

02
、散列函数

散列技术核心难点之一就是如何设计一个准确、快速、均匀、抗碰撞的散列函数。而一个好的散列函数对散列表是至关重要的,这影响散列表的存储和检索效率。

1、四大特性

(1)
确定性
:指相同的输入key总能输出相同的结果;

(2)
快速计算
:指计算散列值的速度尽可能的快;

(3)
均匀分布
:指尽量将输入key均匀的映射到散列表中,以减少碰撞;

(4)
抗碰撞性
:指尽量减少不同的输入key生成出相同的散列值概率;

2、常见散列函数算法

(1)取模算法

该算法是一种最简单且常用的散列函数构造方法。

原理
:通过将key取模散列表的大小(通常是质数)来计算散列值;

公式
:hash(key) = key % m;

优点
:简单易实现,计算速度快;

缺点
:如果m不是质数,会增加碰撞概率,因此m最好选用质数来减少碰撞概率。

示例
:假设我们有个散列表,大小为10,分别散列以下key:11,23,4,19

hash(11) = 11 % 10 = 1

hash(23) = 23 % 10 = 3

hash(4) = 4 % 10 = 4

hash(17) = 17 % 10 = 7

则最终生成的散列值分别为1、3、4、7,而这些值就可以作为散列表的索引。

(2)乘法算法

该算法是通过乘法来降低碰撞概率,以使散列值均匀分布;

原理
:通过将key与一个固定常数 A(通常是黄金比例的倒数)相乘,取其乘积的小数部分,再乘以散列表的大小(通常是质数),所得结果的整数部分即为散列值;

公式
:hash(key) = ⌊m * (key * A % 1)⌋;

优点
:简单易实现,散列值分布更均匀;

缺点
:常数A的选择对计算结果散列值影响很大,选择不好很容易增加碰撞概率;

示例
:假设我们有个散列表,大小为10,常数A为0.618,分别散列以下key:11,23,4,19

hash(11) = ⌊10 * (11 * 0.618 % 1)⌋ = 7

hash(23) = ⌊10 * (23 * 0.618 % 1)⌋ = 2

hash(4) = ⌊10 * (4 * 0.618 % 1)⌋ = 4

hash(17) = ⌊10 * (17 * 0.618 % 1)⌋ = 5

则最终生成的散列值分别为7、2、4、5,而这些值就可以作为散列表的索引。

(3)DJB2算法

DJB2 是一种使用广泛的字符串散列算法,它简单而高效,由 Daniel和J. Bernstein 提出。其核心公式:hash = hash * 33 + c,其中 33 是常用的基数。

原理
:使用一个初始散列值(通常是5381),然后通过对key的每一个字符的ASCII值进行逐步加权处理,最终得到散列值;

公式
:hash(key) = {

hash = 5381

for character c in string:

hash = ((hash << 5) + hash) + c

return hash & 0xFFFFFFFF

}

优点
:简单易懂,速度快,底碰撞;

缺点
:基数(33)的选择对散列性能有一定影响,虽然普遍表现良好,但并不是最佳选择;散列值的输出通常需要进行掩码操作(如 & 0xFFFFFFFF),这可能导致部分信息丢失,尤其在处理较大数据时。

上面的公式中没有使用hash * 33 + c,而是使用((hash << 5) + hash) + c是因为位运算效率更高。

(4)其他算法

除了以上三种算法还有很多其他算法,比如和DJB2算法类似的BKDR算法、PJW算法,比如还有诸如:直接定算法、数字分析算法、平方取中算法、折叠算法、随机数算法等等,这里就不一一细说了,有兴趣的可以自己研究研究。


:测试方法代码以及示例源码都已经上传至代码库,有兴趣的可以看看。
https://gitee.com/hugogoos/Planner

看到这个题目就知道上一节提到的
RISC-V手册
的10.6节又有用武之地了.

这里只需注意,RV32 的分页方案Sv32支持4GiB的虚址空间,RV64 支持多种分页方案,但我们只介绍最受欢迎的一种,Sv39。:

RISC-V 的分页方案以SvX的模式命名,其中X是以位为单位的虚拟地址的长度。

虚拟地址和物理地址

直接访问物理地址

默认情况下是
没有
开启MMU的,此时无论CPU处于哪个特权级,访问内存的地址
都是
物理地址.

启用MMU

有一个CSR(Control and Status Register
控制状态寄存器
),决定了MMU的控制.名叫
satp
(Supervisor Address Translation and Protection
监管地址翻译和保护寄存器
).

其结构如图所示:

  • MODE
    控制 CPU 使用哪种页表实现;

    • MODE
      为0---
      b0000
      的时候,所有的优先级的内存访问都是直接访问物理内存

    • MODE
      设置为8---
      b1000
      时,分页机制被开启,而且选用的

      SV39
      分页机制

      ,那么
      S/U
      级别的特权级访问的时候就需要通过MMU.

    • MODE
      设置为9---
      b1001
      时,分页机制被开启,而且选用的是
      SV48
      分页机制,这里
      不讨论这种分页机制
      .
  • ASID
    表示地址空间标识符,这里还没有涉及到进程的概念,我们不需要管这个地方.
  • PPN
    存的是
    根页表
    所在的物理页号.这样, 给定一个虚拟页号,CPU 就可以从三级页表的根页表开始一步步的将其映射到一个物理页号.

这个
PPN
也很重要,虽然我们在这里只提到了有关于模式选择的
MODE
,但是到了后边真正要完成访存的时候
PPN
决定的根节点决定了我们当前不同
APP
同样的虚拟内存
怎么映射到
不同的物理内存
的.

地址结构

首先,我们只考虑
虚拟地址

物理地址
的位数,而
不去考虑地址的每个位的作用
.

那么39位的虚拟地址,最多可以访问高达512G的内存.

更甚的,拥有
56位
的物理地址,则能够访问更多大的内存范围(数据来自于GPT).

但是实际上讨论这个最大储存上限是没有意义的,这样的地址形式没办法产生
虚拟地址

物理地址
之间的映射,没有固定的映射那就
更难通过MMU
进行地址的转换.

那么我们实际上采用的是分页的储存方式,因此有一套属于分页储存的地址,如下图所示(图是偷的
参考手册
)的.

这个储存方式是
偏移
+
页数
的方式.

这里注意每个页面的大小设置为
4KiB
.这个是我们自己设置的,对应的是
offset

12bit
,这样才能通过偏移来访问每个
Byte
.

RISC-V要求地址长度为64位,这里我们只用到了39位,但是不代表前38位就完全没有要求.

在启用 SV39 分页模式下,只有低 39 位是真正有意义的。SV39 分页模式规定 64 位虚拟地址的 [63:39] 这 25 位必须和第 38 位相同,否则 MMU 会直接认定它是一个不合法的虚拟地址。通过这个检查之后 MMU 再取出低 39 位尝试将其转化为一个 56 位的物理地址。

那么就会有很神奇的事情发生,就是由于后边的[63:39]这部分都必须和第38位相同,那么就是都是1或者都是0,那么,实际上这
0~38
位代表的内存空间不是连续的一个512G,而是分为在地址最高的256G和地址最低的256G.

数据结构抽象

对usize进行封装

所需的数据结构:

  1. 物理地址
  2. 虚拟地址
  3. 物理页数
  4. 虚拟页数

这边使用的方式是使用一个
元组式
结构体

.

// os/src/mm/address.rs

#[derive(Copy, Clone, Ord, PartialOrd, Eq, PartialEq)]
pub struct PhysAddr(pub usize);

#[derive(Copy, Clone, Ord, PartialOrd, Eq, PartialEq)]
pub struct VirtAddr(pub usize);

#[derive(Copy, Clone, Ord, PartialOrd, Eq, PartialEq)]
pub struct PhysPageNum(pub usize);

#[derive(Copy, Clone, Ord, PartialOrd, Eq, PartialEq)]
pub struct VirtPageNum(pub usize);

里边的
usize
就是
STRUCT.0
.

这里注意一点,就是使用
#[derive(Trait)]
自动实现的
Trait
,尤其是之前没怎么用过的
Ord

PartialOrd
:

  1. Copy
    :这个 trait 表示类型的值可以被“复制”。拥有
    Copy
    trait 的类型可以被简单地赋值给另一个变量,而不会改变原始值。例如,基本的数值类型(如
    i32

    f64
    )和元组(如果它们包含的所有类型都实现了
    Copy
    )都实现了
    Copy
    。这个 trait 不能手动实现,只能通过派生。
  2. Clone
    :这个 trait 允许一个值被显式地复制。与
    Copy
    不同,
    Clone
    需要显式的调用(例如,使用
    clone()
    方法)。
    Clone
    trait 要求类型可以被复制,但不要求复制是无成本的。如果一个类型实现了
    Copy
    ,它自动也实现了
    Clone
    ,但反之则不一定。
  3. Ord
    :这个 trait 表示类型支持全序比较,即可以比较任意两个值并确定它们之间的顺序(小于、等于、大于)。这意味着类型必须实现
    PartialOrd

    Eq
  4. PartialOrd
    :这个 trait 允许对类型的值进行部分顺序比较。这意味着可以比较两个值,但可能会返回
    None
    ,表示它们不可比较。大多数时候,如果类型可以完全排序,那么
    PartialOrd
    也会被实现。
  5. Eq
    :这个 trait 表示类型支持等价性比较,即可以比较两个值是否相等。
    Eq

    PartialEq

    Ord
    的基础,它要求类型可以比较相等性。
  6. PartialEq
    :这个 trait 允许对类型的值进行等价性比较,但可能会返回
    None
    ,表示它们不可比较。大多数时候,如果类型可以完全比较,那么
    PartialEq
    也会被实现。
    (此处的解释来自于Kimi)

那么这么封装的好处,实际上是
加一层抽象
,有的时候觉得没用的抽象实际上使用的时候是非常有好处的.

我们刻意将它们各自抽象出不同的类型而不是都使用与RISC-V 64硬件直接对应的 usize 基本类型,就是为了在 Rust 编译器的帮助下,通过多种方便且安全的
类型转换
(Type Conversion) 来构建页表。

通过From进行类型之间和类型与usize之间的转换

封装类型与usize转换

// os/src/mm/address.rs

const PA_WIDTH_SV39: usize = 56;
const PPN_WIDTH_SV39: usize = PA_WIDTH_SV39 - PAGE_SIZE_BITS;

impl From<usize> for PhysAddr {
    fn from(v: usize) -> Self { Self(v & ( (1 << PA_WIDTH_SV39) - 1 )) }
}
impl From<usize> for PhysPageNum {
    fn from(v: usize) -> Self { Self(v & ( (1 << PPN_WIDTH_SV39) - 1 )) }
}

impl From<PhysAddr> for usize {
    fn from(v: PhysAddr) -> Self { v.0 }
}
impl From<PhysPageNum> for usize {
    fn from(v: PhysPageNum) -> Self { v.0 }
}

这里注意
PAGE_SIZE_BITS
是作为一个常数保存在
config.rs
里边.

//os/src/config.rs

//*  Constants for mm *//
pub const PAGE_SIZE_BITS: usize = 12;

封装类型互相之间的转换

刚刚看到这里的时候就发现了一件事,那么
地址
是比
页号
要多一个
offset
信息的,如果直接进行转换,那么怎么才能不进行信息丢失呢?

这里仔细去看如下的代码,我们可以看到,如果只有
PhysPageNum
,那么把它转换为
PhysAddr
的时候默认
offset

0
,那么反过来
PhysAddr
转化为
PhysPageNum
的时候,需要去判断
offset
是不是
0
,如果
offset
不是
0
,那么报错.

// os/src/mm/address.rs

impl PhysAddr {
    pub fn page_offset(&self) -> usize { self.0 & (PAGE_SIZE - 1) }
}

impl From<PhysAddr> for PhysPageNum {
    fn from(v: PhysAddr) -> Self {
        assert_eq!(v.page_offset(), 0);
        v.floor()
    }
}

impl From<PhysPageNum> for PhysAddr {
    fn from(v: PhysPageNum) -> Self { Self(v.0 << PAGE_SIZE_BITS) }
}

同样地,
PAGE_SIZE
是一个常数,被保存在
config.rs
里:

//os/src/config.rs

//*  Constants for mm *//
pub const PAGE_SIZE: usize = 4096;

其中,读取
offset
的方法
page_offset
的实现:

impl PhysAddr {
    pub fn page_offset(&self) -> usize { self.0 & (PAGE_SIZE - 1) }
}

最后我们产生了一些其它的疑问,那么如果
offset
不是
0
,难道就不能进行转换了吗?答案是可以进行转换,但是不能经过
隐式
的转换,要通过显式的转换,即你要知道自己进行了带有
四舍五入
的取整.

// os/src/mm/address.rs

impl PhysAddr {
    pub fn floor(&self) -> PhysPageNum { PhysPageNum(self.0 / PAGE_SIZE) }
    pub fn ceil(&self) -> PhysPageNum { PhysPageNum((self.0 + PAGE_SIZE - 1) / PAGE_SIZE) }
}

其中
floor
是向下取整,
ceil
是向上取整.

这里实际上还是很难理解向上取整的意义,因为这个 offset 太过靠近下一页,所以干脆取下一页吗?

向上取整是取一页新的没有占用过的,向下取整是取当前页.

页表项

页表项
就是一个同时含有
页号信息

标志位
的数据结构.

页号信息相当于是一个字典,映射一个
虚拟地址
和一个
物理地址
.

标志位则各不相同:

  • V(Valid):仅当位 V 为 1 时,页表项才是合法的;
  • R(Read)/W(Write)/X(eXecute):分别控制索引到这个页表项的对应虚拟页面是否允许读/写/执行;
  • U(User):控制索引到这个页表项的对应虚拟页面是否在 CPU 处于 U 特权级的情况下是否被允许访问;
  • G:暂且不理会;
  • A(Accessed):处理器记录自从页表项上的这一位被清零之后,页表项的对应虚拟页面是否被访问过;
  • D(Dirty):处理器记录自从页表项上的这一位被清零之后,页表项的对应虚拟页面是否被修改过。

除了
G
外的上述位可以被操作系统设置,只有
A
位和
D
位会被处理器动态地直接设置为
1
,表示对应的页被访问过或修过( 注:
A
位和
D
位能否被处理器硬件直接修改,取决于处理器的具体实现)。

这时候要在rust中实现它,这时候使用的是用一个位代表一个FLAG的形式,rust提供了这样的一个包,名字叫做
bitflags
.

因此要:


  1. Cargo.toml
    中声明依赖这个包.

  2. main.rs
    中声明使用这个包.

在我写下这篇博客的时候
bitflag
的版本截止到
2.6.0
,可以通过查看
相关网站
看到最新版本和细节.

// os/Cargo.toml

[dependencies]
bitflags = "2.6.0"


main.rs
中加入:

extern crate bitflags;

创建
os/src/mm/page_table.rs
,实现这部分FLAG:

use bitflags::bitflags;

bitflags!{
    pub struct PTEFlags: u8{
        const V = 1<<0;
        const R = 1<<1;
        const W = 1<<2;
        const X = 1<<3;
        const U = 1<<4;
        const G = 1<<5;
        const A = 1<<6;
        const D = 1<<7;
    }
}

怎么解读它呢?这里只提供一个简单的例子,
更详细
的部分需要继续自主学习:

bitflags! {
    struct FlagsType: u8 {
//                    -- Bits type
//         --------- Flags type
        const A = 1;
//            ----- Flag
    }
}

let flag = FlagsType::A;
//  ---- Flags value

这里对应的四个部分:

  1. Bits type
    意味着这个
    flag
    一共有多少位,对应一个相应位数的类型.
  2. FlagsType
    就是给这个这一组标志位取一个总的名字.
  3. Flag
    就是给作为标志位的某个位取得名字.
  4. Flags value
    意味着你可以使用
    FlagsType::Flag
    访问对应的标志位的值.

那么这时候继续实现页表项:

// os/src/mm/page_table.rs

#[derive(Copy, Clone)]
#[repr(C)]
pub struct PageTableEntry {
    pub bits: usize,
}

impl PageTableEntry {
    pub fn new(ppn: PhysPageNum, flags: PTEFlags) -> Self {
        PageTableEntry {
            bits: ppn.0 << 10 | flags.bits as usize,
        }
    }
    pub fn empty() -> Self {
        PageTableEntry {
            bits: 0,
        }
    }
    pub fn ppn(&self) -> PhysPageNum {
        (self.bits >> 10 & ((1usize << 44) - 1)).into()
    }
    pub fn flags(&self) -> PTEFlags {
        PTEFlags::from_bits(self.bits as u8).unwrap()
    }
}

那么也可以继续实现一些有关于判断
标志位
的辅助函数:

// os/src/mm/page_table.rs

impl PageTableEntry {
    pub fn is_valid(&self) -> bool {
        (self.flags() & PTEFlags::V).bits() != PTEFlags::empty().bits()
    }
}

这里注意新版本
bitflags
的代码不允许
PTEFlags
直接进行比较了,于是我们通过比较它的
bits()
.

多级页表

线性表

这个玩意还挺方便的,比如我们要访问
VirtualPageNum

0

页表项
,以映射到
PhysicalPageNum
的时候我们只需要计算
base_addr+8i
就可以访问到了.

这里比较难理解的就是后边它就直接开始计算了,好像所有的从第一个
VirtualPageNum=0
到最后一个
VirtualPageNum=2^27
都用掉了.

那当然了,假如说我们虽然中间的没用到的内存不去用,这里用一块那里用一块,是不是这一块内存都不能用了???这样就好理解了.

文档里的表达是:

由于虚拟页号有
\(2^{27}\)
种,每个虚拟页号对应一个 8 字节的页表项,则每个页表都需要消耗掉 1GiB 内存!

我们的理解是:
由于虚拟页号有
\(2^{27}\)
种,每个虚拟页号对应一个 8 字节的页表项,则每个页表需要预留1GiB内存!

字典树与多级页表

字典树的表述在
参考手册
,写的非常清楚了,我在这里就不重复了,一定要进去学会它.

TIPS:
这个字典树总是让我想到哈夫曼树,实际上是不一样的,哈弗曼树保存的是一行二进制代码对应的字符,字典树则是保存一串字符.

这里他讲完字典树就要直接让你把页表项迁移过去,这个实在是很难从他那几句话理解:

事实上 SV39 分页机制等价于一颗字典树。 27 位的虚拟页号可以看成一个长度 n=3 的字符串,字符集为 α={0,1,2,...,511} ,因为每一位字符都由 9 个比特组成。而我们也不再维护所谓字符串的计数,而是要找到字符串(虚拟页号)对应的页表项。因此,每个叶节点都需要保存 512 个 8 字节的页表项,一共正好 4KiB ,可以直接放在一个物理页帧内。而对于非叶节点来说,从功能上它只需要保存 512 个指向下级节点的指针即可,不过我们就像叶节点那样也保存 512 个页表项,这样每个节点都可以被放在一个物理页帧内,节点的位置可以用它所在物理页帧的物理页号来代替。当想从一个非叶节点向下走时,只需找到当前字符对应的页表项的物理页号字段,它就指向了下一级节点的位置,这样非叶节点中转的功能也就实现了。每个节点的内部是一个线性表,也就是将这个节点起始物理地址加上字符对应的偏移量就找到了指向下一级节点的页表项(对于非叶节点)或是能够直接用来地址转换的页表项(对于叶节点)。

我在这里画了一张图,我们通过这张图来理解,这里把虚拟内存进行分解,把前边27位的页表号给分成3个9位,那每一位能够表述的范围就是0~511一共512种.

那么我们就可以把每一步的
节点的前缀
看成这个9bit的数,那么下一级又是9bit,因此
Root
节点(一级页表)下有512种变化,那么
Node
节点(二级页表)下也有512种变化,那么
Leaf
节点下对应的就是512种
页表项
.

这里是以
0x000 0001
为例的一个表示三级页表的字典树.

通过查页表项中的
PNN
自然可以访问到
物理内存
.

总结下来,查询的顺序是这样的:

这里考虑到一个非常难想到的地方,就是
页表项本身也存在物理内存
里.

那么考虑叶子节点对应的页表项有512个,每个页表项有
8byte
,于是刚好占用了
4KiB
.

这里会想起我们当时设置的每个页面的大小为
4KiB
,那么每个节点刚好占据一个物理页面.

大页

大页的是拓展部分,需要看
SV39 多级页表的硬件机制 - rCore-Tutorial-Book-v3 3.6.0-alpha.1 文档
,这里不多纠结,因为这里和具体实现代码关系不大,我没有什么自己的理解.

SV39多级页表的内存占用

这个部分也是直接看
SV39 多级页表的硬件机制 - rCore-Tutorial-Book-v3 3.6.0-alpha.1 文档
.

这里比较难理解的部分就在于为什么突然他就开始除以
2MiB
,
1GiB
.

这个
2MiB
是这么计算的,三级页表每个节点下边有512个
页表项
,那么一个页表项是可以分配
4KiB
的内存的,
512*4KiB=2MiB
.他的意思是平均下来你每使用
2MiB
空间就需要创建一个三级节点.

同样地,平均分配
1GiB
空间就需要创建一个二级节点.

这里还有一个重点,就是页表项(节点)的消耗为
8Byte
,这和一个页表项能够分配的
4KiB
的内存是不同的,不要搞混了.

SV39地址转换过程

查页表的原理我们之前已经讲了,就是一级一级使用9bit的数据去查三级字典树.

对于 RISC-V的查页表过程还需要讲一下具体操作:

假设我们有虚拟地址
(VPN0,VPN1,VPN2,offset)

  1. 我们首先会记录装载「当前所用的一级页表的物理页」的页号到
    satp
    寄存器中;

  2. VPN0
    作为偏移在一级页表的物理页中找到二级页表的物理页号;

  3. VPN1
    作为偏移在二级页表的物理页中找到三级页表的物理页号;

  4. VPN2
    作为偏移在三级页表的物理页中找到要访问位置的物理页号;
  5. 物理页号对应的物理页基址(即物理页号左移12位)加上
    offset
    就是虚拟地址对应的物理地址。

快表(TLB)

这里参考手册里的描述已经很好了,总结就是利用
TLB
的对映射进行缓存,这样就可以增加转换速度.

我们知道,物理内存的访问速度要比 CPU 的运行速度慢很多。如果我们按照页表机制循规蹈矩的一步步走,将一个虚拟地址转化为物理地址需要访问 3 次物理内存,得到物理地址后还需要再访问一次物理内存,才能完成访存。这无疑很大程度上降低了系统执行效率。
实践表明绝大部分应用程序的虚拟地址访问过程具有时间局部性和空间局部性的特点。因此,在 CPU 内部,我们使用MMU中的
快表(TLB, Translation Lookaside Buffer)
来作为虚拟页号到物理页号的映射的页表缓存。这部分知识在计算机组成原理课程中有所体现,当我们要进行一个地址转换时,会有很大可能对应的地址映射在近期已被完成过,所以我们可以先到 TLB 缓存里面去查一下,如果有的话我们就可以直接完成映射,而不用访问那么多次内存了。

多任务页表

上边进行描述的时候也讲求了:

  1. 有关于要在访问的时候要先把当前的
    一级页号
    存入
    satp
  2. 快表是通过

那么不同的APP的
页表不同
,那么首先要改变
一级页号
,也就是要修改
satp
.

快表中的缓存也需要更新,因此需要使用
sfence.vma
指令来清空整个
TLB
.