2

在最近的一次采访中遇到了一个有趣的问题，就这样吧。

需要实现一个函数，它将接受一个函数指针和一个时间间隔。它应该能够func1被调用每个time_interval.

我们提供了一个 API，每个时钟滴答都会调用它。可以多次调用 create_timer，在这种情况下，它应该根据各自的时间间隔调用每个函数指针。

    // api    
    create_timer(&func, interval) 

    // call to api would look like
    create_timer(&func1, 10);
    create_timer(&func2, 5);

我建议创建一个函数指针的链接列表，但在这种情况下，它是对每个时钟滴答的线性搜索。这不是一个好的解决方案。

我也建议了一个优先队列解决方案，但这也没有奏效。我们需要存储每个函数调用 create_timer 的时间，然后计算与当前时间的差值，如果差值是 time_interval 的倍数，我们调用该函数。

有什么有趣的解决方案吗？

4

2 回答 2

1

“我建议创建一个函数指针的链表”

请注意，这种实现必须在每个新的滴答声中一遍又一遍地遍历所有计划的事件，只是为了找出是否应该调用某个函数。

更好的方法是使用具有明确定义顺序的排序数据结构，比如说一个优先队列，其中所有事件都将按顺序排序，它们应该被处理/执行。IE：

create_timer(&func1, 10);
create_timer(&func2, 5);
create_timer(&func3, 15);

可能会导致以下优先级队列：

5   func1
10  func2
15  func3

到计时器到达第 5 个滴答时，它会调用func1并将其从队列中删除，然后将其插入到此队列中，并更新值为“last val + 5”：

10  func2
10  func1
15  func3

等等。

于 2013-10-19T23:56:30.817 回答
0

这是一个很好的答案。为避免在每次滴答时递减链接列表中的每个计时器，您可以搜索将首先到期的计时器，并记下其到期时间。然后在每个滴答声中递减该计时器，当它到期时，将剩余的计时器递减存储的到期时间，同时找到下一个将到期的计时器，然后重复该过程。这样你只有在计时器到期后才遍历链接列表

于 2013-10-20T00:03:48.243 回答