达夫设备技术简述

在计算机科学领域，达夫设备（英文：Duff's device）是串行复制（serial copy）的一种优化实现，通过汇编语言编程时一常用方法，实现展开循环，进而提高执行效率。这一方法据信为当时供职于卢卡斯影业的汤姆·达夫于1983年11月发明，并可能是迄今为止利用C语言switch语句特性所作的最巧妙的实现。

该技术是以其发明者Tom Duff命名的，他最早建议在C语言中使用该技术。 基本思路是以8的倍数作为迭代次数从而将循环展开为一系列语句。

达夫设备技术的js代码实现

1.基础版

const arr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

let iterations = Math.ceil(arr.length / 8);
let start = arr.length % 8;
let i = 0;

do {
  // 每个case语句后没有加break
  switch(start) {
    case 0: console.log(arr[i++]);
    case 7: console.log(arr[i++]);
    case 6: console.log(arr[i++]);
    case 5: console.log(arr[i++]);
    case 4: console.log(arr[i++]);
    case 3: console.log(arr[i++]);
    case 2: console.log(arr[i++]);
    case 1: console.log(arr[i++]);
  }

  start = 0;
} while(--iterations > 0);

2.进阶版

const getRandomArray = (length) => {
	if (typeof length !== 'number') {
		throw new Error('argument type error');
	}

	if (length <= 0) {
		return [];
	}

	const arr = [];

	// 使用达夫设备技术，拆成多个循环，大大减少循环次数
	let iterations = Math.floor(length / 8);
	let leftover = length % 8;
	let i = 0;

	if (leftover > 0) {
		// 余数次
		do {
			arr[i++] = Math.floor(Math.random() * 100);
		} while (--leftover > 0);
	}

	// 倍数次
	do {
		arr[i++] = Math.floor(Math.random() * 100);
		arr[i++] = Math.floor(Math.random() * 100);
		arr[i++] = Math.floor(Math.random() * 100);
		arr[i++] = Math.floor(Math.random() * 100);
		arr[i++] = Math.floor(Math.random() * 100);
		arr[i++] = Math.floor(Math.random() * 100);
		arr[i++] = Math.floor(Math.random() * 100);
		arr[i++] = Math.floor(Math.random() * 100);
	} while (--iterations > 0);

	return arr;
};

总结：以8的倍数作为迭代次数，大大减少循环次数。

冒泡排序

冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。 使用js代码实现如下：

/**
 * @description 冒泡排序
 * @param {object[number]} arr 
 * @returns {object[number]}
 */
const bubbleSort = (arr) => {
  if (!Array.isArray(arr)) {
		throw new Error('argument type error');
	}

	if (!arr.length) {
		return [];
	}

  for (let i = 0; i < arr.length - 1; i++) {
    for (let j = 0; j < arr.length - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }

  return arr;
};

使用达夫设备技术实现冒泡排序

思路：分别将两个for循环展开，以8的倍数作为迭代次数。

/**
 * @description 使用达夫设备技术实现冒泡排序
 * @param {object[number]} arr 
 * @returns {object[number]}
 */
const duffBubbleSort = (arr) => {
	if (!Array.isArray(arr)) {
		throw new Error('argument type error');
	}

	if (!arr.length) {
		return [];
	}

	const childSort = (idx, numberArr) => {
		const len = numberArr.length - (idx + 1);
		let loops = Math.floor(len / 8);
		let minLoop = len % 8;
		let count = 0;

		if (minLoop > 0) {
			do {
				if (numberArr[count] > numberArr[count + 1]) {
					[numberArr[count], numberArr[count + 1]] = [numberArr[count + 1], numberArr[count]];
				}

				count++;
			} while (--minLoop > 0);
		}

		do {
			if (numberArr[count] > numberArr[count + 1]) {
				[numberArr[count], numberArr[count + 1]] = [numberArr[count + 1], numberArr[count]];
			}
			count++;

			if (numberArr[count] > numberArr[count + 1]) {
				[numberArr[count], numberArr[count + 1]] = [numberArr[count + 1], numberArr[count]];
			}
			count++;

			if (numberArr[count] > numberArr[count + 1]) {
				[numberArr[count], numberArr[count + 1]] = [numberArr[count + 1], numberArr[count]];
			}
			count++;

			if (numberArr[count] > numberArr[count + 1]) {
				[numberArr[count], numberArr[count + 1]] = [numberArr[count + 1], numberArr[count]];
			}
			count++;

			if (numberArr[count] > numberArr[count + 1]) {
				[numberArr[count], numberArr[count + 1]] = [numberArr[count + 1], numberArr[count]];
			}
			count++;

			if (numberArr[count] > numberArr[count + 1]) {
				[numberArr[count], numberArr[count + 1]] = [numberArr[count + 1], numberArr[count]];
			}
			count++;

			if (numberArr[count] > numberArr[count + 1]) {
				[numberArr[count], numberArr[count + 1]] = [numberArr[count + 1], numberArr[count]];
			}
			count++;

			if (numberArr[count] > numberArr[count + 1]) {
				[numberArr[count], numberArr[count + 1]] = [numberArr[count + 1], numberArr[count]];
			}
			count++;
		} while (--loops > 0);
	};

  let iterations = Math.floor((arr.length - 1) / 8);
	let leftover = (arr.length - 1) % 8;
	let i = 0;

	if (leftover > 0) {
		do {
			childSort(i, arr);
			i++;
		} while (--leftover > 0);
	}

	do {
		childSort(i, arr);
		i++;

		childSort(i, arr);
		i++;

		childSort(i, arr);
		i++;

		childSort(i, arr);
		i++;

		childSort(i, arr);
		i++;

		childSort(i, arr);
		i++;

		childSort(i, arr);
		i++;

		childSort(i, arr);
		i++;
	} while (--iterations > 0);

	return arr;
};

展开循环对于大型数据集可以节省很多时间，但对于小型数据集来说，则可能不值得。 达夫设备技术实现冒泡和原生冒泡速度比较