1. 首页
  2. 文章
知点技术

高效计算 TP99 的方法：从排序到优化

zhidiantech · · 66 次点击 · · 开始浏览    

在高性能计算和大数据处理中，TP99（第99百分位响应时间）常被用来衡量系统的稳定性和性能表现。本文将介绍几种计算TP99的常用方法，并讨论如何对算法进行优化，以提高计算效率。

1. 什么是 TP99？

TP99 是第99百分位响应时间，表示排在前99%的请求时间。在实际应用中，它用于衡量系统在高负载下的稳定性。换句话说，TP99 计算的是一组数据中排在第99%的那个值。

2. 使用排序算法计算 TP99

最直接的方法是将数据集进行排序，然后选择位于第 99% 处的元素。

示例代码

import java.util.List;
import java.util.stream.Collectors;

public class PercentileCalculator {

    /**
     * 计算百分位
     *
     * @param percent 百分比值
     * @param datas 数据列表
     * @return 百分位数值
     */
    public Double percent(double percent, List<DataQueryModel> datas) {
        if (datas.isEmpty()) {
            return 0.0;
        }
        List<Double> sortedData = datas.stream()
            .map(dataQueryModel -> dataQueryModel.getValue() != null ? dataQueryModel.getValue() : 0.0)
            .sorted()
            .collect(Collectors.toList());

        return sortedData.get((int) Math.floor(sortedData.size() * percent));
    }

    // 假设 DataQueryModel 是以下形式：
    public static class DataQueryModel {
        private Double value;

        public Double getValue() {
            return value;
        }

        public void setValue(Double value) {
            this.value = value;
        }
    }
}

这种方法的时间复杂度为 O(n log n)，因为需要对整个数据集进行排序。这在数据量较大时效率并不高。

3. 使用堆（Heap）优化

使用最小堆可以有效降低时间复杂度。在这里，我们使用一个大小为 k（即 n * 0.99）的最小堆来只保留最大的 k 个元素。堆顶元素即为第 k 大的元素。

示例代码

import java.util.PriorityQueue;
import java.util.List;

public class TP99WithHeap {

    /**
     * 计算第k分位
     *
     * @param data 数据集
     * @param k 将数据集分成k个部分
     * @return 数据集中第k大的元素
     */
    public static double findKthLargest(List<Double> data, int k) {
        PriorityQueue<Double> minHeap = new PriorityQueue<>(k);

        for (double num : data) {
            minHeap.offer(num);  // 将元素插入最小堆
            if (minHeap.size() > k) {
                minHeap.poll();   // 移除堆顶元素，保持堆大小不超过k
            }
        }

        return minHeap.peek();  // 返回堆顶元素，即第k大的元素
    }
}

优点

  • 时间复杂度：O(n log k)，显著优于全排序。
  • 空间复杂度：O(k)，仅需存储 k 个元素。

4. 使用 QuickSelect 优化

QuickSelect 是一种选择算法，用于查找未排序数组中的第 k 小元素。它的平均时间复杂度为 O(n)，比排序方法更加高效。

示例代码

import java.util.List;
import java.util.Arrays;
import java.util.Random;

public class QuickSelect {

    private static final Random random = new Random();

    /**
     * 找到第 k 大的元素
     *
     * @param data 数据列表
     * @param k    第 k 大的排名
     * @return 第 k 大的元素
     */
    public static double findKthLargest(List<Double> data, int k) {
        int n = data.size();
        return quickSelect(data, 0, n - 1, n - k);
    }

    /**
     * QuickSelect 主函数
     */
    private static double quickSelect(List<Double> data, int left, int right, int k) {
        if (left == right) {
            return data.get(left);
        }

        // 选择一个随机基准元素并进行分区
        int pivotIndex = partition(data, left, right);

        // 基准元素的索引与 k 相比较
        if (k == pivotIndex) {
            return data.get(k);
        } else if (k < pivotIndex) {
            return quickSelect(data, left, pivotIndex - 1, k);
        } else {
            return quickSelect(data, pivotIndex + 1, right, k);
        }
    }

    /**
     * 分区函数
     */
    private static int partition(List<Double> data, int left, int right) {
        double pivot = data.get(right);
        int i = left;
        for (int j = left; j < right; j++) {
            if (data.get(j) <= pivot) {
                swap(data, i, j);
                i++;
            }
        }
        swap(data, i, right);
        return i;
    }

    /**
     * 交换列表中的两个元素
     */
    private static void swap(List<Double> data, int i, int j) {
        double temp = data.get(i);
        data.set(i, data.get(j));
        data.set(j, temp);
    }
}

优点

  • 时间复杂度：平均 O(n)，最坏情况下 O(n^2)，但通过随机选择基准元素可以很好地避免最坏情况。
  • 空间复杂度：O(1)，原地算法。

5. 使用平衡二叉树（如 TreeMap）计算 TP99

使用 TreeMap 或其他平衡二叉树结构，可以在进行插入和删除操作时保证所有元素有序，并通过维护元素的个数来实现高效的百分位计算。

示例代码

import java.util.TreeMap;
import java.util.Map;
import java.util.List;

public class TP99WithTreeMap {

    /**
     * 计算第k分位
     *
     * @param data 数据集
     * @param k 将数据集分成k个部分
     * @return 数据集中第k大的元素
     */
    public static double findKthLargest(List<Double> data, int k) {
        TreeMap<Double, Integer> map = new TreeMap<>();
        
        for (double num : data) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        int targetRank = (int) Math.ceil(data.size() * (k / 100.0));
        int currentSum = 0;
        double tp99 = 0.0;

        for (Map.Entry<Double, Integer> entry : map.entrySet()) {
            currentSum += entry.getValue();
            if (currentSum >= targetRank) {
                tp99 = entry.getKey();
                break;
            }
        }

        return tp99;
    }
}

优点

  • 有序性：平衡二叉树自动维护元素的有序性，方便查找和计算。
  • 操作效率：插入、删除和查找操作的时间复杂度均为 O(log n)。

6. 使用 T-Digest 计算 TP99

T-Digest 是一种高效的数据结构，用于汇总和近似统计大规模数据集的百分位数。它特别适合处理稀疏数据和大数据集。

优点

  • 高效处理大规模数据：适合处理大规模数据集，尤其是实时数据流。
  • 低内存占用：使用压缩数据结构，内存使用率低。
  • 精度高：特别对于尾部百分位（如 TP99, TP99.9）有更高的计算精度。
  • 可合并：多个 T-Digest 实例可以合并，非常适合分布式系统。

示例代码

首先，我们需要在项目中引入 T-Digest 库。

<dependency>
    <groupId>com.tdunning</groupId>
    <artifactId>t-digest</artifactId>
    <version>3.2</version>
</dependency>


import com.tdunning.math.stats.TDigest;

import java.util.ArrayList;
import java.util.List;

public class TP99UsingTDigest {

    public static void main(String[] args) {
        // 假设这是我们的数据集
        List<Double> data = generateDataSet(100000);

        // 创建 T-Digest 实例，推荐使用默认的 delta 值
        TDigest tDigest = TDigest.createDigest(100);

        // 将数据添加到 T-Digest 中
        for (double value : data) {
            tDigest.add(value);
        }

        // 计算 TP99
        double tp99 = tDigest.quantile(0.99);

        System.out.println("TP99: " + tp99);
    }

    /**
     * 生成一个示例数据集
     *
     * @param size 数据集大小
     * @return 数据集列表
     */
    private static List<Double> generateDataSet(int size) {
        List<Double> data = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            data.add(Math.random() * 1000);
        }
        return data;
    }
}

7. T-Digest、QuickSelect 和 Prometheus 分位线算法对比

T-Digest vs QuickSelect

优点和缺点

  • T-Digest：

    • 高效处理大规模数据
    • 内存占用低
    • 在分布式系统中表现良好
    • 精度高，对于尾部百分位表现尤佳
    • 实现复杂
    • 结果近似

  • QuickSelect：

    • 实现简单
    • 高效，平均时间复杂度O(n)
    • 结果精确
    • 最坏情况下时间复杂度O(n^2)
    • 内存使用较高

使用场景

  • T-Digest 适用于实时数据流、大规模数据处理和分布式系统。
  • QuickSelect 适用于需要快速、精确计算的小到中等规模数据集。

Prometheus 分位线算法 线性插值法

Prometheus 使用 Histogram 来计算分位数，通过统计落在每个桶（bucket）中的数据点数目进行估算。

假设我们有以下桶配置和计数：

桶边界	计数
0.1	     20
0.5	     50
1	    100
5	     50
10	     20
+Inf	10

桶边界计数

总计数：250

我们需要计算80百分位数（P80）。

计算 P80

  1. 计算总计数

    • 总计数：= 20 + 50 + 100 + 50 + 20 + 10 = 250

  2. 找到第80百分位数的目标位置

    • 目标位置：250 * 0.80 = 200

  3. 查找第80百分位数所在的桶

    • 通过累加计数来确定200落在哪个桶中：
      • 第1个桶：20
      • 第2个桶：20 + 50 = 70
      • 第3个桶：70 + 100 = 170
      • 第4个桶：170 + 50 = 220

第80百分位数落在第4个桶，即边界为 [1, 5) 的区间内。

使用线性插值法计算 P80

我们需要进行线性插值来确定第80百分位数在这个桶内的具体位置。

  • 桶下界：1
  • 桶上界：5
  • 累计到上一个桶的计数：170
  • 目标位置在桶内的相对位置：200 - 170 = 30
  • 桶内的总计数：50

计算桶中目标位置的相对位置比值 (Ratio)：

Ratio = (200 - 170) / 50 = 30 / 50 = 0.6

线性插值计算 P80：

P80 = 桶下界 + Ratio * 桶宽度 2 = 1 + 0.6 * (5 - 1) 3 = 1 + 0.6 * 4 4 = 1 + 2.4 5 = 3.4

所以，第80百分位数（P80）为 3.4。

优点和缺点

  • Prometheus Histogram Quantiles：
    • 实时计算，适用于及时监控
    • 实现方便
    • 资源消耗低
    • 精度受限于桶配置，结果近似
    • 需要仔细配置桶边界以适应数据分布

适用场景

  • Prometheus Histogram Quantiles 适用于实时监控和指标收集，适合轻量级的实时计算需求。
  • T-Digest 适合复杂数据分布、大数据量和分布式系统。
  • QuickSelect 适合需要精确结果的小到中等规模数据，在单机环境中实现。

总结

计算TP99可以有多种方法，从直接排序到使用堆和QuickSelect优化，再到平衡二叉树和T-Digest，不同方法适用于不同的应用场景。理解每种方法的优缺点和适用场景，可以帮助我们在实际应用中做出最佳选择，提高计算效率，节省资源成本。

66 次点击  
加入收藏 微博
赞
收入我的专栏
上一篇：解决 FPGA 在 BD Ring 上不搬运描述符的问题
下一篇：“翼”起向未来！天翼云亮相2024世界智能产业博览会！
  • java
  • prometheus
  • 代码
  • 二叉树
    0 回复
    暂无回复
    添加一条新回复 （您需要 登录 后才能回复 没有账号 ？）
    • 请尽量让自己的回复能够对别人有帮助
    • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
    • 支持 @ 本站用户；支持表情（输入 : 提示），见 Emoji cheat sheet
    • 图片支持拖拽、截图粘贴等方式上传

    用户登录

     今日阅读排行

      加载中

     一周阅读排行

      加载中