D3:什么是Bisector？

Question

我正在研究用D3制作图表,偶然发现了d3.bisector.但是,我不明白它是什么或从文档中做了什么.

我在Web上找到的几乎所有示例都使用Date数组,类似于官方文档中的示例:

var data = [
  {date: new Date(2011,  1, 1), value: 0.5},
  {date: new Date(2011,  2, 1), value: 0.6},
  {date: new Date(2011,  3, 1), value: 0.7},
  {date: new Date(2011,  4, 1), value: 0.8}
];

var bisect = d3.bisector(function(d) { return d.date; }).right;

那么,除了从数组元素中选择日期对象之外,平分线器还能做什么呢？什么的*.right回报呢？

如果我有一个简单的1维数组,它有用var data = [3, 6, 2, 7, 5, 4, 8]吗？

谢谢你的启发.

Answer 1

背后的基本理念bisect是:

考虑一下你提到的阵列 - var data = [3, 6, 2, 7, 5, 4, 8]

要插入一个新值让我们说3.5成data阵,想知道如何将这项"分区"吧.换句话说,您想知道3.5在data排序数组时它是否插入的索引是什么.

   var data = [3, 6, 2, 7, 5, 4, 8]

   //Sorted data

  [2, 3, 4, 5, 6, 7, 8]

  //You want to insert 3.5


  The sorted array after insertion of 3.5 should look something like:

  [2, 3, 3.5, 4, 5, 6, 7, 8]


  So the index of 3.5 in sorted data array is "2".

在某些情况下,您可能想知道该元素的插入如何"平分"或"划分"数组.在这种情况下,您可能希望首先对该数组进行排序,并执行我们称之为二进制搜索的操作,以找出插入该元素的正确位置.

bisectLeft并且bisectRight在您想要输入数组中已存在的元素的情况下,请注意澄清异常.假设您要3在阵列中输入另一个.有两种情况:

   3* -> The new element to be entered


   [2, 3*, 3, 4, 5, 6, 7, 8] -> entered at "1" (array is still sorted)


   [2, 3, 3*, 4, 5, 6, 7, 8] -> entered at "2" (array is still sorted)

因此,根据我们如何处理这种歧义,我们可以将该元素输入到现有元素的"左"或"右".从文档(标记重点):

返回的插入点i将数组分成两半,以便所有v < x表示左侧的array.slice(lo,i)中的v,对于array.slice(i,hi)中的v > = x表示v右边.

在bisectLeft我们得到1作为合适的索引时,所有重复的条目都将在该索引的右侧,而情况正好相反bisecRight.

现在你知道如何bisectLeft和bisectRight工作中,bisector只允许我们定义一个自定义comparator或accessor函数来分区之前的值或弄懂<和>在对象上也是如此.

所以这段代码:

  var bisect = d3.bisector(function(d) { return d.date; }).right;

  var bisect = d3.bisector(function(a, b) { return a.date - b.date; }).right;

只是指定使用该bisectRight选项并返回合适的索引以插入元素,假设数组已按顺序排列(按升序排列).

所以,如果我要建立你的例子并假设一个bisector名字bisect.你做了:

 bisect(data, 3); //it would return 2.

我希望它澄清事情,让你开始朝着正确的方向前进.

Answer 2

从文档（您已链接到）：

在数组中定位 x 的插入点以保持排序顺序。

这就是它的作用。它告诉你应该在哪里插入一个新元素，之后仍然有一个排序的数组。数组可以是任何类型的结构，这就是为什么有一个访问器函数可以让您“分解”这个结构以进行搜索。

左右二等分之间的区别在于插入点的位置（在最近元素的左侧或右侧）——数组是按升序还是降序排序。

平分线的一个用例是您希望在将鼠标移到图形上时突出显示最近的数据点，例如参见此示例。