算法 & 数据结构

• 耗时与输入无关(即使集合已经排序过, 仍然会消耗同样的时间, 因为总是要遍历剩余的所有元素)
• 原地排序(最左侧是已经排序的集合)

• 在小数组情况下优于冒泡和选择排序
• 原地排序(最左侧是已经排序的集合)

• 即使是排序大型数组, 性能也可接受(尽管还是慢于能在生产中使用的排序算法)

// 来自: 维基百科
public static void shellSort(int[] arr) {
	int length = arr.length;
	int temp;
	for (int step = length / 2; step >= 1; step /= 2) {
		for (int i = step; i < length; i++) {
			temp = arr[i];
			int j = i - step;
			while (j >= 0 && arr[j] > temp) {
				arr[j + step] = arr[j];
				j -= step;
			}
			arr[j + step] = temp;
		}
	}
}

• 自顶向下的归并排序 TopDownMergeSort (递归): 将大数组分割成小数组, 递归这一过程, 最终完成归并.
• 自底向上的归并排序 BottomUpMergeSort (循序渐进):
  从元素数量为2的小数组开始排序,
  完成一遍之后再从头开始排序元素数量为4的数组(上一轮的两个小数组), 以此类推, 最后完成最大数组的排序.
  此方法比较适合链表结构.

• 分而治之

• 归并排序的数组拆分先于数组内容, 总是从中间拆分.
  快速排序的数组拆分后于数组内容, 拆分的位置取决于数组的内容.
• 虽然归并排序的算法复杂度稳定为O(nlogn), 但归并排序的速度慢于快速排序.
  若将算法复杂度误认为算法的速度, 就会被误导.

• 分而治之
• 可原地排序
• 高性能

• 前序/先序(preorder)
• 中序(inorder, 在二叉树中出现),
• 后序(postorder)

• 前序/先序: 在递归后代之前调用回调
• 中序(二叉树): 递归left, 调用回调, 递归right
• 后序: 在递归后代之后调用回调

• 使用次数最多的项目, 即使长时间不使用, 也不会被删除.
• 刚刚进入缓存的项目, 很容易成为使用计数值最小的项目.

1. 1.
   将图片中的每个像素按照RGB颜色放进三维空间.
2. 2.
   将三维空间平均切分为27个桶(即3x3x3切割).
3. 3.
   将落在同一个桶中的像素的颜色值平均, 得到该桶的颜色值.
4. 4.
   将桶按其中的像素数量进行降序排序, 即可得到色板.

1. 1.
   设定色板的颜色数量.
2. 2.
   将图片中的所有像素放进一个桶内.
3. 3.
   统计桶中所有像素的颜色值, 找到RGB三个通道中, 数值范围最大的那个通道.
4. 4.
   根据数值范围最大的通道的值对像素进行排序.
5. 5.
   将排序后的像素的前半部分和后半部分划分为两个桶(即"中位切割").
6. 6.
   对得到的新桶重复执行步骤3~5, 直到桶的数量与要求的色板颜色数量相同.
7. 7.
   对每个桶中的像素的颜色值执行平均.

require! 'prelude-ls': {round, map, zip-with}
nearest-neighbor-interpolation = (zoom, src-image) ->
  color = (image, x, y) ->
    i = (y * image.width + x) * 4
    map (|| 0), image.data[i to i + 3]
  canvas = document.create-element \canvas
  canvas.width = src-image.width * zoom
  canvas.height = src-image.height * zoom
  ctx = canvas.get-context \2d
  dst-image= ctx.create-image-data canvas.width, canvas.height
  for dst-x from 0 til canvas.width
    for dst-y from 0 til canvas.height
      src-color = color src-image, (round dst-x / zoom), (round dst-y / zoom)
      dst-i = (dst-y * canvas.width + dst-x) * 4
      dst-color = map (/ 2), zip-with (+), src-color, color dst-image, dst-x, dst-y
      for i from 0 to 3
        dst-image.data[dst-i + i] = dst-color[i]
  ctx.put-image-data dst-image, 0, 0
  canvas

require! 'prelude-ls': {map, round, floor, ceiling, sqrt, abs, sum}
bilinear-interpolation-put = (zoom, src-image) ->
  color = (image, offset, point) -->
    if point.x >= image.width or point.y >= image.height
      if offset is 3
        255
      else
        0
    else
      image.data[(image.width * point.y + point.x) * 4 + offset]
  [R, G, B, A] = map (color src-image), [0 to 3]
  canvas = document.create-element \canvas
  canvas.width = src-image.width * zoom
  canvas.height = src-image.height * zoom
  ctx = canvas.get-context \2d
  dst-image = ctx.create-image-data canvas.width, canvas.height
  for dst-x from 0 til canvas.width
    for dst-y from 0 til canvas.height
      src = x: dst-x / zoom, y: dst-y / zoom
      lt = x: floor(src.x), y: floor src.y
      rt = x: ceiling(src.x), y: floor src.y
      lb = x: floor(src.x), y: ceiling src.y
      rb = x: ceiling(src.x), y: ceiling src.y
      weight-mean = (src, points) ->
        weights = []
        sf = []
        for p, i in points when p.x < src-image.width and p.y < src-image.height
          w = sqrt(abs(p.x - src.x) * abs(p.y - src.y))
          w = 1 / w if w isnt 0
          weights.push w
          sf.push ((w, p)->
            (f) ->
              w * f p
          )(w, p)
        (f) ->
          s = sum map ((s) -> s(f)), sf
          if sum(weights) is 0 then 0 else s / sum weights
      get-weight-mean = weight-mean src, [lt, rt, lb, rb]
      dst-i = (dst-y * canvas.width + dst-x) * 4
      dst-image.data[dst-i + 0] = round get-weight-mean R
      dst-image.data[dst-i + 1] = round get-weight-mean G
      dst-image.data[dst-i + 2] = round get-weight-mean B
      dst-image.data[dst-i + 3] = round get-weight-mean A
  ctx.put-image-data dst-image, 0, 0
  canvas

require! 'prelude-ls': {map, floor}
bicubic-interpolation-put = (zoom, src-image)->
  color = (image, x, y) ->
    i = (y * image.width + x) * 4
    map (|| 0), image.data[i to i + 3]
  triangle-interpolation = f ->
    f = f / 2
    if f < 0
      f + 1
    else
      1 - f
  clamp = value ->
    return 255 if value > 255
    return 0 if value < 0
    value
  canvas = document.create-element \canvas
  canvas.width = src-image.width * zoom
  canvas.height = src-image.height * zoom
  ctx = canvas.get-context \2d
  dst-image = ctx.create-image-data canvas.width, canvas.height
  for dst-y from 0 til dst-image.height
    src-y = dst-y * zoom
    j = floor src-y
    t = src-y - j
    for dst-x from 0 til dst-image.width
      src-x = dst-x * zoom
      k = floor src-x
      u = src-x - k
      rgba = [0, 0, 0, 0]
      s = 0
      for m from -1 til 3
        for n from -1 til 3
          rgb = color src-image, j + m, k + n
          f1  = triangle-interpolation m - t
          f2 = triangle-interpolation -(n - u)
          s += f2 * f1
          rgba[0] += rgb[0] * f2 * f1
          rgba[1] += rgb[1] * f2 * f1
          rgba[2] += rgb[2] * f2 * f1
          rgba[3] += rgb[3] * f2 * f1
      dst-i = (dst-y * canvas.width + dst-x) * 4
      dst-image.data[dst-i + 0] = clamp parseInt rgba[0] / s
      dst-image.data[dst-i + 1] = clamp parseInt rgba[1] / s
      dst-image.data[dst-i + 2] = clamp parseInt rgba[2] / s
      dst-image.data[dst-i + 3] = clamp parseInt rgba[3] / s
  ctx.put-image-data dst-image, 0, 0
  canvas

• 增减字典项目时, 需要重新构建同级的节点.
• 牺牲一定的性能换取空间高效.

• 将之后的冲突元素全部前移一位.
• 将最后一位交换到被删除元素的位置.
• 惰性删除, 即通过添加标记来实现软删除.

1. 1.
   程序世界发生了一些事情.
2. 2.
   事件处理器得到事件, 检查布尔值变量.
3. 3.
   基于布尔值变量, 事件处理器直接调用相关的组件行为.

1. 1.
   程序世界发生了一些事情.
2. 2.
   事件处理器得到事件, 将事件转发给状态机.
3. 3.
   状态机可能出现两种结果:
4. 1. 1.
      新事件导致状态变更, 此时状态机会调用相关的组件行为.
      根据情况, 状态机与组件的关系可以分为两种类型:
   2. • 耦合(组件需要了解当前状态):
        被调用的行为位于组件侧, 组件侧查询当前状态, 然后选择对应的条件分支.
        这种情况下, 当修改状态机时, 组件侧也需要一起修改.
      • 解耦(组件不需要了解当前状态):
        被调用的行为位于状态机, 组件侧对状态一无所知, 但提供相应的接口允许状态机操纵它.
        这种情况下, 当修改状态机时, 组件侧不需要做修改.
   3. 3.
      新事件未导致状态变更.

• 浅历史状态指的是一个复合状态能够记住它是从哪个状态转换而来的,
• 深历史状态指的是一个复合状态能够记住它是从哪个状态转换而来的, 以及该状态所有后代状态机的状态.

• 根据条件决定状态机的初始化状态.