在循环输入中最小的范围。

To give a bit of context, I have n threads receiving ints. These are coming in cycles (let's say we have a uint16, so after 65535 the next received number will be zero again). There is no known mapping from the respective number to the thread it will be received from, like even numbers are received from thread 1 and odd numbers from thread 2 as a simple example. Some threads can also receive more numbers than others (which is actually the reason why the blocking is neccessary) There can be "jumps", meaning the numbers are not received in a strict ascending order. After a number x is received, the next number, be it in the same or another thread, need not be x+1 but can also be less than x or greater than x+1. We can make assumptions about the size of these jumps though (upper bound is N/2 for N being the largest number possible).

为了提供一些上下文，我有n个线程接收ints。这些是循环的(假设我们有一个uint16，所以在65535之后，下一个接收的数字将再次为零)。从每个数字到它将收到的线程，没有已知的映射，就像从线程1中收到的偶数和从线程2中得到的奇数一样。有些线程还可以接收到比其他线程更多的数字(这实际上就是为什么阻塞是必要的)，可以是“跳转”，这意味着这些数字不会以严格的升序接收。在收到数字x之后，下一个数字，不管是相同的还是另一个线程，不需要是x+1，但也可以小于x或大于x+1。我们可以假设这些跳跃的大小(上限为N/2, N是最大的数目)。

To allow the following subsystem to process the numbers correctly we need to make sure they don't drift apart too far when received. The following example should do the trick:

为了让以下子系统正确处理数字，我们需要确保它们在接收到的时候不会偏离太远。下面的例子应该可以做到这一点:

struct thread_status {
    bool block;
    uint16_t last;
}

void *thread_worker(void *data)
{
    struct thread_status *staus = (struct thread_status*)data;

    while (1) {
        if (status->block) {
            if (status->last <= MIN(array_of_lasts_from_all_threads))
                status->block = false;
            else
                continue;
        }

        status->last = receive_next();

        if (status->last >= MIN(array_of_lasts_from_all_threads) + ALLOWED_DIFF)
            status->block = true;
    }
}

Now the actual question is, how would I implement the MIN function? Instead of always comparing to the array of last values, I could also save the minimum last value and just compare to it. Then I need to implement the comparison operator though.

现在的问题是，如何实现最小值函数?我也可以保存最后一个值并与它进行比较，而不是总是与最后的值数组进行比较。然后我需要实现的比较运算符。

Another example to be more precicse: If I only have ints from 0 to 15 and 3 threads.

另一个例子是，如果我只有0到15和3个线程。

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | | | |X|X| | |0| | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Here, X are the last read values from the other threads and 0 os the currently read value. MIN and comparison are easy here. However in this case

这里，X是来自其他线程的最后读取值，0是当前读取的值。这里的MIN和比较很简单。然而在这种情况下

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|X|0| | | | | | | | | | | | | |X|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

the minimum value should be 15 and not zero.

最小值应该是15，而不是0。

1 个解决方案

#1

I think you might be asking the wrong question, but it's difficult to explain why. Let's answer the simple question first, and see if it helps you figure out how to implement (or avoid implementing) a MIN function.

我想你可能问错了问题，但很难解释原因。让我们先回答这个简单的问题，看看它是否有助于您了解如何实现(或避免实现)一个MIN函数。

If your array boundaries really do lie on a uint16_t boundary, you can find the distance between your 0 read and a given X index with simple subtraction. (Play around with this example a bit to see why.)

如果您的数组边界确实位于uint16_t边界上，那么您可以找到0读和给定的X索引之间的距离，并有简单的减法。(用这个例子来解释一下原因。)

uint16_t recent = 1;
uint16_t previous = 65535;
uint16_t foo = (uint16_t)(recent - previous);
printf("%hu\n", foo);

You might think the result would be a uint16_t, but because of the casting rules in C it's probably going to be an int on your platform, thus the explicit cast above. If 0 is after X, this number will be relatively small; if it's the other way around, the number will be close to UINT16_MAX. If you cast to int16_t instead, on most modern platforms you should get a positive or negative number representing both ordering and distance.

您可能认为结果将是uint16_t，但是由于C中的浇注规则，它可能会在您的平台上是一个int类型，因此上面的显式转换。如果0在X后面，这个数将会相对较小;如果是另一种方法，这个数字将接近UINT16_MAX。如果你改用int16_t，在大多数现代平台上，你应该得到一个正或负的数字，表示排序和距离。

If the array boundaries don't lie on a size boundary, you can use modulo arithmetic to "wrap" the subtraction back into a sane region before casting to a signed type.

如果数组边界不在大小边界上，那么可以使用modulo算法将减法“包装”到一个正常的区域，然后再将其转换为已签名的类型。

#1