首页 \ 问答 \ 调试递归算法(大数据大小)(Debug of recursive algorithm (big data size))

调试递归算法(大数据大小)(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
更新时间:2023-01-12 14:01

最满意答案

我使用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, override paintComponent.
  • 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(); ...
  • 如何尝试反锯齿边缘和双线性变换? 你可以在这里看到一个例子。 同时检查你的图像类型,这个例子使用了一个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.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 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可能已经具有其他 ...

相关文章

更多

最新问答

更多
  • h2元素推动其他h2和div。(h2 element pushing other h2 and div down. two divs, two headers, and they're wrapped within a parent div)
  • 创建一个功能(Create a function)
  • 我投了份简历,是电脑编程方面的学徒,面试时说要培训三个月,前面
  • PDO语句不显示获取的结果(PDOstatement not displaying fetched results)
  • Qt冻结循环的原因?(Qt freezing cause of the loop?)
  • TableView重复youtube-api结果(TableView Repeating youtube-api result)
  • 如何使用自由职业者帐户登录我的php网站?(How can I login into my php website using freelancer account? [closed])
  • SQL Server 2014版本支持的最大数据库数(Maximum number of databases supported by SQL Server 2014 editions)
  • 我如何获得DynamicJasper 3.1.2(或更高版本)的Maven仓库?(How do I get the maven repository for DynamicJasper 3.1.2 (or higher)?)
  • 以编程方式创建UITableView(Creating a UITableView Programmatically)
  • 如何打破按钮上的生命周期循环(How to break do-while loop on button)
  • C#使用EF访问MVC上的部分类的自定义属性(C# access custom attributes of a partial class on MVC with EF)
  • 如何获得facebook app的publish_stream权限?(How to get publish_stream permissions for facebook app?)
  • 如何防止调用冗余函数的postgres视图(how to prevent postgres views calling redundant functions)
  • Sql Server在欧洲获取当前日期时间(Sql Server get current date time in Europe)
  • 设置kotlin扩展名(Setting a kotlin extension)
  • 如何并排放置两个元件?(How to position two elements side by side?)
  • 如何在vim中启用python3?(How to enable python3 in vim?)
  • 在MySQL和/或多列中使用多个表用于Rails应用程序(Using multiple tables in MySQL and/or multiple columns for a Rails application)
  • 如何隐藏谷歌地图上的登录按钮?(How to hide the Sign in button from Google maps?)
  • Mysql左连接旋转90°表(Mysql Left join rotate 90° table)
  • dedecms如何安装?
  • 在哪儿学计算机最好?
  • 学php哪个的书 最好,本人菜鸟
  • 触摸时不要突出显示表格视图行(Do not highlight table view row when touched)
  • 如何覆盖错误堆栈getter(How to override Error stack getter)
  • 带有ImageMagick和许多图像的GIF动画(GIF animation with ImageMagick and many images)
  • USSD INTERFACE - > java web应用程序通信(USSD INTERFACE -> java web app communication)
  • 电脑高中毕业学习去哪里培训
  • 正则表达式验证SMTP响应(Regex to validate SMTP Responses)