相关疑难解决方法(0)

设计一种有效的算法来排序5个不同的 - 非常大的 - 密钥,在最坏的情况下少于8个比较.你不能使用基数排序.

我没有在任何地方找到这个特定主题......

我在23个整数的std :: vector中的不同数据上调用nth_element()算法,每秒大约400,000次,更精确的"无符号短"值.

我想提高计算速度,这个特定的调用需要很大一部分CPU时间.现在我注意到,与std :: sort()一样,即使具有最高优化级别和NDEBUG模式(Linux Clang编译器),nth_element函数在探查器中也是可见的,因此比较是内联的而不是函数调用本身.好吧,更多的preise:不是nth_element()但是std :: __ introselect()是可见的.

由于数据的大小很小,我尝试使用二次排序函数PIKSORT,当数据大小小于20个元素时,它通常比调用std :: sort更快,可能是因为函数将是内联的.

template <class CONTAINER>
inline void piksort(CONTAINER& arr)  // indeed this is "insertion sort"
{
    typename CONTAINER::value_type a;

    const int n = (int)arr.size();
    for (int j = 1; j<n; ++j) {
        a = arr[j];
        int i = j;
        while (i > 0 && a < arr[i - 1]) {
            arr[i] = arr[i - 1];
            i--;
        }
        arr[i] = a;
    }
}

然而,这比在这种情况下使用nth_element慢.

此外,使用统计方法是不合适的,比std :: nth_element更快

最后,由于值在0到约20000的范围内,因此直方图方法看起来不合适. …

问题陈述

我一次给出一个非常大的数字列表,我需要打印" 中位数 ".

更清楚的是,可以有" 125,000,000 "数字,并保证每个数字小于" 1.e + 18 ".

这是一场比赛,因此有内存限制(20 MB顶部)和时间限制(5秒顶部).

" 中位数 "是排序数字中间的数字.
例如,如果这是数字列表:

23
8
16
42
15
4
108

排序后的数字:

1) 4
2) 8
3) 15
4) 16
5) 23
6) 42
7) 108

" 中位数 "将是16;

所以我在互联网上搜索它,但我找不到任何通过这些限制的答案.

途径

我的方法是获取所有数字,将它们保存在文本文件中,对它们进行排序,然后得到" 中位数 ".

思路

1. 我知道我可以从文件中读取所有数字并将它们放在矢量中,然后轻松地对它们进行排序.
   但这将超过内存限制.
   
   
2. 所以当我把它们放在文本文件中时,我提出了这个想法来对数字进行排序.
   这就像有一个循环,从控制台获取下一个数字后读取文件(逐行),当它到达正确的位置时,在那里插入数字,不接触其他数字.
   但问题是我不能在文本文件的中间插入一行,因为它会覆盖其他数字.
   
   
3. 所以我创建了两个文件,其中一个已经输入了数字,另一个读取了第一个文件,并将其自身的数字复制到正确的位置,然后插入最后给定的数字,然后继续复制剩余的数字.
   但它花费了太多时间,因此超出了时间限制.
   

请求

因此,我想要优化其中一个想法,以便通过限制或通过这些限制的任何新想法.

偏爱

我更喜欢使用第二个想法,因为与其他两个不同,它通过限制,但我不能这样做,因为我不知道如何在文本文件的中间插入一行.因此,如果我了解这一点,其余的过程将非常简单.

试图解决方案

这是一个接收数字的函数,通过读取文件,找到它的最佳位置并将其放在那里.
事实上,它代表了我的第三个想法. …