d3.shuffle、Fisher–Yates算法以及js 中的slice

  • d3.shuffle、Fisher–Yates算法以及js 中的slice已关闭评论
  • 116 次浏览
  • A+
所属分类:Web前端
摘要

D3.shuffle() 方法用于将数组中的元素随机排序。它使用 Fisher–Yates 洗牌算法,该算法是无偏的,具有最佳的渐近性能(线性时间和常数内存)。


1.d3.shuffle

D3.shuffle() 方法用于将数组中的元素随机排序。它使用 Fisher–Yates 洗牌算法,该算法是无偏的,具有最佳的渐近性能(线性时间和常数内存)。

D3.shuffle() 方法的语法如下:

d3.shuffle(array, [start, end]) 

其中:

  • array 是原数组。
  • start 是开始索引,默认为 0。
  • end 是结束索引,默认为数组的长度。

如果 end 是负数,则它表示从数组末尾开始向前计算的索引。

D3.shuffle() 方法返回的数组是一个新数组,它包含原数组中元素的随机排列。

D3.shuffle() 方法的常见用法如下:

  • 将数组中的元素随机排序:
const arr = [1, 2, 3, 4, 5]; const shuffledArr = d3.shuffle(arr); 
  • 将数组中的元素随机排序,并只返回指定范围内的元素:
const arr = [1, 2, 3, 4, 5]; const shuffledArr = d3.shuffle(arr, 1, 3); 

D3.shuffle() 方法还可以与其他方法一起使用来实现更复杂的功能。例如,可以使用 D3.shuffle() 方法和 D3.map() 方法来随机选择数组中的元素。

const arr = [1, 2, 3, 4, 5]; const shuffledArr = arr.map(x => d3.shuffle(arr)[0]); 

在上述示例中,D3.shuffle() 方法用于随机选择 arr 数组中的元素。D3.map() 方法用于将 shuffledArr 数组中的每个元素映射到一个新的数组中。

以下是 D3.shuffle() 方法的执行原理:

  1. D3.shuffle() 方法将原数组中的元素复制到一个新数组中。
  2. 使用 Fisher–Yates 洗牌算法对新数组中的元素进行随机排序。()
  3. 返回随机排序后的数组。

因此,D3.shuffle() 方法将返回一个包含原数组中元素的随机排列。

2.fisher-yate 洗牌算法

d3.shuffle、Fisher–Yates算法以及js 中的slice

Fisher–Yates 洗牌算法是一种随机排序算法,它使用以下步骤来将数组中的元素随机排序:

  1. 从数组中随机选择一个元素,并将其移到数组的末尾。(这里实际上是和末尾调换)
  2. 重复步骤 1,直到数组中的所有元素都被移到末尾。(第一部改变之后,最后一位不变)

Fisher–Yates 洗牌算法是无偏的,具有最佳的渐近性能(线性时间和常数内存)。

以下是 Fisher–Yates 洗牌算法的 JavaScript 实现:

function shuffle(arr) {   for (let i = arr.length - 1; i >= 0; i--) {     const j = Math.floor(Math.random() * (i + 1));     [arr[i], arr[j]] = [arr[j], arr[i]];   }   return arr; } 

该算法使用 Math.random() 方法来生成一个随机数,该数用于选择要移到末尾的元素。然后,算法将该元素与数组末尾的元素交换位置。

以下是 Fisher–Yates 洗牌算法的示例:

const arr = [1, 2, 3, 4, 5]; const shuffledArr = shuffle(arr); console.log(shuffledArr); // [5, 4, 3, 2, 1] 

在上述示例中,shuffledArr 数组将包含原数组中元素的随机排列。
来源:stackoverflow

3.示例

示例一:使用 d3.shuffle 来模拟一次扑克牌的洗牌过程。我们可以先创建一个包含52张扑克牌的数组,然后用 d3.shuffle 来打乱这个数组,最后用 d3.slice 来取出前几张牌作为发牌结果。例如:

// 导入 d3 库 import * as d3 from "d3";  // 创建一个扑克牌数组 let suits = ["♠", "♥", "♦", "♣"]; let ranks = ["A", "2", "3", "4", "5", "6", "7", "8", "9", "10", "J", "Q", "K"]; let cards = []; for (let suit of suits) {   for (let rank of ranks) {     cards.push(suit + rank);   } }  // 打乱扑克牌数组 d3.shuffle(cards);  // 取出前五张牌作为发牌结果 let hand = d3.slice(cards, 0, 5);  // 打印出发牌结果 console.log(hand); 

示例一:使用 d3.shuffle 来生成一个随机的颜色序列。我们可以先创建一个包含不同颜色名称和对应颜色代码的对象,然后用 d3.keys 和 d3.values 来提取出颜色名称和颜色代码的数组,再用 d3.shuffle 来打乱这两个数组,最后用 d3.permute 来根据打乱后的顺序重新组合成一个新的对象。例如:

// 导入 d3 库 import * as d3 from "d3";  // 创建一个颜色对象 let colors = {   red: "#ff0000",   orange: "#ffa500",   yellow: "#ffff00",   green: "#008000",   blue: "#0000ff",   violet: "#ee82ee" };  // 提取出颜色名称和颜色代码的数组 let names = d3.keys(colors); let codes = d3.values(colors);  // 打乱两个数组的顺序 d3.shuffle(names); d3.shuffle(codes);  // 根据打乱后的顺序重新组合成一个新的对象 let shuffled = {}; for (let i = 0; i < names.length; i++) {   shuffled[names[i]] = codes[i]; }  // 打印出新的对象 console.log(shuffled);  

observablehq-d3-shuffle

4.js中slice的用法

JavaScript 的 slice() 方法用于从数组中返回一个新的数组,该数组包含原数组中指定范围内的元素。

slice() 方法的语法如下:

array.slice(start, end) 

其中:

  • array 是原数组。
  • start 是开始索引,默认为 0。
  • end 是结束索引,不提取该元素,默认为数组的长度,也就是提取之后的所有元素。

如果 end 是负数,则它表示从数组末尾开始向前计算的索引。

slice() 方法返回的数组是一个浅拷贝,它不会影响原数组。

slice() 方法的常见用法如下:

  • 从数组中返回指定范围内的元素:
const arr = [1, 2, 3, 4, 5]; const newArr = arr.slice(1, 3); // [2, 3] 
  • 从数组中返回所有元素:
const arr = [1, 2, 3, 4, 5]; const newArr = arr.slice(); // [1, 2, 3, 4, 5] 

相当于slice(0,5)

  • 从数组中返回最后一个元素:
const arr = [1, 2, 3, 4, 5]; const newArr = arr.slice(-1); // [5] 

这里相当于slice(-1,5),slice(4,5)

  • 从数组中返回第一个元素:
const arr = [1, 2, 3, 4, 5]; const newArr = arr.slice(0, 1); // [1] 
  • 从数组中返回除最后一个元素之外的所有元素:
const arr = [1, 2, 3, 4, 5]; const newArr = arr.slice(0, -1); // [1, 2, 3, 4] 
  • 从数组中返回除第一个元素之外的所有元素:
const arr = [1, 2, 3, 4, 5]; const newArr = arr.slice(1); // [2, 3, 4, 5] 

这里面是默认end为4

slice() 方法还可以与其他方法一起使用来实现更复杂的功能。例如,可以使用 slice() 方法和 filter() 方法来从数组中返回满足指定条件的元素。

const arr = [1, 2, 3, 4, 5]; const newArr = arr.filter(x => x % 2 === 0); // [2, 4] 

在上述示例中,filter() 方法用于过滤数组中的元素,只保留偶数。slice() 方法用于从过滤后的数组中返回指定范围内的元素。