MIT 18.S191 | 计算机思维导论-Julia, 笔记中1.7节利用迭代器生成路径代码几个疑惑

综合讨论区 Julia入门
1

定义代码

       struct Paths
	    m::Int
	    n::Int
	end
	
	Base.iterate(p::Paths) = fill(1,p.m), fill(1,p.m) #start the iteration with 1's
	Base.IteratorSize(::Type{Paths}) = SizeUnknown()
	
	function Base.iterate(p::Paths, state)
	      if state ≠ fill(p.n,p.m)  # end when each row has an n
	          newstate = next(state,p.n)
    	          return newstate, newstate
	    end
	end
		
	function next(path,n)
	    k = length(path)
	  # start from the end and find the first element that can be updated by adding 1
	    while  k≥2 && ( path[k]==n || path[k]+1 > path[k-1]+1 )
	        k -= 1
	    end   
	    path[k] +=1 #add the one then reset the following elements
	    for j = k+1 : length(path)
	        path[j] = max(path[j-1]-1,1)
	    end
	    return(path)
	end
	
	function allpaths(m,n)
          v=Vector{Int}[]
	  paths = Paths(m,n)
          for p ∈ paths
              push!(v,copy(p))
          end
          v
	end

调用代码

let
	paths1=Paths(6,6)
	v=Vector{Int}[]
	for p in paths1
		push!(v, copy(p))
	end
	length(v), v
end

问题1：调用函数中为什么用copy函数，如果不用copy函数结果只包含两种类型，length(v)=950, v=[[1,1,1,1,1,1],[6,6,6,6,6,6],[6,6,6,6,6,6]…]；如果用copy函数则结果正常。
问题2：next函数中，while循环中 ( path[k]==n || path[k]+1 > path[k-1]+1 )，条件中大于号为什么要同时加上1, 感觉这样做无意义。另外为什么需要这个守卫条件不是很理解。

2

回答1：这个可能是因为p是向量（可变的），第二次调用索引函数的时候p以奇怪的方式被改变了，而不用copy保存的是引用，就会使第二个及以后全部变成最后一次结果
问题2：同时+1可能是作者笔误；看结果似乎是按顺序生成所有k机制数，这个条件注释也写了，是找到第一个需进位处

3

首先谢谢对问题关注和回复。
1。对于问题1的回应。我刚开始也是这么想，但是对于下面这段代码。

aaa=[[1,1,1,1], [2,2,2,2], [3, 3, 3, 3]]
v1 = []
v2 = []
for a in aaa
    push!(v1, a)
    push!(v2, copy(a))
end
v1 == v2

上面代码在终端下执行结果是true，这说明V1保存不是最终a引用指向。

不过从现象上推测，你给的理由似乎是合理，但是我想知道p在那个地方以那种方式被修改了？

2。对于问题2，因为在不等式两边同时加1，这种笔误可能性比较小，猜测可能是为了便于阅读和理解，不过我还是不很理解

4

数组迭代的时候用的辨识器是索引（Int，不可变），应该是有区别的

p在那个地方以那种方式被修改了

这得看代码是怎么被编译的，接口 · Julia中文文档

5

谢谢回复和解惑，通过查看接口文档和帮助文件，对迭代机制接口设计有了更好理解。英文帮助文档说“ Advance the iterator to obtain the next element. If no elements remain, nothing should be returned. Otherwise, a 2-tuple of the next element and the new iteration state should be returned.”（迭代器前进时候获取下一个元素，如果没有元素剩下，就返回"nothing". 否则返回新的元素和新的迭代状态组成元组——对应着接口中while循环内语句 (item, state) = next。）。每次迭代器前进一步，就会执行一次next函数，通过next函数返回元素，在这里实际上也是通过next函数生成所有的路径。

我测试几段代码之后大概把第一个问题搞清楚了。我把next函数改写成如下，不用copy也不会有问题，所以next函数传递参数path时候采用的是引用机制。

function next(path1, n)
      path = copy(path1)
      ...
      return(path)
end

let
	paths1=Paths(3,3)
	v1 = []
        v2 = []
	for p in paths1
                push!(v1, p)
		push!(v2, copy(p))
	end
	v1 == v2
end
# 返回值是true.