以色列排队

队列是一种数据结构，可在短时间内保留元素，直到外围处理系统准备处理它们为止。队列的最常见实现是FIFO队列-先进先出-逐出最先插入的元素，即逐出在队列中花费最多时间的元素。队列还有其他变体，其中一种称为优先级队列。

在Priority Queue中，每个元素都与一个优先级相关联，通常由用户在排队时提供。此关联的优先级用于驱逐期间，在此过程中，具有最高优先级的元素会在出队时首先被驱逐。

在本文中，我们详细研究了优先级队列的一种变体，称为“以色列队列”，其中元素的优先级由其与队列中“朋友”之一的亲和力定义。 Boxma，O. J.，Wal，van der，J.和U Yechiali，U在2007年首次在《轮询与批处理》一书中引入了以色列队列。

以色列的队列通常是不整齐的队列，由于这些队列，人们倾向于找到已经在等待的朋友，他们不遵循后端的常规加入协议，而是直截了当并直接加入了朋友。以色列队列模仿了这种行为，因此得到了这个俗气的名字。

以色列队列是优先级队列的一种变体，在该队列中，不是将优先级与要排队的元素相关联，而是使用“ friend”元素隐式派生了优先级，并且优先级在该朋友所属组的后端加入。入队操作的功能签名如下所示，而其他操作（例如出队和偷看）仍然相当相似。

//将元素“ e”（元素“ f”的朋友）排队入队列“ q”。无效（israeli_queue * q，元素* e，元素* f）;

每个数据结构都旨在有效地解决一个小众用例，以色列队列也不例外，因为事实证明它们是超高效的，它可以批量处理相似的元素，或者任务的设置成本很高。

考虑一个系统，在该系统中，队列用于容纳异构任务，并且只有一台机器负责处理。现在，如果其中一些任务相似并且设置或准备成本很高，例如下载大型图元文件，旋转并行基础架构，甚至建立与设备场的持久连接，将它们排队更近并按顺序处理它们，或者批量处理有助于促进重用，从而减少冗余处理和计算。

通过在“以色列队列”之间排队元素，可以减少冗余处理，但这样做会使自己容易遭受饥饿的经典情况。如果队列中有“朋友”的元素持续频繁进入，则卡在列表尾端的元素可能会饿死更长的时间。

以色列队列的原始实现建议批处理，而不是一次处理一个任务，而是一次处理一批（一组朋友）。当处理单个任务所需的时间远低于其设置成本时，这证明是超级方便的。

实施“以色列队列”的最佳方法是使用“双链表”，该链表中有一堆指针指向其中的组的头和尾。插入到现有组的末尾是该元素的末尾，而如果该元素没有friend元素，则它会进入列表的末尾并形成自己的组。

在实现过程中可能添加的一个约束是，friend元素应始终是组的领导者（head）元素。只要核心概念保持不变，就可以对实现细节进行调整。

以色列队列是有关轮询系统的问题声明的结果。轮询系统通常包含N个队列Q1，Q2，...，Qn，其中处理单元以循环顺序访问每个队列，一次处理一个元素，即Q1，Q2，...，Qn，Q1，Q2，...， Qn等

当服务器出席队列而不是仅处理队列中的一个元素时，它假设设置队列中的元素所需的时间比设置成本要少得多，它会利用设置成本有效地处理队列中存在的整个批次。