近似排序（数组/向量），可预测的运行时间

作者: 不见你
发布时间: 2025-02-09 04:20:20 (12天前)
转自：

6 条回复

0#
回复此人
十二* | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> <P> 听起来像你想要使用 <code> std::partition </code> ：将感兴趣的部分移到前面，将其他部分移到后面。它的复杂性大约是O（n），但它对缓存友好，所以它可能比排序快很多。 </p> </DIV>

编辑
1#
回复此人
小它．Little it | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> <P> 我想到的是迭代向量，如果某个事件不太重要，不要处理它，而是把它放在一边。一旦读完整个矢量，就看看放在一边的事件。当然，您可以使用具有不同优先级的多个存储桶。并且只存储那里的引用，你不想移动数兆字节的数据。（根据Damon的要求，现在发布了答案） </p> </DIV>

编辑
2#
回复此人
喜欢一个人丶 | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> <P> 如果您有N个工作线程，请为每个工作线程提供原始未排序数组的1 / N.工作人员将要做的第一件事是你的近似快速排序算法，优先选择它的阵列的各个部分。然后，他们可以按顺序处理他们的数组 - 大致首先执行更高优先级的项目，并且还非常缓存友好。这样，您不会尝试对整个阵列进行排序，甚至尝试对整个阵列进行近似排序;什么小排序，是完全并行化的。单独分拣10件比分拣整件要便宜得多。 </p> <P> 如果要处理的项目的优先级是随机分布的，这将最有效。如果对它们有一些排序，你最终会被一个被高优先级项目淹没或缺乏的线程处理。 </p> </DIV>

编辑
3#
回复此人
老夫的少女心吖 | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> <P> 为每个优先级使用单独的向量。然后你不需要对它们进行排序。 </p> </DIV>

编辑
4#
回复此人
晴天？霹雳 | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> <P> 听起来像一个很好的例子，近似排序算法可能很有用。 </p> <P> 回到十年前，Chazelle开发了一种不错的数据结构，有点像堆。关键的区别在于时间复杂度。它具有所有重要操作的恒定时间，例如，插入，删除，找到最低元素等 </p> <P> 这种数据结构的技巧是，它通过允许排序顺序中的一些错误来打破O（n * log n）复杂性障碍。 </p> <P> 对我而言，这听起来就像你需要的那样。调用数据结构的<strong> 软堆 </强> 并在维基百科上解释： </p> <P> <a href="https://en.wikipedia.org/wiki/Soft_heap" rel="nofollow"> https://en.wikipedia.org/wiki/Soft_heap </A> </p> <P> 还有其他算法允许一些有利于速度的错误。如果你谷歌的话，你会发现它们的<strong> 近排序算法 </强> </p> <P> 如果您尝试该算法，请在实践中提供一些反馈。我真的很想听听算法在实践中的表现。 </p> </DIV>

编辑

登录后才能参与评论