arts-20210320

Algorithm

• 题目: 优美的排列
• 分析
  1. 优美的排列是一种特殊的排列，需要计算出全排列，然后看某个排列是否符合优美的定义，可以用“回溯“来解决
  2. 根据 labuladong 这篇文章给出的回溯算法框架，只需要确定两个动作就可以
     1. 选择：将当前遍历的节点加入到路径中，即当某个数字 n 在位置 i 上符合”优美“的定义时，将其加入到选择列表中
     2. 取消选择：将当前遍历的节点从选择路径中去掉，进行下一次尝试
• 解法：
  1. 维护以下几个变量进行回溯递归
     • n 排列长度
     • selected 数组，保存已经选择的数字
     • ls 已选择的元素个数
     • result 保存计数结果
  2. 当 ls 长度和 n 相等时，结束递归，返回 count
• 代码

class Solution {
    public static int countArrangement(int n) {
        int []selected = new int[n];
        int ls = 0;
        Result result = new Result();

        backtrace(selected, ls, n, result);
        return result.count;
    }

    public static void backtrace(int[] selected, int ls, int n, Result result) {
        if (ls == selected.length) {
            result.count += 1;
            return;
        }
        for (int j = 1; j <= n; j++) {
            if (contains(selected, j) || !isPerfect(ls + 1, j)) {
                continue;
            }
            // select
            selected[ls] = j;
            backtrace(selected, ls + 1, n, result);

            // unselect
            selected[ls] = 0;
        }
    }

    private static boolean contains(int[] selected, int j) {
        for (int s: selected) {
            if (s == j) {
                return true;
            }
        }
        return false;
    }

    static boolean isPerfect(int i, int n) {
        return i % n == 0 || n % i == 0;
    }

    public static class Result {
        public int count = 0;
    }
}

• 一点优化
  • motivation
    1. 每次回溯时都需要遍历所有的数字，这些数子中部分已经在 selected 数组里了，这部分明显是不符合要求的，因为排列不允许有重复数字
    2. 每次判断当前数字是否已经被选过了，需要自己实现一个数组的 contains 方法，时间复杂度为 O(N)，这个操作比较费时
  • solution
    1. 额外维护一个 candidates 数组，来实时维护有哪些元素是备选
    2. 额外维护一个 lc 变量，表示数组实际长度
    3. 当一个元素从 candidates 中被选走时，将其和数组中最后一个元素交换，并将 lc -1
    4. 当回溯结束后，需要取消选择时，再执行一次 swap 操作，原来的元素就被换回来了
  • 代码如下，从 leetcode 的结果来看，耗时从 235ms 减小到 48ms，说明优化有效

class Solution {

    public static int countArrangement(int n) {
        int []selected = new int[n];
        int ls = 0;

        int []candidates = new int[n];
        for (int i = 0; i < n; i++) {
            candidates[i] = i + 1;
        }

        Result result = new Result();

        backtrace(1, result, selected, ls, candidates, n);
        return result.count;
    }

    public static void backtrace(int index, Result result, int[] selected, int ls, int[] candidates,
        int lc) {
        if (ls == selected.length) {
            result.count += 1;
            return;
        }
        for (int i = 0; i < lc; i++) {
            if (isNotPerfect(index, candidates[i])) {
                continue;
            }

            selected[ls] = candidates[i];
            swap(candidates, i, lc - 1);

            backtrace(index + 1, result, selected, ls + 1, candidates, lc - 1);

            swap(candidates, i, lc - 1);
        }
    }

    private static void swap(int[] candidates, int i, int j) {
        int tmp = candidates[j];
        candidates[j] = candidates[i];
        candidates[i] = tmp;
    }

    static boolean isNotPerfect(int i, int n) {
        return i % n != 0 && n % i != 0;
    }

    public static class Result {
        public int count = 0;
    }
}

Review

• 原文地址： Improving histogram usability for Prometheus and Grafana
• 本文介绍了 Prometheus 原生的 Histogram 存在的 3 个问题，进而介绍了 VictoriaMetrics 为此所做的努力，以及 Histogram 的几种场景
  1. Prometheus Histogram 的问题
     1. bucket 范围无法很好地适应实际的数据分布，原因在于业务迭代时数据点分布可能会发生变化，会导致需要一直调整 bucket range，难以维护
     2. bucket 数量过多导致时间序列基数过大，导致一系列问题，包括内存占用增长、磁盘占用增长、插入效率降低、查询效率降低
     3. 对于同一个 metric，如果两个 TS bucket range 不一致，则这两个 TS 无法进行聚合查询
  2. VictoriaMetrics 的解法
     1. sdk 内置 bucket range 和数量，避免使用者设置的复杂性
     2. 只暴露 bucket 中元素不为 0 的 bucket 给 prometheus，从而减少时间序列数量
  3. 介绍了将 gauge 用 histogram 函数来计算分布，通过 Grafana Heatmap 来可视化的场景，比如进程内存使用量，来了解组织所有服务内存使用分布情况

Tips

1. Prometheus Blackbox Exporter 适合做拨测，主要原理是提供一个 target 和探测方式，将探测结果生成指标，因此有几个点需要注意
   1. 只有 blackbox exporter 没办法直接生成观测工具，需要配合 prometheus 或 vmagent 使用
   2. 探测方式和探测地址均由参数指定，需要配合 relabel 配置来保证 label 的正确性
2. 设计系统前，先明确问题的规模、场景，调研后需要做可行性验证
   1. 设计目标要能量化，除了明确解决什么问题，明确解决到什么程度也必不可少

Share

todo