On 3 , 23:00, "there are some who call me tim.."
> i have an incremental historgram package where i have to keep the
> array buckets sorted.
> each bucket.value is the number of times a value fell near bucket.key
> since the array is sorted, i can do a O(log(N)) binchop to find a
> but sometimes, i am forced into an O(N) operation that i want to
> avoid. as i read in input numbers, if one bucket gets too big, i split
> it dividing the old buckt.value in two. then i add the new number into
> one of the two halves (depending on which on it is closest to)
> thing is, after the split, the array is now one larger so i move
> everything to thr right
> for(i=arraySize; i> newBucket;i--)
> so if (e.g.) bucket one out of 64 splits, then i have to do 63 right
> anyway to avoid that? my current thinking is to make each bucket at
> position i to have three sub-buckets
> a[i]= key
> a[i+2]= keyOfNextBucket
> then use skiplists.
> but, anyone got a better idea?
> tim menzies
If I understand correctly your problem, you've got an array and when
it gets to big, you split it in half, before adding a new value. Then
you choose one of the two halves to put the new value in and then
shift that half. Obviously splitting involves copying to new arrays.
Why on that copy, don't you check for the place of the new value and
add it inplace?