当前位置： 文江博客话题详情

如何以不平凡的方式组合两个生成器

发布于 2024-08-16 11:48:57 字数 150 浏览 6 评论 0原文

我有一个生成器，它生成所有 2 的幂的正整数，另一个生成器生成所有 3 的幂的整数。我现在需要使用它们生成 2^i*3^j 形式的整数，其中 i,j >=0,0 按升序排列。

我认为使用生成器的目的是减少内存消耗。我已经尝试这样做有一段时间了，但没有成功。请帮忙。

原文

I have a generator which produces all positive integers that are powers of 2, and another which produces all integers that are powers of 3. I now need to use those to produce integers of the form 2^i*3^j where i,j >=0,0 in the increasing order.

The point of using generators is to reduce memory consumption, I think. I have been trying to do this for a while now to no avail. Please help out.

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论， 你可以免费 注册 一个本站的账号。

评论（7）

鲜血染红嫁衣 2024-08-23 11:48:57

使用自读流

您可以使用自读流来解决这个问题：

   -----------        -----------
   |  pow 2  |------->|         |
   -----------        |         |
                      |  merge  |-------+------------>
   -----------        |         |       |
.->|   x 3   |------->|         |       |
|  -----------        -----------       |
\_______________________________________/

第一个流产生 2 的幂，
而第二个则确保所有生成的数字
乘以 3 并重新注入到输出中。
合并运算符确保输出已排序。

请注意，我们必须用 1 为输出流“播种”，
或者第一个元素在求值时会尝试生成自身。

这是代码：

(require srfi/41)

(define (merge s1 s2)
  (stream-match s1 ((x . xs)
    (stream-match s2 ((y . ys)
      (if (< x y)
        (stream-cons x (merge xs s2))
        (stream-cons y (merge ys s1))))))))

(define (the-stream)
  (letrec ((s
    (stream-cons 1 (merge (stream-map     (lambda (x) (* 3 x)) s)
                          (stream-iterate (lambda (x) (* 2 x)) 2)))))
  s))

与我的其他提案相比，它非常简单且快速，
因为它除了单调性之外还使用了问题的算术属性。
我错了，它也可以被推广（即将推出）

$ mzscheme -f feedback.scm -e '(display (stream->list (stream-take 20 (the-stream))))'
(1 2 3 4 6 8 9 12 16 18 24 27 32 36 48 54 64 72 81 96)

$ time mzscheme -f feedback.scm -e '(display (stream-ref (the-stream) 10000))'
161968247347450370721577384417107686788864605658546176
real    0m1.746s
user    0m1.344s
sys     0m0.156s

使用生成器和队列

我们也可以使用 python 的生成器来实现它，
但我们需要使用队列来存储在反馈循环中等待的数字：

# Merge the output of two generators
def merge(g1, g2):
    v1 = g1.next()
    v2 = g2.next()
    while 1:
        if v1 < v2:
            yield v1
            v1 = g1.next()
        else:
            yield v2
            v2 = g2.next()

# Generates the powers of 2, starting with n
def pow2(n):
    while 1: yield n; n *= 2

# Generates values shifted from the given 'q' and multiplied by 3
def mul3(q):
    while 1: yield q.pop(0) * 3

# The generator we want
def pow23():
    q = []
    v = 1
    g = merge(pow2(2), mul3(q))
    while 1:
        yield v
        q.append(v)
        v = g.next()

g23 = pow23()
for i in range(10000): g23.next()
print g23.next()

这有点不太优雅（恕我直言），
但生成器更加轻量级：

$ time python feedback.py 
161968247347450370721577384417107686788864605658546176
real    0m0.150s
user    0m0.112s
sys     0m0.012s

为了值得，我做了一个方案实现
（使用闭包作为生成器）
这显示了大致相同的性能。

Using a self-reading stream

You can solve this using a self-read stream:

   -----------        -----------
   |  pow 2  |------->|         |
   -----------        |         |
                      |  merge  |-------+------------>
   -----------        |         |       |
.->|   x 3   |------->|         |       |
|  -----------        -----------       |
\_______________________________________/

The first stream produces the powers of two,
while the second one ensures all the generated numbers
are multiplied by 3 and reinjected into the output.
The merge operator ensures that the output is sorted.

Note that we must "seed" the output stream with 1,
or the first element will try to produce itself when evaluated.

Here is the code:

(require srfi/41)

(define (merge s1 s2)
  (stream-match s1 ((x . xs)
    (stream-match s2 ((y . ys)
      (if (< x y)
        (stream-cons x (merge xs s2))
        (stream-cons y (merge ys s1))))))))

(define (the-stream)
  (letrec ((s
    (stream-cons 1 (merge (stream-map     (lambda (x) (* 3 x)) s)
                          (stream-iterate (lambda (x) (* 2 x)) 2)))))
  s))

It's quite simple and fast compared to my other proposal,
because it uses arithmetic properties of the problem besides monotonicity.
I'm wrong, it can be generalized just as well (upcoming)

$ mzscheme -f feedback.scm -e '(display (stream->list (stream-take 20 (the-stream))))'
(1 2 3 4 6 8 9 12 16 18 24 27 32 36 48 54 64 72 81 96)

$ time mzscheme -f feedback.scm -e '(display (stream-ref (the-stream) 10000))'
161968247347450370721577384417107686788864605658546176
real    0m1.746s
user    0m1.344s
sys     0m0.156s

Using generators and a queue

We can also implement this with python's generators,
but we need to use a queue to store the numbers waiting in the feedback loop:

# Merge the output of two generators
def merge(g1, g2):
    v1 = g1.next()
    v2 = g2.next()
    while 1:
        if v1 < v2:
            yield v1
            v1 = g1.next()
        else:
            yield v2
            v2 = g2.next()

# Generates the powers of 2, starting with n
def pow2(n):
    while 1: yield n; n *= 2

# Generates values shifted from the given 'q' and multiplied by 3
def mul3(q):
    while 1: yield q.pop(0) * 3

# The generator we want
def pow23():
    q = []
    v = 1
    g = merge(pow2(2), mul3(q))
    while 1:
        yield v
        q.append(v)
        v = g.next()

g23 = pow23()
for i in range(10000): g23.next()
print g23.next()

This is somewhat less elegant (IMHO),
but the generators are much more lightweight:

$ time python feedback.py 
161968247347450370721577384417107686788864605658546176
real    0m0.150s
user    0m0.112s
sys     0m0.012s

For what is worth, I have done a scheme implementation
(using closures as generators)
which shows roughly the same performance.

回复 原文
夜深人未静 2024-08-23 11:48:57

我对发电机不太了解
但是我可以提出一个基于流的解决方案（延迟构建，
可能是无限列表），这有点相似。

我的方法是创建一个流
其“状态”本身就是一串串流。

个体的、内在的数字流，
我们称它们为 3 流，
表示从 1 开始的 3 的连续幂的列表，
乘以给定的二的幂。
然后我们可以组装无限个这样的 3 流，
从 1 开始，每个连续的 2 次幂 1。
我们称之为 2 流。

在 ascii-art 中，初始状态是这样的：

---------------------- --- -- -
| The 2-stream ...
--|----|----|----|---- --- -- -
  V    V    V    V
 |1| | 2| | 4| | 8|
 |3| | 6| |12| |24| ...
 |9| |18| |36| |72|         The 3-streams
  :    :    :    :

现在，我们要操纵它，以便在任何时刻，
3 个流将在 2 个流内排序
关于他们的第一个要素。
结果是下一个最小的生成数
将始终是第一个 3 流的第一个元素。

因此，要获得您希望获得的序列中的下一个数字，
我们要拉出第一个 3 流，
取出它的第一个元素（这是我们感兴趣的数字），
然后将3流重新插入2流中
位于由其新第一个元素确定的位置。
提取第一个数字 (1) 后的新状态将是：

---------------------- --- -- -
| The 2-stream ...
---|----|----|----|---- --- -- -
   V    V    V    V
 | 2| | 3| | 4| | 8|
 | 6| | 9| |12| |24| ...
 |18| |27| |36| |72|         The 3-streams
  :    :    :    :

请注意，此方法不具体依赖于 2^i、3^j 或乘法
（只是 2^i * 3^j 随着 i 和 j 单调递增）。
我已经发布了另一个答案，并且
结果是更加简单和快速。
不要相信我：它与数学无关

下面是一个示例实现，使用 SRFI-41 流：

(require srfi/41)

; Geometric sequence with initial value 'init', and ratio 'r'
(define (make-geoseq init r)
  (stream-cons
    init
    (make-geoseq (* r init) r)))

; Your power generators
(define pow2 (make-geoseq 1 2))
(define pow3 (make-geoseq 1 3))

; Construct a 3-stream from the pow3 sequence
(define (make-3stream mult)
  (stream-map (lambda (x) (* mult x)) pow3))

; Construct the (initial) 2-stream from the pow2 sequence
(define initial-2stream
  (stream-map make-3stream pow2))

; Insert a modified 3-stream into the given 2-stream, at the right position
(define (insert two-stream three-stream)
  (if (< (stream-car three-stream)
         (stream-car (stream-car two-stream)))
    ; we have the smallest 3-stream, put it at the front
    (stream-cons
      three-stream
      two-stream) 
    ; otherwise, recurse
    (stream-cons
      (stream-car two-stream)
      (insert (stream-cdr two-stream) three-stream))))

; Construct a 2^n * 3^p stream with the given 2-stream as its "state"
(define (make-the-stream current-2stream)
  (let*
    ; pull out the first 3-stream
    ((first-3s (stream-car current-2stream))
     (other-3s (stream-cdr current-2stream))
     ; use its first element as our next value
     (next-val (stream-car first-3s))
     ; reinsert its tail into the 2-stream's tail
     (next-2s (insert other-3s (stream-cdr first-3s))))

    ; and use the resulting 2-stream to construct the (outer) stream's tail
    (stream-cons
      next-val
      (make-the-stream next-2s))))

; Now, we can construct the stream we want
(define the-stream (make-the-stream initial-2stream))

使用 plt-scheme（在我相当蹩脚的硬件上）：

$ mzscheme -f pow23.scm -e '(display (stream->list (stream-take 20 the-stream)))'
(1 2 3 4 6 8 9 12 16 18 24 27 32 36 48 54 64 72 81 96)

$ time mzscheme -f pow23.scm -e '(display (stream-ref the-stream 10000))'
161968247347450370721577384417107686788864605658546176
real    0m12.550s
user    0m11.005s
sys     0m0.340s

我想可以用生成器来实现这个，
但棘手的部分是实现(insert)。
你可以通过组合生成器来做到这一点，
但每次拉出一个数字时，你最终都会添加一个“层”，
而使用 (insert) 创建的流与原始流共享其尾部
（“层”最终合并）。

I don't know much about generators,
however I can propose a solution based on streams (lazily constructed,
possibly infinite lists), which are somewhat similar.

My approach would be to create a stream
whose "state" itself would be a stream of streams.

The individual, inner streams of numbers,
let's call them the 3-streams,
would represent lists of the successive powers of 3, starting with 1,
multiplied by a given power of two.
We can then assemble an infinity of such 3-streams,
one for each successive power of 2, starting with 1.
Let's call this the 2-stream.

The initial state, in ascii-art, is this:

---------------------- --- -- -
| The 2-stream ...
--|----|----|----|---- --- -- -
  V    V    V    V
 |1| | 2| | 4| | 8|
 |3| | 6| |12| |24| ...
 |9| |18| |36| |72|         The 3-streams
  :    :    :    :

Now, we're going to manipulate this so that at any moment,
the 3-streams will be ordered within the 2-stream
with regards to their first elements.
As a consequence the next smallest generated number
will always be the first element of the first 3-stream.

So, to get the next number in the sequence you wish to obtain,
we're going to pull out the first 3-stream,
pull out its first element (which is the number we're interested in),
and then re-insert the 3-stream in the 2-stream
at a position determined by its new first element.
The new state after the first number (1) has been extracted would be:

---------------------- --- -- -
| The 2-stream ...
---|----|----|----|---- --- -- -
   V    V    V    V
 | 2| | 3| | 4| | 8|
 | 6| | 9| |12| |24| ...
 |18| |27| |36| |72|         The 3-streams
  :    :    :    :

Note that this method does not depend on 2^i, 3^j or multiplication specifically
(just on 2^i * 3^j being monotonically increasing with i and j).
I have posted another answer which does, and
is much more simple and fast as a result.
don't trust me: it has nothing to do with the math

Below is an example implementation, using SRFI-41 streams:

(require srfi/41)

; Geometric sequence with initial value 'init', and ratio 'r'
(define (make-geoseq init r)
  (stream-cons
    init
    (make-geoseq (* r init) r)))

; Your power generators
(define pow2 (make-geoseq 1 2))
(define pow3 (make-geoseq 1 3))

; Construct a 3-stream from the pow3 sequence
(define (make-3stream mult)
  (stream-map (lambda (x) (* mult x)) pow3))

; Construct the (initial) 2-stream from the pow2 sequence
(define initial-2stream
  (stream-map make-3stream pow2))

; Insert a modified 3-stream into the given 2-stream, at the right position
(define (insert two-stream three-stream)
  (if (< (stream-car three-stream)
         (stream-car (stream-car two-stream)))
    ; we have the smallest 3-stream, put it at the front
    (stream-cons
      three-stream
      two-stream) 
    ; otherwise, recurse
    (stream-cons
      (stream-car two-stream)
      (insert (stream-cdr two-stream) three-stream))))

; Construct a 2^n * 3^p stream with the given 2-stream as its "state"
(define (make-the-stream current-2stream)
  (let*
    ; pull out the first 3-stream
    ((first-3s (stream-car current-2stream))
     (other-3s (stream-cdr current-2stream))
     ; use its first element as our next value
     (next-val (stream-car first-3s))
     ; reinsert its tail into the 2-stream's tail
     (next-2s (insert other-3s (stream-cdr first-3s))))

    ; and use the resulting 2-stream to construct the (outer) stream's tail
    (stream-cons
      next-val
      (make-the-stream next-2s))))

; Now, we can construct the stream we want
(define the-stream (make-the-stream initial-2stream))

Using plt-scheme (on my rather crappy hardware):

$ mzscheme -f pow23.scm -e '(display (stream->list (stream-take 20 the-stream)))'
(1 2 3 4 6 8 9 12 16 18 24 27 32 36 48 54 64 72 81 96)

$ time mzscheme -f pow23.scm -e '(display (stream-ref the-stream 10000))'
161968247347450370721577384417107686788864605658546176
real    0m12.550s
user    0m11.005s
sys     0m0.340s

Implementing this with generators could be done I guess,
but the tricky part would be implementing (insert).
You could do so by composing generators,
but you would end up adding one "layer" every time a number is pulled,
whereas a stream created with (insert) shares its tail with the original one
(the "layers" eventually merge).

回复 原文
云雾 2024-08-23 11:48:57

只需合并从此处提取的两个有序列表即可

(define merge
  (lambda (pred ls1 ls2)
    (cond
      [(null? ls1) ls2]
      [(null? ls2) ls1]
      [(pred (car ls1) (car ls2))
       (cons (car ls1) (merge pred (cdr ls1) ls2))]
      [else (cons (car ls2) (merge pred ls1 (cdr ls2)))])))

。

Just merge the two ordered lists a la

(define merge
  (lambda (pred ls1 ls2)
    (cond
      [(null? ls1) ls2]
      [(null? ls2) ls1]
      [(pred (car ls1) (car ls2))
       (cons (car ls1) (merge pred (cdr ls1) ls2))]
      [else (cons (car ls2) (merge pred ls1 (cdr ls2)))])))

lifted from here.

回复 原文
甩你一脸翔 2024-08-23 11:48:57

没有任何示例的简单解决方案是创建一个新的解决方案。

for (i = 0; i < X; i++)
{
 if (i%2 or i%3)
 {
  cout << i
 }
}

编辑：X 是你想要运行它的时间，假设你想要输出 0-100，输入 100。

int counter = 1000;
bool done = false;
while(!done)
{
 if (i%2 or i%3)
 {
  cout << i;
  counter--;
  if(counter <= 1)
   {
     done = true;
   }
 }
i++;
}

这有点乱，但应该可以。

编辑：计数器应该以 1 结束，否则它会给你 1001 个项目。

The simple solution w/o any examples is creating a new one.

for (i = 0; i < X; i++)
{
 if (i%2 or i%3)
 {
  cout << i
 }
}

edit: X is how long you want to run it say you want output 0-100 put 100.

int counter = 1000;
bool done = false;
while(!done)
{
 if (i%2 or i%3)
 {
  cout << i;
  counter--;
  if(counter <= 1)
   {
     done = true;
   }
 }
i++;
}

It's a little messy but should work.

edit: The counter should end at 1 or it will give you 1001 items.

回复 原文
婴鹅 2024-08-23 11:48:57

至少如果我理解你的问题，你只需要合并两个生成器的结果：

  1. 从每个生成器生成一个输出 生成
  2. 两个生成器中较小的一个作为下一个输出
  3. 从该生成器生成下一个输出
  4. 返回到步骤 2

如果两个生成器产生相等的值，将其作为输出，并从每个生成器生成下一个值。

请注意，虽然它通常用于对现有数据进行排序而不是生成新数据，但这与普通合并排序中使用的合并类似，但我假设您不想要重复项，而合并排序通常会保留重复项重复。

编辑：感谢 lpthnc，我重新阅读了这个问题，我认为他是对的——我误读了原来的问题。为了获得正确的输出，您需要创建第三个生成器并生成（在本例中）六的倍数，​​并在该结果集与其他两个生成器的结果集之间使用三向合并。

我没怎么玩过它，但我相信最近迭代的 PLT 方案中的惰性语言级别（或惰性模块）将让您编写代码来生成整个无限序列，理论上这将使用无限的时间和内存，但是仅根据需要评估其中的有限子集。

At least if I understand your question, you just need to merge the results from the two generators:

  1. Generate an output from each generator
  2. Produce the smaller of the two as the next output
  3. Generate the next output from that generator
  4. Go back to Step 2

If the two generators produce equal values, produce that as the output, and generate the next value from each generator.

Note that although it's typically used for sorting existing data instead of generating new data, this is similar to the merge used in a normal merge sort, with the exception that I've assumed you don't want duplicates, where a merge sort normally retains duplicates.

Edit: Thanks to lpthnc, I've reread the question, and I think he's right -- I misread the original question. To get the correct output, you'd need to create a third generator and produces the multiples of (in this case) six, and use a three-way merge between that result set and those from the other two generators.

I haven't played with it much, but I believe the Lazy language level (or lazy module) in recent iterations of PLT Scheme would let you write your code to generate the entire infinite sequence, which would theoretically use infinite time and memory, but only evaluate a finite subset of that as needed.

回复 原文
浪漫人生路 2024-08-23 11:48:57

这在 Haskell 中非常简单：

merge as bs =
  case (as, bs) of
    ([], _) -> bs
    (_, []) -> as
    ((a:as'), (b:bs')) ->
      if a <= b
        then a : (merge as' bs)
        else b : (merge as bs')
rmDups as =
  case as of
    [] -> []
    [a] -> [a]
    (a:bs@(b:_)) ->
      if a == b
        then rmDups bs
        else a:(rmDups bs)
take 25 $ rmDups $ merge (map (2^) [1..]) (map (3^) [1..])

产生以下结果：

[2,3,4,8,9,16,27,32,64,81,128,243,256,512,729,1024,2048,2187,4096,6561,8192,16384,19683,32768,59049]

虽然我想有一种更优雅的方法来做到这一点......

This is pretty easy in Haskell:

merge as bs =
  case (as, bs) of
    ([], _) -> bs
    (_, []) -> as
    ((a:as'), (b:bs')) ->
      if a <= b
        then a : (merge as' bs)
        else b : (merge as bs')
rmDups as =
  case as of
    [] -> []
    [a] -> [a]
    (a:bs@(b:_)) ->
      if a == b
        then rmDups bs
        else a:(rmDups bs)
take 25 $ rmDups $ merge (map (2^) [1..]) (map (3^) [1..])

yields the following:

[2,3,4,8,9,16,27,32,64,81,128,243,256,512,729,1024,2048,2187,4096,6561,8192,16384,19683,32768,59049]

though I imagine there's a more elegant way to do it...

回复 原文
任谁 2024-08-23 11:48:57

已编辑。我越看这个问题，就越觉得我完全错了——而其他人似乎已经有了更好的答案。


抱歉，这些都不是方案中的，只是伪代码...

以下代码与我从您的问题中获得的思维过程相匹配：

编辑：修改伪代码现在我意识到它是“2^i*3^j”，不是“2^i, 3^j”

 // If i got close, this time,
 // inputs min-i=0, max-i=2, min-j=0, max-j=2
 // should get output like
 //  2^0 * 3^0 = 1
 //  2^0 * 3^1 = 3
 //  2^0 * 3^2 = 6
 //  2^1 * 3^0 = 2
 //  2^1 * 3^1 = 6
 //  2^1 * 3^2 = 12
 //  2^2 * 3^0 = 4
 //  2^2 * 3^1 = 12
 //  2^2 * 3^2 = 24

 LET min-i, max-i, min-j, max-j be input
 LET current-value = 1

 FOR i = min-i to max-i
   FOR j = min-j to max-j DO
     PRINT "2^" . i . " * j^" . j . " = " . current-value
     current-value *= 3;
   DONE // end j loop

   current-value *= 2
 DONE // end i loop

Redacted. The more I look at this, the more I think I've got it all wrong - and others appear to have better answers, already.


Sorry, none of this is in scheme, just pseudocode...

The following code matches the thought process I garner from your question:

EDIT: revised pseudocode now that I realize it's "2^i*3^j", not "2^i, 3^j"

 // If i got close, this time,
 // inputs min-i=0, max-i=2, min-j=0, max-j=2
 // should get output like
 //  2^0 * 3^0 = 1
 //  2^0 * 3^1 = 3
 //  2^0 * 3^2 = 6
 //  2^1 * 3^0 = 2
 //  2^1 * 3^1 = 6
 //  2^1 * 3^2 = 12
 //  2^2 * 3^0 = 4
 //  2^2 * 3^1 = 12
 //  2^2 * 3^2 = 24

 LET min-i, max-i, min-j, max-j be input
 LET current-value = 1

 FOR i = min-i to max-i
   FOR j = min-j to max-j DO
     PRINT "2^" . i . " * j^" . j . " = " . current-value
     current-value *= 3;
   DONE // end j loop

   current-value *= 2
 DONE // end i loop

回复 原文
~没有更多了~

关于作者

桃扇骨

暂无简介

0 文章
0 评论
23 人气
发私信

相关话题

更多

热门标签

操作系统 程序设计 IT运维 Linux系统管理 JavaScript 服务器应用 solaris C/C++ PHP Shell BSD Vue.js aix Oracle Python HTML 系统管理 HTML5 CSS 前端
更多

推荐作者

留蓝

文章 0 评论 0

18790681156

文章 0 评论 0

zach7772

文章 0 评论 0

Wini

文章 0 评论 0

ayeshaaroy

文章 0 评论 0

初雪

文章 0 评论 0

更多

友情链接

文江博客
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
    原文