孟庭苇
不知己所为
2006/01/11 00:55 | by
这个问题时在我写一个列队算法时偶尔想到的，
觉得有趣，就拿出看玩玩，
算法的故事描述如下：
有两个电车司机，A是个老好人，B是个工作狂，
A司机在电车到站候客的时候，每次等待5秒，如果5秒内有人上车，
那么继续重新等待5秒，
知道5秒内没有乘客再次上车或者车上乘客数量已满，才开车，
B司机在电车到站候客的时候，很讲效率，每次总共等待50秒，
50秒内乘客尽量上车，时间一到或者车上乘客已满就开车。
于是有了这个代码：
A bus driver
import java.util.ArrayList;
import java.util.List;
/**
* @author wwei
* @version $Id
* @since 2006-1-10
*/
public class BusA
{
private List passengersPool = new ArrayList();
private final int CARRYING_CAPACITY = 60;
boolean newPassenger = false;
private final int WAIT_TIME = 5000;
public void goUp(Passenger passenger)
{
List passengers;
newPassenger = true;
//有新来的乘客
this.notifyAll();
synchronized (this) {
passengersPool.add(passenger);
passengers = passengersPool;
if (CARRYING_CAPACITY <= passengers.size()) {
busStartup(passengers);
newPassenger = false;
passengersPool.clear();
}
else {
try {
newPassenger = false;//乘客上车坐下了
this.wait(WAIT_TIME);
if (!newPassenger) {
//等下一个乘客上车的时间到了，发现没有新的乘客
busStartup(passengers);
newPassenger = false;
passengersPool.clear();
}
}
catch (InterruptedException e) {
e.printStackTrace();
}
finally{
passengersPool.clear();
}
}
}
}
private void busStartup(List passengers)
{
//开车咯～
}
}
B bus driver
import java.util.List;
import java.util.ArrayList;
/**
* @author wwei
* @version $Id
* @since 2006-1-10
*/
public class Bus2
{
private List passengersPool = new ArrayList();
private final int CARRYING_CAPACITY = 60;
boolean firstPassenger = true;
private final int WAIT_TIME = 50000;
public void goUp(Passenger passenger)
{
List passengers;
synchronized(this){
passengersPool.add(passenger);
passengers = passengersPool;
//第一个乘客上车开始计时
if(firstPassenger){
try {
firstPassenger = false;
this.wait(WAIT_TIME);
firstPassenger = true;
}
catch (InterruptedException e) {
e.printStackTrace();
}
finally {
passengersPool.clear();
}
}
else if(CARRYING_CAPACITY <= passengersPool.size()){
//人满走人～
this.notifyAll();
}
}
if(firstPassenger){
busStartup(passengers);
}
}
private void busStartup(List passengers)
{
//开车咯～
}
}
两个算法效率当然各有所长，
如果大规模的人一天到晚围堵在候车台的地方，
B司机当然爽歪歪了，上车走人，一气呵成，
当这个候车台的乘客时多时少的时候，
那么，A司机从来不会误事～呵呵
觉得有趣，就拿出看玩玩，
算法的故事描述如下：
有两个电车司机，A是个老好人，B是个工作狂，
A司机在电车到站候客的时候，每次等待5秒，如果5秒内有人上车，
那么继续重新等待5秒，
知道5秒内没有乘客再次上车或者车上乘客数量已满，才开车，
B司机在电车到站候客的时候，很讲效率，每次总共等待50秒，
50秒内乘客尽量上车，时间一到或者车上乘客已满就开车。
于是有了这个代码：
A bus driver
import java.util.ArrayList;
import java.util.List;
/**
* @author wwei
* @version $Id
* @since 2006-1-10
*/
public class BusA
{
private List passengersPool = new ArrayList();
private final int CARRYING_CAPACITY = 60;
boolean newPassenger = false;
private final int WAIT_TIME = 5000;
public void goUp(Passenger passenger)
{
List passengers;
newPassenger = true;
//有新来的乘客
this.notifyAll();
synchronized (this) {
passengersPool.add(passenger);
passengers = passengersPool;
if (CARRYING_CAPACITY <= passengers.size()) {
busStartup(passengers);
newPassenger = false;
passengersPool.clear();
}
else {
try {
newPassenger = false;//乘客上车坐下了
this.wait(WAIT_TIME);
if (!newPassenger) {
//等下一个乘客上车的时间到了，发现没有新的乘客
busStartup(passengers);
newPassenger = false;
passengersPool.clear();
}
}
catch (InterruptedException e) {
e.printStackTrace();
}
finally{
passengersPool.clear();
}
}
}
}
private void busStartup(List passengers)
{
//开车咯～
}
}
B bus driver
import java.util.List;
import java.util.ArrayList;
/**
* @author wwei
* @version $Id
* @since 2006-1-10
*/
public class Bus2
{
private List passengersPool = new ArrayList();
private final int CARRYING_CAPACITY = 60;
boolean firstPassenger = true;
private final int WAIT_TIME = 50000;
public void goUp(Passenger passenger)
{
List passengers;
synchronized(this){
passengersPool.add(passenger);
passengers = passengersPool;
//第一个乘客上车开始计时
if(firstPassenger){
try {
firstPassenger = false;
this.wait(WAIT_TIME);
firstPassenger = true;
}
catch (InterruptedException e) {
e.printStackTrace();
}
finally {
passengersPool.clear();
}
}
else if(CARRYING_CAPACITY <= passengersPool.size()){
//人满走人～
this.notifyAll();
}
}
if(firstPassenger){
busStartup(passengers);
}
}
private void busStartup(List passengers)
{
//开车咯～
}
}
两个算法效率当然各有所长，
如果大规模的人一天到晚围堵在候车台的地方，
B司机当然爽歪歪了，上车走人，一气呵成，
当这个候车台的乘客时多时少的时候，
那么，A司机从来不会误事～呵呵
