Array Inversion??

[xenodamus]

Hi everybody - I'm taking my first programming class ever......online (which I wouldn't have done if I had it to do over). I'm working on this assignment and I cant get through to my instructor. Here's what he wants:

Write a program to declare and initialize the following array:

int array[] = { 10, 20, 30, 40, 50, 60 };

Now add code to the program that uses a loop to exchange the outermost pair
of element values, then the next interior pair, and so on until the innermost
pair of values is exchanged. Write the program so that it is not sensitive to
the number of elements in the array and test it on an integer array that
contains an odd number of elements. Your program may not have more than one
array. You may use a temp variable in the swapping process.

The program output should be similar to the following:

original array (element 0 first): 10 20 30 40 50 60

array after exchange (element 0 first): 60 50 40 30 20 10

NOTE: you can determine the number of elements in an array with the
following:

int array[] = { 10, 20, 30, 40, 50, 60 };
int x;
x = sizeof(array) / sizeof(array[0]);
// sizeof is a function in iostream.h

Use the sizeof() function to determine the number of elements in any arrays
that are initialized before compilation in all the following assignments. If
the number of elements is determined at run time by console input, then you
may use a counter variable to determine the number of elements in an array.

Here's what I was trying:

#include<iostream>
using namespace std;
int main() {

int array[] = { 10, 20, 30, 40, 50 };
int s = sizeof(array) / sizeof(array[0]);
int n = s - 1;
int x = 0;

while (n > s / 2) {
array[x] = array[n];
n--;
x++;
}

cout << "The inverted array is " << array[s] << endl;

system("PAUSE");
return 0;
}

But it's not giving back what I'd like..... Any insight? - And remember you're dealing with a newbie here Thanks - And sorry this is so long.

[Kheun]

You should implement a swap in your while-loop rather than a simple assignment. As a result, you only copy the result from, e.g. x[4] into x[0] and x[3] into x[1] but forgetting to do x[0] into x[4] and x[1] into x[3]. The swapping functionalities can be achieved as follows.

int temp = array[x];
array[x] = array[n];
array[n] = temp;

In addition, you shouldn't use array[s] where s = 5 for displaying the result of the last element in the array. Since array in C/C++ is always zero-based, the valid range is from 0 to 4 for a 5 elements array.

[exterminator]

iostream.h is not a standard header - use <iostream>.

sizeof is not a function - but an operator.

There is a std::swap that you can use.

If you are allowed the usage of containers - vectors have a reverse() member function that you could use to do the job.

Also, always try to encapsulate small pieces of logic into functions. Like in you code you could choose to make a swap function - one to print the array and one to fill the array and things like that instead of writing everything in main().

[xenodamus]

hmmm....I think I see what you're saying. Kinda like a triangle (1=2, 2=3, 3=1) only with.....5...points. Heh, anyway - I'll give that a try

Is that reverse() just a built in function that does what I'm looking for?

[RoboTact]

xenodamus
Debug your code. See what state your data are in on every step and what changes you get after each operation. If you are not familiar with debugger, write printing methods which print state of system every now and then. For example you could change your source so (not fixing your bugs here):

#include<iostream>
using namespace std;
int array[] = { 10, 20, 30, 40, 50 };
int size = sizeof(array) / sizeof(array[0]);

void print_array() {
  for(int i=0;i<size;++i)
    cout<<array[i]<<" ";
  cout<<endl;
}

int main() {

int s = size;
int n = s - 1;
int x = 0;

while (n > s / 2) {
cout<<"before change (n= "<<n<<", x= "<<x<<"): ";
print_array();
array[x] = array[n];
cout<<"after change: ";
print_array();
n--;
x++;
}

cout << "The inverted array is ";
print_array();

system("PAUSE");
return 0;
}

There is a std::swap that you can use.

If you are allowed the usage of containers - vectors have a reverse() member function that you could use to do the job.

Also, always try to encapsulate small pieces of logic into functions. Like in you code you could choose to make a swap function - one to print the array and one to fill the array and things like that instead of writing everything in main().

I think it's definately too much for "first programming lesson ever with instructor who says that sizeof() is function from iostream.h".

[Kheun]

I am thinking the same here. Since it is a homework, it is a good execrise to implement the function yourself than using an existing function.

[GeoRanger]

You might not care about this, but I'll post it here in case you are interested.

A really neat trick exists by which you can swap two values without going through a temporary variable. It relies on bit manipulation using XOR.

int a, b;

// assign values to a and b.

// Swap starts here
a = a ^ b;      // a ^= b;
b = a ^ b;      // b ^= a;
a = a ^ b;      // a ^= b;
// Swap ends here

To see how it works, imagine the four possible combinations of pairs of bits, where one bit of each pair is in a and one bit of each pair is in b.

a = 1010 // binary number
b = 1100 // binary number

Now watch what happens at each step.

a ^= b;
// Result a = 0110
//        b = 1100
b ^= a;
// Result a = 0110
//        b = 1010
a ^= b;
// Result a = 1100
//        b = 1010

This trick does have one pitfall. You have to make sure you are not using it in an algorithm where a memory location will be swapped with itself because array[i] ^ array[j] == 0 if i == j. If this could happen you want to use a temporary variable.

I think this trick might have come from MIT's AI lab. Their people had a list of tricks and problems collectively refererred to as HAKMEM. See <http://www.inwap.com/pdp10/hbaker/hakmem/hakmem.html>.

Cheers,
GeoRanger

[SuperKoko]

A really neat trick exists by which you can swap two values without going through a temporary variable. It relies on bit manipulation using XOR.

It is a funny trick, but not a neat trick!
At best, it won't change the program's speed.
At worst, it will reduce the program's speed, and may introduce bugs.
Moreover it only works with integers!

That you see no temporary variable doesn't mean that there are none!
In fact, a^=b, needs at least a temporary register for the value of b.
This trick avoid the explicit declaration of an automatic variable. That's fun, but useless.

This trick is inefficient for compilers supporting temporaries in registers!
Moreover if a and b may be aliases, not only it behaves incorrectly, but also it reduces the possibilities of compiler optimization (the work can't be done in registers)!

[SuperKoko]

These routines:

void swapf(int& a,int& b)
{
int c=a;
a=b;
b=c;
}
void swap(int& a,int &b)
{
a^=b;
b^=a;
a^=b;
}

Generate this code with g++ --g O3 -mtune=k6-2 -march=k6-2 -fomit-frame-pointer (GCC 4.1.0):

// swapf
0x08048420 <_Z5swapfRiS_+0>:    push   ebx
0x08048421 <_Z5swapfRiS_+1>:    mov    edx,DWORD PTR [esp+8]
0x08048425 <_Z5swapfRiS_+5>:    mov    ecx,DWORD PTR [esp+12]
0x08048429 <_Z5swapfRiS_+9>:    mov    ebx,DWORD PTR [edx]
0x0804842b <_Z5swapfRiS_+11>:   mov    eax,DWORD PTR [ecx]
0x0804842d <_Z5swapfRiS_+13>:   mov    DWORD PTR [edx],eax
0x0804842f <_Z5swapfRiS_+15>:   mov    DWORD PTR [ecx],ebx
0x08048431 <_Z5swapfRiS_+17>:   pop    ebx
0x08048432 <_Z5swapfRiS_+18>:   ret    ; 9 CPU cycles (and 2 CPU cycles could be saved on 64 bits machines)

// swap
0x08048440 <_Z4swapRiS_+0>:     mov    ecx,DWORD PTR [esp+4]
0x08048444 <_Z4swapRiS_+4>:     mov    edx,DWORD PTR [esp+8]
0x08048448 <_Z4swapRiS_+8>:     mov    eax,DWORD PTR [ecx] ;3
0x0804844a <_Z4swapRiS_+10>:    xor    eax,DWORD PTR [edx] ; 5
0x0804844c <_Z4swapRiS_+12>:    mov    DWORD PTR [ecx],eax ;6
0x0804844e <_Z4swapRiS_+14>:    xor    eax,DWORD PTR [edx]
0x08048450 <_Z4swapRiS_+16>:    mov    DWORD PTR [edx],eax ;9
0x08048452 <_Z4swapRiS_+18>:    xor    DWORD PTR [ecx],eax ;11
0x08048454 <_Z4swapRiS_+20>:    ret    ;12 CPU cycles

But, on pentium CPU, the difference is even greater:

// swapf
0x08048410 <_Z5swapfRiS_+0>:    push   ebx ; 1
0x08048411 <_Z5swapfRiS_+1>:    mov    edx,DWORD PTR [esp+8]
0x08048415 <_Z5swapfRiS_+5>:    mov    ecx,DWORD PTR [esp+12] ; 2
0x08048419 <_Z5swapfRiS_+9>:    mov    ebx,DWORD PTR [edx] ; AGI stall ; 4 (I think a nop operation could save 1 cycle).
0x0804841b <_Z5swapfRiS_+11>:   mov    eax,DWORD PTR [ecx]
0x0804841d <_Z5swapfRiS_+13>:   mov    DWORD PTR [edx],eax ;5
0x0804841f <_Z5swapfRiS_+15>:   mov    DWORD PTR [ecx],ebx ; 6
0x08048421 <_Z5swapfRiS_+17>:   pop    ebx ; 7
0x08048422 <_Z5swapfRiS_+18>:   ret    ; 8

// swap
0x08048430 <_Z4swapRiS_+0>:     mov    ecx,DWORD PTR [esp+4]
0x08048434 <_Z4swapRiS_+4>:     mov    edx,DWORD PTR [esp+8] ;1
0x08048438 <_Z4swapRiS_+8>:     mov    eax,DWORD PTR [ecx] ; AGI stall ; 3
0x0804843a <_Z4swapRiS_+10>:    xor    eax,DWORD PTR [edx] ; 5
0x0804843c <_Z4swapRiS_+12>:    mov    DWORD PTR [ecx],eax
0x0804843e <_Z4swapRiS_+14>:    xor    eax,DWORD PTR [edx] ; 7
0x08048440 <_Z4swapRiS_+16>:    mov    DWORD PTR [edx],eax
0x08048442 <_Z4swapRiS_+18>:    mov    edx,DWORD PTR [ecx] ;8
0x08048444 <_Z4swapRiS_+20>:    xor    edx,eax ;9
0x08048446 <_Z4swapRiS_+22>:    mov    DWORD PTR [ecx],edx ;10
0x08048448 <_Z4swapRiS_+24>:    ret    ; 11

In inline code (or with a less good optimizer) , these speed differences may be greater.

[LanTHrusteR]

If you are allowed the usage of containers - vectors have a reverse() member function that you could use to do the job.

Reversing vectors is not efficient. That is the reason why standard vector doesn't have reverse member function and std::list does.

Unfortunately the source data is a C style array and I don't see anything more simplier and efficient than the methods proposed above.... may be you do.

I thought at first that std::reverse(array[0],array[n]); could do the job efficiently but I was wrong.

He would have to first copy the array into std::lilst than reverse it and then copy back. That is so inefficient.

[exterminator]

Reversing vectors is not efficient. That is the reason why standard vector doesn't have reverse member function and std::list does.

Correct, the reverse is probably just a member in microsoft implementations. I did not find it in the standards.. or Dinkumware implementation. However, as far as efficiency is concerned - I am not sure that it would be really bad considering we are using the swap mechanism with the array.

However, the vector might not actually need to be reverse at all. One could always use the reverse_iterator whenever a reverse vector is to be used. One can also mimic this behaviour with C-style arrays. And since the OP is only doing that to print to the standard output.. this is the best way to go.. without even actually doing the reverse unless that is a rigid requirement. Regards.

[GeoRanger]

It is a funny trick, but not a neat trick!
At best, it won't change the program's speed.
At worst, it will reduce the program's speed, and may introduce bugs.

These objections are practical, certainly, and ultimately we are all concerned with what's going to happen when the rubber meets the road. From other perspectives though, I sometimes find the theoretical to be interesting. Moreover, principles don't change when practical implementations do.

Moreover it only works with integers!

...but data in a digital computer is just a bunch of 0s and 1s. Those 0s and 1s could be an integer, text, music, or a picture. Consider the probably not portable code sample below...

    double d1 = 5, d2 = 3;
    (*reinterpret_cast<__int64 *>(&d1)) ^= (*reinterpret_cast<__int64 *>(&d2));
    (*reinterpret_cast<__int64 *>(&d2)) ^= (*reinterpret_cast<__int64 *>(&d1));
    (*reinterpret_cast<__int64 *>(&d1)) ^= (*reinterpret_cast<__int64 *>(&d2));

That you see no temporary variable doesn't mean that there are none!
In fact, a^=b, needs at least a temporary register for the value of b.
This trick avoid the explicit declaration of an automatic variable. That's fun, but useless.

If the data you are swapping comes from memory, the compiler will have to fetch it and put it somewhere where the processor can operate on it, regardless of how you actually perform the swap. If the compiler decides to put it in registers, the actual swap could in principal be as simple as the C code implies consder...

    __asm
    {
        mov eax, 5
        mov ebx, -984
        xor eax, ebx
        xor ebx, eax
        xor eax, ebx
    }

These routines:
Code:

void swapf(int& a,int& b)
{
int c=a;
a=b;
b=c;
}
void swap(int& a,int &b)
{
a^=b;
b^=a;
a^=b;
}

On a different note, isn't it best to avoid using references in a function like this? Wouldn't "void swap(int * a, int * b)" make clearer at the point where this function is invoked that a and b might be altered. I try to limit my use of references to places where they are really needed, such as when overriding some operator or in a copy constructor.

We have some code in use where I work that was written before a certain gigantic software company's version of the STL was useable. This code implements its own queues and vectors, but unfortantly the function to enqueue something takes its argument as a reference. We don't have to look at this code often enough to remember how it works, and more than once we have we have thought we have stumbled onto a memory leak because we will see something like this...

if (pThing != NULL)
{
    Node * pNode = new Node;
    pNode->data = pThing;
    queue.enque(*pNode);  // So enqueue makes a copy of pNode?
    // memory leak?  Where is pNode deleted if not here since it has local scope?
}

What is totally unobvious is that enqueue internally generates a pointer to the reference and stores it. pNode gets deleted later when it is dequeued. But all of this would be much more obvious if enqueue accepted the non-const pointer instead of a reference.

Cheers,
GeoRanger

[SuperKoko]

...but data in a digital computer is just a bunch of 0s and 1s. Those 0s and 1s could be an integer, text, music, or a picture. Consider the probably not portable code sample below...

Did you ever heard of non-POD types?

If the data you are swapping comes from memory, the compiler will have to fetch it and put it somewhere where the processor can operate on it, regardless of how you actually perform the swap. If the compiler decides to put it in registers, the actual swap could in principal be as simple as the C code implies consder...

    __asm
    {
        mov eax, 5
        mov ebx, -984
        xor eax, ebx
        xor ebx, eax
        xor eax, ebx
    }

Which is excessively slow : 3 CPU cycles! Absolutely not parallelizable!

While, with an intermediate temporary, a good compiler (I tested with GCC 3.2.3) may even produces no operation, and simply "rename" the variables as far as possible!
Or, a bad compiler, will simply generate:

mov edx,eax
mov eax,ebx ; 1 cycle (k6-2 processor)
mov ebx,edx ; 0.5 cycle (I mean that it can be paired with the next instruction)

But, a good compiler will often find "tricks" to optimize!

For example, with GCC 3.2.3:

#include <stdio.h>

void Swap(int& i,int& j)
{
int k=i;
i=j;
j=i;
}
int input();
int main()
{
int i,j;
i=input(); j=input();
if (input()) Swap(i,j);
printf("%d %d", i, j);
return 0;
}

#include <stdio.h>
int input()
{
int w;
scanf("%d",&w);
return w;
}

Produces:

0x401307 <main+23>:     call   0x401370 <_Z5inputv>
0x40130c <main+28>:     mov    esi,eax
0x40130e <main+30>:     call   0x401370 <_Z5inputv>
0x401313 <main+35>:     mov    ebx,eax
0x401315 <main+37>:     call   0x401370 <_Z5inputv>
0x40131a <main+42>:     test   eax,eax
0x40131c <main+44>:     je     0x401320 <main+48>
0x40131e <main+46>:     mov    esi,ebx
0x401320 <main+48>:     push   eax
0x401321 <main+49>:     push   ebx
0x401322 <main+50>:     push   esi
0x401323 <main+51>:     push   0x4012e1
0x401328 <main+56>:     call   0x401870 <printf>
0x40132d <main+61>:     lea    esp,[ebp-8]
0x401330 <main+64>:     pop    ebx
0x401331 <main+65>:     mov    eax,0x0
0x401336 <main+70>:     pop    esi
0x401337 <main+71>:     leave
0x401338 <main+72>:     ret

In fact, the swap operation itself has a cost of 1 CPU cycle (on a k6-2 processor), in the worst case, and none if input() returns zero!

Seriously, variable assignment are perfectly understood by the compier in the normal control flow of a program!

With that swap:

void Swap(int& i,int& j)
{
i^=j;
j^=i;
i^=j;
}

The compiler has been smart enough and understood that it has been written by a .... "optimizing" programmer...

0x401307 <main+23>:     call   0x401370 <_Z5inputv>
0x40130c <main+28>:     mov    esi,eax
0x40130e <main+30>:     call   0x401370 <_Z5inputv>
0x401313 <main+35>:     mov    ebx,eax
0x401315 <main+37>:     call   0x401370 <_Z5inputv>
0x40131a <main+42>:     test   eax,eax
0x40131c <main+44>:     je     0x401320 <main+48>
0x40131e <main+46>:     xchg   esi,ebx
0x401320 <main+48>:     push   eax
0x401321 <main+49>:     push   ebx
0x401322 <main+50>:     push   esi
0x401323 <main+51>:     push   0x4012e7
0x401328 <main+56>:     call   0x401870 <printf>
0x40132d <main+61>:     lea    esp,[ebp-8]
0x401330 <main+64>:     pop    ebx
0x401331 <main+65>:     mov    eax,0x0
0x401336 <main+70>:     pop    esi
0x401337 <main+71>:     leave
0x401338 <main+72>:     ret

But, on a less good optimizer (Borland C++ 5.0), the normal swap operation is translated to:

:00401169 8BC3           mov    eax,ebx
:0040116B 8BDE           mov    ebx,esi ; 1
:0040116D 8BF0           mov    esi,eax

:0040116F 56             push   esi ;2 (k6-2 has special optimization for mov operations, known as register renaming).
:00401170 53             push   ebx ; 3
:00401171 6834D14000     push   0040D134 ;4
:00401176 E84D2C0000     call   printf

While, the xor stuff, generate this code:

:00401169 33DE           xor    ebx,esi ;1
:0040116B 33F3           xor    esi,ebx ; 2
:0040116D 33DE           xor    ebx,esi
:0040116F 56             push   esi ;3
:00401170 53             push   ebx ;4
:00401171 6834D14000     push   0040D134 ; 5
:00401176 E84D2C0000     call   printf

In short, the swap operation used 2.5 cycles instead of 1.5 !

On a different note, isn't it best to avoid using references in a function like this? Wouldn't "void swap(int * a, int * b)" make clearer at the point where this function is invoked that a and b might be altered. I try to limit my use of references to places where they are really needed, such as when overriding some operator or in a copy constructor.

Do you come from a C background?

I used the cannonical syntax of the standard library (std::swap), all C++ programmers can understand that perfectly, since they are used to std::swap!

In fact, std::swap is the best candidate for optimization, since the compiler is free to create optimizations specifically for that function.

What is totally unobvious is that enqueue internally generates a pointer to the reference and stores it. pNode gets deleted later when it is dequeued. But all of this would be much more obvious if enqueue accepted the non-const pointer instead of a reference.

Here, a reference is not natural, because it is a "pointer sink". But for std::swap, it is natural (at least from the point-of-view of a C++ programmer). std::swap does not delete the data!
In fact, since it is a pointer sink, a std::auto_ptr would be very natural, and implicitly documents perfectly that the function "gets ownership" of the data.

There is a thread about references vs pointers.
http://www.codeguru.com/forum/showth...=383452&page=1

[Mitsukai]

duuuuuuuuudesss, swap sounds VERY BAD!!! i mean swap?? no need to swap !!
create a new array copy old array reversed to the new array destroy old array and set the old array pointer to the new array pointer. and thats it. dont you think its HECK ALOT faster than swapping all vars??

[Paul McKenzie]

create a new array copy

That in itself takes time to allocate the memory. What if you wanted to swap 100,000 items?

and set the old array pointer to the new array pointer

What if you don't have a pointer, and instead you only have a reference to the buffer that is being swapped?

Regards,

Paul McKenzie