macOS Array "quiz the forum" question

[SilentPanda]

So one of my co-workers asked me this question and neither he nor I can figure it out... but apparently he was asked this question in an interview a while back... so I figured I'd ask the very smart people at MacRumors... The language doesn't matter too much but this is one of those "general" questions so it probably shouldn't use some super proprietary stuff or things like "Array.removeDuplicatesAndDontUseMoreMemory(a)".

Suppose you have an integer array a of size n that is ordered but has duplicates. For example a = [0, 0, 0, 2, 3, 3, 5, 5, 5, 7, 9, 9] (n = 12). Write a function that removes the duplicates, and then returns the new size. In above example, a becomes [0, 2, 3, 5, 7, 9] and the function returns 6. Do it in-space, meaning no extra memory space should be allocated to store intermediate or final results.

The kicker is that last part... it's a very easy question if you can use an int or two to store the current index... but without that... is there something I'm missing or is the question just junk? Keep in mind the array could come in at any length with any items... it is a sorted, positive integer array though. But it might look like [15, 20, 30, 40, 40, 40, 542214].

My figuring is that once you've checked for a.length = 1 you could access the 1st and last indexes... the 2nd index might be another safe index but otherwise you're stuck with those I think. I also thought about using a known index to store the current index but if the array is already stripped of duplicates that doesn't work either.

Also keep in mind the question asks that the duplicates be removed and the size be returned.

Brain... broken. Now I'll be sad when the next 20 people answer it in seconds.

You get an honorary bamboo sheriffs badge for figuring it out.*

* Offer not valid.

 

[toddburch]

In Ruby:

non_dup_length = myarray.uniq.length

Todd

 

[robbieduncan]

Are you sure you are not allowed any temporary variables at all? I'm not sure it's possible to remove an item from the middle of a C array without at least 1 or 2...

 

[SilentPanda]

In Ruby:

non_dup_length = myarray.uniq.length

Todd

That might be too language specific. But that's a sweet way of doing it! It looks like you might have to do:

myarray.uniq!.length so that it removes the duplicates from itself instead of needing to assign it to a new array.

Are you sure you are not allowed any temporary variables at all? I'm not sure it's possible to remove an item from the middle of a C array without at least 1 or 2...

That's what we're thinking. Without temp variables it seems... impossible. Or a waste of brain power to figure it out. I say just buy more memory and use temp vars.

 

[lazydog]

How about this!

#include <iostream>

void print_array( int* a, size_t size )
{
	std::cout << std::endl ;

	for ( size_t i = 0 ; i < size ; ++ i )
		std::cout << a[ i ] << " " ;
		
	std::cout << std::endl ;
}

int reduce_array( int* a, size_t size )
{
	int *b = a + 1 ;
	
	for ( int i = 1 ; i < size ; ++ i )
		if ( a[ i ] != a[ i - 1 ] )
			*b++ = a[ i ] ;
		
	return b - a ;
}

int test_array[] = { 0, 0, 0, 2, 3, 3, 5, 5, 5, 7, 9, 9 } ;


int main (int argc, char * const argv[])
{

	print_array( test_array, 12 ) ;

	print_array( test_array, reduce_array( test_array, 12 ) ) ;
	
    return 0;
}

b e n

 

[toddburch]

I believe, but haven't tested it, that if the uniq! method is called, and there are not duplicates, nil is returned, and the .length will fail.

Perhaps it's a trick question. Perhaps the emphasis was on "temporary variables" to get you thinking about "variables" and "allocated storage", and purposely lead you away from a valid answer of.... drum roll please... use registers!

Todd

 

[SilentPanda]

How about this!

#include <iostream>
 [b]SNIP![/b]
}

b e n

In memory! It's easy if you use more memory.

I believe, but haven't tested it, that if the uniq! method is called, and there are not duplicates, nil is returned, and the .length will fail.

Perhaps it's a trick question. Perhaps the emphasis was on "temporary variables" to get you thinking about "variables" and "allocated storage", and purposely lead you away from a valid answer of.... drum roll please... use registers!

Todd

Yeah... that's true. If the array is already unique the .length call will fail. So if you do .uniq! on an array and there are no duplicates, you lose your array? That seems odd but I've done very little ruby. It seems like .uniq returns an array whereas .uniq! either replaces your current array or makes your current array nil.

 

[lazydog]

In memory! It's easy if you use more memory.

Do it in-space, meaning no extra memory space should be allocated to store intermediate or final results.

Just my opinion, but the spirit of the question is simply to reduce the array without using a duplicate array or a counter for the size, which I haven't. If you want to be pendantic then any solution uses extra memory.

b e n

 

[toddburch]

So if you do .uniq! on an array and there are no duplicates, you lose your array?

No. When the result of the .uniq! is nil - the array is still intact, and you have (already had) your answer. When uniq! works because there were dups, myarray does change and becomes [0,2,3,5,7,9].

Todd

 

[iSee]

In memory! It's easy if you use more memory.

LazyDog's reduce_array() does the reduction in-place. I think you misunderstand what the limitation means.

 

[iSee]

The confusion might be coming from the term "in-space" in the quote of the original question. I've never heard that term before in this context. They almost surely mean "in-place" which has a fairly common definition.

Here's a Wikipedia article on it: http://en.wikipedia.org/wiki/In-place_algorithm.

To be a little more formal, memory allocation for an in-place algorithm is O(1) as opposed to O(n) (where n is the length of the array). That is, it requires the same amount of memory regardless of the size of the array.

 

[SilentPanda]

LazyDog's reduce_array() does the reduction in-place. I think you misunderstand what the limitation means.

The confusion might be coming from the term "in-space" in the quote of the original question. I've never heard that term before in this context. They almost surely mean "in-place" which has a fairly common definition.

I think you guys are correct. It was explained to me that no other variables could be used and that the example solution that had been made was incorrect by the interviewer even though it was in space as the true definition was. Maybe the interviewer had no idea what they were talking about. After reading the wikipedia it makes a lot more sense.

Bamboo badges all around!

 

[iSee]

I think you guys are correct. It was explained to me that no other variables could be used and that the example solution that had been made was incorrect by the interviewer even though it was in space as the true definition was. Maybe the interviewer had no idea what they were talking about. After reading the wikipedia it makes a lot more sense.

Bamboo badges all around!

Yeah.

When you get right down to it, calling a function at all uses stack space (at the very least) for the parameters, return address, etc.

I guess the idea of using registers and making the it an inline function (to avoid the function call memory usage) technically fits the bill.

 

[lazydog]

Okay, just spent the last couple of hours bending my brain. This one doesn't use any extra variables etc. Instead it uses recursion… but like iSee points out, it blows memory usage out the window because of it's use of the stack.
Anyway… kudos to anyone who could solve this problem in an interview!

int reduce_array( int a[], size_t size )
{
	if ( size == 1 )
		return size ;
		
	if ( a[ size - 1 ] <= a[ reduce_array( a , size - 1 ) - 1 ] )
		return reduce_array( a , size - 1 ) ;

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

	return reduce_array( a , size - 1 ) ;
	
}

b e n

 

[sherpa78]

lazydog: Wow. You are the man! I was just about to post my solution, when I came across your recursive one. Phew! Hadn't had a chance to read/understand it so that I can try to come up with a recursive solution myself. It's an awesome solution without using any temp variables.

Anyhow, here's my solution:

#include <iostream>
using namespace std;

int reduceInSpace(int *array, int size)
{
   int lastPos=0, curPos=lastPos+1;
   for (;curPos<size; ++curPos)
   {
      if (array[lastPos] == array[curPos])
         continue;

      array[++lastPos] = array[curPos];
   }
   return lastPos+1;
}

void printArray(int *array, int size)
{
   cout << "[ ";
   for (int i=0; i<size-1; ++i)
   {
      cout << array[i] << ", ";
   }
   cout << array[size-1] << " ]";
}

int main(void)
{
   int array[]={0,0,0,2,3,3,5,5,5,7,9,9};
   int size=sizeof(array)/sizeof(int);

   cout << "Prior to reduction" << endl;
   cout << "\tSize of array = " << size << endl;
   cout << "\tarray = "; printArray(&array[0], size); cout << endl;

   size = reduceInSpace(&array[0], size);

   cout << "After reduction" << endl;
   cout << "\tSize of array = " << size << endl;
   cout << "\tarray = "; printArray(&array[0], size); cout << endl;

   return 0;
}

I believe "in-place" algorithms allow for "bookkeeping" storage, as long as the memory it takes is constant. In this case, my reduceInPlace function (disregarding stack space taken by functional call) adds an additional 8 bytes (at least, on a 32-bit machine).

-sherpa78


EDIT: opps.... saw that iSee has already posted the information about in-place algorithms.

 

[lazydog]

Hi sherpa78
Although the recursive solution doesn't declare any additional variables it really does use them, lots more - they're just hidden on the stack, 1 per array element I think.

Out of curisoity I put a counter in to see how many times reduce_array_recursive() is called. For a list with 32 numbers it totally blew away an int - I had to go to long long for it to run! That's the first time I've ever had to use a long long! On my aging Powerbook G4 it took 320 seconds and over 17,000,000,000 calls to reduce_array_recursive() to sort this list:-

#define MAX_SIZE ( 32 )

int fixed_array[ MAX_SIZE ] = { 1, 2, 4, 5, 7, 9, 11, 12, 13, 14, 14, 15, 17, 18, 19, 19, 20, 21, 21, 22, 22, 22, 24, 26, 28, 28, 30, 32, 34, 34, 36, 37 };

I would love to know how long it would take on an Intel iMac as I'm going to get one soon… hopefully!

b e n

 

[toddburch]

Ben, put the timing code in the program and I'l be happy to run it on both my 2.1ghz 2GB ram Macbook and my 3ghz 2gbram MacPro.

Todd

 

[lazydog]

You're a star Todd!

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


//
// Return a list of numbers as a formatted string.
//
std::string array_as_str( int a[], size_t size )
{	
	std::ostringstream str ;
	
	for ( size_t i = 0 ; i < size ; ++ i )
		str << a[ i ] << " " ;
		
	return str.str() ;
}

int reduce_array( int* a, size_t size )
{
	if ( size == 1 )
		return 1 ;
		
	int temp_size =  reduce_array( a , size - 1 ) ;	
	
	if ( a[ size - 1 ] == a[ temp_size - 1 ] )
		return temp_size ;
		
		a[ temp_size ] = a[ size - 1 ] ;
		temp_size ++ ;
	
	return temp_size ;
}

//
// Reduce a list of numbers and return its size.
// The function is used in two ways, the first is to reduce the specified list.
// The other is to count the size of a list which has already been reduced.
//
int reduce_array_recursive( int a[], size_t size, long long & count )
{
	//
	// Count the number of times the function is entered.
	//
	count ++ ;
	
	if ( size == 1 )
		return size ;
		
	//
	// Compare the last number in this list to the last number in the reduced list.
	// If it's the same or less then there is nothing to do except return the
	// length of the reduced list.
	//
	if ( a[ size - 1 ] <= a[ reduce_array_recursive( a , size - 1, count ) - 1 ] )
		return reduce_array_recursive( a , size - 1, count ) ;

	//
	// The number at the head of this list needs to be moved to the
	// end of the reduced list. If the length of this list is the same
	// as the length of the reduced list then the number is already at the end
	// of the reduced list and so there is nothing to do.
	//
	if ( reduce_array_recursive( a , size - 1, count ) == size - 1 )
		return size ;
	
	//
	// The reduced list is smaller than this list, so the number needs
	// to be appended to reduced list.
	//
  	a[ reduce_array_recursive( a , size - 1, count )  ] = a[ size - 1 ] ;

	//
	// All done, just need to return the length of the reduced list.
	//
	return reduce_array_recursive( a , size - 1, count ) ;
}

//
// Fill an array with a random list of numbers.
//
void fill_array( int a[], unsigned long seed, size_t size )
{
	srandom( seed ) ;
	
	a[ 0 ] = random() % 3 ;
	
	for ( int i = 0 ; i < size ; ++ i )
		a[ i ] = random() % 3 + a[ i - 1 ] ;
}

//
// Copy one list of numbers to another.
//
void copy_array( int a[], int b[], size_t size )
{
	for ( int i = 0 ; i < size ; ++ i )
		b[ i ] = a[ i ] ;
}

//
// Always use the same list of number for different machines.
//
#define MAX_SIZE ( 32 )

int fixed_array[ MAX_SIZE ] = { 1, 2, 4, 5, 7, 9, 11, 12, 13, 14, 14, 15, 17, 18, 19, 19, 20, 21, 21, 22, 22, 22, 24, 26, 28, 28, 30, 32, 34, 34, 36, 37 };

int main (int argc, char * const argv[])
{
	//
	// Time how long it takes to reduce fixed_array in steps.
	//
	for ( int i = 1 ; i <= MAX_SIZE ; ++ i ) 
	{
		//
		// Counter used to keep track of the number
		// of times reduce_array_recursive() is entered.
		//
		long long count = 0 ;
		
		//
		// Use a temporary array for each step reduction.
		//
		int test_array[ MAX_SIZE ] ;
		copy_array( fixed_array, test_array, i ) ;
		
		//
		// Time the reduction for this step size.
		//
		time_t start_time, end_time ;
		time( & start_time ) ;
		
		int size = reduce_array_recursive( test_array, i, count ) ;
		
		time( & end_time ) ;
		
		//
		// That's it.
		//
		std::cout << i << ") : " << ( end_time - start_time ) << "s, " << static_cast<float>( count ) << " calls, list : " << array_as_str( test_array, size ) << std::endl ;
	}
	
    return 0;
}

It should be okay to compile as a C++ command line tool in xcode.

many thanks

b e n

 

[toddburch]

Here you go. Glad I could help. How do these times compare with your G4?

[Session started at 2007-07-23 10:58:16 -0500.]
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) : 0s, 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) : 0s, 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) : 1s, 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) : 3s, 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) : 6s, 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) : 13s, 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) : 18s, 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) : 45s, 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) : 100s, 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 

lazydog_times has exited with status 0.

Todd
(edit - that's the MacPro. Now I'll do it on the Macbook.)

 

[toddburch]

Here are the Macbook times. Sure made the fan kick on!!

Todd

[Session started at 2007-07-23 11:11:49 -0500.]
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) : 0s, 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) : 2s, 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) : 4s, 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) : 9s, 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) : 18s, 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) : 25s, 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) : 63s, 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) : 140s, 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 

deleteme has exited with status 0.

 

[gnasher729]

I think you guys are correct. It was explained to me that no other variables could be used and that the example solution that had been made was incorrect by the interviewer even though it was in space as the true definition was. Maybe the interviewer had no idea what they were talking about. After reading the wikipedia it makes a lot more sense.

An interview is two-way. If you are in an interview, and the interviewer wants to get the "correct" answers to some trick questions, then you might come to the conclusion that maybe you don't really want that job. So if you come up with a perfectly fine solution like lazydog did, and you are told it is no good, then it is their loss.

On the other hand, a good interviewer will want to know how you react to a question. Maybe they are looking for someone who is confident and who is not afraid to speak up instead of a yes man. So in that situation the best is to explain calmly why the requirement (no local variables) makes no sense and see what happens.

 

[lazydog]

Thanks Todd

Here are the timings for my G4 1.5 PB

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) : 0s, 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) : 1s, 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) : 2s, 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) : 2s, 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) : 4s, 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) : 9s, 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) : 20s, 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) : 43s, 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) : 57s, 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) : 147s, 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) : 325s, 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

Yeah, my fans were on full blast too.

The numbers are interesting. Your laptop is over twice as fast and that's only on one core. I guess the program is stressing the on board cache and not memory bandwidth etc.


thanks again todd

b e n

 

[MongoTheGeek]

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) : 0s, 716787 calls, list : 1 2 4 5 7 9 11 12 13 14 15 17 18 19 20 21 
19) : 1s, 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) : 2s, 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) : 10s, 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) : 23s, 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) : 30s, 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) : 77s, 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) : 171s, 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

2GHz G5

Cores/CPUs shouldn't matter though. Its not like the code is set up to be MT.

 

[Nutter]

Are we comparing the size of our stacks?

 

[toddburch]

For grins, I compiled it under VC++ under XP. I had to remove the LONG LONG and change srandom/random to srand/rand, but for the most part, it worked fine. You can see the oveflow (because of no LONG LONG) in iteration #32 when the count went negative.

D:\lazydog2\Debug>lazydog2
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) : 0s, 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+006 calls, list : 1 2 4 5 7 9 11 12 13 14 15 17 18 19 20 21 22
21) : 0s, 3.60037e+006 calls, list : 1 2 4 5 7 9 11 12 13 14 15 17 18 19 20 21 22
22) : 1s, 5.69752e+006 calls, list : 1 2 4 5 7 9 11 12 13 14 15 17 18 19 20 21 22
23) : 1s, 1.82804e+007 calls, list : 1 2 4 5 7 9 11 12 13 14 15 17 18 19 20 21 22 24
24) : 2s, 4.34463e+007 calls, list : 1 2 4 5 7 9 11 12 13 14 15 17 18 19 20 21 22 24 26
25) : 4s, 9.37779e+007 calls, list : 1 2 4 5 7 9 11 12 13 14 15 17 18 19 20 21 22 24 26 28
26) : 6s, 1.27332e+008 calls, list : 1 2 4 5 7 9 11 12 13 14 15 17 18 19 20 21 22 24 26 28
27) : 16s, 3.28659e+008 calls, list : 1 2 4 5 7 9 11 12 13 14 15 17 18 19 20 21 22 24 26 28 30
28) : 36s, 7.31312e+008 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) : 75s, 1.53662e+009 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) : 100s, 2.07349e+009 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) : 257s, 9.99748e+008 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) : 572s, -1.14774e+009 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

Todd

(1.7ghz Pentium M, 1GB ram, Dell D800 Latitude laptop - corporate issue)