标签: non-deterministic

所以我至少有两位教授提到回溯会使算法不确定,而不会对其原因作出太多解释.我想我明白这是怎么发生的,但我无法用语言表达.有人能给我一个简明的解释原因吗？

考虑一个函数choose在库里的编程语言与"规范(choose xs)的非确定性选择一个元素从列表中xs".

我将通过两个替代的非确定性规则直接实现它:

choose :: [a] -> a
choose x:_ = x
choose _:xs = choose xs

但是在Muenster Curry Compiler的 /usr/lib/curry-0.9.11/Success.curry中,它使用辅助函数定义:

choose (x:xs) = choosep x xs
  where choosep x [] = x
        choosep x (_:_) = x
        choosep _ (x:xs) = choosep x xs

编译器提供的模块定义的优点(如果有的话)是什么？2个定义是否完全等价(即使在一些非确定性和未定义值的棘手情况下)？在某些情况下,其中一个更有效吗？

增加:更深入的考虑

cthom06(谢谢!)已经正确地指出我的定义会导致在更多情况下达到未定义的值(因为我们会尝试使用一个空列表参数调用此函数,每次我们的"顶级"调用一次非空列表参数).(嗯,为什么我没有立刻注意到这个考虑因素？..)效率较低.

但我想知道:有任何语义差异吗？可能在一些棘手的情况下,差异是否重要？

我们看到两个定义之间的差异 - 在非空列表的情况下 - 基本上归结为两个潜在定义之间的差异id:

我的定义就像定义id为:

id x = x
id _ = undefined

他们的定义就像定义id正常的方式:

id …

如果输入可以采用无限多的值,则使用列表来模拟非确定性是有问题的.例如

pairs = [ (a,b) | a <- [0..], b <- [0..] ]

这将返回[(0,1),(0,2),(0,3),...]并且永远不会向您显示任何第一个元素不对的对0.

使用Cantor配对功能将列表列表折叠到单个列表中可以解决此问题.例如,我们可以定义一个类似绑定的运算符,它可以更智能地对其输出进行排序

(>>>=) :: [a] -> (a -> [b]) -> [b]
as >>>= f = cantor (map f as)

cantor :: [[a]] -> [a]
cantor xs = go 1 xs
  where
    go _ [] = []
    go n xs = hs ++ go (n+1) ts
      where
        ys = filter (not.null) xs
        hs = take n $ map head ys
        ts = …

当代码等待延迟时间不确定的某种情况时,看起来很多人选择使用指数退避,即等待N秒,检查条件是否满足; 如果没有,等待2N秒,检查条件等.这对于检查恒定/线性增加的时间跨度有什么好处？

相同的数学运算可以在不同的架构或浏览器中返回不同的结果吗？

用户'singpolyma' 在reddit上询问是否存在一些基本结构:

data FailList a e = Done | Next a (FailList a e) | Fail e

建议使用免费的monad,但我想知道是否可以通过applicative functors更一般地建模.在使用Applicatives的抽象中,Bazerman向我们展示了两个应用函子的总和也是一个应用函子,左/右偏向,只要我们在偏差的方向上有一个自然的变换.这听起来像是我们需要的!因此,我开始提出建议,但很快就遇到了问题.谁能看到这些问题的解决方案？:

首先,我们从两个仿函数之和的定义开始.我从这里开始是因为我们想要建模和类型 - 成功或成功以及失败.

data Sum f g a = InL (f a) | InR (g a)

我们想要使用的两个仿函数是:

data Success a = Success [a]
data Failure e a = Failure e [a]

Success直截了当 - 基本上就是这样Const [a].但是,Failure e我不太确定.它不是一个应用程序的函子,因为pure没有任何定义.但是,它是Apply的一个实例:

instance Functor Success where
  fmap f (Success a) = Success a

instance Functor …

我有一个不使用随机化的脚本,当我运行它时会给出不同的答案.每次运行脚本时,我都希望答案是一样的.问题似乎只发生在某些(病态的)输入数据上.

该片段来自为线性系统计算特定类型控制器的算法,它主要由线性代数(矩阵求逆,Riccati方程,特征值)组成.

显然,这对我来说是一个主要的担忧,因为我现在不能相信我的代码能给我正确的结果.我知道条件差的数据结果可能是错误的,但我预计一直都是错误的.为什么我的Windows机器上的答案并不总是一样的？为什么Linux和Windows机器没有给出相同的结果？

我正在使用Python 2.7.9 (default, Dec 10 2014, 12:24:55) [MSC v.1500 32 bit (Intel)] on win 32Numpy版本1.8.2和Scipy 0.14.0.(Windows 8,64位).

代码如下.我也尝试在两台Linux机器上运行代码,脚本总是给出相同的答案(但机器给出了不同的答案).一个是运行Python 2.7.8,Numpy 1.8.2和Scipy 0.14.0.第二个是使用Numpy 1.6.1和Scipy 0.12.0运行Python 2.7.3.

我三次解决Riccati方程,然后打印答案.我每次都期待相同的答案,而不是我得到序列'1.75305103767e-09; 3.25501787302e-07; 3.25501787302e-07' .

    import numpy as np
    import scipy.linalg

    matrix = np.matrix

    A = matrix([[  0.00000000e+00,   2.96156260e+01,   0.00000000e+00,
                        -1.00000000e+00],
                    [ -2.96156260e+01,  -6.77626358e-21,   1.00000000e+00,
                        -2.11758237e-22],
                    [  0.00000000e+00,   0.00000000e+00,   2.06196064e+00,
                         5.59422224e+01],
                    [  0.00000000e+00,   0.00000000e+00,   2.12407340e+01,
                        -2.06195974e+00]])
    B = matrix([[     0.        ,      0.        ,      0.        ],
                    [     0.        ,      0.        ,      0.        ], …

我所谓的确定性程序会在不同的运行中产生一些略有不同的输出.输入,编译器和计算机是不变的.我不确定哪个输出是正确的,因为它看起来总是合理的.

除了对rand()的迷路调用之外,怎么可能呢？

经过一些搜索和阅读文档之后,很明显您可以在SQL Server中编写用户定义的函数,这些函数被标记为确定性或非确定性,具体取决于正文中使用的内置函数.

RAND()列在非确定性函数下(参见msdn文章).那么为什么我不能在函数中使用它呢？

通常,据说多线程程序是非确定性的,这意味着如果它崩溃,则几乎不可能重新创建导致该条件的错误.一个人真的不知道接下来会运行什么线程,以及它什么时候会再次被抢占.

当然这与操作系统线程调度算法有关,而且事实上人们不知道接下来要运行什么线程,以及它将有效运行多长时间.程序执行顺序也起到了作用,等等......

但是如果你有用于线程调度的算法怎么办？如果你知道什么线程正在运行,那么多线程程序是否会变成"确定性",就像在,你将能够重现崩溃？