我不想解一個方程,我的問題不是關於圖和樹數據結構。我正在嘗試從用戶給出的公式中爲圖生成數據點。我想要高效的算法,易於使用且易於維護數據結構。我有兩個解決方案在腦海中從等式生成圖的數據點
1:這是微不足道的,我見過很多應用程序。
String expr = "2*x+3*x";
Evaluator evaluator = new Evaluator();//I have this class
for (int i = start; i < end; i += step)
{
evaluator.setConstant("x", i);
double ans = evaluator.evaluate(expr);
}
這是非常緩慢的,因爲每一個每一個步驟重複像tokenzing,驗證,轉換爲RPN,準備棧和隊列,並在最後結果的計算時間。這個問題的可能解決方案是以某種方式緩存所有堆棧和隊列,但之後需要在當前表達式和以前的表達式之間進行比較以使用最後存儲的狀態。
2:目前我正在開發第二種解決方案。這樣做的目的是效率,並將在未來的符號計算中使用。
到目前爲止,我實現
Variable.java
import java.text.DecimalFormat;
public class Variable
{
private final double pow;
private final double coefficient;
private final String symbol;
public Variable(String symbol)
{
this.symbol = symbol;
this.pow = 1.0;
this.coefficient = 1.0;
}
public Variable(String symbol, double coefficient, double pow)throws IllegalArgumentException
{
if (coefficient == 0.0)throw new IllegalArgumentException("trying to create variable with coefficient 0");
if (pow == 0.0)throw new IllegalArgumentException("trying to create variable with exponent 0");
this.symbol = symbol;
this.pow = pow;
this.coefficient = coefficient;
}
public final String getSymbol()
{
return this.symbol;
}
public final double getPow()
{
return this.pow;
}
public final double getCoefficient()
{
return this.coefficient;
}
@Override
public String toString()
{
StringBuilder builder = new StringBuilder();
DecimalFormat decimalFormat = new DecimalFormat("#.############");
if (coefficient != 1.0)builder.append(decimalFormat.format(this.coefficient));
builder.append(this.symbol);
if (this.pow != 1.0)builder.append("^").append(decimalFormat.format(this.pow));
return builder.toString();
}
/*
* Stub Method
* Generate some unique hash code
* such that chances of key collision
* become less and easy to identify
* variables with same power and same
* symbol*/
@Override
public int hashCode()
{
return 0;
}
}
Equation.java
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
public class Equation
{
private final ArrayList<Boolean> operations;
private final HashMap<String, Variable> variableHashMap;
private int typesOfVariables;
public Equation(Variable variable)
{
this.variableHashMap = new HashMap<>();
this.operations = new ArrayList<>();
this.typesOfVariables = 1;
this.variableHashMap.put(variable.getSymbol(), variable);
}
/*Stub Method*/
public void addVariable(Variable variable, boolean multiply)
{
/*
* Currently not covering many cases
* 1: Add two variables which have same name
* and same pow.
* 2: variable which are wrapped inside functions e.g sin(x)
* and many other.*/
if (multiply && variableHashMap.containsKey(variable.getSymbol()))
{
Variable var = variableHashMap.get(variable.getSymbol());
Variable newVar = new Variable(var.getSymbol(), var.getCoefficient() * variable.getCoefficient(), var.getPow() + variable.getPow());
/*
* Collision chances for variables with same name but
* with different powers*/
this.variableHashMap.replace(var.getSymbol(), newVar);
}
else
{
++this.typesOfVariables;
this.variableHashMap.put(variable.getSymbol(), variable);
}
this.operations.add(multiply);
}
/*Stub Method
*Value for every variable at any point will be different*/
public double solveFor(double x)
{
if (typesOfVariables > 1)throw new IllegalArgumentException("provide values for all variables");
Iterator<HashMap.Entry<String, Variable>> entryIterator = this.variableHashMap.entrySet().iterator();
Variable var;
double ans = 0.0;
if (entryIterator.hasNext())
{
var = entryIterator.next().getValue();
ans = var.getCoefficient() * Math.pow(x, var.getPow());
}
for (int i = 0; entryIterator.hasNext(); i++)
{
var = entryIterator.next().getValue();
if (this.operations.get(i))ans *= var.getCoefficient() * Math.pow(x, var.getPow());
else ans += var.getCoefficient() * Math.pow(x, var.getPow());
}
return ans;
}
@Override
public String toString()
{
StringBuilder builder = new StringBuilder();
Iterator<HashMap.Entry<String, Variable>> entryIterator = this.variableHashMap.entrySet().iterator();
if (entryIterator.hasNext())builder.append(entryIterator.next().getValue().toString());
Variable var;
for (int i = 0; entryIterator.hasNext(); i++)
{
var = entryIterator.next().getValue();
if (this.operations.get(i))builder.append("*").append(var.toString());
else builder.append(var.toString());
}
return builder.toString();
}
}
Main.java
class Main
{
public static void main(String[] args)
{
try
{
long t1 = System.nanoTime();
Variable variable = new Variable("x");
Variable variable1 = new Variable("x", -2.0, 1.0);
Variable variable2 = new Variable("x", 3.0, 4.0);
Equation equation = new Equation(variable);
equation.addVariable(variable1, true);//2x+x
equation.addVariable(variable2, true);
for (int i = 0; i < 1000000; i++)equation.solveFor(i);//Calculate Million Data Points
long t2 = System.nanoTime();
System.out.println((t2-t1)/1000/1000);
System.out.println(equation.toString());
}
catch (Exception e)
{
System.out.println("Error: " + e.getMessage());
}
}
}
我在正確的方向前進? 這個問題有沒有常用的算法?
我的主要目標是效率,代碼清潔和代碼可維護性。
注意:我不是英語母語的人,所以請忽略任何語法錯誤。
謝謝。
我想計算數百萬個點的代碼更好。 –