JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
Find index with given cumulative frequency algorithm | Reply
In the article said:
MaxVal - maximum value which will have non-zero frequency
bitMask - initialy, it is the greatest bit of MaxVal
But to properly use this algorithm I had to set:
P = maximum value which will have non-zero frequency
MaxVal = min{ 2k such that 2k >= P }
bitMask = greatest bit of MaxVal
to avoid skipping some values while binary searching.

Someone else got this?

EDIT: typo
Re: Find index with given cumulative frequency algorithm (response to post by Xyphen) | Reply
I suppose that you wanted to write
MaxVal = min{ 2^k such that 2^k >= P }

However, you have right. While I was writing the article, I set MaxVal to be in form 2^n, where n is non-negative integer, but didn't mention it - sorry. I wanted to add it later, but it seems that sometimes it is very hard to get response from moderators when it is about articles (i.e. I have send article "Concurrent programming in Java" several times in the last year, but as you see it is not among the articles). Instead setting MaxVal to be in that form, you can add (start body of condition)
if (tIdx <= MaxVal){

after
int tIdx = idx + bitMask;

and close before (just put })
bitMask >>= 1;


Please, accept my apologize if this kind of mistake did make you (or to anyone other) trouble.

EDIT: typo
Re: Find index with given cumulative frequency algorithm (response to post by boba5551) | Reply
boba5551 wrote: I suppose that you wanted to write
MaxVal = min{ 2^k such that 2^k >= P }
Yep, you're right.
boba5551 wrote: Please, accept my apologize if this kind of mistake did make you (or to anyone other) trouble.
Don't worry man.
In fact, I just wanted to know if it could be possible to use any kind of trick/s to make this algorithm work using linear space instead of exponential space.
I'll test ur fix in a while, thanks.
Re: Find index with given cumulative frequency algorithm (response to post by Xyphen) | Reply
Well, it still use linear space with constant at most 2. But, if you want linear space with constant 1, then it is enough to add that condition.
Re: Find index with given cumulative frequency algorithm (response to post by boba5551) | Reply
It works great.
I hadn't thought to fix it in that way.
Thanks!.
RSS