Revisions to Why is processing a sorted array faster than processing an unsorted array?

Replaced dead link with a wayback machine variant

Source Link

edit approved Jan 27, 2021 at 10:03

jakubde

23
1
4

Here's a link to this code: Red Black Trees Red Black Trees, Eternally Confuzzled

Made compliant with the Jon Skeet Decree - <https://twitter.com/PeterMortensen/status/976400000942034944>.

Source Link

edited May 27, 2019 at 13:08

Peter Mortensen

29.8k
21
98
124

// declareDeclare and then fill in the lookup table
int lut[256];
for (unsigned c = 0; c < 256; ++c)
    lut[c] = (c >= 128) ? c : 0;

// useUse the lookup table after it is built
for (unsigned i = 0; i < 100000; ++i)
{
    // Primary loop
    for (unsigned c = 0; c < arraySize; ++c)
    {
        sum += lut[data[c]];
    }
}

// declare and then fill in the lookup table
int lut[256];
for (unsigned c = 0; c < 256; ++c)
    lut[c] = (c >= 128) ? c : 0;

// use the lookup table after it is built
for (unsigned i = 0; i < 100000; ++i)
{
    // Primary loop
    for (unsigned c = 0; c < arraySize; ++c)
    {
        sum += lut[data[c]];
    }
}

// Declare and then fill in the lookup table
int lut[256];
for (unsigned c = 0; c < 256; ++c)
    lut[c] = (c >= 128) ? c : 0;

// Use the lookup table after it is built
for (unsigned i = 0; i < 100000; ++i)
{
    // Primary loop
    for (unsigned c = 0; c < arraySize; ++c)
    {
        sum += lut[data[c]];
    }
}

readers generally don't care about what has been added or removed, they just want to read a good post. For those who are more curious, there is the edit history. https://meta.stackexchange.com/a/127655/316262

Source Link

edited Feb 27, 2019 at 10:56

Neuron

4.2k
4
28
50

EDIT: One thing I forgot to put in.

The technique of indexing into an array, instead of using an if statement, can be used for deciding which pointer to use. I saw a library that implemented binary trees, and instead of having two named pointers (pLeft and pRight or whatever) had a length-2 array of pointers and used the "decision bit" technique to decide which one to follow. For example, instead of:

EDIT: One thing I forgot to put in.

The technique of indexing into an array, instead of using an if statement, can be used for deciding which pointer to use. I saw a library that implemented binary trees, and instead of having two named pointers (pLeft and pRight or whatever) had a length-2 array of pointers and used the "decision bit" technique to decide which one to follow. For example, instead of: