2
\$\begingroup\$

I need to optimize this piece of code I made because this will run in real-time mode.

It's a matrix shifter that pulls downward and will neglect any transparent element.

Code:

void shiftDown(int col)
{
    int x = 0;  //transparent element
    int N = 5;  //size
    int i,j,k,l;

    for ( i = N - 1;i >= 0; --i )
    {
        if( map[i][col] == x )
        {
            for( j = i;j >= 0; --j )
            {
                if ( map[j][col] != x )
                {
                    for ( l = i, k = j;l >= 0; --l, --k )
                    {
                        map[l][col] = map[k][col];
                    }
                }
            }
        }
    }
}

Data:

(before)

0 2 3 2 0
0 1 4 0 1
1 2 2 0 3
2 1 0 0 4
4 3 1 1 3

(after)

0 2 0 0 0
0 1 3 0 1
1 2 4 0 3
2 1 2 2 4
4 3 1 1 3
    ^ ^

Other code

int map[][5] =
{
  {0, 2, 3, 2, 0},
  {0, 1, 4, 0, 1},
  {1, 2, 2, 0, 3},
  {2, 1, 0, 0, 4},
  {4, 3, 1, 1, 3}
};

void printMap();
void shiftDown(int col);

int main()
{
    cout << "before\n";
    printMap();

    for (int i = 0;i < 5; ++i)
    {
        shiftDown(i);
    }
    cout << "after\n";
    printMap();


    cin.get();
    return 0;
}

void printMap()
{
    for (int row = 0;row < 5; ++row)
    {
        for (int col = 0;col < 5; ++col)
        {
            cout << map[row][col] << '\t';
        }
        cout << endl << endl << endl << endl;
    }
}

Note: Looked at my comment again and I need to correct my error. Its int map[N][N] again. This will not work for M x N matrix.

\$\endgroup\$
1
\$\begingroup\$

You can sort each column separately (only move the transparent value to the top of the column) with a fast sorting algorithm like merge sort:

void mergeSortBlock(int *a, int index1, int index2, int size, int transparent){
    int *result;
    int resultIndex = 0;
    int mergeIndex1 = index1;
    int mergeIndex2 = index2;

    result = new int [size*2];

    while (mergeIndex1 <= (index1 + size -1) && mergeIndex2 <= (index2 + size -1)){
        if (a[mergeIndex2] == transparent) {  // check the transparency
            result[resultIndex] = a[mergeIndex2];
            resultIndex++;
            mergeIndex2++;
        }
        else {
            result[resultIndex] = a[mergeIndex1];
            resultIndex++;
            mergeIndex1++;
        }
    }

    if (mergeIndex2 <= (index2 + size - 1)) {
        for (int i = mergeIndex2 ; i< (index2 + size); i++) {
            result[resultIndex] = a[mergeIndex2];
            resultIndex++;
            mergeIndex2++;              
        }
    }
    else{
        for (int i = mergeIndex1 ; i< (index1 + size); i++) {
            result[resultIndex] = a[mergeIndex1];
            resultIndex++;
            mergeIndex1++;
        }
    }

    // copy the result back
    for (int i=0; i < size*2; i++) {
        a[index1+i] = result[i];
    }       
    delete [] result;
}

void mergeSort(int *a, int indexFront,int indexEnd, int transparent){
    int size = (indexEnd - indexFront +1)/2;
    if (size > 1){
        mergeSort(a, indexFront, indexFront + size - 1, transparent); 
        mergeSort(a, indexFront + size, indexEnd, transparent);
    }
    mergeSortBlock(a, indexFront, indexFront + size, size, transparent);
}

As you can see, in the mergeSortBlock function, instead of examining a[mergeIndex1]>a[mergeIndex2] you check the transparency condition.

the indexFront is the index of the first element of your array and indexEnd is the index of the last element.

Now in your main, first you need to transpose the matrix so that the ith row of the transposed matrix (called result in this example) represents the ith column of your map matrix. then call the mergeSort function for each row of the transposed matrix, Result .

int  main()
    int result[5][5];
    int map[][5] =
    {
        {0, 2, 3, 2, 0},
        {0, 1, 4, 0, 1},
        {1, 2, 2, 0, 3},
        {2, 1, 0, 0, 4},
        {4, 3, 1, 1, 3}
    };

    //transpose map => map's ith column = result's ith row
    for (int i = 0; i<5; i++)
        for (int j = 0; j<5; j++)
            result[j][i] = map[i][j];


    for (int i=0; i<5; i++) 
        mergeSort(result[i],0,4,0);


    //transpose reuslt => result's ith row = map's ith column
    for (int i = 0; i<5; i++)
        for (int j = 0; j<5; j++)
            map[j][i] = result[i][j];

    return 0;
}

At the end again we need to transpose the matrix result.

Note: The complexity of merge sort is O(n.logn). You have n columns. This makes the complexity of the matrix shifter O(n^2.logn). Thanks to the nature of your problem, you can still improve this by parallel programming (of course if you have multiple processors). The complexity of transpose is O(n^2). The complexity of your own algorithm is O(n^3).

Note2: You can modify mergeSort and mergeSortBlock functions to work directly with the columns of your matrix.

\$\endgroup\$
  • \$\begingroup\$ Thanks for answering, but that would alter all its content. I need to preserved their order. Only the transparent element are needed to move up. \$\endgroup\$ – mr5 Oct 28 '13 at 17:59
  • \$\begingroup\$ @mr5: I know. You can still do it. check the answer. Hope it's clear enough. \$\endgroup\$ – Nejla Oct 28 '13 at 23:25
  • \$\begingroup\$ I haven't tested this entire thing yet, but it looks like you should still consider an std::vector to avoid the new and delete. \$\endgroup\$ – Jamal Oct 28 '13 at 23:31
  • \$\begingroup\$ @Jamal: Yes, you can use std::vector. You can also use smart pointers like std::auto_ptr or boost::shared_ptr but that's beyond the scope of this question. \$\endgroup\$ – Nejla Oct 28 '13 at 23:37
  • \$\begingroup\$ Right, but it could help with optimization. \$\endgroup\$ – Jamal Oct 28 '13 at 23:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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