不仅仅是洗牌算法

问题

某天测试同事给某已离职的同事提了个问题单,在特定数据下,饼图的标签存在重叠且超出部分无法正常展示,大致效果如下:

pie-sorted.svg

// 数据借用自 <https://zhuanlan.zhihu.com/p/272710806>
const dataSource = [
  {
    name: '充值失败',
    value: 192
  },
  {
    name: '频繁停电',
    value: 10
  },
  {
    name: '低电压',
    value: 0
  },
  {
    name: '错发短信',
    value: 6
  },
  {
    name: '办理用电',
    value: 3
  },
  {
    name: '电费电价',
    value: 2
  },
  {
    name: '其他',
    value: 49
  }
];

const option = {
  series: [
    {
      type: 'pie',
      radius: '50%',
      center: ['50%', '50%'],
      avoidLabelOverlap: true,
      data: dataSource.sort((a, b) => a.value - b.value),
      label: {
        position: 'outside',
        alignTo: 'none',
        bleedMargin: 5,
        show: true,
        formatter: `{b}\n数量:{c}\n占比:{d}%`
      }
    }
  ]
};

该饼图使用 echarts 实现,启用 avoidLabelOverlap 配置项后,echarts 会在标签拥挤重叠的情况下会挪动各个标签的位置,防止标签间的重叠。但是很不幸,仍然出现了重叠问题,只能从其他角度解决问题,比如——修改饼图数据显示顺序。

洗牌算法

产生标签重叠的主要原因是数据分布不均匀,如果数据按从小到大顺序排列,大量占比小的数据重叠现象尤其明显。那我们把数据打乱是不是就可以避免这个问题呢?

祭出我们的洗牌算法:

/**
 * 一个简易的 Fisher–Yates 洗牌算法实现
 */
function shuffle<T>(array: T[] = []): T[] {
  let copy = Array.from(array);
  let count = copy.length;
  let randomIndex, currentIndex, temp;

  while (count > 0) {
    // 从剩余元素中随机选取一个元素
    randomIndex = Math.floor(Math.random() * count);
    currentIndex = count - 1;

    // 交换元素
    temp = copy[currentIndex];
    copy[currentIndex] = copy[randomIndex];
    copy[randomIndex] = temp;

    count--;
  }

  return copy;
}

看上去很完美地解决了数据均匀分布的问题。但是重复试验 N 次后,打乱的数据中竟然有一次是有序的!于是不得不重新评估洗牌算法,洗牌算法虽然每次都是随机取元素进行排列,但存在最坏情况,即恰好洗出有序的结果。和排序算法做对比,相当于使用猴子排序排出了有序结果。

不仅仅是洗牌算法

除了洗牌算法,还有其他算法可以解决这个问题吗?让我们从生活经验中找找灵感。

分班算法

上学的时候,老师按分数将一批学生分到两个班,第1名分到1班,第2名分到2班;为了平衡1班和2班分数差距,第3名分到2班,第4名分到1班;第5名分到1班,第6名分到2班,依此类推。实际操作中,这种分班算法也存在公平性争议(超出讨论范围)。

接下来实现这个分班算法,实现一个函数,可以把有序数组 [1,2,3,4,5,6,7,8,9] 处理成 [1,4,5,8,9,7,6,3,2],其中小数在两头,大数在中间。

/**
 * 对有序数组进行重排,使得小数在两头,大数在中间
 * [1,2,3,4,5,6,7,8,9] -> [1,4,5,8,9,7,6,3,2]
 */
function shuffle<T>(array: T[] = []): T[]{
  // n, n+3, n+4, n+7, n+8, ...
  //    n+1, n+2, n+5, n+6, ...
  let left: T[] = [];
  let right: T[] = [];
  let index = 0;
  let isRight = false;
  while (index < array.length) {
    if (index === 0) {
      left.push(array[index]);
      index++;
      isRight = !isRight;
    } else {
      isRight ? right.unshift(array[index]) : left.push(array[index]);
      index++;
      if (index < array.length) {
        isRight ? right.unshift(array[index]) : left.push(array[index]);
        index++;
        isRight = !isRight;
      }
    }
  }

  return left.concat(right);
}

对这段代码进行优化:

  1. 能用数组的 length 属性解决的,坚决不额外声明新的变量 index
  2. isRight 转换成取模运算
/**
 * 对有序数组进行重排,使得小数在两头,大数在中间
 * [1,2,3,4,5,6,7,8,9] -> [1,4,5,8,9,7,6,3,2]
 */
function shuffle<T>(array: T[] = []): T[]{
  const copy = Array.from(array);
  const left: T[] = [];
  const right: T[] = [];

  while (copy.length > 0) {
    const item = copy.shift() as T;
    if (left.length < right.length) {
      left.push(item);
    } else if (left.length > right.length) {
      right.unshift(item);
    } else {
      // 0, 0  left
      // 1, 0  right
      // 1, 1  right
      // 1, 2  left
      if (left.length % 2 === 0) {
        left.push(item);
      } else {
        right.unshift(item);
      }
    }
  }

  return left.concat(right);
}

再对 if 条件进行合并:

/**
 * 对有序数组进行重排,使得小数在两头,大数在中间
 * [1,2,3,4,5,6,7,8,9] -> [1,4,5,8,9,7,6,3,2]
 */
function shuffle<T>(array: T[] = []): T[] {
  const copy = Array.from(array);
  const left: T[] = [];
  const right: T[] = [];

  while (copy.length > 0) {
    const item = copy.shift() as T;
    if (
      (left.length === right.length && left.length % 2 === 0) ||
      left.length < right.length
    ) {
      left.push(item);
    } else {
      right.unshift(item);
    }
  }

  return left.concat(right);
}

使用新算法后的饼图渲染效果:

pie-shuffled.svg

数据按从小到大顺序均匀分到了左右两侧。

“一对一帮扶”算法

还是从给我们传道授业解惑的老师那儿学到的方法。既然不希望大量小数据集中在一起,那就采取“一对一帮扶”,一个小数搭配一个大数。

实现一个函数,可以把有序数组 [1,2,3,4,5,6,7,8,9] 处理成 [1,9,2,8,3,7,4,6,5]

/**
 * 对有序数组进行重排,一个小数搭配一个大数
 * [1,2,3,4,5,6,7,8,9] -> [1,9,2,8,3,7,4,6,5]
 */
function shuffle<T>(array: T[] = []): T[] {
  const copy = Array.from(array);
  const dist: T[] = [];
  while (copy.length > 0) {
    const leftItem = copy.shift() as T;
    dist.push(leftItem);
    if (copy.length > 0) {
      const rightItem = copy.pop() as T;
      dist.push(rightItem);
    }
  }
  return dist;
}

使用新算法后的饼图渲染效果:

pie-reordered.svg

思考

本文问题的核心在于根据一定规则将一组数据转换成另一组数据。这个规则可以是有序转无序,比如洗牌算法,也可以是无序转有序,比如各种排序算法。对于有序数据,除了常见的按从小到大顺序排列,还可以是符合各种分布函数的排序方式,比如标准正态分布,也可以是符合各种函数曲线的排序方式。

相关链接