2

这是一个关于如何表示优先级的后续问题
答案引导我将设计基于Priority Queue ADT.

我的问题是我无法弄清楚如何为这个问题建模（我了解 a 的PQ工作原理）。
所以使用我原来的（简单的例子）假设我有PersonA PersonB...... PersonY（表示为类），它们喜欢各种菜肴Pizzas Spaggeti Steak等。
我想找到一种方法来指定应该根据哪些菜肴来祝愿人Preference（这可能是一个额外的类正如在开始问题线程的答案中的朋友也建议的那样）。
我不确定这应该如何建模。我的第一个想法是PriorityQueue为每道菜（PizzaPQ等SpaggetiPQ）创建一个，在每个队列中加入所有Persons并开始从每个队列中删除顶部（作为对该菜具有最大偏好的队列）并将其Person从其他队列中删除。此过程按顺序遍历所有队列。
现在虽然从概念上看它似乎是正确的（但这不是最好的方法，因为我认为由于过程本身会出现差异），但我不认为我走在正确的轨道上，因为

  1. 从其他队列中删除是线性操作（我说的是已经在remove(Object)哪里提供服务并且不应该再出现在其他队列中）并且将花费 队列数量在哪里（在我看来，这增加了很多优先级队列的使用）ObjectPizzaO(N*k)k
  2. 在我看来，我需要一些抽象来处理优先队列的“池”，我不确定是否真的存在这样的数据结构，我也不知道。

我想这个问题可以概括为如何分配作业或如何操作多个队列（也许？）
对于这些问题必须有一个标准的设计方法。
非常欢迎任何输入

@Thomas 回答后更新：
问题稍微复杂一些。
除了偏好之外，还可能存在其他（一个人的）属性。
例如PersonA，PersonB他们都喜欢牛排而不是其他任何菜肴。但PersonA胆固醇高，PersonB是一名运动员。以某种方式考虑这些属性，然后PersonB应该得到牛排。也许PersonA最终会以其他方式结束。
这就是我最初想到PQs菜肴的原因

4

3 回答 3

1

这个应用程序是否可以在多线程环境中执行？如果是这样，我有一些想法可以提供帮助。

  1. 创建一个调度线程，其工作是获取一个 Person 对象并将其分配给 PQ。假设一个人应该只在 1 个 PQ 上，这有助于解决您从上述其他 PQ 中删除人的问题。这会将 Person 应放置在何处的逻辑（和 CPU 处理时间）从代码的 PQ 执行部分移开，从而使 PQ 更具凝聚力并降低其与 Person 的耦合。如果一个人可能在多个 PQ 上，或者您想将他们从一个 PQ 移动到另一个 PQ，等等，这应该在调度程序代码中执行。

  2. 如果 PQ 多于可用线程，则为 PQ 创建一个线程池，否则只需为每个 PQ 创建一个线程。这样您就不必担心如何迭代 PQ 和可能的 PQ 饥饿。处理 PQ 和 Person 对象的代码对于每个线程都是相同的。

即使您不使用多线程模型，我也会考虑让 Person 对象继承自 PQ 知道的 PQitem 对象，因此 PQ 不必知道有关 Person 对象的任何内容，可能是这样的：（对不起c++，但我想你明白了）

class PQitem
{
public:
    virtual void execute() = 0;
    virtual void getPriority() = 0;
private:
    // PQ specific stuff here
};

class Person : public PQitem
{
public:
    void execute() { /* logic executed when taken off the PQ */ }
    void getPriority() { /* logic used to determine where to place this Person */ }
};
于 2012-05-03T09:04:17.900 回答
0

颠倒逻辑呢？

  • 将所有菜肴放入地图
  • 遍历所有人
    • 循环遍历该人的菜肴优先队列
    • 检查这道菜是否还在地图中
    • 如果这道菜在地图上，请将其移除并结束循环

这样，您将拥有一份菜肴地图和一份人员列表以及他们的优先队列（或地图人员-> 队列）。

然后迭代将O(n * m)是n人数，并且m是一个人的菜优先队列的长度。

如果您稍后在菜肴地图中添加一个计数器，例如您有 5 个披萨可用，您需要更改的只是当计数器达到 0 时从地图中删除该菜肴（并在上菜时增加计数器，课程 ：） ）。

您仍然需要处理以下问题：

  • 谁将开始接受服务？
  • 如果一个人的优先队列中的菜肴都不再出现在地图上，会发生什么？

解决这些问题的一种方法可能是从优先队列最短的人开始，因为他们更有可能没有得到任何菜。这仍然不能解决整个问题（如果两个人只想要披萨而周围只有一个披萨怎么办？）。

于 2012-05-02T16:58:06.137 回答
0

这是 java 的优先级队列的链接：http: //docs.oracle.com/javase/7/docs/api/

定义优先级的关键是定义一个比较不同菜肴的比较器。可能每个人只有一个比较器或一个比较器来定义他们的偏好。

于 2012-05-02T16:59:41.627 回答