我目前正在学习数据结构和算法课程，我们已经完成了两个项目，它们以略有不同的方式完成相同的任务。
第一个项目创建了一个数组（包含我们的“生态系统”或“河流”），其中包含500个动物对象，它们被标记为熊，鱼或空。这些数组名称是随机分配的。然后，每个单元格尝试移动到另一个随机单元格。如果熊和熊相遇，则另一个小熊（熊的“伴侣”）将填充一个空单元格。鱼和鱼也一样。如果熊遇到一条鱼，反之亦然，则该鱼被“吃掉”（变成一个空单元格）。关键是运行代码，直到整个数组充满熊为止。
我们完成的第二个项目执行相同的操作，不同之处在于它使用了双向链接列表，每个节点要么随机移动到其旁边的节点，要么保持原状。我已经开发了这些项目，但是现在我们应该创建一个代码，该代码乘以运行具有不同生态系统容量的每个项目所需的时间。
我一直在使用chromebook进行编码，这虽然很困难，但是很容易管理。但是，对于此作业，即使我尝试将其放置几个小时，也无法运行所有代码。我不确定我的程序是否过于复杂，或者我的chromebook无法处理数据。我想知道是否有人可以运行我的Java文件来查看它仅仅是我还是它不能真正有效地运行。我重写了第一个项目的代码，以便每个单元仅尝试移至它旁边的单元，以查看这是否更简单，但仍无法在合理的时间内完成运行。
编辑
我不确定要添加哪个代码，因为我使用了很多不同的文件。我想我将在下面将每个文件都分隔开来发布。
首先，我有一个动物类，这两个项目都相同：
package HW4;
public class Animal {
private String species;
public Animal(String s) {
species = s;
}
public String getSpecies(){
return species;
}
public void setSpecies(String newSpecies) {
species = newSpecies;
}
}
然后，对于我的数组项目，我有River类来构建函数，而Main类则单独运行。这是河课：
package HW4;
import Project2.Animal;
import java.util.Random;
public class River {
//instance variables
private int numAnimals = 0;
public Animal[] emptyRiver; //array of Animal classes named river
//constructor
public River(int capacity) {
numAnimals = capacity;
emptyRiver = new Animal[numAnimals]; }
//methods
public void fillRiver() {
Random rand = new Random();
for(int i = 0; i < emptyRiver.length; i++) {
int x = rand.nextInt(3);
if (x == 0) {
Animal newAnimal = new Animal("Null");
emptyRiver[i] = newAnimal;
}
else if (x == 1) {
Animal newAnimal = new Animal("Bear");
emptyRiver[i] = newAnimal;
}
else if (x == 2) {
Animal newAnimal = new Animal("Fish");
emptyRiver[i] = newAnimal;
}
}
}
public void printRiver(){
int bearCount = 0;
int fishCount = 0;
int nullCount = 0;
for (Animal I:emptyRiver) {
switch(I.getSpecies()) {
case "Bear":
bearCount++;
break;
case "Fish":
fishCount++;
break;
default:
nullCount++;
}
}
System.out.println("Bears: " + bearCount + "\nFish: " +fishCount + "\nNulls: " + nullCount);
}
public void timeStep() {
for (Animal ani:emptyRiver) {
Random rand = new Random();
int randomIndex = rand.nextInt(numAnimals);
if (ani.getSpecies() != "Null") {
if (ani.getSpecies() == "Bear" && emptyRiver[randomIndex].getSpecies() == "Bear") {
for (Animal ani2:emptyRiver) {
if (ani2.getSpecies() == "Null") {
ani2.setSpecies("Bear");
break;
}
}
}
else if(ani.getSpecies() == "Bear" && emptyRiver[randomIndex].getSpecies() == "Fish") {
emptyRiver[randomIndex].setSpecies("Null");
}
else if(ani.getSpecies() == "Fish" && emptyRiver[randomIndex].getSpecies() == "Fish") {
for (Animal ani2 : emptyRiver) {
if (ani2.getSpecies() == "Null") {
ani2.setSpecies("Fish");
break;
}
}
}
else if(ani.getSpecies() == "Fish" && emptyRiver[randomIndex].getSpecies() == "Bear") {
ani.setSpecies("Null");
}
}
}
}
public boolean isallbears() {
for (Animal chk:emptyRiver) {
if (chk.getSpecies() != "Bear") {
return false;
}
}
return true;
}
}
这是我的主语：
package HW4;
import Project2.River;
public class Main {
public static void main(String[] args) {
River myRiver = new River(500);
myRiver.fillRiver();
System.out.println("The river has been initialized.");
myRiver.printRiver();
int counter = 1;
while (myRiver.isallbears()==false) {
System.out.println("\n" + "Year: " + counter);
myRiver.timeStep();
myRiver.printRiver();
counter++;
}
System.out.println("\n" + "The river is now all bears.");
}
}
对于第二个使用双向链表的项目，我使用了相同的动物类，然后使用了一个名为AnimalLinkedLists的类。与上一个不同，这个包含了我的主要内容。看起来像这样：
package HW4;
import HW3.Animal;
import java.util.Random;
public class AnimalLinkedList<E> {
private static class Node<E> {
//instance variables
//elements are animals
private Animal animal;
//references to adjacent nodes
private Node<E> next;
private AnimalLinkedList.Node<E> prev;
//constructor
public Node(Animal a, Node<E> n, Node<E> p) {
animal = a;
next = n;
prev = p;
}
//Access methods
public Animal getAnimal() {
return animal;
}
public Node<E> getPrevious() {
return prev;
}
//update methods
public void setNext(Node<E> n) {
next = n;
}
}
//instance variables
private Node<E> head = null; //head node of list (or null if empty)
private Node<E> tail = null; //tail node of list (or null if empty)
private int size = 0; //number of nodes in the list
//access methods
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public Animal last() { //return element of last node
if (isEmpty()) return null;
return tail.getAnimal();
}
//update method
public void addFirst(Animal a) {
if (isEmpty()) {
Node<E> newNode = new Node(a, null, null);
head = newNode;
tail = newNode;
size++;
} else if (size == 1) {
Node<E> newNode = new Node(a, null, head);
head.setNext(newNode);
head = newNode;
tail.setNext(newNode);
size++;
} else {
Node<E> newNode = new Node(a, null, head);
head.setNext(newNode);
head = newNode;
size++;
}
}
public int capacity;
public void fillList(int capacity) {
Random rand = new Random();
int i = 0;
while (i < capacity) {
int x = rand.nextInt(3);
Animal newAnimal;
if (x == 0) {
newAnimal = new Animal("Bear");
} else if (x == 1) {
newAnimal = new Animal("Fish");
} else {
newAnimal = new Animal("Null");
}
addFirst(newAnimal);
i++;
}
}
public void printList() {
int bearCount = 0;
int fishCount = 0;
int nullCount = 0;
if (!isEmpty()) {
Node<E> currNode = head;
do {
if (currNode.getAnimal().getSpecies() == "Bear") {
bearCount++;
} else if (currNode.getAnimal().getSpecies() == "Fish") {
fishCount++;
} else {
nullCount++;
}
currNode = currNode.prev;
} while (currNode != null);
System.out.println("Number of Bears: " + bearCount);
System.out.println("\nNumber of Fish: " + fishCount);
System.out.println("\nNumber of Nulls: " + nullCount);
}
}
//animals meeting
public void checkMove(Node curr, Node next) {
if (curr.getAnimal().getSpecies() == "Bear" && next.getAnimal().getSpecies() == "Bear") {
Node<E> nowNode = head;
do {
if (nowNode.getAnimal().getSpecies() == "Null") {
nowNode.getAnimal().setSpecies("Bear");
break;
}
nowNode = nowNode.prev;
} while (nowNode != null);
}
else if (curr.getAnimal().getSpecies() == "Bear" && next.getAnimal().getSpecies() == "Fish") {
next.getAnimal().setSpecies("Null");
}
else if (curr.getAnimal().getSpecies() == "Fish" && next.getAnimal().getSpecies() == "Bear") {
curr.getAnimal().setSpecies("Null");
}
else if (curr.getAnimal().getSpecies() == "Fish" && next.getAnimal().getSpecies() == "Fish") {
Node<E> nowNode = head;
do {
if (nowNode.getAnimal().getSpecies() == "Null") {
nowNode.getAnimal().setSpecies("Fish");
break;
}
nowNode = nowNode.getPrevious();
} while (nowNode != null);
}
}
//make random movements in list
public void timeStep() {
Random rand = new Random();
Node<E> currNode = head;
do{
int x = rand.nextInt(3);
if (x == 0) {
if (currNode.next!=null) {
checkMove(currNode, currNode.next);
}
}
else if (x==1) {
if (currNode.prev!=null) {
checkMove(currNode, currNode.prev);
}
}
currNode = currNode.prev;
}while(currNode!=null);
}
//find bears
public boolean isallbears() {
Node <E> currNode = head;
do {
if (currNode.getAnimal().getSpecies() != "Bear") {
return false;
}
currNode = currNode.prev;
}while(currNode!=null);
return true;
}
public static void main(String[] args) {
AnimalLinkedList animalList = new AnimalLinkedList();
animalList.fillList(500);
System.out.println("The river has been initiated.\n");
int year = 1;
animalList.printList();
while(!animalList.isallbears()) {
System.out.println("\nYear: " + year);
animalList.timeStep();
animalList.printList();
year++;
}
System.out.println("\nThe river is now all bears.");
}
}
最后，我的项目将评估不同容量（分别为5000、10000、20000、40000、80000、160000和320000）的时间，如下所示：
package HW4;
public class compTime {
public static void main(String[] args) {
int trials = 10;
long avgTime;
//array capacity 5000
long startTime = System.currentTimeMillis();
for (int i = 0; i < trials; i++) {
River myRiver = new River(5000);
myRiver.fillRiver();
while (myRiver.isallbears() == false) {
myRiver.timeStep();
}
}
long endTime = System.currentTimeMillis();
avgTime = (endTime - startTime) / trials;
System.out.println("River array capacity 5000 took: " + avgTime);
//array capacity 10000
startTime = System.currentTimeMillis();
for (int i = 0; i < trials; i++) {
River myRiver = new River(10000);
myRiver.fillRiver();
while (myRiver.isallbears() == false) {
myRiver.timeStep();
}
}
endTime = System.currentTimeMillis();
avgTime = (endTime - startTime) / trials;
System.out.println("River array capacity 10000 took: " + avgTime);
//array capacity 20000
startTime = System.currentTimeMillis();
for (int i = 0; i < trials; i++) {
River myRiver = new River(20000);
myRiver.fillRiver();
while (myRiver.isallbears() == false) {
myRiver.timeStep();
}
}
endTime = System.currentTimeMillis();
avgTime = (endTime - startTime) / trials;
System.out.println("River array capacity 20000 took: " + avgTime);
//array capacity 40000
startTime = System.currentTimeMillis();
for (int i = 0; i < trials; i++) {
River myRiver = new River(40000);
myRiver.fillRiver();
while (myRiver.isallbears() == false) {
myRiver.timeStep();
}
}
endTime = System.currentTimeMillis();
avgTime = (endTime - startTime) / trials;
System.out.println("River array capacity 40000 took: " + avgTime);
//array capacity 80000
startTime = System.currentTimeMillis();
for (int i = 0; i < trials; i++) {
River myRiver = new River(80000);
myRiver.fillRiver();
while (myRiver.isallbears() == false) {
myRiver.timeStep();
}
}
endTime = System.currentTimeMillis();
avgTime = (endTime - startTime) / trials;
System.out.println("River array capacity 80000 took: " + avgTime);
//array capacity 160000
startTime = System.currentTimeMillis();
for (int i = 0; i < trials; i++) {
River myRiver = new River(160000);
myRiver.fillRiver();
while (myRiver.isallbears() == false) {
myRiver.timeStep();
}
}
endTime = System.currentTimeMillis();
avgTime = (endTime - startTime) / trials;
System.out.println("River array capacity 160000 took: " + avgTime);
//array capacity 320000
startTime = System.currentTimeMillis();
for (int i = 0; i < trials; i++) {
River myRiver = new River(320000);
myRiver.fillRiver();
while (myRiver.isallbears() == false) {
myRiver.timeStep();
}
}
endTime = System.currentTimeMillis();
avgTime = (endTime - startTime) / trials;
System.out.println("River array capacity 320000 took: " + avgTime);
//Doubly Linked List Version
//doubly linked list capacity 5000
startTime = System.currentTimeMillis();
for (int i = 0; i < trials; i++) {
AnimalLinkedList animalList = new AnimalLinkedList();
animalList.fillList(5000);
while (!animalList.isallbears()) {
animalList.timeStep();
}
}
endTime = System.currentTimeMillis();
avgTime = (endTime - startTime) / trials;
System.out.println("River Linked List capacity 5000 took: " + avgTime);
//doubly linked list capacity 10000
startTime = System.currentTimeMillis();
for (int i = 0; i < trials; i++) {
AnimalLinkedList animalList = new AnimalLinkedList();
animalList.fillList(10000);
while (!animalList.isallbears()) {
animalList.timeStep();
}
}
endTime = System.currentTimeMillis();
avgTime = (endTime - startTime) / trials;
System.out.println("River Linked List capacity 10000 took: " + avgTime);
//doubly linked list capacity 20000
startTime = System.currentTimeMillis();
for (int i = 0; i < trials; i++) {
AnimalLinkedList animalList = new AnimalLinkedList();
animalList.fillList(20000);
while (!animalList.isallbears()) {
animalList.timeStep();
}
}
endTime = System.currentTimeMillis();
avgTime = (endTime - startTime) / trials;
System.out.println("River Linked List capacity 20000 took: " + avgTime);
//doubly linked list capacity 40000
startTime = System.currentTimeMillis();
for (int i = 0; i < trials; i++) {
AnimalLinkedList animalList = new AnimalLinkedList();
animalList.fillList(40000);
while (!animalList.isallbears()) {
animalList.timeStep();
}
}
endTime = System.currentTimeMillis();
avgTime = (endTime - startTime) / trials;
System.out.println("River Linked List capacity 40000 took: " + avgTime);
//doubly linked list capacity 80000
startTime = System.currentTimeMillis();
for (int i = 0; i < trials; i++) {
AnimalLinkedList animalList = new AnimalLinkedList();
animalList.fillList(80000);
while (!animalList.isallbears()) {
animalList.timeStep();
}
}
endTime = System.currentTimeMillis();
avgTime = (endTime - startTime) / trials;
System.out.println("River Linked List capacity 80000 took: " + avgTime);
//doubly linked list capacity 120000
startTime = System.currentTimeMillis();
for (int i = 0; i < trials; i++) {
AnimalLinkedList animalList = new AnimalLinkedList();
animalList.fillList(120000);
while (!animalList.isallbears()) {
animalList.timeStep();
}
}
endTime = System.currentTimeMillis();
avgTime = (endTime - startTime) / trials;
System.out.println("River Linked List capacity 120000 took: " + avgTime);
//doubly linked list capacity 160000
startTime = System.currentTimeMillis();
for (int i = 0; i < trials; i++) {
AnimalLinkedList animalList = new AnimalLinkedList();
animalList.fillList(160000);
while (!animalList.isallbears()) {
animalList.timeStep();
}
}
endTime = System.currentTimeMillis();
avgTime = (endTime - startTime) / trials;
System.out.println("River Linked List capacity 160000 took: " + avgTime);
//doubly linked list capacity 320000
startTime = System.currentTimeMillis();
for (int i = 0; i < trials; i++) {
AnimalLinkedList animalList = new AnimalLinkedList();
animalList.fillList(320000);
while (!animalList.isallbears()) {
animalList.timeStep();
}
}
endTime = System.currentTimeMillis();
avgTime = (endTime - startTime) / trials;
System.out.println("River Linked List capacity 320000 took: " + avgTime);
}
}
我希望这不要太混乱，如果需要清除任何内容，我将添加另一个编辑。
我看到的问题是您的动物实际上从未动过。 checkMove（）仅检查交配和食用条件，但熊或鱼在任何时候都不会改变列表中的位置。在您的第一个代码中这不是问题，因为您检查的索引是随机的，但是在第二个代码中，由于空头不动，所以他们吃新鱼的唯一方法是交配。我认为它仍然应该在某个时刻终止，但是可能会花费非常非常长的时间。想象只有一对配对的熊，其余的是鱼。熊吃东西并随后直接交配的可能性很小，因此它需要很长时间才能发生。
我认为问题不在于chromebook，问题在于您的算法。