我试图在视觉上显示处理中的一些算法(但实际上,此问题适用于具有GUI框架的任何语言)。我的问题是,一个具有绘制循环的程序会根据每秒的帧数进行更新,您如何执行算法并更新其视觉显示?
例如,如果我将随机值数组显示为条形图。我想使用不同的排序方式(气泡排序,快速排序,合并排序)对数组进行排序。如何通过在新动画帧中显示每个交换来显示算法的每个步骤?
另一个例子是寻路。我想显示BFS,DFS,A *的步骤,而不仅仅是最终解决方案的路径(搜索的所有拍子)。
我在寻找视觉效果的示例可在以下算法的Wikipedia文章中找到:
http://en.wikipedia.org/wiki/Quicksort
http://en.wikipedia.org/wiki/File:Astar_progress_animation.gif
问题在于算法完成时,绘制循环仅循环了一次,因此用户看不到进度。
我唯一想到的就是拥有一个“状态”对象,其中包含算法每一步的相关值。完成后,遍历每个状态并直观地显示它。有没有更好的办法?
参考方案
import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
/**
* A panel that can show a demonstration of Quicksort in action. The items to be
* sorted are the hues of a set of vertical bars. When sorted, the bars form a
* spectrum from red to violet. Initially, the bars are sorted. There is a Start
* button. When the user clicks this button, the order of the bars is randomized
* and then Quicksort is applied. During the sort, a black bar marks the
* location of an empty space from which the "pivot" element has been removed.
* The user can abort the sort by clicking the button again.
* <p>
* The main point of this program is to demonstrate threads, with very simple
* inter-thread communication. The recursive Quicksort algorithm is run in a
* separate thread. The abort operation is implemented by setting the value of a
* volatile variable that is checked periodically by the thread. When the user
* aborts the sort before it finishes, the value of the variable changes; the
* thread sees the change and exits.
* <p>
* This class contains a main() routine that allows the demo to be run as a
* stand-alone application.
*/
public class QuicksortThreadDemo extends JPanel {
/**
* This main routine just shows a panel of type QuicksortThreadDemo.
*/
public static void main(String[] args) {
JFrame window = new JFrame("Demo: Recursion in a Thread");
QuicksortThreadDemo content = new QuicksortThreadDemo();
window.setContentPane(content);
window.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
window.pack();
Dimension screenSize = Toolkit.getDefaultToolkit().getScreenSize();
window.setLocation((screenSize.width - window.getWidth()) / 2,
(screenSize.height - window.getHeight()) / 2);
window.setVisible(true);
}
private final static int ARRAY_SIZE = 150; // The number of colored bars.
private int[] hue = new int[ARRAY_SIZE]; // The array that will be sorted.
private Color[] palette = new Color[ARRAY_SIZE]; // Colors in spectral
// order.
private Display display; // The panel that displays the colored bars.
private JButton startButton; // The button that starts and stops the demo.
private Runner runner; // The thread that runs the recursion.
private volatile boolean running; // Set to true while recursion is running;
// This is set to true as a signal to
// the
// thread to abort.
/**
* When the user aborts the recursion before it finishes, an exception of
* this type is thrown to end the recursion cleanly.
*/
private class ThreadTerminationException extends RuntimeException {
}
/**
* A subpanel of type Display shows the colored bars that are being sorted.
* The current pivot, if any, is shown in black. A 3-pixel gray border is
* left around the bars.
*/
private class Display extends JPanel {
Display() {
setPreferredSize(new Dimension(606, 206));
setBackground(Color.GRAY);
}
protected void paintComponent(Graphics g) {
super.paintComponent(g);
double barWidth = (double) (getWidth() - 6) / hue.length;
int h = getHeight() - 6;
for (int i = 0; i < hue.length; i++) {
int x1 = 3 + (int) (i * barWidth + 0.49);
int x2 = 3 + (int) ((i + 1) * barWidth + 0.49);
int w = x2 - x1;
if (hue[i] == -1)
g.setColor(Color.BLACK);
else
g.setColor(palette[hue[i]]);
g.fillRect(x1, 3, w, h);
}
}
}
/**
* The constructor sets up the panel, containing the Display and the Start
* button below it.
*/
public QuicksortThreadDemo() {
for (int i = 0; i < ARRAY_SIZE; i++) {
palette[i] = Color.getHSBColor((i * 230) / (ARRAY_SIZE * 255.0F),
1, 1);
hue[i] = i;
}
setLayout(new BorderLayout());
display = new Display();
add(display, BorderLayout.CENTER);
startButton = new JButton("Start");
JPanel bottom = new JPanel();
bottom.add(startButton);
bottom.setBackground(Color.WHITE);
add(bottom, BorderLayout.SOUTH);
startButton.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent e) {
if (running)
stop();
else
start();
}
});
}
/**
* This method is called when the user clicks the Start button, while no
* thread is running. It starts a new thread and sets the signaling
* variable, running, to true; Also changes the text on the Start button to
* "Finish".
*/
private void start() {
startButton.setText("Finish");
runner = new Runner();
running = true; // Set the signal before starting the thread!
runner.start();
}
/**
* This method is called when the user clicks the button while a thread is
* running. A signal is sent to the thread to terminate, by setting the
* value of the signaling variable, running, to false.
*/
private void stop() {
/*
* Set the value of the signaling variable to false as a signal to the
* thread to terminate.
*/
running = false;
/*
* Wake the thread, in case it is sleeping, to get a more immediate
* reaction to the signal.
*/
runner.interrupt();
/*
* Wait for the thread to stop before setting runner = null. One second
* should be plenty of time for this to happen, but in case something
* goes wrong, it's better not to
*/
try {
runner.join(1000); // Wait for thread to stop. One second should be
// plenty of time.
} catch (InterruptedException e) {
}
runner = null;
}
/**
* This method is called frequently by the thread that is running the
* recursion, in order to insert delays. It calls the repaint() method of
* the display to allow the user to see what is going on; the delay will
* give the system a chance to actually update the display. Since this
* method is called regularly while the recursion is in progress, it is also
* used as a convenient place to check the value of the signaling variable,
* running. If the value of running has been set to false, this method
* throws an exception of type ThreadTerminatedException. This exception
* will cause all active levels of the recursion to be terminated. It is
* caught in the run() method of the thread.
*
* @param millis
* The number of milliseconds to sleep.
*/
private void delay(int millis) {
if (!running)
throw new ThreadTerminationException();
display.repaint();
try {
Thread.sleep(millis);
} catch (InterruptedException e) {
}
if (!running)
throw new ThreadTerminationException();
}
/**
* The basic non-recursive QuickSortStep algorithm, which uses hue[lo] as a
* "pivot" and rearranges elements of the hue array from positions lo
* through hi so that positions the pivot value is in its correct location,
* with smaller items to the left and bigger items to the right. The
* position of the pivot is returned. In this version, we conceptually
* remove the pivot from the array, leaving an empty space. The space is
* marked by a -1, and it moves around as the algorithm proceeds. It is
* shown as a black bar in the display. Every time a change is made, the
* delay() method is called to insert a 1/10 second delay to let the user
* see the change.
*/
private int quickSortStep(int lo, int hi) {
int pivot = hue[lo]; // Save pivot item.
hue[lo] = -1; // Mark location lo as empty.
delay(100);
while (true) {
while (hi > lo && hue[hi] > pivot)
hi--;
if (hi == lo)
break;
hue[lo] = hue[hi]; // Move hue[hi] into empty space.
hue[hi] = -1; // Mark location hi as empty.
delay(100);
while (lo < hi && hue[lo] < pivot)
lo++;
if (hi == lo)
break;
hue[hi] = hue[lo]; // Move hue[lo] into empty space.
hue[lo] = -1; // Mark location lo as empty.
delay(100);
}
hue[lo] = pivot; // Move pivot item into the empty space.
delay(100);
return lo;
}
/**
* The recursive quickSort algorithm, for sorting the hue array from
* positions lo through hi into increasing order. Most of the actual work is
* done in quickSortStep().
*/
private void quickSort(int lo, int hi) {
if (hi <= lo)
return;
int mid = quickSortStep(lo, hi);
quickSort(lo, mid - 1);
quickSort(mid + 1, hi);
}
/**
* This class defines the treads that run the recursive QuickSort algorithm.
* The thread begins by randomizing the array. It then calls quickSort() to
* sort the entire array. If quickSort() is aborted by a
* ThreadTerminationExcpetion, which would be caused by the user clicking
* the Finish button, then the thread will restore the array to sorted order
* before terminating, so that whether or not the quickSort is aborted, the
* array ends up sorted.
*/
private class Runner extends Thread {
public void run() {
try {
for (int i = hue.length - 1; i > 0; i--) { // Randomize array.
int r = (int) ((i + 1) * Math.random());
int temp = hue[r];
hue[r] = hue[i];
hue[i] = temp;
}
delay(1000); // Wait one second before starting the sort.
quickSort(0, hue.length - 1); // Sort the whole array.
} catch (ThreadTerminationException e) { // User aborted quickSort.
for (int i = 0; i < hue.length; i++)
hue[i] = i;
} finally {// Make sure running is false and button label is
// correct.
running = false;
startButton.setText("Start");
display.repaint();
}
}
}
} // end QuicksortThreadDemo
`
Java-向Servlet动态添加URL模式 - java是否可以在运行时动态地将URL模式添加到Servlet?例如,当Servlet启动时,扫描文件夹中的注释,然后将这些URL模式注入到Servlet中?提供更多清晰度-在Servlet的init文件中,我要执行此操作(伪代码)// scan all the files in the package my.project.services // find all…
执行shell命令时永久挂起(Java) - java令人讨厌的代码块如下。该代码几乎总是可以工作,但有时会永远挂起。该应用程序是一个EJB计时器bean。实际上,它只挂了一次,我无法复制它。它的工作已经有将近两年没有任何问题。但是,在测试应用程序的更新版本时,计时器仅在运行几天后冻结,而从未从上次运行时释放数据库锁。日志清楚地表明它冻结在下面的代码块中的某个位置。它正在运行的命令是“ chmod”。publi…
如何检索字符串的特定部分 - java我有一个目录以字符串形式列出,我想检索字符串的特定部分,唯一的是,由于这是一个目录,它的长度可以更改我想从字符串中检索文件名"C:\projects\Compiler\Compiler\src\JUnit\ExampleTest.java" "C:\projects\ExampleTest.java" 因此,在这两种情…
Java:增加YoungGen大小以提高GC性能 - java我正在阅读以下文章:http://java.sun.com/docs/hotspot/gc1.4.2/example.html,无法理解以下几行:Young generation size is too small The young generation heap size in this first example is about 4 Mbytes w…
如果仅对BinaryOperator参数之一进行汇总,那么Java流实际上会减少什么? - java看一下下面的代码:在二进制运算符中,我们有reduce((x,y)-> x + x)。为什么实际上计算为Optional [512]?我没有解释System.out.println((Stream.generate(()->1d).limit(10). peek((doubleValue)->{ System.out.println(…