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

定义代码

       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, 感觉这样做无意义。另外为什么需要这个守卫条件不是很理解。

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

首先谢谢对问题关注和回复。
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,这种笔误可能性比较小,猜测可能是为了便于阅读和理解,不过我还是不很理解

数组迭代的时候用的辨识器是索引(Int,不可变),应该是有区别的

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

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

谢谢回复和解惑,通过查看接口文档和帮助文件,对迭代机制接口设计有了更好理解。英文帮助文档说“ 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.

备案号:京ICP备17009874号-2