Master1991
Lieutenant
- Registriert
- Okt. 2007
- Beiträge
- 689
Hi,
ich versuche für einen Alorithmus das "Distributivgesetz" zu implementieren (mit ein paar änderungen).
Beispiel:
(P4+P1+P9)(P9+P9)
ausmultipliziert wird es zu:
(P4P9+P4P9+P1P9+P1P9+P9P9+P9P9)
gewollt wäre hier nur P9 folgend den Regeln: X*X=X, XY+X=X, X+X=X (Es handelt sich um logik funktionen weshalb dies hier so gilt).
X*X=X habe ich in meinem Code bereits berücksichtigt sodass mein Ergebnis momentan
(P4P9+P4P9+P1P9+P1P9+P9+P9)
so aussieht.
Die anderen regeln wären noch zu implementieren (um die Problemgröße zu reduzieren, denn das wächst nicht linear).
Mein Hauptproblem ist momentan jedoch ein OutOfMemory error: heap space error.
Meine Idee ist nun den genutzten Speicher komplett vorher abzuschätzen und zu allokieren, daran scheitere ich momentan jedoch. es geht sozusagen um die verbesserung der multiplyArray() Methode. Der komplette Beispielcode:
PS: Ich benutze die Wrapper Klasse um direkt auf Methoden wie contains auf dem array zugreifen zu können. Ich habe es vorhin auch schon mit einen int[][][] array probiert, dort war meine implementerung jedoch langsamer.
Bei
public int rowValues = 10;
public int columnValues = 7;
bekommen ich dann den memory error wobei es zeittechnisches noch vollkommen okay wäre
ich versuche für einen Alorithmus das "Distributivgesetz" zu implementieren (mit ein paar änderungen).
Beispiel:
(P4+P1+P9)(P9+P9)
ausmultipliziert wird es zu:
(P4P9+P4P9+P1P9+P1P9+P9P9+P9P9)
gewollt wäre hier nur P9 folgend den Regeln: X*X=X, XY+X=X, X+X=X (Es handelt sich um logik funktionen weshalb dies hier so gilt).
X*X=X habe ich in meinem Code bereits berücksichtigt sodass mein Ergebnis momentan
(P4P9+P4P9+P1P9+P1P9+P9+P9)
so aussieht.
Die anderen regeln wären noch zu implementieren (um die Problemgröße zu reduzieren, denn das wächst nicht linear).
Mein Hauptproblem ist momentan jedoch ein OutOfMemory error: heap space error.
Meine Idee ist nun den genutzten Speicher komplett vorher abzuschätzen und zu allokieren, daran scheitere ich momentan jedoch. es geht sozusagen um die verbesserung der multiplyArray() Methode. Der komplette Beispielcode:
PS: Ich benutze die Wrapper Klasse um direkt auf Methoden wie contains auf dem array zugreifen zu können. Ich habe es vorhin auch schon mit einen int[][][] array probiert, dort war meine implementerung jedoch langsamer.
Bei
public int rowValues = 10;
public int columnValues = 7;
bekommen ich dann den memory error wobei es zeittechnisches noch vollkommen okay wäre
Code:
package test;
import java.util.Arrays;
import java.util.Random;
public class DistributiveTest {
private IntSetArray[][] data;
public int maxValue = 9;
public int rowValues = 2;
public int columnValues = 3;
public int maxEntrys = 1;
private int index;
public static void main(String[] args) {
DistributiveTest dl = new DistributiveTest();
dl.generateTestData();
//Print Array
System.out.println("Array (" + dl.data.length + " x " + dl.data[0].length + "): ");
String sep = "";
String prefix = "";
System.out.print("(");
for (int i = 0; i < dl.data.length; i++) {
System.out.print(sep);
sep = ")(";
prefix = "";
for (int j = 0; j < dl.data[i].length; j++) {
if (dl.data[i][j] != null) {
System.out.print(prefix);
prefix = "+";
System.out.print(dl.data[i][j]);
}
}
}
System.out.println(")");
//Multiply array
dl.index = 0;
long startTime = System.currentTimeMillis();
while ((dl.index + 1) < dl.data.length) {
dl.multiplyArray();
dl.index += 1;
//System.out.println(dl.productOfSums.toString());
}
long elapsedTime = System.currentTimeMillis() - startTime;
System.out.println("Multiply took: " + elapsedTime + " ms");
if (dl.data[dl.index].length < 20) {
System.out.print("(");
prefix = "";
for (int i = 0; i < dl.data[dl.index].length; i++) {
if (dl.data[dl.index][i] != null) {
System.out.print(prefix);
prefix = "+";
System.out.print(dl.data[dl.index][i]);
}
}
System.out.print(")");
}
}
private void generateTestData() {
data = new IntSetArray[rowValues][columnValues];
Random rand = new Random();
for (int i = 0; i < rowValues; i++) {
//Between 2 and columnValues
int columnValue = rand.nextInt(columnValues - 1) + 2;
for (int j = 0; j < columnValue; j++) {
data[i][j] = new IntSetArray(maxValue + 1);
int entrys = rand.nextInt(maxEntrys) + 1;
for (int k = 0; k < entrys; k++) {
int value = rand.nextInt((int) maxValue + 1);
if (!data[i][j].contains(value)) {
data[i][j].add(value);
} else {
k--;
}
}
}
}
}
private void multiplyArray() {
IntSetArray[] is1 = data[index];
IntSetArray[] is2 = data[index + 1];
IntSetArray[] tmpArray = new IntSetArray[is1.length * is2.length];
int loopCount = 0;
for (int i = 0; i < is1.length; i++) {
for (int j = 0; j < is2.length; j++) {
if (is1[i] != null && is2[j] != null) {
IntSetArray tmp = new IntSetArray(maxValue + 1);
tmp.addAll(is1[i].getIntSet());
tmp.addAll(is2[j].getIntSet());
//is2[j].addAll(is1[i].getIntSet());
tmpArray[loopCount++] = tmp;
}
}
}
data[index] = null;
data[index + 1] = tmpArray;
}
class IntSetArray {
int[] intSet;
int arraySize;
int currentAddIndex;
public IntSetArray(int size) {
this.arraySize = size;
this.intSet = new int[arraySize];
Arrays.fill(intSet, -1);
this.currentAddIndex = 0;
}
public void add(int i) {
if (!contains(i) && i != -1) {
intSet[currentAddIndex] = i;
currentAddIndex++;
}
}
public int[] getIntSet() {
return intSet;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < intSet.length; i++) {
if (!(intSet[i] == -1)) {
sb.append("P");
sb.append(intSet[i]);
}
}
return sb.toString();
}
boolean contains(int value) {
for (int i = 0; i < arraySize; i++) {
if (intSet[i] == value) {
return true;
} else if (intSet[i] == -1) {
return false;
}
}
return false;
}
void addAll(int[] a) {
for (int i = 0; i < a.length; i++) {
if (a[i] == -1) {
break;
}
this.add(a[i]);
}
}
int size() {
return arraySize;
}
}
}
(schnell ist der Ansatz und Speicher verbraucht er auch kaum - beim Input
