Time optimization for generating permutations (competetive programming)

I'm trying to optimize the speed of the competitive programming problem. So far I have ended up with this code. The problem is about getting all permutations on N in lexicographic order. Can you please suggest any ideas, if it is possible to make it run faster?

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    scanf("%d", &n);
    int v[9] = {1, 2, 3, 4, 5, 6, 7, 8, 9};

    do
    {
        for(int i = 0; i < n; i++)
            printf("%d ", v[i]);
        printf("\n");
    } while(next_permutation(v, v+n));

    return 0;
}

Answers


Here are some techniques to try, not all will produce significant savings:

Set compiler optimizations to high, for speed.

First, let the compiler try optimizing your code. Print out the assembly language listing and see what the compiler did. Incorporate those optimizations into C++ code (if possible).

Use block (bulk) output.

For many applications, outputting is where most of the time is spent.

Try using snprintf to a character buffer, then at the end of the program, use a block write (fwrite) to write the character buffer to the output stream.

For most output streams, one large transaction is more efficient than many small transactions.

Loop Unrolling

Repeat statements in the body of the loop to reduce the number of iterations.

Most processors dislike branch instructions because they either invoke costly branch prediction algorithms or cause the instruction pipeline to flush. For example, eliminating a branch means no time wasted in the branch prediction.

In your case, this may not be significant as you make function calls within the loop.

Specialize your formatted output

The printf function is optimized for generic output: translating format specifications and outputting data.

You may save some time by writing your own conversion function that eliminates the translation of format specification. For example, your function only outputs decimal, so you could write your own function that converts integer numbers to a text buffer, then outputs the text buffer (see fwrite or puts).

Write your own permutation function

Again, the std::next_permutation is designed for genericity. You may be able to write your own that is more specialized or optimized for this specific application.


Need Your Help

WebDriver can't find element by xpath using Java

java testing xpath selenium webdriver

The following is the snippet of WebDriver code using Java: