相关疑难解决方法(0)

的std::sort算法(及其同类std::partial_sort和std::nth_element从C++标准库)是在大多数实现的更基本的排序算法复杂和混合合并,如选择排序,插入排序,快速排序,归并排序,或堆排序.

这里和姐妹网站上有很多问题,例如https://codereview.stackexchange.com/,与错误,复杂性以及这些经典排序算法的实现的其他方面有关.大多数提供的实现包括原始循环,使用索引操作和具体类型,并且在正确性和效率方面分析通常是非常重要的.

问:如何使用现代C++实现上述经典排序算法？

• 没有原始循环,但结合了标准库的算法构建块<algorithm>
• 迭代器接口和模板的使用,而不是索引操作和具体类型
• C++ 14风格,包括完整的标准库,以及语法降噪器,如auto模板别名,透明比较器和多态lambda.

备注:

• 有关排序算法实现的进一步参考,请参阅Wikipedia,Rosetta Code或http://www.sorting-algorithms.com/
• 根据Sean Parent的惯例(幻灯片39),原始循环for比使用运算符的两个函数的组合更长.所以f(g(x));或f(x); g(x);或f(x) + g(x);不生循环,也不是在环路selection_sort和insertion_sort下方.
• 我遵循Scott Meyers的术语来表示当前的C++ 1y已经作为C++ 14,并且将C++ 98和C++ 03都表示为C++ 98,所以不要因此而激怒我.
• 正如@Mehrdad的评论中所建议的那样,我在答案的最后提供了四个实现作为实例:C++ 14,C++ 11,C++ 98和Boost and C++ 98.
• 答案本身仅以C++ 14的形式呈现.在相关的地方,我表示各种语言版本不同的语法和库差异.

在大多数处理器中,为什么L1缓存的大小小于L2缓存的大小？

我正在尝试在霓虹灯中实现直方图.矢量化是否可能？

首先，我有一个数组int a[1000][1000]。所有这些整数都在 0 到 32767 之间，它们是已知的常量：它们在程序运行期间永远不会改变。

其次，我有一个数组 b[32768]，它包含 0 到 32 之间的整数。我使用这个数组将 a 中的所有数组映射到 32 个 bin：

int bins[32]{};
for (auto e : a[i])//mapping a[i] to 32 bins.
    bins[b[e]]++;

每次，数组 b 将用一个新数组初始化，我需要将数组 a 中的所有 1000 个数组（每个包含 1000 个整数）散列到 1000 个数组，每个数组包含 32 个整数，表示有多少整数落入其每个 bin 。

int new_array[32768] = {some new mapping};
copy(begin(new_array), end(new_array), begin(b));//reload array b;

int bins[1000][32]{};//output array to store results .
for (int i = 0; i < 1000;i++)
    for (auto e : a[i])//hashing a[i] …

我有一个特别的问题。我将尝试尽可能准确地描述这一点。

我正在做一个非常重要的“微优化”。一次运行数天的循环。所以如果我能减少这个循环时间，它需要一半的时间。10 天将减少到只有 5 天等。

我现在拥有的循环是函数：“testbenchmark1”。

我有 4 个索引需要在这样的循环中增加。但是当从列表中访问索引时，实际上需要一些额外的时间，正如我所注意到的。这就是我想知道是否有其他解决方案。

indexes[n]++; //increase correct index

“testbenchmark1”的完整代码需要 122 毫秒：

void testbenchmark00()
{
    Random random = new Random();
    List<int> indexers = new List<int>();
    for (int i = 0; i < 9256408; i++)
    {
        indexers.Add(random.Next(0, 4));
    }
    int[] valueLIST = indexers.ToArray();


    Stopwatch stopWatch = new Stopwatch();
    stopWatch.Start();

    int[] indexes = { 0, 0, 0, 0 };
    foreach (int n in valueLIST) //Takes 122 ms
    {
        indexes[n]++; //increase correct index
    }

    stopWatch.Stop();
    MessageBox.Show("stopWatch: " + stopWatch.ElapsedMilliseconds.ToString() …