Hi there,
I remember a comment from way back in 1st year Computer Science regarding
the use of Fibonacci numbers in memory allocation strategies. The idea is to
minimise the number of times that the memory allocation routine is called -
so you try to predict how much memory will be requested the next time based
on history of the previous requests. Below I present my basic implementation
of a 'Fibonacci String' class.
For those who don't remember:
f(0) = 0
f(1) = 1
f(n) = f(n-1) + f(n-2) ;for n > 1
I designed the class for situations where you know that a string has to grow
over time, but you can't easily predict how big or how quickly it will grow.
You want to minimise the amount of time spent re-allocating memory and
copying the string every time the string is added to. By using the FibString
class the string size will quickly
My constructor assumes a minimum size of 100 characters, but realistically
you would set this to 4k or more.
I'd appreciate some feedback-
1. Is my implementation correct (apart from the memory move line which is
probably wrong - don't have a compiler handy)?
2. Are there any other enhancements/optimisations that I should consider?
This code may be included in free or commercial source libraries provided
full credit is given to me, including a link to my web site.
Regards,
Simon
--
mailto:lau...@ozemail.com.au
http://www.crystalsoftware.com.au
TextPipe Search/Replace - The Webmaster Text Transformation Workbench
Other products: LFNit!, DirSize, BabyShield, DirDate, ZeroIn, Arc Menu,
ClipSize, Clean 'n' Go
const
minimum_realistic_size = 100;
type
TFibString = class(TObject)
buffer : string;
occupiedLength : integer;
private
bufferLength : integer;
fibonacci1 : integer;
fibonacci2 : integer;
{the length handed to the constructor}
initialLength : integer;
public
constructor create( initial : integer );
procedure add( const s : string );
procedure clear;
procedure resetSize;
function getString : string;
end;
constructor TFibString.create( initial : integer );
begin
if initial < minimum_realistic_size then
initialLength := minimum_realistic_size
else
initialLength := initial;
bufferLength := initialLength;
resetSize;
end;
function TFibString.getString : string;
begin
result := copy(buffer,1,occupiedLength);
end;
procedure TFibString.add( const s : string );
var
sLength : integer;
begin
sLength := length(s);
if bufferLength + sLength > bufferLength then
begin
{we have to resize}
{f(n)=f(n-1)+f(n-2) for n>1 }
fibonacci1 := fibonacci2; {old length}
fibonacci2 := bufferLength + sLength; {new required length}
bufferLength := fibonacci1 + fibonacci2;
setLength( buffer, bufferLength );
end;
{now append to the buffer}
{** NOTE - this line is not expected to compile yet **}
movemem( s, buffer[ occupiedLength + 1 ], sLength );
inc( occupiedLength, sLength );
end;
procedure TFibString.clear;
begin
occupiedLength := 0;
end;
procedure TFibString.resetSize;
begin
clear;
{f(0)=0, f(1)=1}
fibonacci1 := 0;
fibonacci2 := initialLength;
setLength( buffer, fibonacci2 );
end;