前言

任务队列的输入是称为任务的工作单元。专用的工作进程不断监视任务队列以执行新工作。

通过消息进行通信，通常使用代理在客户和工作人员之间进行调解。为了启动任务，客户端将一条消息添加到队列中，然后代理将该消息传递给工作人员。

队列常常系统可以由多个 部分 组成，这样可以让位于高可用性和横向扩展。

可以在单机上运行， 也可以在多台机器上运行，甚至可以跨数据中心运行。

5.1 任务队列的用途

通常一个任务队列可以完成以下工作

• 监控
  实现监控事件
  监控事件流由工作人员发出，并被内置和外部工具用来实时告诉您集群在做什么。

• 调度

  任务队列可以指定以秒或其他单位运行任务，可以使用基于简单间隔的重复事件周期性任务，或crontab表达式

• 工作流程

  任务队列可以使用一组称之为 画布 的强大原语去组合简单和复杂的工作流程，包括分组，链接，分块。

• 资源泄露保护

  有些任务队列可以支持 max tasks per child 选项，用于泄露资源的用户任务，如内存或文件描述符，但是这些一般不受使用者的控制。

• 时间和速率限制

您可以控制每秒或每分钟，小时可以执行多少任务，或者允许任务运行多长时间，这可以设置默认值，用于特定工作人员或单独用于每个任务类型

• 组件定制

支持组件定制，符集组件可以由用户定义。 一些队列 是使用 bootsteps构建的，包括一个依赖图，可以对内部进行细粒度控制。

5.2 合并工作，有任务队列用作跨线程或机器分配工作的机制。

假设我们有几个消息队列服务的有序数据被服务器进程分别接收，此时我们需要对齐它们并将其合并到一个队列。

由于某种原因，我们无法使用编程语言原生的合并函数，因此我们必须自己实现几个队列的合并，当然最简单的就是两个队列。

它们的每个数据大概是这个样子，

队列1 形如下格式： []task{}

    task1 = {id:1  desc:*DescStructTask1 Url: aliaws.cloudform.com/data/task1  picture: http://aliaws.picstore.info/oss/task1}
    
    task2 = {id:2  desc:*DescStructTask2 Url: aliaws.cloudform.com/data/task2  picture: http://aliaws.picstore.info/oss/task2}

    task4 = {id:4  desc:*DescStructTask4 Url: aliaws.cloudform.com/data/task4  picture: http://aliaws.picstore.info/oss/task4}
    
    task5 = {id:5  desc:*DescStructTask5 Url: aliaws.cloudform.com/data/task5  picture: http://aliaws.picstore.info/oss/task5}

    task7 = {id:7  desc:*DescStructTask7 Url: aliaws.cloudform.com/data/task7  picture: http://aliaws.picstore.info/oss/task7}
    
    task9 = {id:9  desc:*DescStructTask9 Url: aliaws.cloudform.com/data/task9  picture: http://aliaws.picstore.info/oss/task9}
   
   ....

队列2 形如下格式： []jobs{}

    jobs3= {num:3  desc:*DescStructJob3 Url: aliaws.cloudform.com/data/jobs3  picture: http://aliaws.picstore.info/oss/jobs3}

    jobs5= {num:5  desc:*DescStructJob5 Url: aliaws.cloudform.com/data/jobs5  picture: http://aliaws.picstore.info/oss/jobs5}

    jobs6= {num:6  desc:*DescStructJob6 Url: aliaws.cloudform.com/data/jobs6  picture: http://aliaws.picstore.info/oss/jobs6}
	
	jobs8= {num:8  desc:*DescStructJob8 Url: aliaws.cloudform.com/data/jobs8  picture: http://aliaws.picstore.info/oss/jobs8}

	jobs10= {num:5  desc:*DescStructJob10 Url: aliaws.cloudform.com/data/jobs10  picture: http://aliaws.picstore.info/oss/jobs10}

	jobs11= {num:5  desc:*DescStructJob11 Url: aliaws.cloudform.com/data/jobs11  picture: http://aliaws.picstore.info/oss/jobs11}

    ....

因此容易知道，两个队列内部分别，总是有序递增的，并且序号如下

set1 = [1, 2, 4, 5,7,9 ...]
set2 = [3, 5, 6, 8, 10, 11 ...]

将它们合并为一个队列，如何操作？ 当然如果使用 语言内部的函数 可能一行代码就够了，sorted(set1 + set2).

但是场景限制我们无法那样做。

5.3 方法原理

我们保持队列set2不动，将队列set1依次取出，并与队列set2对比，如果小于set2 内的未读取第一个元素。

那么队列2的指针保持不变， 并将队列1的当前值写入队列3，也就是结果中。

       if s1 < s2:
                self._a3.append(s1)

如果大于或等于set2的的值则选择放入 set2的当前元素

      self._a3.append(s2)
      a2.remove(s2)

并从set2中删除该元素。如此直到完成遍历为止。

当队列2完成遍历后， a1仍然没有完成，那么添加a1 到结果队列中。

   while a2:
      ...
   else:
     self._a3.extend(a1)

如果set1已经完成了，但是最后仍有队列2 没有完成，则添加队列2到结果中

   for a1:
       ...
       while a2:
          ....
   else:
        self._a3.extend(a2)

for的队列对象两者都可以，也就是说 保持set1不变，或保持set2不变都可以完成此任务。

5.4 python 版本

由于python支持在while 和for 完成后进行else 计算，因此，我们可以利用该特点，方便快捷地实现。

遍历 set1 队列，并切割 set2队列

        for s1 in a1:
            while a2:
               s2 = a2[0]
               ......

处理中间的依序插入

           if s1 < s2:
                self._a3.append(s1)
                break
           else:
                self._a3.append(s2)
                a2.remove(s2)

处理剩余项:

         else:
            self._a3.extend(a1)
        
    else:
        self._a3.extend(a2)

完整的代码:

     _a3 = []

    for s1 in set1:
        
        while set2:
            s2 = a2[0]
            if s1 < s2:
                _a3.append(s1)
                break
            else:
                _a3.append(s2)
                a2.remove(s2)
        else:
            _a3.extend(a1)
        
    else:
        _a3.extend(a2)

是不是很简单。

5.5 go 版本

由于go没有 while 语句并且也不支持 for 完成后的else 计算，因此，我们需要在循环遍历的外侧做进一步的判断和处理。

遍历 set1 队列，并切割 set2队列

    var a3 = []int{} 
    aa2 := set2[:]
	for i, v := range set1 {
		for j, va := range aa2 {
			...

处理中间的依序插入:

			if v < va {
				a3 = append(a3, v)
				break
			} else {
				a3 = append(a3, aa2[0]) // 添加aa2的第一个元素
				aa2 = aa2[1:]           // 删除第一个元素
			}
		}

处理剩余项:

		if len(aa2) == 0 {
			a3 = append(a3, a[i:]...)
		}
	}
	if len(aa2) != 0 {
		a3 = append(a3, aa2...)
	}

完整的代码:

    aa2 := set2[:]
	for i, v := range set1 {
		for j, va := range aa2 { 
			
			if v < va {
				a3 = append(a3, v)
				break
			} else {
				a3 = append(a3, aa2[0])  
				aa2 = aa2[1:]            
			}
		}


		if len(aa2) == 0 {
			a3 = append(a3, a[i:]...)
		}
	}

	if len(aa2) != 0 {
		a3 = append(a3, aa2...)
	}

5.6 计算复杂度

此复杂度分场景如下:

如果set1的长度为 m， set2的长度为n，m < n, 那么最好的场景是两个队列中最小的那一个，
也就是它的每一个都比另一个队列的小，因此只需要在最后直接添加两个队列即可。

也就是: O(N) = m

最差的场景是每个队列的每个值依次大小相间，那么需要完整查看两个队列，

因此复杂度是 O(N) = m * n

小结

我们完成了两个不同类型的队列的合并操作，并且充分利用它们的有序性质以较高的性能操作它们。

队列或列表操作有许多内容可以讨论，比如查找方式，合并方式，子列表等等。
有机会我们依次展开。