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
bucket

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--)
         a[i]=a[i-1]

so if (e.g.) bucket one out of 64 splits, then i have to do 63 right
shifts

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+1]=value
a[i+2]= keyOfNextBucket

then use skiplists.

but, anyone got a better idea?

thanks!

tim menzies

On 3     , 23:00, "there are some who call me tim.."
<menzies....@gmail.com> wrote:
> 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
> bucket
>
> 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--)
>          a[i]=a[i-1]
>
> so if (e.g.) bucket one out of 64 splits, then i have to do 63 right
> shifts
>
> 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+1]=value
> a[i+2]= keyOfNextBucket
>
> then use skiplists.
>
> but, anyone got a better idea?
>
> thanks!
>
> 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?

  Vassilis