Re: !! Help !! Finding an open range within a range of numbers
- From: "Maarten Wiltink" <maarten@xxxxxxxxxxxxxxxxxx>
- Date: Wed, 24 Aug 2005 23:07:52 +0200
"Justin" <j.a.dorus@xxxxxxxxx> wrote in message
news:1124914502.138611.260810@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
> I have a range of numbers (1-10000). These numbers correspond as record
> numbers in a table. I am looking for some sort of algorithm or
> pseudocode that can find a variable amount of consecutive open values.
> Say for instance...I need 13 consecutive un-occupied numbers starting
> with the lowest available.
>
> I understand that if I find the lowest, and check the next value all
> the way up until the variant (13 in this case) it should go to the next
> available and try counting from there, but for some reason...I'm just
> drawing a blank with the best way to code this.
Just start with _any_ way to code it. Ten thousand isn't much anymore;
the most naive algorithm possible is probably good enough. You have the
idea, and it is sound. Just loop over all your data and keep a counter
for the length of the range of free cells you're currently in. In every
cell, either increment it or reset it to zero. (_Don't_ look if it was
zero already.) When it reaches N, break. When you reach the end of the
input, fail. You're probably not seeing the simplicity because you want
to look for holes. Just look at all cells in turn; seeing holes comes
on top of that.
This is of course an extremely well researched problem. All disk and
memory allocation comes back to it. Most algorithms require a "free
list" or construct it every time. Standard algorithms include first
fit, best fit, worst fit (a better contender than it might sound) and
the usual champion circular first fit. You don't say if you ever get
ranges back; if so, you may want to merge adjacent free blocks.
An alternative is to not require a single free block, but to have
some indexing scheme. FATs, inodes, sector chaining...
Groetjes,
Maarten Wiltink
.
- Follow-Ups:
- Re: !! Help !! Finding an open range within a range of numbers
- From: Maarten Wiltink
- Re: !! Help !! Finding an open range within a range of numbers
- References:
- Prev by Date: Re: anchor a grid to a specific tab of a page control
- Next by Date: Re: !! Help !! Finding an open range within a range of numbers
- Previous by thread: !! Help !! Finding an open range within a range of numbers
- Next by thread: Re: !! Help !! Finding an open range within a range of numbers
- Index(es):
Relevant Pages
|
|
