标签: non-deterministic

是否可以在C#中实施McCarthy的amb-operator用于非确定性选择？

显然.NET缺乏持续支持但yield return可能有用.这可能在其他静态.NET语言中如F#吗？

在这个页面中,在帖子之后有一个评论,它给出了一个非常短的实现amb过程:

(define (amb-backtrack)
  (error "no solution found"))

(define (amb . args)
  (call/cc (lambda (return)
             (let ((backtrack amb-backtrack))
               (map (lambda (x)
                      (call/cc (lambda (k)
                                 (set! amb-backtrack k)
                                 (return x))))
                    args)
               (backtrack 'fail)))))

但我通常看到amb实现为宏 - 在schemers.org常见问题解答中,以及在Dorai Sitaram的书中:

(define amb-fail '*)

(define initialize-amb-fail
  (lambda ()
    (set! amb-fail
      (lambda ()
        (error "amb tree exhausted")))))

(initialize-amb-fail)

(define-macro amb
  (lambda alts...
    `(let ((+prev-amb-fail amb-fail))
       (call/cc
        (lambda (+sk)

          ,@(map (lambda (alt)
                   `(call/cc
                     (lambda (+fk)
                       (set! amb-fail
                         (lambda ()
                           (set! …

所以我正在研究我已经提出的下推自动机和无上下文语言的测试,我坚持这个结构.

我让这个自动机的每个部分都完全正常工作,除了我将在下面解释的一个部分.

它需要识别的语言是:{x#y#z#w | x,y,z,w在{0,1} +中,其中x≠w且y≠z}.

所以我遇到的问题是将Xi与Wi进行比较,因为Wi的元素在自动机处理W时是不知道的,就像我设计的那样.

如果我存储X的内容,当弹出时间并将每个元素与W的元素进行比较时,它们将以相反的顺序弹出,因此认为000111和111000是相同的字符串,而PDA将拒绝,当它应该明确接受(它们是不同的字符串).这只是一个例子,这也会导致错误地分析其他输入.

如果有一种方法可以按相反的顺序将X的内容压入堆栈,它们将以原始形式弹出,这样我就可以正确地比较字符串的内容.

如果在正常推送后有一种方法可以反转堆栈的内容,这也可以让我得出解决方案.

任何帮助将不胜感激.谢谢.

尝试从集合中选择伪随机元素时，我看到了不确定的行为，即使已为RNG注入了种子（如下所示的示例代码）。为什么会发生这种情况，我是否应该期望其他Python数据类型显示类似的行为？

注意：我仅在Python 2.7上进行了测试，但是在两台不同的Windows计算机上都可以重现。

相似的问题：Python随机种子无法与遗传编程示例代码一起使用时的问题可能相似。根据我的测试，我的假设是，集合之间的运行间内存分配差异导致针对同一RNG状态拾取不同的元素。

迄今为止，我还没有在Python文档中找到关于set或random的这种警告/问题。

示例代码（randTest生成不同的运行结果）：

import random

''' Class contains a large set of pseudo-random numbers. '''
class bigSet:
    def __init__(self):
        self.a = set()
        for n in range(2000):
            self.a.add(random.random())
        return


''' Main test function. '''
def randTest():
    ''' Seed the PRNG. '''
    random.seed(0)

    ''' Create sets of bigSet elements, presumably many memory allocations. ''' 
    b = set()
    for n in range (2000):
        b.add(bigSet())

    ''' Pick a random value from a random bigSet. Would have expected this to …

我们有一个庞大而复杂的功能,需要具有确定性.它是我们公司的主力之一,涵盖了大量的代码.由于python的dict迭代器,这段代码经常变得不确定.这已经发生了很多次,并且很难追踪,并且通常不会立即注意到.我们想编写一个自动测试来检测非确定性,但我不知道该怎么做.

我们已经尝试在循环中运行函数,并且测试结果总是相同的,但有时,即使函数是非确定性的,函数也会通​​过此测试,因为dict迭代器的任意但有些一致的排序.

有没有办法编写自动化测试来捕获这种bug？

也许有一种方法来破解python的dict,以便迭代器在这个测试中是随机的而不是随意的？那样重复调用函数会更容易发生分歧吗？这似乎是一个相当复杂的方法,但我想不出任何其他方式.

编辑:

我们目前正在使用Python 2.7.

我们对各个子模块进行了单元测试,但由于字典顺序的任意但一致的性质,它们通常不会暴露非确定性.

此外,也许非确定性不是描述这个问题的正确方法.这个函数接受{id:data},但是id的值不应该影响代码的结果,但是由于python dict的排序,它有时会这样做.也许测试这个的最好方法是用随机值替换id,并检查在使用不同id的多次运行后输出是否相同.

在下面的代码中,如何替换put 1某些在该状态下插入非确定性1或2的代码？

import Control.Monad.List
import Control.Monad.Trans.State

test :: StateT Int [] Int
test = do
  put 1
  v <- get
  return v

我正在尝试在T-SQL中使用LAG来计算一些滞后功能.当LAG参考页面说这个函数是非确定性的时候,我有点担心.关于函数确定性的参考页面说"在查询中指定ORDER BY子句不会改变在该查询中使用的函数的确定性".但是,我不明白为什么LAG会在相同条件下返回不同的结果.如果是这样,为什么人们会使用它？也许我不是正确地解释"决定论"？谢谢!

鉴于我认为是相同的 Swift UUID，我hashValue在后续运行代码时得到了不同的 s。在单次运行中它是一致的。

例如：

func UUIDTest() {
    let uuid = UUID(uuidString: "00000000-0000-0000-0000-000000000001")
    
    let h = uuid.hashValue
    
    print("\(String(describing: uuid)) -> \(h)")
    
    /*
     
     Run #1:
     Optional(00000000-0000-0000-0000-000000000001) -> 8072320274727128679

     Run #2:
     Optional(00000000-0000-0000-0000-000000000001) -> -2566074080105686496

     */
}

文档并未明确说明哈希值是否严格属于 UUID 的函数，或者是否还有其他成分。

对于 Hashable 是否有一些我还没有的理解？

使用Google Test，我想测试Server.AcceptRequest方法的行为：

class Server {
public:
    // Clients can call this method, want to test that it works
    Result AcceptRequest(const Request& request) {
        queue_.Add(request);
        ... blocks waiting for result ...
        return result;
    }
private:
    // Executed by the background_thread_;
    void ProcessRequestsInQueue() {
        while (true) {
            Process(queue_.PopEarliest());
        }
    }

    MySynchronizedQueue queue_;
    std::thread background_thread_ = thread([this] {ProcessRequestsInQueue();});
};

该方法接受客户端请求，将其排队，阻止等待结果，并在可用时返回结果。

当后台线程处理队列中的相应请求时，结果可用。

我有一个测试，如下所示：

TEST(ServerTest, TwoRequests) {
    Server server;
    Result r1 = server.AcceptClientRequest(request1);
    Result r2 = server.AcceptClientRequest(request2);
    ASSERT_EQ(r1, correctResultFor1);
    ASSERT_EQ(r2, correctResultFor2); …

我正在使用 Petgraph 的toposort函数来获取图表节点的排序列表。toposort然而，不保证同一级别的所有节点都将以一致的确定性顺序返回。Petgraph 中是否还有其他选项可以按确定性顺序返回节点，或者我需要编写自己的函数吗？（如果是的话，有什么指示吗？）