Python：跟踪最新的消息序列ID，没有间隔

Question

我正在用Python编写一个网络应用程序，从服务器接收编号的消息。消息的序列号在1..N范围内，可能出现顺序错误。我想跟踪收到的最新消息，条件是到目前为止消息中没有空白。你知道吗

比如说

• 如果消息是1,3,2，我会将3标记为收到的最新未封盖消息。你知道吗
• 如果消息是1,2,5,4，我会将2标记为收到的最新未封盖消息，因为我还没有收到3。你知道吗
• 一旦3进入，我会将5标记为收到的最新消息。你知道吗

最有效的方法是什么？是否有一些数据结构或编程习惯实现一个算法来解决这个问题？你知道吗

Answer 1

我环顾了一下，没有马上找到一个很好的答案。你知道吗

这是我通过一个小的阻塞类来尝试的。从技术上讲，对于单个handle\u new\u索引，这可能是O（N），但是handle\u new\u index操作的平均时间仍然应该保证是恒定的。你知道吗

我不认为时间复杂度会变得更好，因为无论做什么，都必须在某种数据结构上进行插入。你知道吗

对于数十亿个请求和非常广泛的分布，非连续集可以有适度的内存占用。你知道吗

import random

class gapHandler:
    def __init__(self):
        self.greatest = 0
        self.non_contiguous = set()

    def handle_new_index(self, message_index):
        """
        Called when a new numbered request is sent. Updates the current
        index representing the greatest contiguous request.

        """
        self.non_contiguous.add(message_index)
        if message_index == self.greatest + 1:
            self._update_greatest()

    def _update_greatest(self):
        done_updating = False
        while done_updating is False:
            next_index = self.greatest + 1
            if next_index in self.non_contiguous:
                self.greatest = next_index
                self.non_contiguous.remove(next_index)
            else:
                done_updating = True


def demo_gap_handler():
    """ Runs the gapHandler class through a mock trial. """
    gh = gapHandler()

    for block_id in range(20000):
        start = block_id*500 + 1
        end = (block_id + 1)*500 + 1

        indices = [x for x in range(start, end)]
        random.shuffle(indices)
        while indices:
            new_index = indices.pop()
            gh.handle_new_index(new_index)
            if new_index % 50 == 0:
                print(gh.greatest)


if __name__ == "__main__":
    demo_gap_handler()

以下是一些基本测试：

import unittest
import gaps


class testGaps(unittest.TestCase):

    def test_update_greatest(self):
        gh = gaps.gapHandler()
        gh.non_contiguous = set((2, 3, 4, 6))

        gh._update_greatest()
        self.assertEqual(gh.greatest, 0)

        gh.greatest = 1
        gh._update_greatest()
        self.assertEqual(gh.greatest, 4)

    def test_handle_new_index(self):
        gh = gaps.gapHandler()
        gh.non_contiguous = set((2, 3, 4, 6, 2000))

        gh.handle_new_index(7)
        self.assertEqual(gh.greatest, 0)

        gh.handle_new_index(1)
        self.assertEqual(gh.greatest, 4)

        gh.handle_new_index(5)
        self.assertEqual(gh.greatest, 7)

if __name__ == "__main__":
    unittest.main()