# FAST Kit简介

FAST Kit（算法加速服务）以理论计算机为基础、面向开发者提供算法加速能力。当前开放线段表、矩形划分求解器、数字信号处理（DSP）、数理预测与系统性能优化接口，支撑应用的开发体验和用户体验提升。

当前FAST Kit包括以下功能域：

* 高阶数据结构（Advanced Data Structure）加速功能域旨在融合理论计算机科学中具有理论保证的高级数据结构与现代硬件特性，当前提供[线段表数据结构](https://developer.huawei.com/consumer/cn/doc/harmonyos-guides/fast-segment-map)，[并发哈希表数据结构](https://developer.huawei.com/consumer/cn/doc/harmonyos-guides/fast-concurrent-hashmap)。

* 规划求解（Solver）加速功能域旨在将理论计算机科学与运筹学中的优化求解能力运用到鸿蒙生态中的各类场景，当前提供[矩形划分求解器](https://developer.huawei.com/consumer/cn/doc/harmonyos-guides/fast-rect-partition)、[多项式零点求解器](https://developer.huawei.com/consumer/cn/doc/harmonyos-guides/fast-polynomial-root)。

* 数字信号处理（Digital Signal Processing）加速功能域旨在提供高性能的向量运算、FFT变换及二阶IIR滤波器能力，当前提供[向量运算](https://developer.huawei.com/consumer/cn/doc/harmonyos-guides/fast-dsp-vector-calculation)，[FFT变换](https://developer.huawei.com/consumer/cn/doc/harmonyos-guides/fast-dsp-transform)，[二阶IIR滤波](https://developer.huawei.com/consumer/cn/doc/harmonyos-guides/fast-dsp-iir-filter)。

* 容器（Collections）加速功能域旨在提供高性能的容器数据结构，当前提供[哈希表数据结构](https://developer.huawei.com/consumer/cn/doc/harmonyos-guides/fast-hashmap)。

* 算法（Algorithm）加速功能域旨在提供高性能的通用算法，当前提供[通用排序算法](https://developer.huawei.com/consumer/cn/doc/harmonyos-guides/fast-algorithm)，支持任意数据类型的完整排序、部分排序以及自然语言字符串排序。

* 数理预测（Math Prediction）加速功能域旨在提供基于历史采样数据的预测能力，当前提供[智能序列预测](https://developer.huawei.com/consumer/cn/doc/harmonyos-guides/fast-math-prediction)。

* 系统性能优化（Scheduling Optimization）加速功能域旨在允许应用程序向系统提供性能场景信息，系统据此在API生效范围内尽可能优化应用性能，以提升用户体验，当前提供[系统性能优化接口（ArkTS）](https://developer.huawei.com/consumer/cn/doc/harmonyos-guides/fast-scheduling-optimization_arkts)和[系统性能优化接口（C/C++）](https://developer.huawei.com/consumer/cn/doc/harmonyos-guides/fast-scheduling-optimization_c)。

## 场景介绍

FAST Kit基于理论计算机科学，通过理论算法优化，为应用的性能、负载与功耗优化提供算法加速能力支持，当前Kit提供"高阶数据结构-线段表"，"规划求解-矩形划分求解器"，"规划求解-多项式零点求解器"，"高阶数据结构-并发哈希表"，"数字信号处理"和"数理预测-智能序列预测"，具体如下：

* 线段表：是一种用于高效处理区间段信息的数据结构，支持数据序列区间段的快速更新和快速查询。以下是一些典型使用场景：

  * 数据可视化：股票K线图中快速响应用户对于标记特定价格或时间区间的请求；甘特图/时间轴渲染中高效渲染大量任务的时间区间等。
  * 资源监控与日志分析：在APP性能监控中记录卡顿或异常发生的时间区间，聚合分析高频问题时段；统计用户在特定页面停留的连续时间区间、分析行为模式等。
  * 游戏开发：管理游戏中多个持续生效的技能或状态，检查是否重叠或冲突；将物体在轴上的投影作为区间，快速筛选可能碰撞的对象等。
* 矩形划分求解器：用于解决矩形划分问题，其接收若干个彼此不相交的矩形作为输入，计算出覆盖相同区域的矩形划分方案，并使输出的矩形数量尽可能少。以下是一些典型使用场景：

  * UI渲染与布局优化：多个相邻UI控件背景合并为更少的绘制区域，减少GPU绘制调用；合并虚拟列表中相邻项的渲染区域，减少DOM元素或View数量等。
  * 游戏开发：合并相邻的地形或可通行区域，优化碰撞检测；合并相邻的光照影响区域，简化光照计算等。
  * 文档与表格处理：表格应用中，自动合并相邻的相同格式单元格；用户选择的多个文本标注区域自动合并为连续区域等。
* 多项式零点求解器：用于计算一元多项式的实根。以下是一些典型使用场景：

  * 计算机辅助设计：求解曲线、曲面交点的参数方程根；几何约束求解中的多项式方程求根等。
  * 信号处理：数字滤波器设计中的特征多项式求根；系统稳定性分析中计算特征根等。
  * 控制理论：控制系统传递函数的极点计算；根轨迹分析中求解特征方程等。
  * 科学计算：数值分析中的插值与逼近问题；物理学中的运动方程求解等。
* 并发哈希表：是一种专为高并发场景设计的数据结构，支持在多线程环境下安全、高效地进行键值对的插入、删除与查找操作。以下是一些典型使用场景：

  * 分布式系统与中间件：在分布式缓存集群中管理海量键值数据，支持多节点同时读写；消息队列中维护消费者偏移量或会话状态，保证并发更新的一致性。
  * 实时缓存与数据库：高频交易系统中缓存行情数据或用户会话，支持毫秒级并发存取；数据库连接池或查询缓存中快速路由与共享资源，避免锁竞争。
  * 网络与网关服务：API网关或负载均衡器中记录IP限流计数、实时更新路由策略；Web服务器管理并发用户会话，快速定位并维持状态信息。
* 数字信号处理：提供高性能的向量运算、FFT计算与二阶IIR滤波器能力，支持单精度和双精度算术运算。以下是一些典型使用场景：

  * 快速傅里叶变换：频谱分析、频域滤波、信号重构、音频处理、振动分析等。
  * 音频信号处理：音频降噪、均衡器（EQ）、低通/高通/带通滤波、多通道音频处理等。
  * 传感器数据分析：加速度计、陀螺仪等传感器数据的滤波与特征提取；实时信号峰值检测与统计计算等。
  * 通信与信号分析：复数信号格式转换（交错/分离格式）、向量点积运算、信号能量计算等。
* 通用和自然语言排序：提供高性能的通用排序算法，支持任意数据类型的完整排序、部分排序以及自然语言字符串排序。以下是一些典型使用场景：

  * 数据预处理：对数值、浮点数等基础类型数据进行排序，为后续二分查找等操作做准备；对自定义类型按特定字段排序等。
  * Top-K问题：快速获取数组中最大或最小的K个元素，无需完全排序；中位数查找；分位数计算等。
  * 文件列表排序：按自然顺序排序文件名（如file1.txt, file2.txt, file10.txt）；版本号字符串排序（如v1.0, v1.10, v2.0）等。
  * 多语言文本排序：支持UTF-8编码的多语言文本自然排序；带编号资源排序（如img1, img2, img10）等。
  * 机器学习推理：特征向量计算、向量归一化、统计特征提取等预处理操作。
* 智能序列预测：基于历史采样数据，利用FAST Kit内置算法预测下一个时刻的序列值。以下是一些典型使用场景：

  * 手势跟踪：根据历史触摸点的位置和时间，预测下一帧触摸点的索引位置，减少触摸跟随延迟。
  * 动画曲线预测：基于动画曲线已有的关键帧索引-时间采样，预测后续帧的索引变化趋势，实现更平滑的动画过渡。
  * 运动轨迹预估：在游戏或交互应用中，根据物体的历史运动轨迹采样，预测其后续位置，提升响应速度。
  * 滚动惯性预测：在列表滚动场景中，根据历史滚动偏移量采样，预测减速阶段的最终停止位置。
* 哈希表：是一种高性能的键值对数据结构，支持插入、删除与查找操作，适用单线程场景优化设计。以下是一些典型使用场景：

  * 应用启动与初始化：APP启动时快速构建配置索引表，加速资源加载与初始化流程；预加载常用数据到内存哈希表，减少后续查询延迟等。
  * 缓存与状态管理：本地缓存系统中存储用户偏好设置、会话令牌等键值数据；游戏或应用中维护玩家状态、物品属性等实时数据的快速访问等。
  * 索引与查找优化：文档编辑器中建立关键词到位置的索引，实现快速定位与高亮；内容管理系统中构建标签到文章的映射，支持快速检索与分类等。
  * 去重与计数：日志分析系统中统计特定事件的occurrence次数；网络应用中维护已处理请求的ID集合，防止重复处理；数据清洗中快速识别并过滤重复记录等。
  * 配置与元数据管理：微服务架构中缓存服务注册信息与路由配置；应用运行时动态加载的配置参数快速读取与更新等。
* 系统性能优化：允许应用程序向系统提供性能场景信息，系统据此在API生效范围内尽可能优化应用性能，以提升用户体验。以下是一些典型使用场景：

  * 应用启动优化：在应用启动关键阶段，通过perfHint接口提示系统尽可能加速应用启动流程。
  * 页面切换优化：在页面切换过程中，通过perfHint接口提示系统尽可能减少页面切换卡顿。
  * 页面加载优化：在页面加载过程中，通过perfHint接口提示系统尽可能提升页面加载速度。
  * 网络文件处理优化：在网络文件处理场景中，通过perfHint接口提示系统尽可能加快网络文件处理速度。
  * 本地文件处理优化：在本地文件处理场景中，通过perfHint接口提示系统尽可能加快本地文件处理速度。
  * 页面绘制优化：在页面绘制场景中，通过perfHint接口提示系统尽可能提升页面绘制流畅度。
  * 动画播放优化：在动画播放场景中，通过perfHint接口提示系统尽可能确保动画流畅播放。
  * 媒体播放优化：在媒体播放场景中，通过perfHint接口提示系统尽可能提升播放流畅度。
  * 媒体编解码优化：在音视频编解码处理场景中，通过perfHint接口提示系统尽可能提升处理效率。

## 基本概念

不透明配置（Opaque Configuration）：一种ABI稳定的配置抽象机制，库以不完整类型（Incomplete Type）前向声明配置对象，外部代码仅通过指向该对象的指针句柄进行传递与操作，而对象的大小、字段布局及解释规则完全由库内部定义，从而将实现细节与调用者彻底隔离，并保证后续版本可在不破坏二进制兼容性的前提下任意变更存储格式与语义。

## 约束与限制

### 支持的国家和地区

当前仅支持中国境内（香港特别行政区、澳门特别行政区、中国台湾除外）。

### 支持的设备

|FAST Kit提供的能力|支持的设备类型|
|:----------------------------------------------------------------------------------------------------------------|:-------------------------------|
|[线段表数据结构](https://developer.huawei.com/consumer/cn/doc/harmonyos-guides/fast-segment-map)|Phone、Tablet、PC/2in1|
|[并发哈希表数据结构](https://developer.huawei.com/consumer/cn/doc/harmonyos-guides/fast-concurrent-hashmap)|Phone、Tablet、PC/2in1|
|[矩形划分求解器](https://developer.huawei.com/consumer/cn/doc/harmonyos-guides/fast-rect-partition)|Phone、Tablet、PC/2in1|
|[多项式零点求解器](https://developer.huawei.com/consumer/cn/doc/harmonyos-guides/fast-polynomial-root)|Phone、Tablet、PC/2in1|
|[向量运算](https://developer.huawei.com/consumer/cn/doc/harmonyos-guides/fast-dsp-vector-calculation)|Phone、Tablet、PC/2in1|
|[FFT变换](https://developer.huawei.com/consumer/cn/doc/harmonyos-guides/fast-dsp-transform)|Phone、Tablet、PC/2in1|
|[二阶IIR滤波](https://developer.huawei.com/consumer/cn/doc/harmonyos-guides/fast-dsp-iir-filter)|Phone、Tablet、PC/2in1|
|[哈希表数据结构](https://developer.huawei.com/consumer/cn/doc/harmonyos-guides/fast-hashmap)|Phone、Tablet、PC/2in1|
|[通用排序算法](https://developer.huawei.com/consumer/cn/doc/harmonyos-guides/fast-algorithm)|Phone、Tablet、PC/2in1|
|[智能序列预测](https://developer.huawei.com/consumer/cn/doc/harmonyos-guides/fast-math-prediction)|Phone、Tablet、PC/2in1|
|[系统性能优化（ArkTS）](https://developer.huawei.com/consumer/cn/doc/harmonyos-guides/fast-scheduling-optimization_arkts)|Phone、Tablet、PC/2in1、Wearable、TV|
|[系统性能优化（C/C++）](https://developer.huawei.com/consumer/cn/doc/harmonyos-guides/fast-scheduling-optimization_c)|Phone、Tablet、PC/2in1、Wearable、TV|

## 模拟器支持情况

本Kit支持模拟器。

模拟器与真机存在通用差异，详情请参见"[模拟器与真机的差异](https://developer.huawei.com/consumer/cn/doc/harmonyos-guides/ide-emulator-specification#section1227613205203)"。