难以理解/可视化SICP流汉明数程序 [英] Trouble understanding / visualising SICP streams Hamming numbers program

问题描述

我在SICP中基本坚持3.56.问题是这样的:

I'm basically stuck at excercise 3.56 in SICP. The problem goes like this:

锻炼3.56.由R. Hamming提出的一个著名问题是，以升序(无重复)枚举除2、3或5以外没有素数的所有正整数.一种显而易见的方法是简单地测试每个整数依次查看是否有2、3和5以外的任何其他因素.但这效率很低，因为随着整数变大，越来越少的整数符合要求.或者，让我们调用所需的数字流S，并注意以下有关事实.

Exercise 3.56. A famous problem, first raised by R. Hamming, is to enumerate, in ascending order with no repetitions, all positive integers with no prime factors other than 2, 3, or 5. One obvious way to do this is to simply test each integer in turn to see whether it has any factors other than 2, 3, and 5. But this is very inefficient, since, as the integers get larger, fewer and fewer of them fit the requirement. As an alternative, let us call the required stream of numbers S and notice the following facts about it.

• S以1开头.
  • (比例流S 2)的元素也是S的元素.
  • (比例流S 3)和(比例流5 S)也是如此.
  • 这些都是S的全部元素.
  • S begins with 1.
    • The elements of (scale-stream S 2) are also elements of S.
    • The same is true for (scale-stream S 3) and (scale-stream 5 S).
    • These are all the elements of S.

    现在我们要做的就是结合这些来源的元素.为此，我们定义了一个过程合并，将两个有序流合并为一个有序结果流，从而消除了重复:

    Now all we have to do is combine elements from these sources. For this we define a procedure merge that combines two ordered streams into one ordered result stream, eliminating repetitions:

    (define (merge s1 s2)
       (cond ((stream-null? s1) s2)
             ((stream-null? s2) s1)
             (else
              (let ((s1car (stream-car s1))
                    (s2car (stream-car s2)))
                (cond ((< s1car s2car)
                       (cons-stream s1car (merge (stream-cdr s1) s2)))
                      ((> s1car s2car)
                       (cons-stream s2car (merge s1 (stream-cdr s2))))
                      (else
                       (cons-stream s1car
                                    (merge (stream-cdr s1)
                                           (stream-cdr s2)))))))))
    

    然后可以通过合并来构造所需的流，如下所示:

    Then the required stream may be constructed with merge, as follows:

    (define S (cons-stream 1 (merge <??> <??>)))

    在上面标记的地方填写缺少的表达式.

    Fill in the missing expressions in the places marked above.

    在解决此特定问题之前，我已经能够使用信号处理框图直观地了解这些隐式流的定义，并将原始流反馈给该过程.

    Before this particular problem, I've been able to visualize and understand these implicit stream definitions using a signal processing block diagram with the original stream being fed back to the procedure.

    但是我基本上已经碰到了这个特定问题，我已经查找了解决方案，但是我发现无法想象解决方案在我的脑袋/纸上的工作方式.

    But I've basically hit a wall with this particular problem, I've looked up the solution, but I'm finding it impossible to visualize how the solution would work in my head/paper.

    是否有技巧来理解和提出针对此类问题的解决方案?

    Is there a trick for understanding and coming up with solutions for these sort of problems?

    这是可行的解决方案:

    (define S 
      (cons-stream 1 (merge (scale-stream S 2)
                            (merge (scale-stream S 3)
                                   (scale-stream S 5)))))
    

    谢谢.

    推荐答案

    作为适当的命名，merge不应删除重复项，因为其名称表明它是mergesort的一部分，应保留它们. Union是此类操作的更好名称，它可以看到(此处)通过增加唯一编号列表来表示集合，该约束应通过删除只能来自其两者的重复项来保留，以保持其约束.争论.

    As a matter of proper naming, merge shouldn't be removing duplicates, as its name suggests its being part of mergesort which ought to preserve them. Union is a better name for such operation, which sees sets represented (here) by increasing lists of unique numbers, which constraint it ought to preserve by removing the duplicates which can only come from both of its arguments.

    回到问题本身，让我们用符号表示为

    Back to the problem itself, let's write it symbolically as

    S235 = {1} ∪ 2*S235 ∪ 3*S235 ∪ 5*S235

    S235 = {1} ∪ 2*S235 ∪ 3*S235 ∪ 5*S235

    过早实现是万恶之源！ (等等， ?)我们甚至都不会尝试确定这些∪的工作准确程度，甚至没有确定顺序.甚至有多少个术语:

    Premature implementation is the mother of all evil! (wait, what?) We won't even yet try to establish how exactly those ∪s do their job, not even in which order. Or even how many of the terms there are there:

    S23 = {1} ∪ 2*S23 ∪ 3*S23

    S23 = {1} ∪ 2*S23 ∪ 3*S23

    甚至

    S2 = {1} ∪ 2*S2

    S2 = {1} ∪ 2*S2

    现在，这看起来很简单.我们甚至可以在这里简单地伪造实现A和B的联合，因为，首先，获取A的所有元素，然后获取B的-.在这里，它会很好用，因为在∪的左侧输入中只有一个元素:

    Now this looks simple enough. We can even fake-implement the union of A and B here simply as, first, taking all the elements of A, and then -- of B. And it will work just fine, here, because there's only one element in this ∪'s left input:

     {1} ----∪-->--->--S₂--.--->S₂
            /               \        
            \______*2_______/        
              ---<----<---         
    

    这是如何工作的? 1进入∪ combiner ，先退出，无条件(注意，此发现的要求很重要，因为如果∪具有要立即检查其两个参数，我们会得到一个无限循环(在Haskell argot中为黑洞)，由. splitter 分为两部分，然后1的第一个副本继续前进到输出点，而1的第二个副本通过*2乘法器返回，结果2这次在右边的处返回∪ >与左上的任何内容对立(此时已为空)，并以相同的方式继续进行操作，因此2转到输出点，然后是4，然后是8，依此类推.等等.

    How does this work? 1 enters the ∪ combiner, exits it first, unconditionally (NB this discovered requirement is important, for if ∪ had to examine both of its arguments right away we'd get ourselves an infinite loop, a black hole in Haskell argot), is split in two by the . splitter, then the first copy of 1 continues forth to the output point while the second copy of 1 goes back through the *2 multiplier, the resulting 2 enters back the ∪ this time on the right, unopposed by anything on the left (which is at this time already empty), and continues on in the same fashion so 2 goes to the output point, then 4, then 8, etc. etc..

    换句话说，S₂包含{1}的所有元素；加上一次通过*2乘数的所有{1}元素；和两次；和三倍;等等，依此类推- 2 的所有功能按升序排列:

    To put it differently, S₂ contains all elements of {1}; plus all elements of {1} that went through the *2 multiplier once; and twice; and three times; and so on and so forth -- all the powers of 2 in increasing order:

    S2 = {1} ∪ 2*{1} ∪ 2*2*{1}                ;; == {1, 2, 4, 8, 16, 32, ...}
                     ∪ 2*2*2*{1}
                     ∪ 2*2*2*2*{1}
                     ∪ ..........
    

    图中的两个S₂是相同的，因为无论我们在分离点处虹吸它如何，都不会对其产生影响.

    The two S₂'s in the diagram are the same because whatever we siphon from it at the splitter point does not affect it.

    这不是很有趣吗?

    那么我们如何添加3的倍数呢?一种方法是

    So how do we go about adding the multiples of 3 to it? One way to do it is

    S23 = S2 ∪ 3*S23

    S23 = S2 ∪ 3*S23

     {1} ----∪-->--->--S₂--.---S₂----∪-->--->--S₂₃--.--->S₂₃
            /               \       /                \        
            \______*2_______/       \______*3________/        
              ---<----<---            ---<----<---         
    

    ^{S₂中的1进入第二个∪组合器，前进到输出点S₂₃，然后通过*3乘法器返回，变成3.现在，第二个∪具有2,4,8,...和3,...作为输入； 2会同时变为6.接下来，∪具有4,8,16,...和3,6,...； 3通过.接下来，4;等等等等.}

    ^{Here 1 from S₂ enters the second ∪ combiner and proceeds to the output point S₂₃ as well as back through the *3 multiplier, turning into 3. Now the second ∪ has 2,4,8,... and 3,... as its inputs; 2 goes through as well as turning into 6. Next, ∪ has 4,8,16,... and 3,6,...; 3 goes through. Next, 4; etc., etc., and so on and so forth.}

    因此，S₂的所有元素都是S₂₃的一部分，但S₂的所有元素也都通过*3乘数一次，两次，依此类推，等等-- 2 和 3 以递增顺序相乘:

    Thus all elements of S₂ are part of S₂₃, but so are also all elements of S₂ that went through the *3 multiplier once, and twice, etc., -- all the powers of 2 and 3 multiplied together, in increasing order:

    S23 = S2 ∪ 3*S2 ∪ 3*3*S2                   ;; = S2 ∪ 3*( S2 ∪ 3*S2 
                    ∪ 3*3*3*S2                 ;;               ∪ 3*3*S2 
                    ∪ 3*3*3*3*S2               ;;               ∪ 3*3*3*S2 
                    ∪ ..........               ;;               ∪ ........ )   !!

    为什么顺序递增?如何?为什么，这是∪的责任！您好，另一个发现了要求.无论从哪一侧进入，它都必须先产生较小的元素，然后再产生较大的元素.

    Why the increasing order? How? Why, that is the responsibility of ∪! Hello, another discovered requirement. Whatever enters it on either side, it must produce the smaller element before the larger one.

    如果两者相等，该怎么办?我们在此方案中是否甚至需要考虑这个问题?这有可能发生吗?

    And what is it to do in the event the two are equal? Do we even need to concern ourselves with this question in this here scheme? Can this ever happen, here?

    不能.因此，我们可以将∪ 此处实施为merge，而不是union(但是记住第一个发现的要求！-它仍然有效吗?需要吗?添加新案例). Merge应该比union更有效率，因为它与等号的情况无关.

    It can't. And so we can implement the ∪ here as a merge, not as a union (but remember the first discovered requirement! -- is it still valid? needed? with the addition of new cases). Merge ought to be more efficient than union as it doesn't concern itself with the case of equals.

    还有 5 的倍数吗?我们继续，因为

    And for the multiples of 5 also? We continue, as

    S235 = S23 ∪ 5*S235

    S235 = S23 ∪ 5*S235

     {1} ----∪-->--->--S₂--.---S₂----∪-->--->--S₂₃--.---S₂₃----∪-->--->--S₂₃₅--.--->S₂₃₅
            /               \       /                \         /                 \ 
            \______*2_______/       \______*3________/         \_______*5________/ 
              ---<----<---            ---<----<---                ---<----<---     
    

    • 这是否描述了本书中的代码? _______
    • 这是否描述了比本书中的代码快两倍的代码? _______
    • 为什么它的速度比本书中的代码快两倍? _______
    • 此答案是否是您的问题? _______
    • 此帮助您回答了您的问题吗? _______
    • Does this describe the code from the book? _______
    • Does this describe a code which is about twice faster than the one from the book? _______
    • Why is it about twice faster than the code from the book? _______
    • Does this answer your question? _______
    • Does this help you answer your question? _______

    (填空).

    另请参阅:

    • 无限制生成汉明序列的最新技术水平

    本书代码的信号处理框图为:

    And the signal processing block diagram for the book's code is:

                                      1 --->---\
                                                 cons-stream ->-- S ---.---> S
        /----->---->--- *2 --->---\            /                       |
       /                            union ->--/                        /
      .-->-- *3 -->--\            /                                   /
      |                union ->--/                                   /
      .-->-- *5 -->--/                                              /
      \                                                            /
       \__________<__________<__________<_________<_______________/
    

    在书中将删除重复项的联合"称为merge.

    where the duplicates-removing "union" is called merge in the book.

    这篇关于难以理解/可视化SICP流汉明数程序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！