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

0 |

9/3/2007 8:00:21 PM

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

0 |

9/4/2007 4:47:23 AM