65.9K
CodeProject 正在变化。 阅读更多。
Home

生命游戏，高级编程风格

Maximilian1986
starIconstarIconstarIconstarIconstarIcon

5.00/5 (5投票s)

2015 年 10 月 27 日

CPOL

7分钟阅读

viewsIcon

17488

downloadIcon

251

“生命游戏”是对人类进化的一种数学表示，其中一些模式随着时间而发展。

下载 GameOfLife.zip

引言

“生命游戏”是对人类进化的一种数学表示，其中一些模式随着时间而发展。每种模式通过时间的演变来改变二维正交宇宙的状态。它非常酷，并且具有简单的规则，却能产生极其复杂的行为。

规则

生命宇宙非常简单。一个方形网格包含细胞，这些细胞可以是死的或活的。每个细胞的行为根据以下规则与其八个邻居相互作用

  1. 任何拥有少于两个存活邻居的存活细胞都会死亡，仿佛是由于人口不足。
  2. 任何拥有两个或三个存活邻居的存活细胞将继续生存到下一代。
  3. 任何拥有三个以上存活邻居的存活细胞都会死亡，仿佛是由于人口过剩。
  4. 任何拥有正好三个存活邻居的死亡细胞会变成一个存活细胞，仿佛是由于繁殖。

它从网格上的一个模式开始——时间 t0 的世代——然后同时对所有细胞应用规则。此操作会产生一个新模式（时间 t1 的世代），其中二维宇宙的状态已发生改变。

之后，我们再次对所有细胞应用规则，依此类推。

就是这样。没有其他规则了。

方法

有几种不同的方法来处理这个问题。 

不熟练的开发人员可能会直接从规则开始，不加分析，可能实现 MVC 模式，而没有利用可能的并发编程风格。

大多数并发应用程序围绕任务的执行进行组织：将应用程序的工作分解为任务可以简化程序组织，通过提供自然的事务边界来方便错误恢复，并通过提供自然的并行化工作结构来促进并发，以异步模式运行。

设计空间中的步骤

首先，我们必须分析问题以识别可利用的并发，然后识别并发架构。我们可以通过识别以下内容来做到这一点：

  • 可能的任务
    • 一系列指令，对应算法的某个逻辑部分。实际上，这是一项作为赋值（面向设计的定义）所需完成的工作。
  • 数据分解及其依赖关系
    • 将任务映射到实体
      • 激活负责执行任务的实体
      • 封装任务执行的控制逻辑

数据分解模式

概念类

问题可以很容易地分解成可以相对独立操作的单元；就像“分而治之”的原则一样，它可以自然地分解成一组独立的任务。

  • 任务必须足够独立，以至于管理依赖项只占用程序总体执行时间的一小部分。
  • 独立性有利于并发，因为如果存在足够的处理资源，独立的任务就可以并行执行。
  • 选择良好的任务边界，加上合理的任务执行策略，有助于实现这些目标。

更确切地说

  • 首先，识别数据单元，然后是相关的任务，以便识别单元。
  • 在这种情况下，任务分解遵循数据分解。
  • 执行以异步模式进行：不同的任务有助于计算结果，然后，它们通过一个简单的监视器以被动模式同步。

关于同步的注意事项：并发编程风格的“毒药”

  • 串行化/顺序化对性能是致命的。
  • 但对于正确性（安全属性）是必需的。

生活中我们不能拥有一切，每个故事都有两面:-)

 

架构和模式

在这种情况下，我将使用主从工作者模式。
该架构由一个主实体和一个动态的工作者实体集合组成，它们通过一个充当任务集的适当协调介质进行交互。

  • Master
    • 将全局任务分解为子任务
    • 通过将任务分配插入到任务集中来分配子任务。
    • 收集任务结果
  • 工作者
    • 从任务集中检索要执行的任务，执行任务 
    • 沟通结果
      • 数据结构的监视器可用于聚合和同步结果。

架构

它选择了一个 MVC 架构，其中

  • 视图： 
    • 启动算法
    • 停止算法
    • 在网格上设计单元格
    • 检查细胞存活的数量
  • 控制器 (Controller)
    • 设置模型和视图
    • 实现 start 方法
    • 创建一个“安全启动”标志
    • 调用模型启动算法
    • 实现 stop 方法
  • 模型
    • 模型是所有项目的核心，它实现了所选的策略。 
    • 我们选择了 Executor 框架来实现上述策略：这个 Executor 基于生产者-消费者模式，其中提交任务的活动是生产者（产生要完成的工作单元），执行任务的线程是消费者（消费这些工作单元）。

我们开始吧！

视图
public GameOfLifeView(Dimension windowsSize, Dimension matrixSize,int blockSize) {
    super("Game Of Life Viewer Small Grid");
	setSize(windowsSize);
	// Center the window in the middle of the screen
	setLocation(
				(Toolkit.getDefaultToolkit().getScreenSize().width - getWidth()) / 2,
				(Toolkit.getDefaultToolkit().getScreenSize().height - getHeight()) / 2
                );

	listeners = new ArrayList<inputlistener>();

	startButton = new JButton("start");
	stopButton = new JButton("stop");

	// When start the program, the Button "stop" is not enabled
	stopButton.setEnabled(false);

	JPanel controlPanel = new JPanel();

	controlPanel.add(startButton);
	controlPanel.add(stopButton);

	setPanel = new GameOfLifePanel(matrixSize, blockSize);
	setPanel.setSize(matrixSize);

	addMouseMotionListener(this);
	addMouseListener(this);

	JPanel infoPanel = new JPanel();
	state = new JTextField(20);
	state.setText("Ready...");
	state.setEditable(false);
	infoPanel.add(new JLabel("State"));
	infoPanel.add(state);
	JPanel cp = new JPanel();
	LayoutManager layout = new BorderLayout();
	cp.setLayout(layout);
	cp.add(BorderLayout.NORTH, controlPanel);

	// Add in the grid the Gosper Glider Gun like a test
	setPanel.CannoneAliantiGosper();

	cp.add(BorderLayout.CENTER, setPanel);
	cp.add(BorderLayout.SOUTH, infoPanel);
	setContentPane(cp);

	startButton.addActionListener(this);
	stopButton.addActionListener(this);
	setDefaultCloseOperation(EXIT_ON_CLOSE);
	setResizable(false);
}

首先，我创建了 View，我在其中插入了
- 开始按钮
- 停止按钮
- 网格（set Panel 是实现 Grid 的类）
- 用于检查细胞——死或活——的标签

一旦创建了视图，GUI 的结果应该是这样的。

控制器 (Controller)
public class Controller implements InputListener {

	private GameOfLifeView view;
	private GameOfLifeSet set;
	private Flag stopFlag;
	
	public Controller(GameOfLifeSet set, GameOfLifeView view){
		this.set = set;
		this.view = view;
	}

	@Override
	public void started(ArrayList< point > matrix){
		set.setupMatrix(matrix);
		stopFlag = new Flag();
		new QuadratureService(set,view,stopFlag, matrix).start();	
	}

	@Override
	public void stopped() {
		stopFlag.set();
	}
}

Controller 类非常简单：考虑到程序的结构，Controller 仅限于连接模型和视图，创建 start 和 stop 方法的监视器。

模型

程序的模型是文章的核心，其中上述架构得以实现。
首先，我创建了 `QuadratureService` 类，它

  • 创建主线程，该线程将所有细胞的状态（“存活”或“死亡”）返回到网格。 
  • 接下来，它更新模型（GameOfLifeSet）和视图（GameOfLifeView）的网格。
/**
* Main thread to check the status of the algorithm Game of Life
* 
* @param set
* @param view
* @param stopFlag
* @param matrix
*/
public QuadratureService(GameOfLifeSet set, GameOfLifeView view, Flag stopFlag, ArrayList< point > matrix) {
	this.view = view;
	this.set = set;
	this.stopFlag = stopFlag;
	pointBoardT0 = new boolean[3][3];
}
@Override
public void run() {
	try {
		if (set.getMatrix().isEmpty()) {
			stopFlag.set();
			view.changeState("No point in Matrix!");
		}
		while (!stopFlag.isSet()) {
			Thread.sleep(50);
            //The numbers of core in your pc
			int poolSize = Runtime.getRuntime().availableProcessors() + 1;

			/*
			 * I create master which calculates the state of the cells. the
			 * result of all cells counted is saved in Variable result
			 * (ArrayList < point >) that it is passed to both the Model that
			 * the View to update the status of the structure Data and the
			 * grid display screen
			 */
			Master master = new Master(set, poolSize, stopFlag);
			ArrayList< point > result = master.compute();
			set.setupMatrix(result);
			view.setUpdated(result);

			if (stopFlag.isSet()) {
				view.changeState("Interrupted. Cell live: " + result.size());
			} else
				view.changeState(String.valueOf(result.size()));
		}
	} catch (Exception ex) {
		ex.printStackTrace();
	}
}

主线程 `Master` 是一个 Executor，更准确地说，是 `Executors.newFixedThreadPool(poolSize);`
但是，我为什么要使用它？

  • newFixedThreadPool。一个固定大小的线程池在提交任务时创建线程，直到达到最大池大小，然后尝试保持池大小恒定（如果线程因意外异常而死亡，则添加新线程）。
  • newCachedThreadPool。缓存的线程池在池的当前大小超过处理需求时，可以更灵活地回收空闲线程，并在需求增加时添加新线程，但不对池的大小设置限制。

简单来说：我为每个存活的细胞创建了一个异步任务。统计上，存活的细胞数量非常多，所以我更喜欢使用 `newFixedThreadPool` 方法。

public Master(GameOfLifeSet set, int poolSize, Flag stopFlag) {
	this.executor = Executors.newFixedThreadPool(poolSize);
	// this.executor = Executors.newCachedThreadPool();
	this.set = set;
	this.stopFlag = stopFlag;
}

/**
 * The function returns the list of the living cells of the game
 * 
 * @return
 * @throws InterruptedException
 */
public ArrayList< point > compute() throws InterruptedException {

	ArrayList< future < point > > pointT1 = new ArrayList< future < point > >();
	gameBoard = new boolean[set.getSizeX() + 1][set.getSizeY() + 1];
	for (Point current : set.getMatrix()) {
		if (current != null)
			gameBoard[current.x + 1][current.y + 1] = true;
	}
	for (int i = 1; i < gameBoard.length - 1; i++) {
		for (int j = 1; j < gameBoard[0].length - 1; j++) {
			try {
				pointBoardT0 = new boolean[3][3];
				// load points near instant T0
				pointBoardT0[0][0] = gameBoard[i - 1][j - 1];
				pointBoardT0[0][1] = gameBoard[i - 1][j];
				pointBoardT0[0][2] = gameBoard[i - 1][j + 1];
				pointBoardT0[1][0] = gameBoard[i][j - 1];
				// pointBoard[1][1] (me)
				pointBoardT0[1][2] = gameBoard[i][j + 1];
				pointBoardT0[2][0] = gameBoard[i + 1][j - 1];
				pointBoardT0[2][1] = gameBoard[i + 1][j];
				pointBoardT0[2][2] = gameBoard[i + 1][j + 1];

				/*
				 * If the point is evaluated "false" (white grid) then it is
				 * useless to create the res object type Future < point > as
				 * it will always be "false" and the grid does not change.
				 */
				int check = 0;
				for (boolean state[] : pointBoardT0) {
					for (boolean b : state) {
						if (b)
							check++;
					}
				}

				if (check != 0) {
				    /*
				     * I create the object of res futures; that is a
				     * "promise" of Point ("live" or. "Dead")
				     */
				    Future< point > res = executor.submit(new ComputeTask(
						    set, gameBoard[i][j], pointBoardT0, i, j,
						    stopFlag));
				    // The result I insert it in the list point T1 (at time T1)
                    // Like a monitor barrier
				    pointT1.add(res);
			    }
			} catch (Exception e) {
			e.printStackTrace();
		}
	}
}

我们深入研究！到目前为止，程序为每个存活的细胞创建一个异步任务。这意味着并发得到了最大化。

@Override
public Point call() {
	Point pointT1 = null;
	try {
		pointT1 = result.computePoint(pointT0, pointBoard, i, j);
		if (stopFlag.isSet()) {
			// log("task interrupted");
		} else {
			// log("task completed");
		}
	} catch (Exception ex) {
		ex.printStackTrace();
	}

	return pointT1;
}

最后，`computePoint` 计算细胞是存活还是死亡，实现了生命游戏的规则。

public Point computePoint(boolean pointT0, boolean[][] pointBoard, int i, int j) {
	int surrounding = 0;
	if (pointBoard[0][0]) surrounding++;
	if (pointBoard[0][1]) surrounding++;
	if (pointBoard[0][2]) surrounding++;
	if (pointBoard[1][0]) surrounding++;
	// pointBoard[1][1]
	if (pointBoard[1][2]) surrounding++;
	if (pointBoard[2][0]) surrounding++;
	if (pointBoard[2][1]) surrounding++;
	if (pointBoard[2][2]) surrounding++;

	if (pointT0) {
		// A cell m [i, j] that in state s (t) is live and has
		// two or three neighbouring cells live,
		// in state s (t + 1) remains live ("survives")

		if ((surrounding == 2) || (surrounding == 3))
			return new Point(i - 1, j - 1);
	} else {
		// A cell m [i, j] that in state s (t) is dead and has
		// Three neighbouring cells live,
		// In state s (t + 1) become live
		if (surrounding == 3)
			return new Point(i - 1, j - 1);
	}
	/**
	 * 1) a cell m [i, j] that in state s (t) is live and has zero or more a
	 * neighbouring cell live (and other dead), in state s (t + 1) becomes
	 * Dead ("die of loneliness")
	 *
	 * 2) a cell m [i, j] that in state s (t) is live and has four or more
	 * neighbouring cells live in the state s (t + 1) becomes dead ("dies
	 * over-population ")
	 */
	return null;
}

关机

一旦任务被并行化，并且并发最大化，如何关闭算法？
我们已经看到了如何创建 Executor，但没有看到如何关闭它。因为 Executor 异步处理任务，所以在任何给定时间，先前提交的任务的状态都不是一目了然的。
有些可能已完成，有些可能正在运行，还有一些可能已排队等待执行。
为了关闭应用程序，有一个范围从

  • 优雅关闭
    • 完成你已经开始的事情，但不要接受新的工作。
  • 突然关闭
    • 关闭机房的电源，以及介于两者之间的各种选项。

对于这个应用程序，我使用了

  • 监视器 `Flag`：检查用户是否按下了视图中的开始/停止按钮。
  • 优雅关闭：启动有序关闭，其中已提交的任务将被执行，不会接受新任务。
public class Flag {
	
	private boolean isSet;
	
	public Flag(){
		isSet = false;
	}
	
	public synchronized void set(){
		isSet = true;
	}
	
	public synchronized boolean isSet(){
		return isSet;
	}
	
	public synchronized void reset(){
		isSet = false;
	}
}

好奇心

英国数学家约翰·康威，现任普林斯顿大学教授，于 20 世纪 60 年代末发明了生命游戏。他选择的规则产生了最不可预测的行为。
如果您想了解更多关于生命游戏的信息和历史背景，这里有一个约翰·康威关于生命游戏起源的最新采访。

结论

围绕任务的执行来构建应用程序可以简化开发并促进并发。Executor 框架允许您将任务提交与执行策略解耦，并支持各种执行策略。
为了最大化将应用程序分解为任务的好处，您必须识别合理的任务边界，这可以通过分析问题的各个阶段来完成。
在某些应用程序中，明显的任务边界效果很好，而在其他应用程序中，可能需要一些分析来发现更细粒度的可利用并行性，就像本案例研究一样。

参考文献

  • http://www.theguardian.com/science/alexs-adventures-in-numberland/2014/dec/15/the-game-of-life-a-beginners-guide
  • https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life
  • Java Concurrency in Practice - Goetz et al., Addison Wesley, 2006
© . All rights reserved.