5
\$\begingroup\$

I have a text file that contains 100,000 numbers from 1 ~ 100,000 in an unsorted manner (no duplicates).

The name of the file is "IntegerArray.txt"

My task is to count the number of inversions in the text file. An inversion is a pair of elements a, b where a comes before b, but a > b. Thus "1 2 3 6 4 5" contains two inversion (6 > 4 and 6 > 5).

I implemented it with the merge sorting method.

The following is my code:

long long mergeAndCount(vector<int>& vec, int p, int q, int r) {
    long long count = 0;

    vector<int> L, R;
    for (int i = p; i <= q; ++i) L.push_back(vec[i]);
    for (int j = q + 1; j <= r; ++j) R.push_back(vec[j]);

    L.push_back(numeric_limits<int>::max()); //sentinel element
    R.push_back(numeric_limits<int>::max());

    int i = 0, j = 0;

    for (int k = p; k <= r; ++k) {
        if (L[i] <= R[j]) {
            vec[k] = L[i];
            ++i;
        } else {
            vec[k] = R[j];
            ++j;
            if (L[i] != L.back() && R[j] != R.back())
                count += q - p + 1 - i
        }
    }
    return count;
}

long long inversion(vector<int>& vec, int p, int r) {
    long long count = 0;

    if (p < r) {
        int q = (p + r) / 2;
        count = inversion(vec, p, q);
        count += inversion(vec, q + 1, r);
        count += mergeAndCount(vec, p, q, r);
    }

    return count;
} 

int main() {
    ifstream infile("IntegerArray.txt"); 
    int a;
    vector<int> vec;

    while (infile >> a)
        vec.push_back(a);

    cout << inversion(vec, 0, vec.size()-1);
    return 0;
}

The result from the above code is 2407905288, which is correct.

The answer by brute force with the following code is 2407905288, which is correct. The following is a brute force version (it took me more than 10 minutes to run this code):

long long inversion(vector<int>& vec, int p, int r) {
    long long count = 0;

    for (int i = 0; i < vec.size(); ++i)
        for (int j = i + 1; j < vec.size(); ++j)
            if (vec[i] > vec[j])
                ++count;

    return count;
}

Any improvements in runtime or efficiency would be much appreciated.

\$\endgroup\$
1
  • 2
    \$\begingroup\$ Hi @JaeMinJimmyShin, thanks for fixing the error. Unfortunately you did some more: you did some improvements suggested in answers. That's not so good, as it invalidates the answers, so I had to roll back your edit. In any case, since it seems you've already received an answer you're happy with, it might be best to leave this question alone, and ask a new one instead of you want further reviews. (Editing a question puts it in the review queue for reopening, that's how I found this.) \$\endgroup\$
    – janos
    Dec 27, 2015 at 7:31

2 Answers 2

5
\$\begingroup\$

What kind of efficiency?

You ask for efficiency, but don't clarify whether you want programmer or processor efficiency. And, at least sometimes, the two can both be improved simultaneously by leveraging the right pre-existing tools, so it's worth considering programmer efficiency.

Programmer efficiency comes in at least three general categories:

  • Writing less code:

    I would be strongly tempted to confirm whether this can be written to leverage std::sort with a custom type that implements a counter in its overload to std::swap. If you can transform the problem like this, you don't have to worry about coding a merge sort correctly, and should have less code.

  • Writing clearer code:

    The arguments to mergeAndCount are named vec, p, q, and r, and have no comments that clarify the meaning of p, q, and r (inversion's arguments p and r suffer similarly). Furthermore mergeAndCount's local variables are named L and R. What do these mean? The parameters appear to be local indices for special spots in the vector; perhaps they could be named accordingly.

    As an extension of "naming things is important", consider also renaming inversion to use a verb instead of a noun. Something like invert is typically better than inversion; something that indicates what it's doing could be better still. Perhaps sortAndCount?

    Sometimes avoiding raw loops can help. For example, the loops that fill L and R could be written with std::copy. But better yet, you could construct them in place with the range constructor:

    vector<int> L(&vec[p], &vec[q + 1]);
    vector<int> R(&vec[q + 1], &vec[r + 1]);
    

    Two side comments here: your use of a final index rather than one past final (closed range instead of open range) conflicts with the standard library. If main called inversion with .size() instead of .size() - 1, and everything else was updated to match, a number of + 1 and/or - 1 items should disappear, starting with the three + 1 instances in my little code excerpt.

    Second, I'm uncertain what I think of the use of a sentinel as opposed to verifying the index location. Doesn't it have a side effect that would harm lists with that number? While the current problem definition excludes use of the sentinel, problems have a tendency of changing over time; attempts to reuse code may result in using code that isn't suited for the new problem.

  • Making it harder to screw up:

    The indices you pass into inversion and mergeAndCount represent very important values that never change. You should consider marking them const in order to avoid losing the ends of your ranges.

On the flip side, processor efficiency comes from many things that often compete with programmer efficiency. Here are a couple that could be relevant.

  • Avoiding allocations:

    Often allocating in a loop is a source of run-time inefficiency. Note, for example, that std::merge requires input and output ranges, rather than allocating its own helper ranges internally. This allows std::sort to allocate them once and reuse them as necessary. (This comment conflicts with the above suggestion to use the range constructor.)

  • Memory access patterns:

    Scanning through memory linearly is often the fastest way to access it. Your code does a pretty good job of this already, so without profiling there's little I can offer here.

\$\endgroup\$
2
  • 2
    \$\begingroup\$ std::sort is not guaranteed to use swap. For example, an typical insertion won't perform a single swap and will use std::move instead. \$\endgroup\$
    – Morwenn
    Dec 23, 2015 at 17:28
  • \$\begingroup\$ Wow very helpful answer Micahel Urman. I believe your answer will generally help me improve my style and readability. Thank you. \$\endgroup\$
    – Jay Shin
    Dec 23, 2015 at 19:51
2
\$\begingroup\$

reserve() your vectors before push_back() into them, this saves a lot of reallocations and copying.

Additionally, use a profiler to find where you can improve.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ can you elaborate more on that? \$\endgroup\$
    – Jay Shin
    Dec 24, 2015 at 0:45

Not the answer you're looking for? Browse other questions tagged or ask your own question.