代码之家 › 专栏 › 技术社区 › Michael

python->方案转换问题

scheme arrays python

Michael · 技术社区 · 17 年前

我目前正在尝试使用scheme语义编写一个Python程序,这样我以后就可以将其翻译成scheme,而不需要依赖很多Python的东西。

我正在尝试使用*、深度优先和广度优先的搜索算法来解决滑动谜题问题(其中你有9个槽和8个方块排列在一个正方形中)。大约11年前,我在Lisp的一些人工智能课上做了这件事,但当时我基本上不知道Lisp,我非常讨厌它,只有回想起来,我才意识到我在用Lisp编写“C”。教授在这件事上没有帮忙。

我有一个python函数,可以很容易地交换两个图块:

def swap(p, (r1, c1), (r2, c2)):  
    # Swaps *any* two locations and returns new configuration  
    # Does not concern itself with zero location, etc  
    # Not sure how to do this functionally  
    p_p = p[:]  
    temp = p_p[r1][c1]  
    p_p[r1][c1] = p_p[r2][c2]  
    p_p[r2][c2] = temp  
    return p_p

我想把它变成你在SICP中可能会发现的东西,避免副作用等。

但这引发了一个问题。我在SICP中读到的所有内容都是通过递归循环的。在恒定时间内访问数组/向量/列表时,我没有看到任何东西。我可以想象一种循环/递归的方式来读取一个元素,但我发现很难想象一种方法来创建一个新的列表,其中某个元素发生了变化,而不会产生副作用,比如set!,而不必诉诸于关于应该更改哪个元素的疯狂if/then/else条款。当考虑二维数组时,这当然会变得更加令人困惑。在这种情况下,python的解决方案是显而易见的,因为它原生支持多维数组。

在C/C++/Python/Matlab/Lua/其他任何语言中,通过[i]语法访问列表/数组都很容易,并且可以直接转换为下面某个面向硬件的指针查找。考虑到SICP版本的scheme中定义的原子操作,我不明白scheme是如何做到这一点的,这些操作看起来都非常面向循环和搜索。向量和列表数组访问函数如何工作以获得恒定时间访问?(我在这里完全是个新手,所以我不确定我会说什么功能)。是否有一个秘密访问的C或汇编库?scheme中是否有任何固有的恒定时间语义可用于列表/数组/向量访问,并且目前可以让我在Python中使用这种习惯用法,而不会感到内疚?

我如何使用Schemish语义在python中重写上述函数?如何在Scheme中重写上述函数?

4 回复 | 直到 13 年前

Draemon 17 年前

您发现最初的问题是试图用Lisp编写C语义。尝试用python编写方案语义不是在重复错误吗?我总是试图将语言X作为一种范式来学习,并以最X化的方式写作。

如果这是一个你知道要迁移的商业应用程序,这可能是合理的,但否则我一开始就只会把它写在scheme中。

Kyle Cronin 17 年前

大约一年前,我用Lisp编写了一个8谜题求解器。我刚刚使用了一个由3个列表组成的列表,每个子列表都有3个元素是数字。它不是恒定的时间,但它是便携式的。

不管怎样,如果你真的有兴趣在功能上做到这一点(Scheme不要求你这样做),最简单的方法是创建一些辅助函数,这些函数在给定行/col的情况下会得到一个特定的值,并在给定行/col的情况下“设置”一个值。set操作将基于旧状态构造新状态,而不是修改原始数据结构。

然后,您可以根据这些get和set操作编写交换操作。以下是我一年前在Common Lisp中写的内容,但它很容易转换为Scheme:

; getval
;
; This function takes a position (r . c) where and returns the corresponding
; number in the 8-puzzle state. For example, if you wanted (1 . 2) from
; ((1 2 3) (4 5 6) (7 8 9)), the value would be 6. The r and c values begin
; at 0.
;
; parameters:  pos    The position to get
;              state  The 8-puzzle state
; returns:     The value at pos in state
(defun getval (pos state)
  (if (null state) 'no-value
      (if (= 0 (car pos))
      (if (= 0 (cdr pos))
          (caar state)
          (getval (cons (car pos) (- (cdr pos) 1)) (list (cdar state))))
      (getval (cons (- (car pos) 1) (cdr pos)) (cdr state)))))

; setval
;
; This function returns a state where the value at pos is replaced by val.
; Like getval, this function is zero-based. Accessing beyond the size of
; the state is undefined (and probably broken)
;
; parameters:  pos    Position to set
;              val    Value to set
;              state  State to modify
; returns:     New state where pos is val
(defun setval (pos val state)
  (if (null state) '()
      (if (= 0 (car pos))
      (if (= 0 (cdr pos))
          (cons (cons val (cdar state)) (cdr state))
          (let ((temp (setval (cons (car pos) (- (cdr pos) 1)) val
                  (cons (cdar state) (cdr state)))))
        (cons (cons (caar state) (car temp)) (cdr temp))))
      (cons (car state) (setval (cons (- (car pos) 1) (cdr pos)) val (cdr state))))))

; state-swap
;
; This function takes a state and two positions and returns a new state with
; the values in those two positions swapped.
;
; parameters:  state  State to swap within
;              a      Position to swap with b
;              b      Position to swap with a
; return:      State with a swapped with b
(defun state-swap (state a b)
  (let ((olda (getval a state)) (oldb (getval b state)))
    (setval a oldb (setval b olda state))))

Brian 17 年前

这里有一种实现方法。使用一个将应用适当映射的函数重新创建列表。

def swap(p, (r1,c1), (r2,c2)):
    def getitem(r,c):
        if (r,c) == (r1,c1): return p[r2][c2]
        elif (r,c) == (r2,c2): return p[r1][c1]
        return p[r][c]
    return [ [getitem(r,c) for c in range(len(p[0]))] for r in range(len(p)) ]

你甚至可以更进一步,使函数成为实际的接口,其中每个交换只返回一个函数,该函数在传递给下面的函数之前进行适当的转换。性能不是特别好,但这是一种相当简单的函数式方法,省去了讨厌的可变数据结构:

def swap(f, (r1,c1), (r2,c2)):
    def getitem(r,c):
        if (r,c) == (r1,c1): return f(r2,c2)
        elif (r,c) == (r2,c2): return f(r1,c1)
        return f(r,c)
   return getitem

l=[ [1,2,3], [4,5,6], [7,8,0]]
f=lambda r,c: l[r][c]    # Initial accessor function
f=swap(f, (2,1), (2,2))  # 8 right
f=swap(f, (1,1), (2,1))  # 5 down
print [[f(x,y) for y in range(3)] for x in range(3)]
# Gives: [[1, 2, 3], [4, 0, 6], [7, 5, 8]]

michael michael 17 年前

太棒了,谢谢你的lisp代码。我需要研究一下,以确保我得到它。

至于第一个答案,我第一次用lisp“写c”,因为这是我知道如何编程的唯一方法,我不知道为什么有人会使用lisp。这一次,我一直在玩scheme,但想使用python,所以如果我被困在某件事上,我可以“作弊”并使用python风格的东西,然后在等待usenet答案的同时,继续解决问题的下一部分。