问一个算法，solution ， 一直没想出来怎么做。

数据从左端输入，然后同时经过7个数据处理流程，每个流程都有一个数据出口。

每个数据处理流程都有7个处理步骤，每个步骤有不同的属性，不同的属性会导致该处理步骤的输出数据不一致。

最简单的方法是数据到来，即copy 7份数据给所有流程，然后各自流程的线程进行处理。但是这样的做法有浪费，性能不够好（空间性能），因为如上图，流程三和流程四有4个相同步骤，只需要流程三处理一次，流程四等待，然后在步骤D完成之后copy给流程四即可。
上表的处理流程应该如下：



另外，这张表中各步骤的属性可能是动态变化的，要求达到最优性能。

该怎么做呢？Thx

15 个解决方案

#1

也就是说完全有可能没有办法共享数据咯？比如第一个步骤的属性全部一样。

#2

全部不一样。

#3

我理解的意思就是对每个流程，找一个跟它有最长前缀匹配的流程。。不知是不是这样？？如果是这样你把每个流程看作一个字符串，排一下序，然后跟它前边那个比较一下就得了。。

#4

这题思路挺有意思, 思路如下:

根据每个步骤构造一颗广义前缀树(trie树), 每个节点包含属性和执行的函数. 叶节点就是每个Task的最后一步. 
主线程从根节点开始. 遇到N个分叉就构造N-1个线程并发运行(包括他自身就是N个线程), 每个线程运行次分叉处的N个子树的下一步(下一个节点). 这样对于每个线程, 就有了一个属于它的子树, 线程运行完一步(节点)后重复上述, 方式. 没有分叉, 继续运行下一步(节点), 有M个分叉, 构造M-1个线程, 并发运行下去.

#5

引用 1 楼 cqdjyy01234 的回复:

也就是说完全有可能没有办法共享数据咯？比如第一个步骤的属性全部一样。

比如流程三和流程四，前4各步骤一致，流程三做一遍就可以，到了步骤E，两个属性不一致了，流程三需要在步骤D结束后copy数据给流程四。

#6

引用 5 楼 ADF1230 的回复:

Quote: 引用 1 楼 cqdjyy01234 的回复:

也就是说完全有可能没有办法共享数据咯？比如第一个步骤的属性全部一样。

比如流程三和流程四，前4各步骤一致，流程三做一遍就可以，到了步骤E，两个属性不一致了，流程三需要在步骤D结束后copy数据给流程四。

引用 4 楼 youyou1912 的回复:

这题思路挺有意思, 思路如下:

根据每个步骤构造一颗广义前缀树(trie树), 每个节点包含属性和执行的函数. 叶节点就是每个Task的最后一步. 
主线程从根节点开始. 遇到N个分叉就构造N-1个线程并发运行(包括他自身就是N个线程), 每个线程运行次分叉处的N个子树的下一步(下一个节点). 这样对于每个线程, 就有了一个属于它的子树, 线程运行完一步(节点)后重复上述, 方式. 没有分叉, 继续运行下一步(节点), 有M个分叉, 构造M-1个线程, 并发运行下去.

4楼果然是高人！

#7

引用 3 楼 hugett 的回复:

我理解的意思就是对每个流程，找一个跟它有最长前缀匹配的流程。。不知是不是这样？？如果是这样你把每个流程看作一个字符串，排一下序，然后跟它前边那个比较一下就得了。。

是这样，但是你少考虑了一种情况,当流程一和流程二有2个相同步骤，流程一和流程三有3个相同步骤，这时候，对流程二，匹配到的是流程一还是三呢？

#8

引用 4 楼 youyou1912 的回复:

这题思路挺有意思, 思路如下:

根据每个步骤构造一颗广义前缀树(trie树), 每个节点包含属性和执行的函数. 叶节点就是每个Task的最后一步. 
主线程从根节点开始. 遇到N个分叉就构造N-1个线程并发运行(包括他自身就是N个线程), 每个线程运行次分叉处的N个子树的下一步(下一个节点). 这样对于每个线程, 就有了一个属于它的子树, 线程运行完一步(节点)后重复上述, 方式. 没有分叉, 继续运行下一步(节点), 有M个分叉, 构造M-1个线程, 并发运行下去.

没怎么看懂，我慢慢研究...   基础是硬伤啊。

#9

引用 4 楼 youyou1912 的回复:

这题思路挺有意思, 思路如下:

根据每个步骤构造一颗广义前缀树(trie树), 每个节点包含属性和执行的函数. 叶节点就是每个Task的最后一步. 
主线程从根节点开始. 遇到N个分叉就构造N-1个线程并发运行(包括他自身就是N个线程), 每个线程运行次分叉处的N个子树的下一步(下一个节点). 这样对于每个线程, 就有了一个属于它的子树, 线程运行完一步(节点)后重复上述, 方式. 没有分叉, 继续运行下一步(节点), 有M个分叉, 构造M-1个线程, 并发运行下去.

高人，能不能以这个例子讲一下怎么操作 ？ 
    A   B   C
1
2
3
   2    3   2

#10

引用 7 楼 ADF1230 的回复:

Quote: 引用 3 楼 hugett 的回复:

我理解的意思就是对每个流程，找一个跟它有最长前缀匹配的流程。。不知是不是这样？？如果是这样你把每个流程看作一个字符串，排一下序，然后跟它前边那个比较一下就得了。。

是这样，但是你少考虑了一种情况,当流程一和流程二有2个相同步骤，流程一和流程三有3个相同步骤，这时候，对流程二，匹配到的是流程一还是三呢？

都跟前一个匹配。。第二个跟第一个匹配，第三个跟第二个匹配。。

#11

搜“卡诺图”

提醒：尺有所短，寸有所长。

#12

引用 9 楼 ADF1230 的回复:

Quote: 引用 4 楼 youyou1912 的回复:

这题思路挺有意思, 思路如下:

根据每个步骤构造一颗广义前缀树(trie树), 每个节点包含属性和执行的函数. 叶节点就是每个Task的最后一步. 
主线程从根节点开始. 遇到N个分叉就构造N-1个线程并发运行(包括他自身就是N个线程), 每个线程运行次分叉处的N个子树的下一步(下一个节点). 这样对于每个线程, 就有了一个属于它的子树, 线程运行完一步(节点)后重复上述, 方式. 没有分叉, 继续运行下一步(节点), 有M个分叉, 构造M-1个线程, 并发运行下去.

高人，能不能以这个例子讲一下怎么操作 ？ 
     A   B   C
T1 1   2   1
T2 1   2   2
T3 1   1   3
 

以上例子构造的trie数如下
              root
A              1
B        2          1
C    1     2       3
    (T1)  (T3)   (T2)

每个节点包含函数和属性值. 主线程T1从根节点开始运行->A(1), 输入原始数据, 得到输出outA1, 然后遇到2个分叉B(2), B(1), 构造一个线程T2运行B(1), 输入outA1, 输出outA1B1. 主线程T1并发运行B(2)输入outA1输出outA1B2, 2个线程各自继续沿树向下. T1再次遇到2个分叉C(1),C(2), 构造一个线程T3运行C(2), 输入outA1B2, 输出outA1B2C2. 主线程T1并发运行C(1)输入outA1B2,输出outA1B2C1. 同时线程T2并发运行C(3), 输入outA1B1, 得到outA1B1C3
最后就得到了所有结果 outA1B2C1, outA1B2C2, outA1B1C3. 过程中有合并相同计算且尽量并发.

#13

格式乱了, 上面是以一下例子为例.
     A   B   C
T1 1   2   1
T2 1   1   3
T3 1   2   2

#14

引用 11 楼 zhao4zhong1 的回复:

搜“卡诺图”

提醒：尺有所短，寸有所长。

嗯，我搜索看看。谢谢。

#15

引用 13 楼 youyou1912 的回复:

格式乱了, 上面是以一下例子为例.
     A   B   C
T1 1   2   1
T2 1   1   3
T3 1   2   2

谢谢，人理解起来很容易，写成程序挺难。
CSDN没提醒，到今天才看到你的回帖，抱歉。