algorithm - 按循环序列号对项目进行排序

Question

我正在开发一种算法来重新排序传输中的数据包。每个数据包在 [0, 256) 中都有一个关联的序列号。第一个数据包的序列号可以采用这些值中的任何一个，之后下一个数据包采用下一个值，下一个数据包采用下一个值，依此类推(在 255 之后滚动)。

按照正确的顺序，数据包的序列号如下所示，其中“n”是第一个数据包的序列号:

n, n+1, n+2, ..., 254, 255, 0, 1, 2, ..., 254, 255, 0, 1, 2, ..., 254, 255, 0, 1, ...

每个数据包在到达目的地时都会被赋予一个时间戳，并且它们都大致按顺序到达。 (我没有确切的数字，但是给定一个按到达时间戳排序的数据包列表，可以肯定地说数据包与其在列表中由其序列号指示的位置的距离永远不会超过五个点。)

鉴于电信的普及及其对计算机科学发展的历史重要性，我觉得我不可能是第一个处理此类问题的人。那么我的问题是:

1. 在给定循环变化的 key 的情况下，是否存在一种众所周知的算法来对近似有序的序列(例如上述序列)进行重新排序？

2. 是否有此算法的变体可以容忍大块缺失项目？让我们假设这些 block 可以是任意长度。我特别担心丢失 256 件或更多元素。

我对第一个算法有一些想法，但对第二个没有。然而，在我投入工时来验证我的算法是否正确之前，我想确保贝尔实验室(或其他任何地方)的某个人在 30 年前还没有做得更好。

Answer 1

我不知道这个解决方案是否真的在任何地方使用，但这是我会尝试的(假设没有丢失数据包，最多“洗牌”五个位置，最大序列号为 255):

n = 0;
max_heap h = empty;
while( true ) do
  while( h.top().index != 0 ) do
    p = next_packet;
    i = n - p.seq;
    if( i > 0 ) i = i - 255;
    h.add( i, p );
  done

  p = h.pop();
  n = n + 1;
  p.increase_indexes( 1 );
  // Do something with it
done

基本上在优先级队列中，我们存储在最后处理的数据包和仍在等待处理的数据包之间有多少数据包。队列将保持非常小，因为数据包在进入时会尽快处理。增加键也将非常简单，因为不需要对堆进行重新排序。

我不确定您如何使它适应丢失的数据包。最有可能通过使用一些超时或最大偏移量，之后 packtets 被声明为“下一个”并且相应地更新堆。

但是，如果您错过超过 256 个数据包，我认为这个问题根本不可能发生。取子序列

127,130,128,129

这可能有多种原因

1) 数据包 128 和 129 乱序，应该重新排序

2)丢了128和129包，然后丢了253包，所以顺序是对的

3)1和2的混合