From: "Michael W. Ryder" <_mwryder@...> Date: 2008-07-18T05:25:06+09:00 Subject: Re: The next number that is not in an array Robert Dober wrote: > On Thu, Jul 17, 2008 at 9:05 PM, Michael W. Ryder > <_mwryder@worldnet.att.net> wrote: >> Robert Dober wrote: >>> On Thu, Jul 17, 2008 at 3:44 PM, Robert Dober >>> wrote: >>>>> true while restricted_numbers.include?(n+=1) >>>> I think there is a typo in here ;) >>>> >>>> Did you mean >>>> >>>> 42 while restricted_numbers.include?( n+= 1 ) >>>> >>>> of course you did. >>>> >>>> >>> Now to add injustice to injury ;) >>> >>> What about >>> >>> n = ([*n.succ..rn.max.succ]-rn).min || n.succ >>> >>> This will be about 10 times slower than David's beautiful code. >>> However in some extreme cases, e.g. very densely populated rn arrays >>> this functional approach becomes more interesting. >>> >>> If rn is [*1..1_000] the functional code runs 50 times faster, and if >>> you have to jump over an restricted >>> numbers array of [*1..10_000] the functional code runs 500 times faster. >>> >>> So maybe just in case you can afford the extra runtime for the >>> "normal" case you can assure nice performance in edge cases by the >>> functional approach. >>> >>> Cheers >>> Robert >>> >> I just thought of an "optimization" that might work with dense arrays of >> restricted numbers. Instead of storing just an array of restricted numbers >> store the restricted number along with the final number in the range, or the >> first non-restricted number. Then you would just have to build the original >> array once and then read it to get the next available number. Much less >> looping, etc. >> >> >> > > After my benchmarks I suspect that Ruby does this for [*a..b] internally > So, if I have an array [2,3,4,5,6,8,9,10,11,15,16,17] and entered '2' it would know that 7 was the first number not in the array without looking at 2, 3, 4, 5, and 6 first? Or maybe the time to loop through the numbers was so small that it wasn't noticeable.