标签: partial-sort

我正在尝试通过许多标准为可排序的数据集实现分页算法.不幸的是,虽然其中一些标准可以在数据库级别实现,但有些必须在应用程序级别完成(我们必须与另一个数据源集成).我们有一个分页(实际上是无限滚动)的要求,并且正在寻找一种方法来最小化在每个分页调用时在应用程序级别对整个数据集进行排序的痛苦.

进行部分排序的最佳方法是什么,只排序绝对需要排序的列表部分？是否有相当于std::partial_sort.NET库中可用的C++ 函数？我该如何解决这个问题？

编辑:这是我想要的一个例子:

假设我需要根据一些排序标准获得1000个元素集的元素21-40.为了加快排序速度,因为我每次都必须遍历整个数据集(这是一个基于HTTP的Web服务,这是无状态的),我不需要整个数据集.我只需要正确排序21-40元素.创建3个分区就足够了:元素1-20,未排序(但都小于元素21); 元素21-40,排序 ; 和元素41-1000,未排序(但都大于元素40).

以下两种方法之间是否存在显着差异？方式1使用sort或partial_sort取决于向量的大小,而方式2总是使用partial_sort.我发现方式2更具吸引力,因为我的谓词比示例中的更复杂,所以我不想重复它.但我想知道是否partial_sort表现更差,sort因为它不是用来排序整个范围,这就是为什么我倾向于使用方式1.

int main()
{
  std::vector<double> vec;
  vec.push_back(1.0);
  vec.push_back(3.0);
  vec.push_back(2.0);
  vec.push_back(5.0);
  vec.push_back(4.0);
  vec.push_back(9.0);
  const size_t numBest = 3;
  const size_t numTotal= vec.size();

#if WAY1
  if (numTotal < numBest)
  {
    std::sort(vec.begin(), vec.end(), std::not2(std::less<double>()));
  }
  else
  {
    std::partial_sort(vec.begin(), vec.begin() + numBest, vec.end(), std::not2(std::less<double>()));
    vec.resize(numBest);
  }
#elif WAY2
  {
    const size_t numMiddle = numTotal < numBest ? numTotal : numBest;
    std::partial_sort(vec.begin(), vec.begin() + numMiddle, vec.end(), std::not2(std::less<double>()));
    vec.resize(numMiddle);
  }
#endif

  // now vec contains the …

我需要从一个Vec相当大的生产中获得前N个项目.目前我这样做效率很低:

let mut v = vec![6, 4, 3, 7, 2, 1, 5];
v.sort_unstable();
v = v[0..3].to_vec();

在C++中,我会使用std::partial_sort,但我在Rust文档中找不到相应的东西.

我只是忽略它,还是不存在(还)？