Array on the heap

[OOzy]

Hi Gurus

How can I create 15 element array on the heap then sort it?

OOzy

 

[Cagliostro]

Do you have some troubles? If so, which ones? John Fill

ivfmd@mail.md

 

[Zyrenthian]

quick sort would be the way to go imho. You can use the built in qsort function but if you have troubles with the passing of function pointers you could always do a bubble sort. If the array size is always going to be small, you wont see that much of a performance difference. Bubble sort is the simplest sort that will traverse the array in the best case one time (array already sorted) or n-1 times in the worst case (n=# of elements; array sorted in reverse order)

Bubble sort works as follows
// n = # of elements
for(int x = 0;i<n-1;x++)
{
if(array[x]>array[x+])
{
int y = array[x];
array[x] = array[x+1];
array[x+1] = y;
}
}

This is the easiest to follow sorting algorithm and once you understand it, it can be modified to work quicker.

For each traversal of the array it moves the largest element to its proper position

Example
3,5,2,7,9,1 //start
3,2,5,7,1,9 //pass 1
2,3,5,1,7,9 //pass 2
2,3,1,5,7,9
2,1,3,5,7,9
1,2,3,5,7,9

Matt

 

[OOzy]

I am trying to write a program that create 15 elements on the heap and then sort them. I did this

const int arraySize=10;
int a [arraySize] = {102, 312, 542, 346, 158, 755, 251,...};
int *ArrayPtr = a;

then I used the bublesort idea. My function was as follow

void swap(int *elePtr1, int *elePtr2)
{
int hold = *elePtr1;
*elePtr1 = *elePtr2;
*elePtr2 = hold;
}

Am I on the right track?

 

[Zyrenthian]

yep... looks like it should work. Now incorporate the swap funciton into a loop and it should sort the array

matt

 

[Cagliostro]

void fast_swap(int& elePtr1, int& elePtr2)
{
elePtr1^=elePtr2^=elePtr1^=elePtr2;
}
John Fill

ivfmd@mail.md

 

[OOzy]

Thank you guys but someone told me that I need two
things. The first is the pointer (which I have), the second is the use of the new operator. For example: int *a = new int[Size]; But it is not working for me.

How can I use the new operator

HB

 

[Cagliostro]

if Size is an integer, in C++ it sure works. What ie the extension of file you compille, .c or .cpp? John Fill

ivfmd@mail.md

 

[rpet]

John, function &quot;fast_swap()&quot; should be &quot;slow_swap()&quot; because it is slower than the 'normal' method. Instead of 3 assignments you need 3 assignments plus 3 XORs.

-- ralf

 

[Zyrenthian]

To side with john, binary methods are lower level and should be executed quicker. I guess it depends on the compiler. However, I have not timed the execution of the process myself and would be curious what the end result was. If I have time today I will check it out.

Matt

 

[OOzy]

Hi

Again thank you all. My file is .cpp

 

[rpet]

>To side with john, binary methods are lower level and >should be executed quicker.

That's true, but you need the assignments anyway. The binary operations are just overhead. I tested it with several compilers and did not find one where xor-swap is faster. Please reply if you get different results.

-- ralf

 

[Zyrenthian]

Will do =) I may need to write it up at home. I got a product release due for Japan at the end of the month and WHOA... it is july 31 hehe...

Matt

 

[Cagliostro]

rpet, have you forgotten about *? My procedure is faster, because it works without stars, but directly. And also it does not create in stack local variables, which also takes processor time.
//fastest for using in a function
x^=y^=x^=y; John Fill

ivfmd@mail.md

 

[OOzy]

Hi Guys

I got another problem. Here is my code

const int arraySize=10;
int *ArrayPtr;
int i;
ArrayPtr = new int[arraySize];

Now how can I assign 10 element to ArrayPtr. I am lost. Do I do this:
a[]={1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
then I do
ArrayPtr=a;

Will count that I created a 10 element array on the heap?

 

[rpet]

>rpet, have you forgotten about *? My procedure is faster, because it works without stars, but directly.

MSVC produces the same code for f(int *) and f(int &).
There's no difference.

>And also it does not create in stack local variables, which also takes processor time.

That's true. Anyway, the XOR code is less efficient.
Please check out this little test program. With VC++6
(release mode) I get the following results:

elapsed xor: ~ 80
elapsed mov: ~ 58

If my test program is correct, and think it is, this shows that swap_mov() is faster. Just a little bit, but it is faster. I tested a while ago with Borland TC++ and get similar results. Please try to reproduce this, John.


#include <time.h>
#include <iostream>

void swap_xor(int &, int &);
void swap_mov(int *, int *);

const unsigned long MAX_LONG = 0xFFFFFFFFL;

int main(int argc, char ** argv, char ** envp)
{
clock_t t0;
int x = 100000, y = 45678;

t0 = clock();

for(long k=0L; k<MAX_LONG; ++k)
swap_xor(x, y);

std::cout << &quot;elapsed xor: ~ &quot; << (clock()-t0) / CLOCKS_PER_SEC << std::endl;

t0 = clock();

for(k=0L; k<MAX_LONG; ++k)
swap_mov(&x, &y);

std::cout << &quot;elapsed mov: ~ &quot; << (clock()-t0) / CLOCKS_PER_SEC << std::endl;

return 0;
}

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

void swap_mov(int * i, int * j)
{
int t = *i;
*i = *j;
*j = t;
}

 

[rpet]

>Will count that I created a 10 element array on the heap?

No. You assign the address of a[] to ArrayPtr. You should not do this because

a) ArrayPtr does not point to an array on the heap but to an array on the stack

b) The memory that you allocated using &quot;new&quot; is lost. You cannot access it because the pointer is overwritten. If you try to use delete[] ArrayPtr, you try to delete static memory and this may let your program crash.

If you want to fill a dynamic array with a pre-defined set of values you can do the following instead:


[...]
// create array on the heap
const int arraySize=10;
int * ArrayPtr = new int[arraySize];
[...]
// copy values into the array
int a[]={1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
memcpy(ArrayPtr, a, sizeof a);
[...]
// free the dynamic memory
delete[] ArrayPtr;


-- ralf

 

[Cagliostro]

rpet, did you see disassembler code? I believe not. Would you like me to put it in the forum for you to believe me? I saw it. John Fill

ivfmd@mail.md

 

[rpet]

>rpet, did you see disassembler code? I believe not.

John, I think you get me wrong. Of course I did. I compiled the test program from my previous post with Visual C++ 6, SP5 on Windows 2000. Setting: Win32 Release, Optimization: Maximize Speed. The following code is from the assembler listing. It is obvious that

a) There is no difference betwenn func(int *) and func(int &)

b) There's an overhead in swap_xor.

>Would you like me to put it in the forum for you to believe me? I saw it.

Please do it. And tell me which compiler, os and settings you have used.

regards,
-- ralf


?swap_xor@@YAXAAH0@Z PROC NEAR ; swap_xor, COMDAT

; 33 : i ^= j ^= i ^= j;

mov ecx, DWORD PTR _j$[esp-4]
mov eax, DWORD PTR _i$[esp-4]
push esi
mov edx, DWORD PTR [ecx]
mov esi, DWORD PTR [eax]
xor esi, edx
mov DWORD PTR [eax], esi
mov edx, esi
mov esi, DWORD PTR [ecx]
xor esi, edx
mov DWORD PTR [ecx], esi
mov edx, DWORD PTR [eax]
mov ecx, esi
pop esi
xor edx, ecx
mov DWORD PTR [eax], edx

; 34 : }

ret 0
?swap_xor@@YAXAAH0@Z ENDP ; swap_xor



?swap_mov@@YAXPAH0@Z PROC NEAR ; swap_mov, COMDAT

; 38 : int t = *i;
; 39 : *i = *j;

mov edx, DWORD PTR _j$[esp-4]
mov eax, DWORD PTR _i$[esp-4]
push esi
mov esi, DWORD PTR [edx]
mov ecx, DWORD PTR [eax]
mov DWORD PTR [eax], esi

; 40 : *j = t;

mov DWORD PTR [edx], ecx
pop esi

; 41 : }

ret 0
?swap_mov@@YAXPAH0@Z ENDP ; swap_mov

 

[Cagliostro]

look at my method:

50: x^=y^=x^=y;
0040B8EA mov eax,dword ptr [ebp-4]
0040B8ED xor eax,dword ptr [ebp-8]
0040B8F0 mov dword ptr [ebp-4],eax
0040B8F3 mov ecx,dword ptr [ebp-8]
0040B8F6 xor ecx,dword ptr [ebp-4]
0040B8F9 mov dword ptr [ebp-8],ecx
0040B8FC mov edx,dword ptr [ebp-4]
0040B8FF xor edx,dword ptr [ebp-8]
0040B902 mov dword ptr [ebp-4],edx
and your method:

49: int* l=&z;
0040B8E4 lea edx,[ebp-0Ch]
0040B8E7 mov dword ptr [ebp-18h],edx
52: *l=x;x=y;y=x;
0040B917 mov eax,dword ptr [ebp-18h]
0040B91A mov ecx,dword ptr [ebp-4]
0040B91D mov dword ptr [eax],ecx
0040B91F mov edx,dword ptr [ebp-8]
0040B922 mov dword ptr [ebp-4],edx
0040B925 mov eax,dword ptr [ebp-4]
0040B928 mov dword ptr [ebp-8],eax

is the same number of steps, but XOR comment is faster. John Fill

ivfmd@mail.md