针对我的特定问题的有效数据结构
我有一个优先级队列，其中包含一个排序矩阵 A 及其在矩阵中的 (row,col) 位置。所以我有一个数据结构“queue_element”，它有三个字段，queue_element.value、queue_element.row和queue_element.col
我需要处理优先级队列，对于我弹出的每个元素，我需要返回到位置A（ row,col) 并消除位于同一 row# 和 col# 上的所有元素。
例如，如果优先级队列的顶部包含 element.value = 0.99、element.row=4 和 element.col=20，那么我需要将 A(4,:) 和 A(:,20) 归零，其中“:”表示法代表“全部”或从 0 到结束的整个范围。这是 MATLAB/Python 表示法，但我使用 C++ 来实现。
我目前正在使用单独的布尔矩阵 P(x,y) 进行消除。对于从优先级队列中弹出的每个 (x,y) 位置，我只需循环所有行/列，并为位于同一行/列上的所有内容设置一个假值。然后，当我从队列中弹出一个元素时，我只需检查它是否已在 P(x,y) 中设置为 false。
然而，这是相当低效的。我的算法的基本情况只需要消除整个行/列。
编辑：抱歉错过了我的问题的最后一部分...
该算法的更高级版本需要消除同一行/列上的所有内容，但最近的 4 个邻居除外。另一个版本要求当 XY 网格放置在 (row,col) 位置时消除矩阵右上象限和左下象限中的所有内容。
我的问题基本上是，是否有一个明显的数据结构可供我使用。它必须a）允许我有效地“消除”或将我需要的元素归零，b）使我能够非常快速地检查集合成员资格。
关于我应该如何解决这个问题有什么想法吗？
I have a priority queue which contains a sorted matrix A together with its (row,col) location in the matrix. So I have a data structure "queue_element" which has three fields, queue_element.value, queue_element.row and queue_element.col
I need to process the priority queue and for each element that I pop, I need to go back to the location A(row,col) and eliminate all elements lying on the same row# and col#.
So for example, if the top of the priority queue contains element.value = 0.99, element.row=4 and element.col=20, then I need to zero out A(4,:) and A(:,20), where the ':' notation stands for "all" or the entire range from 0 to end. This is MATLAB/Python notation but I'm using C++ for this.
I'm currently using a separate boolean matrix P(x,y) for the elimination. For every (x,y) location that is popped from the priority queue, I just loop over all the row/col and set a false value for everything that lies on the same row/col. Then when I pop an element from the queue, I just check if it is has been set to false in P(x,y).
However, this is quite inefficient. The base case of my algorithm requires just eliminating the entire row/col.
EDIT: Sorry for missing the last part of my question...
The more advanced version of this algorithm requires eliminating everything on the same row/col but except for the nearest 4 neighbors. Another version requires eliminating everything in the upper right and the lower left quadrant of the matrix when an X-Y grid is placed at the (row,col) position.
My question basically, is whether there is an obvious data structure that I could use. It would have to a) allow me to efficiently "eliminate" or zero out the elements that I need and b) enable me to check for set membership very fast.
Any ideas on how I should go about this?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
两象限消除法给了我一个想法。您听说过四叉树吗？
我不确定你的元素的放置顺序，但如果你能找到一种方法来为每个象限设置一个优先级范围（例如，右下象限是优先级 1 到 N，左下象限是 N+1 到M 等），并编写一个树重新平衡方法，该方法根据优先级将所有内容布置在这种数据结构中。然后检查集合成员资格确实会很快（每次搜索迭代都会消除 3/4 的搜索空间），你应该能够修剪树的象限很好。然而，在四叉树中修剪单行或单列将是地狱，因为元素跨越两个主要象限和无数个次要象限。
你可以做的是使用我谈到的树重新平衡方法构造一个临时四叉树，然后修剪两个象限并将剩余元素填充到新矩阵中。然后，在进行行/列消除时，只需使用矩阵结构将元素清零即可。在这两种情况下，修剪本身都变得微不足道，但四叉树的构造可能会产生很大的开销，以致效率低下。
消除矩阵象限的另一种方法是仅让嵌套循环从 [row,col] 运行到 [row,0]，然后从 [row-1,col] 运行到 [row-1,0]，并将每个元素归零出去那条路？
编辑：好的，所以，要构造一个四叉树，您必须将每个元素放入其中，因此您需要调用一个（递归）函数来连接一堆各种元素之间的指针。为了将这里的值清零，我们有一个 NULL 指针，因此没有子指针。我个人没有使用过四叉树，所以我应该提供的是 链接到其他 实现。
我有自己的实现它的想法，但它们是半成形的，并且由于您对可扩展性的需求，我不会在这篇文章中尝试设计空间最优的四叉树。
The two quadrant elimination thing gives me an idea. Have you heard of a quadtree?
I'm not sure in which order your elements are placed, but if you can figure out a way to set perhaps a priority range for each quadrant (e.g lower-right quadrant is priority 1 through N, lower-left is N+1 through M, etc), and write a tree rebalancing method which lays everything out in that sort of data structure based on priority.. then checking set membership will indeed be fast (you eliminate 3/4 of the search space for every search iteration), and you should be able to prune quadrants from the tree pretty well. A single row or column would be hell to prune in a quadtree though, with elements crossing two of the major quadrants and umpteen minor ones.
What you could do is construct a temporary quadtree using the tree rebalancing method I talked about, and then prune the two quadrants and stuff the remaining elements into a new matrix. And then just use the matrix structure to zero out elements when it comes to a row/column elimination. In both instances, the pruning itself becomes trivial, but the quadtree construction could be so much of an overhead that this is inefficient.
Another way to eliminate a quadrant of a matrix is to just have nested loops running from [row,col] to [row,0], then [row-1,col] to [row-1,0], and zero every element out that way?
EDIT: Okay, so, to construct a quadtree you're going to have to place each element in it, so you're going to need to call a (recursive) function to connect up a bunch of pointers between various elements. To zero out a value here, we have a
NULLpointer, and thus no child. I haven't personally worked with a quadtree, so all I should offer is links to other implementations.I have my own ideas for implementing it, but they're half-formed and due to your need for scalability I'm not going to attempt to design a space-optimal quadtree in this post.
对于你的“另一个版本”，我会采取不同的策略。由于每行最多可以有一个元素，因此在每一行中找到“最佳”元素 - 不会被消除的元素是这些元素的子集。现在只需检查所有对并找出哪些幸存下来。如果当行数超过列数时使用列而不是行，那么这与首先创建矩阵一样快。
编辑：我不觉得我得到了整个故事，因为其他情况下的当前算法运行得与创建矩阵一样快。有增量更新之类的吗？
For your "another version", I would take a different tack. Since there can be at most one element per row, locate the "best" element in each row – the elements that are not going to be eliminated are a subset of these. Now just examine all pairs and figure out which ones survived. If you use columns instead of rows when rows outnumber columns, then this is asymptotically as fast as creating the matrix in the first place.
EDIT: I don't feel as though I'm getting the whole story because the current algorithm for the other cases runs as fast as creating the matrix. Are there incremental updates or something?