Databases
StackOverflow2013
Postsdbo
POHow to efficiently find a contiguous range of used/free slots from a Fenwick tree
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POHow to efficiently find a contiguous range of used/free slots from a Fenwick tree
    primarykey
    data
    text
    <p>Assume, that I am tracking the usage of slots in a Fenwick tree. As an example, lets consider tracking 32 slots, leading to a Fenwick tree layout as shown in the image below, where the numbers in the grid indicate the index in the underlying array with counts manipulated by the Fenwick tree where the value in each cell is the sum of "used" items in that segment (i.e. array cell 23 stores the amount of used slots in the range [16-23]). The items at the lowest level (i.e. cells 0, 2, 4, ...) can only have the value of "1" (used slot) or "0" (free slot). </p> <p><img src="https://i.stack.imgur.com/wVK2B.png" alt="Example Fenwick tree layout"></p> <p>What I am looking for is an efficient algorithm to find the first range of a given number of contiguous free slots.</p> <p>To illustrate, suppose I have the Fenwick tree shown in the image below in which a total of 9 slots are used (note that the light gray numbers are just added for clarity, not actually stored in the tree's array cells).</p> <p><img src="https://i.stack.imgur.com/INdUe.png" alt="Example tree"></p> <p>Now I would like to find e.g. the first contiguous range of 10 free slots, which should find this range:</p> <p><img src="https://i.stack.imgur.com/MrwIB.png" alt="Example search result"></p> <p>I can't seem to find an efficient way of doing this, and it is giving me a bit of a headache. Note, that as the required amount of storage space is critical for my purposes, I do not wish to extend the design to be a segment tree. </p> <p>Any thoughts and suggestions on an O(log N) type of solution would be very welcome.</p> <p><strong>EDIT</strong></p> <p>Time for an update after bounty period has expired. Thanks for all comments, questions, suggestions and answers. They have made me think things over again, taught me a lot and pointed out to me (once again; one day I may learn this lesson) that I should focus more on the issue I want to solve when asking questions. </p> <p>Since <a href="https://stackoverflow.com/users/337475/erik-p" title="@Erik P.">@Erik P</a> was the only one that provided a reasonable answer to the question <em>that included the requested code/pseudo code</em>, he will receive the bounty. </p> <p>He also pointed out correctly that O(log N) search using this structure is not going to be possible. Kudos to <a href="https://stackoverflow.com/users/2825668/dan-bjorge" title="@DanBjorge">@DanBjorge</a> for providing a proof that made me think about worst case performance. </p> <p>The comment and answer of <a href="https://stackoverflow.com/users/1009831/evgeny-kluev" title="@EvgenyKluev">@EvgenyKluev</a> made me realize I should have formulated my question differently. In fact I was already doing in large part what he suggested (see <a href="https://gist.github.com/anonymous/7594508" rel="nofollow noreferrer">https://gist.github.com/anonymous/7594508</a> - which shows where I got stuck before posting this question), and asked this question hoping there would be an efficient way to search contiguous ranges, thereby preventing changing this design to a segment tree (which would require an additional 1024 bytes). It appears however that such a change might be the smart thing to do.</p> <p>For anyone interested, a binary encoded Fenwick tree matching the example used in this question (32 slot fenwick tree encoded in 64 bits) can be found here: <a href="https://gist.github.com/anonymous/7594245" rel="nofollow noreferrer">https://gist.github.com/anonymous/7594245</a>.</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USCommunity
    1. USAlex
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POHow to efficiently find a contiguous range of used/free slots from a Fenwick tree
      1. USAlex
      1. VTBountyStart
    2. VO
      singulars
      1. POHow to efficiently find a contiguous range of used/free slots from a Fenwick tree
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POHow to efficiently find a contiguous range of used/free slots from a Fenwick tree
      1. This table or related slice is empty.
      1. VTUpMod
    1. COnot too sure i understand, but if cell 23 stores #used in 16-23, and you have to find > 8, then you only have to search the tips (7,15,23, etc). Discard if it's > 0, check the next 2 if it *is* 0? That way you search only the tips (log) of the ranges, plus a small constant increase in the event of partial success?
      singulars
      1. POHow to efficiently find a contiguous range of used/free slots from a Fenwick tree
      1. USim so confused
    2. COCan you please clarify what you mean by "efficient"? Are you looking to optimize for worst-case time or average-case time? If average-case, do you have any information about expected input distributions?
      singulars
      1. POHow to efficiently find a contiguous range of used/free slots from a Fenwick tree
      1. USDan Bjorge
    3. CO@DanBjorge by efficient I mean that it would preferably be O(log N) amortized, i.e. optimize for average-case time. For my specific use case, I expect there to be large consecutive fully used ("1") regions (note that the tree I am actually using is quite a bit larger than the one in the example). I expect searches to generally be for ranges of 1-16 free slots, with a median (guessing here) probably around 4.
      singulars
      1. POHow to efficiently find a contiguous range of used/free slots from a Fenwick tree
      1. USAlex
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload