blocks|key|4241785|text|我可以想到相当多的选择，每个选择都有自己的成本和收益。这实际上归结于你的需求是什么--什么才是真正为你定义的“最佳”。我在下面给出了几种可能的代码，希望能帮助你入门。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|4241786|选项1:每个时间单位执行以下命令(在您的示例中为毫秒)|4241787|func+callEachMs
++++time+=+getCurrentTime()
++++for+each+datum
++++++++for+each+customer
++++++++++++if+time+%25+datum.customer.rate+==+0
++++++++++++++++sendMsg()|code-block|syntax|javascript|4241788|这样做的优点是不需要一致存储的内存--您只需在每个时间单位检查是否应该发送消息。这也可以处理不是以time+==+0发送的消息--只需存储最初以速率为模发送消息的时间，并用if+time+%25+datum.customer.rate+==+data.customer.firstMsgTimeMod替换条件。|offset|length|style|CODE|4241789|这种方法的一个缺点是它完全依赖于总是以1ms的速率被调用。如果CPU上的另一个进程导致延迟，并且它错过了一个周期，那么您可能完全错过了发送消息(而不是延迟发送消息)。|4241790|选项2:维护元组列表，其中每个条目表示在该毫秒内需要完成的任务。让你的列表至少和最长速率除以时间单位一样长(如果你的最长速率是50毫秒，你要用毫秒来计算，那么你的列表必须至少有50长)。启动程序时，请在第一次将消息发送到队列时放置。然后，每次您发送消息时，请在下次发送该列表中的消息时进行更新。|4241791|func+buildList(&list)
++++for+each+datum
++++++++for+each+customer
++++++++++++if+list.size+<+datum.customer.rate
++++++++++++++++list.resize(datum.customer.rate%2B1)
++++++++++++list[customer.rate].push_back(tuple(datum.name,+customer.name))

func+callEachMs(&list)
++++for+each+(datum.name,+customer.name)+in+list[0]
++++++++sendMsg()
++++++++list[customer.rate].push_back((datum.name,+customer.name))
++++list.pop_front()
++++list.push_back(empty+list)|4241792|这具有避免许多不必要的模数计算选项1所需的优点。然而，这也带来了内存使用量增加的代价。如果各种消息的速率有很大的差异，这种实现也不会有效率(尽管您可以修改它以更有效地处理具有较长速率的算法)。它仍然需要每毫秒调用一次。|4241793|最后，您必须非常仔细地考虑您使用的数据结构，因为这将对其效率产生巨大的影响。因为每次迭代都是从前面弹出，从后面推，并且列表的大小是固定的，所以您可能想要实现一个circular+buffer来避免不必要的值移动。对于元组列表，由于它们只会迭代(不需要随机访问)，而且需要频繁添加，因此单链表可能是最佳解决方案。|4241794|。|4241795|显然，有更多的方法可以做到这一点，但希望这些想法可以让你开始。此外，请记住，您在其上运行此程序的系统的性质可能会对哪种方法工作得更好有很大的影响，或者您是否想做完全不同的事情。例如，这两种方法都要求能够以一定的速率可靠地调用它们。我也没有描述并行化实现，如果您的应用程序支持它们，这可能是最好的选择。|4241796|entityMap|0|LINK|mutability|MUTABLE|url|https://en.wikipedia.org/wiki/Circular_buffer^0|0|0|0|1D|9|2E|1Q|0|0|0|0|0|28|F|0|0|0|0^^$0|@$1|2|3|4|5|6|7|1A|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|1B|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|1C|8|@]|9|@]|A|$G|H]]|$1|I|3|J|5|6|7|1D|8|@$K|1E|L|1F|M|N]|$K|1G|L|1H|M|N]]|9|@]|A|$]]|$1|O|3|P|5|6|7|1I|8|@]|9|@]|A|$]]|$1|Q|3|R|5|6|7|1J|8|@]|9|@]|A|$]]|$1|S|3|T|5|F|7|1K|8|@]|9|@]|A|$G|H]]|$1|U|3|V|5|6|7|1L|8|@]|9|@]|A|$]]|$1|W|3|X|5|6|7|1M|8|@]|9|@$K|1N|L|1O|1|1P]]|A|$]]|$1|Y|3|Z|5|6|7|1Q|8|@]|9|@]|A|$]]|$1|10|3|11|5|6|7|1R|8|@]|9|@]|A|$]]|$1|12|3|-4|5|6|7|1S|8|@]|9|@]|A|$]]]|13|$14|$5|15|16|17|A|$18|19]]]]

I can think of quite a few options, each with their own costs and benefits. It really comes down to exactly what your needs are -- what really defines "best" for you. I've pseudocoded a couple possibilities below to hopefully help you get started.

Option 1: Execute the following every time unit (in your example, millisecond)

<pre><code>func callEachMs
 time = getCurrentTime()
 for each datum
 for each customer
 if time % datum.customer.rate == 0
 sendMsg()
</code></pre>

This has the advantage of requiring no consistently stored memory -- you just check at each time unit whether your should be sending a message. This can also deal with messages that weren't sent at <code>time == 0</code> -- just store the time the message was initially sent modulo the rate, and replace the conditional with <code>if time % datum.customer.rate == data.customer.firstMsgTimeMod</code>.

A downside to this method is it is completely reliant on always being called at a rate of 1 ms. If there's lag caused by another process on a CPU and it misses a cycle, you may miss sending a message altogether (as opposed to sending it a little late).

Option 2: Maintain a list of lists of tuples, where each entry represents the tasks that need to be done at that millisecond. Make your list at least as long as the longest rate divided by the time unit (if your longest rate is 50 ms and you're going by ms, your list must be at least 50 long). When you start your program, place the first time a message will be sent into the queue. And then each time you send a message, update the next time you'll send it in that list.

<pre><code>func buildList(&amp;list)
 for each datum
 for each customer
 if list.size &lt; datum.customer.rate
 list.resize(datum.customer.rate+1)
 list[customer.rate].push_back(tuple(datum.name, customer.name))

func callEachMs(&amp;list)
 for each (datum.name, customer.name) in list[0]
 sendMsg()
 list[customer.rate].push_back((datum.name, customer.name))
 list.pop_front()
 list.push_back(empty list)
</code></pre>

This has the advantage of avoiding the many unnecessary modulus calculations option 1 required. However, that comes with the cost of increased memory usage. This implementation would also not be efficient if there's a large disparity in the rate of your various messages (although you could modify this to deal with algorithms with longer rates more efficiently). And it still has to be called every millisecond.

Finally, you'll have to think very carefully about what data structure you use, as this will make a huge difference in its efficiency. Because you pop from the front and push from the back at every iteration, and the list is a fixed size, you may want to implement a <a href="https://en.wikipedia.org/wiki/Circular_buffer" rel="nofollow noreferrer">circular buffer</a> to avoid unneeded moving of values. For the lists of tuples, since they're only ever iterated over (random access isn't needed), and there are frequent additions, a singly-linked list may be your best solution.

.

Obviously, there are many more ways that you could do this, but hopefully, these ideas can get you started. Also, keep in mind that the nature of the system you're running this on could have a strong effect on which method works better, or whether you want to do something else entirely. For example, both methods require that they can be reliably called at a certain rate. I also haven't described parallellized implementations, which may be the best option if your application supports them.

blocks|key|4241937|text|就像Helium_1s2描述的那样，还有第二种方法，它基于我所说的计划表，这就是我现在使用的方法，但这种解决方案有其局限性。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|4241938|假设我们有一个数据要发送，两个消费者C1和C2：|4241939|📷|atomic|offset|length|4241940|​|4241941|就像你看到的，我们必须提取我们的调度表，我们必须识别重复传输周期和空闲最小周期的值。事实上，在最小的时间间隔(例如1ms、1ns、1mn或1h+)上循环是无用的，但它并不总是最好的周期，我们可以像下面这样优化这个循环。|4241942|例如1+(C1在6，C2在9)，我们注意到存在从0到18重复的周期。两个连续发送事件的最小差值等于3。因此：|4241943|HCF(6,9)+=+3+=+IDLE+MINIMUM+PERIOD
LCM(6,9)+=+18+=+transmission+cycle+length
LCM/HCF+=+6+=+size+of+our+schedule+table|code-block|syntax|javascript|4241944|明细表是：|4241945|4241946|4241947|4241948|发送循环看起来像这样：|4241949|while(1)+{
++sleep(IDLE_MINIMUM_PERIOD);+//+free+CPU+for+idle+min+period
++i%2B%2B;+//+initialized+at+0
++send(ScheduleTable[i]);
++if+(i+==+sizeof(ScheduleTable))+i=0;
}|4241950|这种方法的问题是，如果LCM增长，这个数组就会增长，如果我们有不好的组合，比如rate+=质数等，就会出现这种情况。|4241951|entityMap|0|IMAGE|mutability|IMMUTABLE|imageUrl|https://ask.qcloudimg.com/http-save/yehe-900000/cd2629bf40f1a49309105fa5e8dec6ed.png|imageAlt|1|https://ask.qcloudimg.com/http-save/yehe-900000/1edfc31ca01fe28cb132c56146cc03d5.png^0|0|0|0|1|0|0|0|0|0|0|0|0|0|1|1|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|1F|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|1G|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|1H|8|@]|9|@$G|1I|H|1J|1|1K]]|A|$]]|$1|I|3|J|5|6|7|1L|8|@]|9|@]|A|$]]|$1|K|3|L|5|6|7|1M|8|@]|9|@]|A|$]]|$1|M|3|N|5|6|7|1N|8|@]|9|@]|A|$]]|$1|O|3|P|5|Q|7|1O|8|@]|9|@]|A|$R|S]]|$1|T|3|U|5|6|7|1P|8|@]|9|@]|A|$]]|$1|V|3|J|5|6|7|1Q|8|@]|9|@]|A|$]]|$1|W|3|E|5|F|7|1R|8|@]|9|@$G|1S|H|1T|1|1U]]|A|$]]|$1|X|3|J|5|6|7|1V|8|@]|9|@]|A|$]]|$1|Y|3|Z|5|6|7|1W|8|@]|9|@]|A|$]]|$1|10|3|11|5|Q|7|1X|8|@]|9|@]|A|$R|S]]|$1|12|3|13|5|6|7|1Y|8|@]|9|@]|A|$]]|$1|14|3|-4|5|6|7|1Z|8|@]|9|@]|A|$]]]|15|$16|$5|17|18|19|A|$1A|1B|1C|-4]]|1D|$5|17|18|19|A|$1A|1E|1C|-4]]]]

Like Helium_1s2 described, there is a second way which based on what I called a schedule table and this is what I used now but this solution has its limits.

Suppose that we have one data to send and two consumer C1 and C2 :
<a href="https://i.stack.imgur.com/lzO4M.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/lzO4M.png" alt="simulation with three different couple rates"></a>

Like you can see we must extract our schedule table and we must identify the repeating transmission cycle and the value of IDLE MINIMUM PERIOD. In fact, it is useless to loop on the smallest peace of time ex 1ms or 1ns or 1mn or 1h (depending on the case) BUT it is not always the best period and we can optimize this loop as follows.

for example one (C1 at 6 and C2 at 9), we remark that there is cycle which repeats from 0 to 18. with a minimal difference of two consecutive send event equal to 3. 
so : 

<pre><code>HCF(6,9) = 3 = IDLE MINIMUM PERIOD
LCM(6,9) = 18 = transmission cycle length
LCM/HCF = 6 = size of our schedule table
</code></pre>

And the schedule table is :

<a href="https://i.stack.imgur.com/I9aTD.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/I9aTD.png" alt="enter image description here"></a>

and the sending loop looks like :

<pre><code>while(1) {
 sleep(IDLE_MINIMUM_PERIOD); // free CPU for idle min period
 i++; // initialized at 0
 send(ScheduleTable[i]);
 if (i == sizeof(ScheduleTable)) i=0;
}
</code></pre>

The problem with this method is that this array will grows if LCM grows which is the case if we have bad combination like with rate = prime number, etc.

I'm looking for best algorithm for message schedule. What I mean with message schedule is a way to send a messages on the bus when we have many consumers at different rate.

Example : 
Suppose that we have data D1 to Dn
 . D1 to send to many consumer C1 every 5ms, C2 every 19ms, C3 every 30ms, Cn every Rn ms
 . Dn to send to C1 every 10ms, C2 every 31ms , Cn every 50ms

What is best algorithm which schedule this actions with the best performance (CPU, Memory, IO)? 

Regards

Schedule sending messages to consumers at different rate

数据结构

我正在寻找消息调度的最佳算法。我所说的消息调度是指当我们有许多不同速率的消费者时，在总线上发送消息的一种方式。例如:假设我们有到Dn的数据D1。D1每5ms发送一次C1，C2每19ms发送一次，C3每30ms发送一次，Cn每Rn ms发送一次。Dn每10ms发送到C1，C2每31ms发送一次，Cn每50ms发送一次以最...

问调度以不同的速率向消费者发送消息
EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问调度以不同的速率向消费者发送消息EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问调度以不同的速率向消费者发送消息
EN