生成0到1之间的无限唯一数字流

Question

之前在面试中遇到过这个问题。要求是编写一个函数

1. 生成0 ~ 1之间的数字
2. 永远不会返回相同的数字
3. 可扩展(每隔几毫秒调用一次，连续数年)
4. 只能使用1mb堆内存
5. 不需要以小数形式返回，可以直接渲染到stdout

我的想法是最好的hacky涉及到操作"0.1"字符串然后"0.11";然后"0.12";等。由于要求没有提到它必须均匀分布，所以它不需要是随机的。另一个想法是生成yyyyMMddhhmmssSSS(其中SSS是msec)形式的时间戳，然后将其转换为字符串并以"0."。这样，值将始终是唯一的。

这是一个非常开放的问题，我很好奇其他人会如何处理它。

Answer 1

伪代码可以做除之外的事情，保证不重复

1. 取1 MB的分配。
2. 随机设置每个字节
3. 返回标准输出为" 0.<bytes as integer string> "(将非常长)
4. 转到#2

你的"永远不会返回相同的数字"不能保证，但它是极不可能的(1在2^8192)假设一个很好的实现随机。

Answer 2

分配约一百万个字符，初始设置为所有0。

然后每次调用函数都简单地增加数字并返回它，如:

# 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]

使用lastposn可以防止输出尾随零。如果你不关心这个，你可以删除lastposn的每一行，并从1 to size(num)运行输出循环。

每毫秒调用一次，将为您提供超过10^{一些-big-number- results -in-a-run - time-old -than-the-age-of- universe}年的运行时间。

我不会采用你基于时间的解决方案，因为时间可能会改变——想想夏令时或夏令时，人们会因为漂移而调整时钟。

---

下面是一些实际的Python代码来演示它:

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()

输出:

0.00001
0.00002
0.00003
0.00004
0.00005
0.00006
0.00007
0.00008
0.00009
0.0001
0.00011
0.00012
0.00013
0.00014
0.00015

Answer 3

您的方法最终将使用超过1mb的堆内存。每一种表示数字的方式，如果你受到1mb堆的限制，那么只有有限数量的值。我会尽可能使用最大的内存量，并在每次调用时将最低有效位增加1。这将确保在返回重复的号码之前运行尽可能长的时间。

Answer 4

是的，因为没有随机的要求，你有很大的灵活性。

我认为这里的想法是非常接近枚举正则表达式[0-9]*上的所有字符串，并进行了一些修改:

• 实字符串以序列0.

开始

• 你不能结束 0

那么如何枚举呢?一个想法是

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 ...

我认为这里唯一需要的状态是一个整数。只要聪明地跳过最后的零就行了(其实并不难)。1mb的内存就可以了。它存储了一个非常大的整数，所以我想你在这里会很好。

(它与你的不同，因为我生成了所有的一个字符串，然后所有的两个字符串，然后所有的三个字符串，…因此，我认为除了最后生成的数字外，不需要其他状态。

我可能又错了;我还没试过。

附录

好吧，我试试。下面是Ruby

中的生成器

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

看起来不错....

Answer 5

如果你在用C语言编程，nextafter()系列函数是posix兼容的函数，可用于在任何给定值之后或之前生成下一个双精度数。如果输出正值和负值，这将为您输出大约2^64个不同的值。

如果需要打印出值，请使用%a或%a格式进行精确表示。来自printf(3)手册页:"对于'a'转换，双参数被转换为十六进制表记(使用字母abcdef)，格式为[-]0xh.hhhhp±d…"如果存在以2为基数的精确表示，则默认精度足以满足该值的精确表示…

如果您想生成随机数而不是顺序升序的数字，也许可以在google上搜索64位KISS RNG。在web上可以找到Java、C、Ada、Fortran等语言的实现。64位KISS RNG本身的周期是~ 2^250，但是64位双精度数并没有那么多，所以有些数字会在2^64输出中重新出现，但是邻居值不同。在某些系统上，长双精度值为128位;在其他地方，只有80或96个。使用长双精度对象，您可以通过在每个输出中组合两个随机值来相应地增加输出不同值的数量。

在面试中，这个问题的重点可能是看你是否能在看到一个愚蠢的规格说明时认出它。