Generate infinite stream of unique numbers between 0 and 1_问答_开发者

Came across this question previously on an interview. The requirements are to write a function that

Generates a number between 0..1
Never returns the same number
Can scale (called every few milliseconds and continuously for years)
Can use only 1mb of heap memory
Does not need to return as a decimal, can render directly to stdout

My idea was hacky at best which involved manipulating a string of the "0.1" then "0.11" then "0.12" etc. Since the requirements did not mention it had to be uniformly distributed, it does not need to be random. Another idea is generate a timestamp of the form yyyyMMddhhmmssSSS (where SSS is msec) then convert that to a string and prefix it with "0." . This way the values will开发者_运维技巧 always be unique.

It's a pretty open ended question and I'm curious how other people would tackle it.

Pseudo code that can do what you except guarantee no repeats.

Take your 1 MB allocation.
Randomly set every byte.
Echo to stdout as "0.<bytes as integer string>" (will be very long)
Go to #2

Your "Never returns the same number" is not guaranteed but it is extremely unlikely (1 in 2^8192) assuming a good implementation of Random.

Allocate about a million characters and set them initially to all 0.

Then each call to the function simply increments the number and returns it, something like:

# Gives you your 1MB heap space.

num = new digit/byte/char/whatever[about a million]

# Initialise all digits to zero (1-based arrays).

def init():
    for posn ranges from 1 to size(num):
        set num[posn] to 0

# Print next value.

def printNext():
    # Carry-based add-1-to-number.
    # Last non-zero digit stored for truncated output.

    set carry to 1
    set posn to size(num)
    set lastposn to posn

    # Keep going until no more carry or out of digits.

    while posn is greater than 0 and carry is 1:
        # Detect carry and continue, or increment and stop.

        if num[posn] is '9':
            set num[posn] to '0'
            set lastposn to posn minus 1
        else:
            set num[posn] to num[posn] + 1
            set carry to 0
        set posn to posn minus one

    # Carry set after all digits means you've exhausted all numbers.

    if carry is 1:
        exit badly

    # Output the number.

    output "0."
    for posn ranges from 1 to lastposn
        output num[posn]

The use of lastposn prevents the output of trailing zeros. If you don't care about that, you can remove every line with lastposn in it and run the output loop from 1 to size(num) instead.

Calling this every millisecond will give you about well over 10^{some--big-number-resulting-in-a-runtime-older-than-the-age-of-the-universe} years of run time.

I wouldn't go with your time-based solution because the time may change - think daylight savings or summer time and people adjusting clocks due to drift.

Here's some actual Python code which demonstrates it:

import sys
num = "00000"
def printNext():
    global num
    carry = 1
    posn = len(num) - 1
    lastposn = posn

    while posn >= 0 and carry == 1:
        if num[posn:posn+1] == '9':
            num = num[:posn] + '0' + num[posn+1:]
            lastposn = posn - 1
        else:
            num = num[:posn] + chr(ord(num[posn:posn+1]) + 1) + num[posn+1:]
            carry = 0
        posn = posn - 1

    if carry == 1:
        print "URK!"
        sys.exit(0)

    s = "0."
    for posn in range (0,lastposn+1):
        s = s + num[posn:posn+1];
    print s

for i in range (0,15):
    printNext()

And the output:

Your method would eventually use more than 1mb of heap memory. Every way you represent numbers, if you are constrained by 1mb of heap then there is only a finite number of values. I would take the maximum ammount of memory possible, and increment the least significant bit by one on each call. That would ensure running as longer as possible before returning a repeted number.

Yes, because there is no random requirement, you have a lot of flexibility.

The idea here I think is very close to that of enumerating all strings over the regular expression [0-9]* with a couple modifications:

the real string starts with the sequence 0.
you cannot end with a 0

So how would you enumerate? One idea is

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 0.11 0.12 0.13 0.14 0.15 ... 0.19 0.21 0.22 ... 0.29 0.31 ... 0.99 0.101 0.102 ...

The only state you need here is an integer I think. Just be clever in skipping those zeros at the end (not difficult really). 1 MB of memory should be fine. It stores a massive massive integer, so I think you would be good here.

(It is different from yours because I generate all one character strings, then all two character strings, then all three character strings, ... so I believe there is no need for state other than the last number generated.)

Then again I may be wrong; I haven't tried this.

ADDENDUM

Okay I will try it. Here is the generator in Ruby

i = 0
while true
  puts "0.#{i}" if i % 10 != 0
  i += 1
end

Looks okay to me....

If you are programming in C, the nextafter() family of functions are Posix-compatible functions useful for producing the next double after or before any given value. This will give you about 2^64 different values to output, if you output both positive and negative values.

If you are required to print out the values, use the %a or %A format for exact representation. From the printf(3) man page: "For 'a' conversion, the double argument is converted to hexadecimal notation (using the letters abcdef) in the style [-]0xh.hhhhp±d..." "The default precision suffices for an exact representation of the value if an exact representation in base 2 exists..."

If you want to generate random numbers rather than sequentially ascending ones, perhaps do a google search for 64-bit KISS RNG. Implementations in Java, C, Ada, Fortran, et al are available on the web. The period of 64-bit KISS RNG itself is ~ 2^250, but there are not that many 64-bit double-precision numbers, so some numbers will re-appear within 2^64 outputs, but with different neighbor values. On some systems, long doubles have 128-bit values; on others, only 80 or 96. Using long doubles, you could accordingly increase the number of different values output by combining two randoms into each output.

It may be that the point of this question in an interview is to figure out if you can recognize a silly spec when you see it.