c - 两个函数同时执行

Question

我正在对已排序的双向链表(包含一串整数 ID)进行线性搜索。为此，我使用一个分配给 head 的临时指针(保存 dbl 的第一个值)，并继续到下一个指针，直到找到请求的 ID。

为了缩短搜索时间，我可以将另一个指针分配给尾部(保存最后一个值的指针)并沿着前一个指针向后移动

我对线性搜索的实现

struct node* find(long int value) { 
    struct node*temp = head, *temp1 = tail;
    while(temp->id < value && temp1->id > value){
        temp = temp->next;
        temp1 = temp1->prev;
    }
    if(temp->id == value)
        return temp;
    else if(temp1->id == value)
        return temp1;
    else
        return NULL;
}

这里 temp1 继续向后移动，只有在 temp 向前移动之后

我的问题:

有没有办法同时移动前向(temp)和后向(temp1)指针？

[我的意思是平行移动两个指针，甚至减少同步时间]

关键词:排序双向链表，C语言

Answer 1

如果您的 C 实现支持它，您可以包含 <threads.h>标题并创建新线程。这将允许您使用一个线程向前扫描列表，而另一个线程向后扫描列表。但是，这有很多问题，包括:

• 如果您有这么多节点需要检查，创建一个额外的线程来扫描它们可以显着缩短执行时间，那么您有这么多节点，您可以通过使用比双向链表更好的结构来改进对它们的搜索，例如树或哈希。
• 启动一个新线程相当容易，但以合理的方式停止线程就比较难了。当另一个线程找到结果时，您需要停止一个线程，并且当两个线程在列表中相遇时，您需要停止两个线程。这意味着要添加更多用于通信和协调的代码。
• 在适当的情况下，创建多个线程可以减少“挂钟”执行时间(获得结果所需的时间)，但它不会减少消耗的资源。您将在大约相同的总时间内使用两个处理器，而不是使用一个处理器一段时间。 (“总计”是指每个处理器上执行时间的总和。)
• 处理器使用的一些资源是共享的。例如，它们都访问相同的主内存。根据您的程序所需的确切资源，让它使用更多处理器可能无济于事。如果你的程序的瓶颈是从内存中读取数据，那么第一个处理器只是在等待内存，添加第二个处理器就意味着它们都在等待。在您是唯一用户并且没有大量使用它的系统上，这可能没问题(尽管存在以一种方式与另一种方式相比可能使用多少能量的问题)。但是，在有许多进程在运行并且需要全部 CPU 能力的系统上，使用多个进程来更快地获得结果可能是一种浪费。
• 相反，现代处理器非常复杂，并且在内部包含一些多处理功能 - 处理器可以在请求从内存加载其他数据的同时比较一些数据。有时巧妙地编写代码可以利用这种多重处理来一次完成多项工作。例如，您可以编写在列表中交替向前和向后工作的代码，一次每一步一起在一个循环中，处理器可能会有效地执行此操作，比较来自一个方向的数据，同时加载另一个方向的数据。

考虑使用并行处理来加速程序是个不错的主意，但对于双向链表的简单扫描来说，这可能不是正确的方法。除了上面讨论的那些之外，还有其他并发症。