use*_*457 1 math concurrency combinatorics
我决定学习并发性,并希望了解来自两个不同进程的指令可以重叠的方式.两个进程的代码只是一个10迭代循环,在每次迭代中执行3条指令.我想出了一个问题,包括将X指令固定在一个点,然后在空间之间安装来自另一个进程的其他X指令,同时考虑到它们必须被排序(进程B的指令4必须总是在指令20之前).
我编写了一个程序来计算这个数字,查看结果我发现解决方案是n组合k,其中k是在一个过程的整个循环中执行的指令数,因此对于10次迭代,它将是30,并且n是k*2(2个过程).换句话说,n个固定的n个对象并且必须在空间中拟合n/2而没有后者n/2失去它们的顺序.
好的问题解决了.不,不是真的.我不知道为什么会这样,我明白组合的定义是,你可以用多少种方式从一组n中取k个元素,这样所有的组都是不同的,但你采用这些元素的顺序并不是'无所谓.在这种情况下,我们有n个元素,我们实际上是全部,所有指令都被执行(n C n).
如果一个人说,有2K蓝色(A)和红色(B)解释了它在一个袋子对象,你从包里取k个对象,你仍然只有k取指令时,2K指令实际执行.你能否对此有所了解？
提前致谢.
FWIW可以这样看:你有一个包含k蓝色和k个红色球的包.相同颜色的球是难以区分的(类似于同一过程/线程中的指令顺序是固定的限制 - 在现代处理器中不是这样,但现在让我们保持简单).有多少种方法可以将所有球从包中取出来？
我的组合技能非常生疏,但我的第一个猜测是
(2k!)
-----
2*k!
根据维基百科的说法,这确实是平等的
(2k)
(k )
(对不起,我不知道如何展示这个).
对于n个过程,可以通过在袋中具有n种不同颜色的球来概括.
更新:请注意,从严格意义上讲,这仅模拟了在单个处理器上执行不同进程的情况,因此所有进程的所有指令都必须在处理器级别进行线性排序.在多处理器环境中,可以同时按字面执行多条指令.