调试递归算法(大数据大小)(Debug of recursive algorithm (big data size))
我使用基于DFS的算法来计算大图中的强组件。 该算法在小图上运行良好,但我在大图上遇到问题。 所以在大约28 K后,DFS函数程序的递归调用才会挂起。 VS2010给我一条消息VS很忙,没有崩溃没有错误。 为了弄清楚发生了什么,我打印了一些信息(由于速度低,无法在调试中运行)。 我发现程序挂在第4位并且没有到达位置1(观察代码)。
// Main DFS function void DFS(vector<Edge>& graph, int source_node, bool *vertex_visited, pair<int, int>& direction){ cout << "\r" << "Position 1" << std::flush; // mark vertex as visited vertex_visited[source_node - 1] = false; // array for all neighbour edges vector<vector<Edge>::iterator> all_neighbours; // doesent matter if (direction.second){ size_of_scc++; } // binary search of edges incident with source vertex pair<vector<Edge>::iterator, bool> itera = find_if_binary_for_edges(graph.begin(), graph.end(), source_node); cout << "\r" << "Position 2" << std::flush; // push all incident edges to all_neighbours vector if (itera.second){ pair<vector<Edge>::iterator, vector<Edge>::iterator> bounds = find_all_in_range(itera.first, graph); vector<Edge>::iterator it = bounds.first; while (it != bounds.second){ all_neighbours.push_back(it++); } } cout << "\r" << "Position 3" << std::flush; // if this vertex wasn't visited in the past cal DFS from neighbour vertex for (vector<vector<Edge>::iterator>::iterator it = all_neighbours.begin(); it != all_neighbours.end(); ++it){ if (vertex_visited[(**it)[1] - 1]){ cout << "\r" << "Position 4" << std::flush; DFS(graph, (**it)[1], vertex_visited, direction); }; } // need this stuff for SCC computation cout << "\r" << "Position 5" << std::flush; if (direction.first) finishing_times[finishing_times_counter++] = source_node; }
所以我不知道接下来该做什么,接下来需要做哪些调试步骤...? 位置4程序必须再次调用DFS然后打印“位置1”但它不会发生。 因为它可能是什么? 图形具有大约857K个顶点和5 * 10 ^ 6个边。 谢谢。
I use DFS based algorithm for computing strong components in the large graph. The algorithm works fine on small graphs, but i encounter with a problem on the large graphs. So after around 28 K recursive calls of DFS function program just hangs. VS2010 give me an message VS is busy, no crashes no errors. To figure out what is going on, i printed some information (can't run it in debug because of the low speed). And i found out that program hangs on position 4 and dosen't reaches position 1 (watch the code).
// Main DFS function void DFS(vector<Edge>& graph, int source_node, bool *vertex_visited, pair<int, int>& direction){ cout << "\r" << "Position 1" << std::flush; // mark vertex as visited vertex_visited[source_node - 1] = false; // array for all neighbour edges vector<vector<Edge>::iterator> all_neighbours; // doesent matter if (direction.second){ size_of_scc++; } // binary search of edges incident with source vertex pair<vector<Edge>::iterator, bool> itera = find_if_binary_for_edges(graph.begin(), graph.end(), source_node); cout << "\r" << "Position 2" << std::flush; // push all incident edges to all_neighbours vector if (itera.second){ pair<vector<Edge>::iterator, vector<Edge>::iterator> bounds = find_all_in_range(itera.first, graph); vector<Edge>::iterator it = bounds.first; while (it != bounds.second){ all_neighbours.push_back(it++); } } cout << "\r" << "Position 3" << std::flush; // if this vertex wasn't visited in the past cal DFS from neighbour vertex for (vector<vector<Edge>::iterator>::iterator it = all_neighbours.begin(); it != all_neighbours.end(); ++it){ if (vertex_visited[(**it)[1] - 1]){ cout << "\r" << "Position 4" << std::flush; DFS(graph, (**it)[1], vertex_visited, direction); }; } // need this stuff for SCC computation cout << "\r" << "Position 5" << std::flush; if (direction.first) finishing_times[finishing_times_counter++] = source_node; }
So i don't know what to do next, which debug steps i need to do next ...? After position 4 program have to call DFS again and then print "Position 1" but it dosen't happens. Because of what it could be? Graph have approximately 857K vertexes and 5 * 10^6 edges. Thanks.
原文:https://stackoverflow.com/questions/14773505
最满意答案
我使用MadProgrammer的推荐改造了你的代码:
- 不要覆盖
paint
,覆盖paintComponent
。- 在执行任何自定义绘画之前调用
super.paint
,- 永远不要对任何事情进行
finalize
,特别是对自己没有创建的对象。- 使用Swing Timer
请注意以下内容
限定this用于从ActionListener内部类访问ImageRotationView实例。
AffineTransform.getRotateInstance
返回一个围绕锚点旋转坐标的变换。- 速度可以优化,但它可以像这样正常工作。
- 此类作为独立应用程序运行
- 名为
dice.png
的文件应存在于基目录中。。
import java.awt.EventQueue; import java.awt.Graphics; import java.awt.Graphics2D; import java.awt.Image; import java.awt.event.ActionEvent; import java.awt.event.ActionListener; import java.awt.geom.AffineTransform; import java.io.File; import java.io.IOException; import javax.imageio.ImageIO; import javax.swing.JComponent; import javax.swing.JFrame; import javax.swing.Timer; public class ImageRotationFrame { public static void main(String[] args) { new ImageRotationFrame(); } public ImageRotationFrame() { EventQueue.invokeLater(new Runnable() { @Override public void run() { JFrame frame = new JFrame("Testing"); frame.setSize(400, 400); frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); frame.add(new ImageRotationComponent()); frame.setLocationRelativeTo(null); frame.setVisible(true); } }); } private class ImageRotationComponent extends JComponent { Image arrow; double angle = 0.0; @Override protected void paintComponent(Graphics g) { super.paintComponent(g); angle += 0.4; AffineTransform trans = AffineTransform.getRotateInstance(angle, getWidth() / 2, getHeight() / 2); ((Graphics2D) g).drawImage(arrow, trans, this); } public ImageRotationComponent() { try { arrow = ImageIO.read(new File("dice.png")); } catch (IOException e) { e.printStackTrace(); } int delay = 500; //milliseconds ActionListener taskPerformer = new ActionListener() { @Override public void actionPerformed(ActionEvent evt) { ImageRotationComponent.this.repaint(); } }; new Timer(delay, taskPerformer).start(); } } }
I've transformed your code using the recommendation of MadProgrammer:
- Don't override
paint
, overridepaintComponent
.- Call
super.paint
before performing any custom painting,- Never call
finalize
on anything and especially not on objects you didn't create yourself.- Use a Swing Timer
Note the following
A qualified this is used to access the ImageRotationView instance from the ActionListener inner class.
AffineTransform.getRotateInstance
returns a transform that rotates coordinates around an anchor point.- Speed can be optimized but it works correctly like this.
- This class works as a standalone application
- A file named
dice.png
should be present in the base directory..
import java.awt.EventQueue; import java.awt.Graphics; import java.awt.Graphics2D; import java.awt.Image; import java.awt.event.ActionEvent; import java.awt.event.ActionListener; import java.awt.geom.AffineTransform; import java.io.File; import java.io.IOException; import javax.imageio.ImageIO; import javax.swing.JComponent; import javax.swing.JFrame; import javax.swing.Timer; public class ImageRotationFrame { public static void main(String[] args) { new ImageRotationFrame(); } public ImageRotationFrame() { EventQueue.invokeLater(new Runnable() { @Override public void run() { JFrame frame = new JFrame("Testing"); frame.setSize(400, 400); frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); frame.add(new ImageRotationComponent()); frame.setLocationRelativeTo(null); frame.setVisible(true); } }); } private class ImageRotationComponent extends JComponent { Image arrow; double angle = 0.0; @Override protected void paintComponent(Graphics g) { super.paintComponent(g); angle += 0.4; AffineTransform trans = AffineTransform.getRotateInstance(angle, getWidth() / 2, getHeight() / 2); ((Graphics2D) g).drawImage(arrow, trans, this); } public ImageRotationComponent() { try { arrow = ImageIO.read(new File("dice.png")); } catch (IOException e) { e.printStackTrace(); } int delay = 500; //milliseconds ActionListener taskPerformer = new ActionListener() { @Override public void actionPerformed(ActionEvent evt) { ImageRotationComponent.this.repaint(); } }; new Timer(delay, taskPerformer).start(); } } }
相关问答
更多-
你想要做的是恢复变换。 尝试 AffineTransform oldXForm = g.getTransform(); g.rotate(...); g.drawLine(...); g.setTransform(oldXForm); // Restore transform g.drawLine(...); What you'll want to do is restore the transform. Try AffineTransform oldXForm = g.getTransform(); ...
-
Java Swing:Graphics2D旋转创建令人厌恶的边缘(Java Swing: Graphics2D rotation creating disgusting edges)[2023-11-13]
如何尝试反锯齿边缘和双线性变换? 你可以在这里看到一个例子。 同时检查你的图像类型,这个例子使用了一个BufferedImage 。 g2.setRenderingHint(RenderingHints.KEY_INTERPOLATION, RenderingHints.VALUE_INTERPOLATION_BILINEAR); What about trying antialiased edges and bilinear transform? You can s ... -
如果需要在内存中操作图像,请创建BufferedImage,然后调用BufferedImage.createGraphics()以访问图形对象以绘制到图像的缓冲区中。 如果要将该图像渲染到UI中的组件上,请使用该组件的paintComponent()方法。 请注意,这涉及两个单独的图形对象,用于两个不同的目的。 If you need to manipulate an image in memory, create a BufferedImage and then call BufferedImage.cr ...
-
我使用MadProgrammer的推荐改造了你的代码: 不要覆盖paint ,覆盖paintComponent 。 在执行任何自定义绘画之前调用super.paint , 永远不要对任何事情进行finalize ,特别是对自己没有创建的对象。 使用Swing Timer 请注意以下内容 限定this用于从ActionListener内部类访问ImageRotationView实例。 AffineTransform.getRotateInstance返回一个围绕锚点旋转坐标的变换。 速度可以优化,但它可以像这 ...
-
您已经拥有了在方法中旋转和翻译(在某个位置绘制)的代码。 您的原始代码已经在坐标-width / 2,-height / 2处绘制图像(因为您的图像围绕其中心旋转,而不是围绕它的左上角) 所以,这是在xPos,yPos上添加你需要的额外翻译的问题: transform.translate(-xPos + player.getWidth() / 2, -yPos + player.getHeight() / 2); transform.rotate(Math.toRadians(degrees ...
-
这听起来像你需要一个正向和反向变换来在两个坐标系之间进行转换。 在这个例子中 ,缩放方程是明确的; 在这种替代方法中 ,使用了第二个AffineTransform 。 It sounds like you need both a forward and inverse transform to translate between the two co-ordinate systems. In this example, the scaling equations are explicit; in this ...
-
Java Graphics2D获得旋转图像边界和新协调(Java Graphics2D obtain rotated image bounding and new coordiinates)[2023-05-04]
你只需要自己旋转图像角落。 java.awt.geom包提供了Point2D和AffineTransform类,通过对各个点应用旋转变换来实现。 旋转的边界框的宽度和高度可以计算为最大和最大旋转x和y坐标之间的差值,最小x和y坐标为偏移量。 以下程序实现了该算法,并以30°的步长显示了从0°到360°的几次旋转的结果: package stackoverflow; import java.awt.geom.AffineTransform; import java.awt.geom.Point2D; imp ... -
SVG到Java Graphics2D(SVG to Java Graphics2D)[2023-11-09]
试着看看SVG Salamander图书馆。 在此页面上有一些开始提示。 如果你只想绘制一些svgs,这是一件好事。 Try to look at SVG Salamander library. On this page there are some starting tips. It's a good thing if You want only to draw some svgs. -
评论您的代码: AffineTransform ZombiePowered = new AffineTransform();//Create an Id. transform ZombiePowered.setTransform(zombieIdentity);//Set it as a copy of an Id. transform ZombiePowered.rotate(2, 37.5, 37.5);//Concatenate the rotation with the Id ...
-
来自Oracle文档: 要添加坐标变换,请使用变换,旋转,缩放或剪切方法。 setTransform方法仅用于在渲染后恢复原始Graphics2D变换。 只能有一个变换,您可以在其中连接新的变换,例如旋转方法: 将当前的Graphics2D Transform与转换的旋转变换连接起来。 随后的渲染通过变换进行变换,该变换通过平移到指定的位置,旋转指定的弧度,并向后平移与原始平移相同的量来构造。 还有一个警告: 警告:永远不应该使用此方法在现有变换之上应用新的坐标变换,因为Graphics2D可能已经具有其他 ...