macOS Array "quiz the forum" question

[lazydog]

Todd, those numbers make my PB look sweet

Well I'm not sure what I've learnt from this exercise except perhaps it's time to upgrade my Mac.

b e n

 

[toddburch]

Did anyone else notice that with each iteration, the number of recursive calls increased by a power of 2? Each iteration is a increasing power of 2 minus one.

Todd

 

[lazydog]

Did anyone else notice that with each iteration, the number of recursive calls increased by a power of 2? Each iteration is a increasing power of 2 minus one.

I think that pattern result from these lines.

if ( a[ size - 1 ] <= a[ reduce_array_recursive( a , size - 1, count ) - 1 ] )
		return reduce_array_recursive( a , size - 1, count ) ;

if ( length_reduced_list == size - 1 )
		return size ;

In most cases the list is reduced and so the first if fails and the second succeeds. If the first if succeeds, there is still a second recursize call. Hence the ^2 pattern.

On the occasions that both ifs fails then you get an extra 2 recursive calls.


I'm not sure where the -1 comes in though!

b e n

 

[After G]

Here, for fun, is a Mac mini (Intel).

[Session started at 2007-07-24 19:29:04 -0700.]
1) : 0s, 1 calls, list : 1 
2) : 0s, 3 calls, list : 1 2 
3) : 0s, 7 calls, list : 1 2 4 
4) : 0s, 15 calls, list : 1 2 4 5 
5) : 0s, 31 calls, list : 1 2 4 5 7 
6) : 0s, 63 calls, list : 1 2 4 5 7 9 
7) : 0s, 127 calls, list : 1 2 4 5 7 9 11 
8) : 0s, 255 calls, list : 1 2 4 5 7 9 11 12 
9) : 0s, 511 calls, list : 1 2 4 5 7 9 11 12 13 
10) : 0s, 1023 calls, list : 1 2 4 5 7 9 11 12 13 14 
11) : 0s, 2047 calls, list : 1 2 4 5 7 9 11 12 13 14 
12) : 0s, 8189 calls, list : 1 2 4 5 7 9 11 12 13 14 15 
13) : 0s, 20475 calls, list : 1 2 4 5 7 9 11 12 13 14 15 17 
14) : 0s, 45049 calls, list : 1 2 4 5 7 9 11 12 13 14 15 17 18 
15) : 0s, 94199 calls, list : 1 2 4 5 7 9 11 12 13 14 15 17 18 19 
16) : 0s, 126967 calls, list : 1 2 4 5 7 9 11 12 13 14 15 17 18 19 
17) : 0s, 323573 calls, list : 1 2 4 5 7 9 11 12 13 14 15 17 18 19 20 
18) : 1s, 716787 calls, list : 1 2 4 5 7 9 11 12 13 14 15 17 18 19 20 21 
19) : 0s, 978931 calls, list : 1 2 4 5 7 9 11 12 13 14 15 17 18 19 20 21 
20) : 0s, 2.55179e+06 calls, list : 1 2 4 5 7 9 11 12 13 14 15 17 18 19 20 21 22 
21) : 0s, 3.60037e+06 calls, list : 1 2 4 5 7 9 11 12 13 14 15 17 18 19 20 21 22 
22) : 0s, 5.69752e+06 calls, list : 1 2 4 5 7 9 11 12 13 14 15 17 18 19 20 21 22 
23) : 0s, 1.82804e+07 calls, list : 1 2 4 5 7 9 11 12 13 14 15 17 18 19 20 21 22 24 
24) : 1s, 4.34463e+07 calls, list : 1 2 4 5 7 9 11 12 13 14 15 17 18 19 20 21 22 24 26 
25) : 1s, 9.37779e+07 calls, list : 1 2 4 5 7 9 11 12 13 14 15 17 18 19 20 21 22 24 26 28 
26) : 3s, 1.27332e+08 calls, list : 1 2 4 5 7 9 11 12 13 14 15 17 18 19 20 21 22 24 26 28 
27) : 5s, 3.28659e+08 calls, list : 1 2 4 5 7 9 11 12 13 14 15 17 18 19 20 21 22 24 26 28 30 
28) : 13s, 7.31312e+08 calls, list : 1 2 4 5 7 9 11 12 13 14 15 17 18 19 20 21 22 24 26 28 30 32 
29) : 27s, 1.53662e+09 calls, list : 1 2 4 5 7 9 11 12 13 14 15 17 18 19 20 21 22 24 26 28 30 32 34 
30) : 37s, 2.07349e+09 calls, list : 1 2 4 5 7 9 11 12 13 14 15 17 18 19 20 21 22 24 26 28 30 32 34 
31) : 93s, 5.29471e+09 calls, list : 1 2 4 5 7 9 11 12 13 14 15 17 18 19 20 21 22 24 26 28 30 32 34 36 
32) : 205s, 1.17372e+10 calls, list : 1 2 4 5 7 9 11 12 13 14 15 17 18 19 20 21 22 24 26 28 30 32 34 36 37 

Array has exited with status 0.

Pretty good ... all things considered

 

[MongoTheGeek]

I did a quick test and found that for the cost of an int even the largest runs are vanishingly fast.

 

[lazydog]

I did a quick test and found that for the cost of an int even the largest runs are vanishingly fast.

Is this in the recursive version?

b e n

 

[MongoTheGeek]

Is this in the recursive version?

b e n

Yes. I sent an int to the first call of reduce_array_recursive and replaced all of the calls except for the last one with the int since only the first and last would actually change anything.

 

[lazydog]

That's strange, I've just tried and it's still taking over 200s for the last run.. better than to 350s from before though.

This is what I've got:-

int reduce_array_recursive_int( int a[], size_t size, long long & count )
{
	count ++ ;
	
	if ( size == 1 )
		return size ;
		
	int reduced_size = reduce_array_recursive( a , size - 1, count ) ;
	
	if ( a[ size - 1 ] <= a[ reduced_size - 1 ] )
		return reduced_size ;

	if ( reduced_size == size - 1 )
		return size ;
	
  	a[ reduced_size  ] = a[ size - 1 ] ;

	return reduced_size + 1 ;
}

I even took out the call on the last line.

b e n

 

[MongoTheGeek]

That's strange, I've just tried and it's still taking over 200s for the last run.. better than to 350s from before though.

This is what I've got:-

When I ran that it ran for 0s with 32 recursive calls.

 

[lazydog]

I'm an idiot, I was calling the old function reduce_array_recursive from the new one reduce_array_recursive_int!

b e n