commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Mark R. Diggory" <mdigg...@latte.harvard.edu>
Subject Re: [math][patch] New RollingUnivariateImpl
Date Fri, 16 May 2003 16:04:40 GMT


O'brien, Tim wrote:
> On Fri, 2003-05-16 at 09:37, Mark R. Diggory wrote
> 
> Your patch involves moving (n-1) elements of the list on every insert. 
> Using ContractableDoubleArray accomplishes the same task, but simply
> increments the startIndex of an internal storage array.  Storage is
> reclaimed periodically when certain storage limits are exceeded.
> 

Tim,

My implementation requires no such thing! ;-) Look at it again, it 
"rolls" around the array simply replacing the last value in the window 
with the new value in the window and increments the index representing 
the beginning of the array (when this index reaches the end of the array 
it gets mod'ed to send it back to the beginning of the array. No 
elements "move". The array doesn't change size, this is an extremely 
efficient design.

> 
>>What do you think? Maybe RollingArray extends ExpandableArray and masks 
>>the rolling behavior behind its interface so it can be plugged in easily 
>>to the other Implementations?
> 
> 
> DoubleArray already exposes addElementRolling() in the public interface.
> 

Don't get me wrong, but doesn't your implementation actually produce an 
array that has an unused portion at the beginning?, consecutive calls to 
addElementRolling() bloat this portion of the array when you push the 
startIndex up each roll?

	public synchronized double addElementRolling(double value) {
		double discarded = internalArray[startIndex];
		
		if ( (startIndex + (numElements+1) ) > internalArray.length) {
			expand();
		}
		// Increment the start index
		startIndex += 1;
		
		// Add the new value
		internalArray[startIndex + (numElements -1)] = value;
		
		return discarded;
	}

I don't see where storage is reclaimed at the beginning of the array 
because you always copy the array starting at 0. The fact that you have 
to copy the array is somewhat "exaustive". Expecially in the case where 
your gathering statistics via updating. This effort will only end up 
copying exaustively larger and larger arrays in the current implementation.




	private synchronized void expandTo(int size) {
		double[] tempArray = new double[size];
		// Copy and swap
		System.arraycopy(internalArray,0,tempArray,0,internalArray.length);
		internalArray = tempArray;
	}

	protected synchronized void expand() {

		int newSize = (int) Math.ceil(internalArray.length * expansionFactor);
		double[] tempArray =
			new double[newSize];

		// Copy and swap
		System.arraycopy(internalArray, 0, tempArray, 0, internalArray.length);
		internalArray = tempArray;
	}

I think it really may be wiser to separate the functionalities of 
Rolling and Expanding, At least until theres a clear methodology for the 
best implementation of each and a clear means of combining them.


I'll chill now. Cheers,
Mark




---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org


Mime
View raw message