标签: non-deterministic

几个月前,我开始在C中开发用于空间应用的实时系统软件,以及用于C++的微控制器.在这样的系统中有一个经验法则,即永远不应该创建堆对象(因此没有malloc/new),因为它使程序不确定.当人们告诉我时,我无法验证此声明的正确性.那么,这是正确的陈述吗？

对我来说困惑的是,据我所知,确定性意味着两次运行程序将导致完全相同的执行路径.根据我的理解,这是多线程系统的一个问题,因为多次运行相同的程序可能每次都以不同的顺序运行不同的线程.

我做了很少的遗传算法; 他们工作(他们很快找到合理的解决方案).但我现在发现了TDD.有没有办法以TDD方式编写遗传算法(严重依赖于随机数)？

为了更一般地提出问题,如何测试非确定性方法/函数.这是我想到的:

1. 使用特定的种子.如果我首先在代码中犯了一个错误,但在重构时有助于发现错误,那将无济于事.

2. 使用已知的数字列表.与上面类似,但我可以手动遵循代码(这将非常繁琐).

3. 使用常数.至少我知道会发生什么.当RandomFloat(0,1)总是返回1时,确保骰子总是读取6是很好的.

4. 尝试尽可能多地从GA中移出非确定性代码.这看起来很愚蠢,因为这是它的目的的核心.

关于测试的非常好的书籍的链接也将受到赞赏.

我最近从Python 2.7切换到Python 3.3,似乎在Python 2中,字典键的排序是任意的但是一致的,在Python 3中,用例如获得的字典的键的排序vars()看起来是非确定性的.

如果我跑:

class Test(object): pass
parameters = vars(Test)
print(list(parameters.keys()))

在Python 2.7和Python 3.3中,然后:

• Python 2.7一直给我

  ['__dict__', '__module__', '__weakref__', '__doc__']
  

  Run Code Online (Sandbox Code Playgroud)

• 使用Python 3.3,我可以得到任何随机顺序 - 例如:

  ['__weakref__', '__module__', '__qualname__', '__doc__', '__dict__']
  ['__doc__', '__dict__', '__qualname__', '__module__', '__weakref__']
  ['__dict__', '__module__', '__qualname__', '__weakref__', '__doc__']
  ['__weakref__', '__doc__', '__qualname__', '__dict__', '__module__']
  

  Run Code Online (Sandbox Code Playgroud)

这种非决定论来自哪里？为什么会这样

list({str(i): i for i in range(10)}.keys())

......在跑步之间保持一致,总是给予

['3', '2', '1', '0', '7', '6', '5', '4', '9', '8']

......？

我不理解非确定性图灵机的概念.我想我理解术语非确定性算法 :(非确定性算法是一种算法,可以在不同的运行中表现出不同的行为,而不是确定性算法.)所以算法可能是这样的:

a = fromSomeAlgo();

if(a > foo)
   stateA();
else
   stateB();

但是对于我读过的非确定性图灵机,它可以在给定时间处于多个状态.另外一篇维基百科文章暗示"非确定性图灵机(NTM),可能有一套规则,规定了针对特定情况的多个动作".

那是什么意思 ？..对于给定的情况,不止一个行动......多个州......我根本就不明白这一点.

任何人都可以解释(更好的用简单英语的例子)列表monad可以做什么来模拟非确定性计算？即问题是什么以及列表monad可以提供什么解决方案.

我有以下用户定义的函数:

create function [dbo].[FullNameLastFirst]
(
    @IsPerson bit,
    @LastName nvarchar(100),
    @FirstName nvarchar(100)
)
returns nvarchar(201)
as
begin
    declare @Result nvarchar(201)
    set @Result = (case when @IsPerson = 0 then @LastName else case when @FirstName = '' then @LastName else (@LastName + ' ' + @FirstName) end end)
    return @Result
end

我无法使用此函数在计算列上创建索引,因为它不是确定性的.有人可以解释为什么它不是确定性的,最终如何修改以使其具有确定性？谢谢

我知道在Prolog中你可以做类似的事情

someFunction(List) :- 
    someOtherFunction(X, List)
    doSomethingWith(X)
    % and so on

这不会迭代List中的每个元素; 相反,它将分支到不同的"机器" (通过使用多个线程,在单个线程上回溯,创建并行Universe或者你是什么),并为每个可能的X值执行单独的执行,导致someOtherFunction(X, List)返回true!
(我不知道它是如何做到的,但这对问题并不重要)

我的问题是: 还有哪些其他非决定性编程语言？ 似乎非确定性是在具有不可变变量的语言中实现多线程的简单化和最合乎逻辑的方式,但我以前从未见过这样做 - 为什么这种技术不再流行？

我观察到运行以下java代码的错误行为:

public class Prototype {
  public static void main(String[] args) {
    final int start = Integer.MAX_VALUE/2;
    final int end = Integer.MAX_VALUE;
    {
      long b = 0;
      for (int i = start; i < end; i++) {
        b++;
      }
      System.out.println(b);
    }
    {
      long b = 0;
      for (int i = start; i < end; i++) {
        b++;
      }
      System.out.println(b);
    }
  }
}

两个循环完全相同.然而,第二个输出非确定性的错误值.我正在使用Version在Linux上运行代码:

java version "1.6.0_25"
Java(TM) SE Runtime Environment (build 1.6.0_25-b06)
Java HotSpot(TM) 64-Bit Server VM (build 20.0-b11, mixed mode) …

我正在尝试编写一个脚本来计算所有可能的模糊字符串匹配匹配到一个短字符串,或'kmer',并且在Python 2.7.X中工作的相同代码给了我一个非确定性的答案与Python 3.3 .X,我无法弄清楚为什么.

我在我的代码中遍历字典,itertools.product和itertools.combinations,但我迭代完所有这些完成而没有中断或继续.另外,我将所有结果存储在一个单独的字典中,而不是我正在迭代的字典中.简而言之 - 我没有犯任何明显的错误,为什么Python2和Python3之间的行为有所不同？

示例,稍微简化的代码如下:

import itertools

def find_best_fuzzy_kmer( kmers ):
    for kmer, value in kmers.items():
        for similar_kmer in permute_string( kmer, m ):
            # Tabulate Kmer

def permute_string( query, m ):
    query_list = list(query)
    output = set() # hold output
    for i in range(m+1):
        # pre-calculate the possible combinations of new bases
        base_combinations = list(itertools.product('AGCT', repeat=i))
        # for each combination `idx` in idxs, replace str[idx]
        for positions in itertools.combinations(range(len(query_list)), i):
            for bases in base_combinations:
                # Generate Permutations …

不太了解Haskell中并发性和并行性的上下文中的确定性.一些例子会有所帮助.谢谢