我在掌握并发队列的想法时遇到了一些麻烦.我理解一个队列是FIFO,或先到先服务,数据结构.

现在,当我们添加并发部分时,我将其解释为线程安全(请告诉我,如果这是不正确的),事情会变得有点模糊.并发性是指各种线程可以添加到队列中,还是从队列中删除(服务项目)的方式？并发是否为这种操作提供了一种排序感？

我非常感谢并发队列功能的一般描述.这里的类似帖子并不像我希望的那样普遍.

还有并发优先级队列这样的东西吗？它的用途是什么？

非常感谢,对此主题的任何简短解释或有用的链接.

它应该是非常自然的东西,我想知道是否有来自TPL DataFlow库的Prioritized BufferBlock的现成实现？

我正在尝试在Java中创建一个优先级阻塞队列,该队列维护具有相同优先级的元素的FIFO顺序.Oracle文档提供了一些帮助,但我仍然非常纠结.

我应该注意以下主题对我来说都是非常新的:泛型,作为类型的接口和静态嵌套类.所有这些都在以下类定义中发挥作用.特别是泛型,令人困惑,我确信我已经完全搞砸了他们.

我已经包含了注释,以确定我目前正在获得的编译器错误.

几个具体问题:

1. 是否可以让类表示排队的事件对象,实际的队列是静态类成员？

2. 将Oracle的FIFO事件"包装器"作为静态嵌套类包含在内是否合理？

3. 我在这里至少走在正确的轨道上,在一个外层阶段做到这一切吗？

这是我写的课程:

import java.util.concurrent.PriorityBlockingQueue;
import java.util.concurrent.atomic.AtomicLong;

public class FIFOPBQEvent {

/**
 * First we define a static nested class which, when instantiated,
 * encapsulates the "guts" of the event - a FIFOPBQEvent - along with
 * a sequence number that assures FIFO behavior of events of like priority.
 *  
 * The following is lifted ALMOST verbatim (I added "static" and some 
 * comments) from …

在(最大)堆中,很容易及时找到最大的项目O(1),但要实际删除它,您需要复杂性O(log(n)).

因此,如果从堆中插入和删除两者O(log(n)),堆超过二叉树表示优先级队列的优点是什么？

这个网站建议如果我想反向排序我的优先级队列,我应该使用以下代码:

#include <iostream>
#include <queue>
using namespace std;

class mycomparison{
    bool reverse;
  public:
    mycomparison(const bool &revparam=false) {reverse=revparam;}
    bool operator() (const int &lhs, const int &rhs) const {
      if (reverse) return (lhs>rhs);
      else         return (lhs<rhs);
    }
};

int main (){
  int myints[]= {10,60,50,20};

  priority_queue<int, vector<int>, mycomparison(true)> first;

  return 0;
}

这困扰我:

• 我必须在构造函数中指定存储类.
• 我创建了一个类,其唯一目的是传递给优先级队列.

是否有更优雅或更简洁的方式对优先级队列进行反向排序？

向量和链接列表

向量以串行方式存储在存储器中,因此可以使用数据库访问任何元素operator[],就像在数组中一样.

链表包含可能不会连续存储在内存中的元素,因此必须使用迭代器通过以下指针访问随机元素.

(你可能已经知道了.)

优先级的优势

最近我发现了'优先级队列',它有点像堆栈,但是元素被push()装入容器中operator<,我相信这个功能根据与之比较的顺序将它们放在一个顺序中.

这非常适合我,因为我正在测试事件并根据它们发生的剩余时间将它们放入队列中.队列会自动按照我push()和pop()元素对它进行排序.(弹出不影响顺序.)我可以写一个operator<所以这不是问题.

我无法解决的问题

我需要对此事件队列执行三项操作:

1 :)在事件队列中搜索项目.我假设这可以通过标准库中的算法来完成？例如,'找'？如果不是,我可以自己实施,只要我可以做第2点.(见下文)

2 :)迭代队列.我认为默认的底层容器是std::vector......有没有办法访问底层向量中的随机元素？如果我选择使用该std::deque怎么办？我需要这样做来修改某些事件参数.(事件放在队列中.)例如,我可能需要处理一个事件,然后从每个剩余事件的'time_to_event'参数中减去一个恒定的时间.我怀疑由于这个问题不能做到这一点.

3 :)从队列中删除一个元素.有时在处理事件时,其他事件会失效,因此需要删除.

点1-3可以完成吗？我所拥有的所有信息std::priority_queue都来自cplusplus.com,所以我的默认答案是"不",没有办法做任何这些事情.如果我不能做所有这三件事,那么我想我将不得不编写自己的优先级队列包装器.(哦很无聊)

我在大量数据上使用java.

[我试图尽可能地简化问题]

实际上我有一个小类(元素)包含一个int KEY和一个双重WEIGHT(带有getter和setter).

我从文件中读取了很多这些对象,我必须得到最好的(最重量级)M对象.

实际上我正在使用一个PriorityQueue和一个Comparator来比较两个Element,它可以工作,但它太慢了.

你知道(我知道你这样做)更快的方法吗？

谢谢

我正在寻找至少Scala 2.8的不可变优先级队列的实现,但最好是更新.在某处有一个很好的实现吗？

请考虑以下代码:

import java.util.PriorityQueue;

public class Test {

    public static void main(String argv[]) {
        PriorityQueue<A> queue = new PriorityQueue<>();
        System.out.println("Size of queue is " + queue.size()); // prints 0
        queue.add(new A()); // does not throw an exception
        try {
            queue.add(new A()); // this time, an exception is thrown
        } catch (ClassCastException ignored) {
            System.out.println("An exception was thrown");
        }
        System.out.println("Size of queue is " + queue.size()); // prints 2
    }

} 

class A { } // non-comparable object

在此代码中,首先将不可比较的对象添加到a PriorityQueue.这段代码工作得很好,如前所述 …

我想知道什么

我想问一下以下两个问题.

• 在C++中std :: priority_queue中使用了什么类型的堆？
• top(), pop(), push()在C++中std :: priority_queue 的操作时间复杂度是多少？

我在互联网上查了一下,但我找不到答案.
请告诉我答案.如果你不知道C++中的所有版本,请告诉我GCC C++ 11或C++ 14的答案.

我为什么需要

我想实现Dijkstra算法的最短路径问题.

让number of vertex = |V|, number of edge = |E|图中的.
时间复杂性是O(|E| log |V|)使用二进制堆.
但时间的复杂性在于O(|E| + |V| log |V|)使用Fibonacci Heap.

如您所见,如果图形密集,时间会有很大差异.
实际上,有O(|V|^2)没有使用堆的算法,所以我也想知道我是否必须实现它.

我的实施

这是我使用Binary Heap实现优先级队列.
insert(x)等于push(x),extract()等于top() --> pop().
但是std :: priority_queue远比我的实现快得多.

#include <vector>
#include <algorithm>
using namespace std;
template<class …