Memory

A day to remember, september 21th, 2007

A list of accomplishments for today:
1. Beat a certain someone at a science subject test. My score was 90. I have tried for 2 years. Finally I beat her. Finally it happened
2. My first credit card! Finally it happened
3. Spent $120 on getting hosting from site5.com (migration: next 3 days...) Finally it happened
4. Spent $6 for food, in school. First time I spend that much money in school. After I become a Junior, this is the first real lunch . Finally it happened
5. In fact, today is the day I spent the most money..
6. Start to work on the mathematic love letter. currently, successful. Finally it happened
it's funny, not because I'm a geek in love. Inspired by Mathematicians love letter. Which I think it's too much geometry and too little algebra.
7. All my frustrations are temporarily gone. So nice to not have a girlfriend.

C++ Learning Note

Crashes!

unsigned char map[5242880];

Does not crash!

unsigned char* map = new unsigned char[5242880];

Copy some memory to another place

memcpy(pointer destination ,pointer source ,int bytes);

Find the peak memory usage

Profiling, a very interesting topic.
Some time ago, I tried to find the peak memory usage because my program does a lot of memory free actions. A new function added in PHP5 can do just that:
memory_get_peak_usage()
I'm posting this because I know most people are using PHP4 (no offense but... MAKE THE CHANGE! )
I don't know much about command line, which lead to me using some PHP native code to track the highest memory usage.
Remember the ticks? that makes the best profiler. Compare the memory usage now and the previous max memory and chose the larger one over the smaller one.
Note the declare should only run on Linux, on windows this causes apache to crash.
Sample code:

function get_max_mem($dump){
	static $mem;
	$a = memory_get_usage();
	if($a>$mem){
		$mem = $a;
	}
	if($dump){
		return $mem;
	}
}
register_tick_function('get_max_mem');
get_max_mem();
declare(ticks=1);
//now put this in the end of your script
//echo get_max_mem(TRUE);

String is better than array: Memory exhausting calculation special case--Return all prime number below x

When I was working with the Sieve of Eratosthenes, a Sieve for finding all prime number below x, the input number. I have to keep track of an array that contains either 0 or 1. The size of the array equals to the input number.
The code before using string:

function esprime($limit){
	$sqrtlimit = sqrt($limit);
	$range = 1;
	while($range<$limit){
		$i[$range] = 1;
		$range+=2;
	}
	$n = 2;
	while($n < $sqrtlimit){
		if ($i[$n]){
			$sqn = $n*$n;
			$k = $sqn;
			$i[$k]=0;
			while($k<=$limit){
				$k += $n;
				$i[$k]=0;
			}
		}
		++$n;
	}
	$n = 1;
	while($n<$limit){
		if($i[$n]) $primes[] = $n;
		$n+=2;
	}
	if($limit>=2) $primes[0] = 2;
	return $primes;
}

This is extremely memory exhausting. 32MB of memory is all used up while trying to find all prime numbers up to 500,000.
32MB = 33,554,432 bytes
Without running the function, the script uses 4,786,192 bytes of memory. So 27 MB is used for creating a size 250,000 array(all the even ones are dropped).
Is there any way to fix this problem? This array have to be created instantly so you can't just drop values out from it. Doesn't that mean it's impossible for this to work?
There is really nothing we can do with array in this case.
Don't despair! we can use string!
Because the value of the array can be represent by a character, the key of the array can be represent by the position of the character in the string.
so instead of this code

$range = 1;
while($range<$limit){
	$i[$range] = 1;
	$range+=2;
}

I uses this:

$range = 0;
while($range<$limit){
	$i .= '11';
	$range+=2;
}

The good thing about this is I don't need to change my entire script, because each character inside a string can be accessed like an array by it's position:

$i = '30000'
echo $i[0];//3

Using the string method, I successfully made it run up to 5,000,000 with out a problem.
I don't know things like this will ever occur to a PHP programmer, because this is useful only when you are having limited memory but also having an array with huge amount of data that can be represent by a limited amount of keys.

Robert Mark Howting made it even better :)

$range = 0;
$i = str_repeat('01',floor($limit/2));

It's much more efficient. Except this time we have to have a case to output the even prime 2.
You can see it in the end of this script.

BTW, I'm also working on Sieve of Atkin. Strange I can't make it faster than Sieve of Eratosthenes.

Syndicate content
Honey Pot that kill bots