A* Algorithmus

Superbyte

Mitglied
Hallo liebe Community,

ich habe ein kleines Problem bei meinem A*-Algorithmus. Ich habe ihn für ein Projekt der Uni programmiert und habe versucht den A* mit dem ExecutorService ein bisschen flotter zu machen. Leider ist das Gegenteil eingetreten. Mit dem ExcecutorService braucht der A* 3 mal so lange um den Weg zu finden. Ich hoffe mir kann da jemand weiterhelfen.
Hier der Code:

Java:
package pp2012.pathfinding;

import java.awt.Point;
import java.util.ArrayList;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;

import pp2012.world.Tile;
import pp2012.world.Unit;

public class AStar{

	private static AStar aStar = new AStar();

	/** The AStar class is a Singleton Class*/
	private AStar() {
	}

	/**
	 * Method takes the tileMap and the unit and calculates the shortest path from 
	 * the unit location to the unit destination and returns the shortest path.
	 * If no path is found the algorithm returns a null value
	 * The algorithm uses the heapsort algorithm to sort the openList to guarantee 
	 * a time complexity of O(n lg n)
	 * 
	 * 
	 * @param tileMap
	 * @param unit
	 * @return path
	 */
	
	public ArrayList<Point> getPath(final Tile[][] tileMap, final Unit unit) {
		final ArrayList<AStarNode> openList = new ArrayList<>();
		final ArrayList<AStarNode> closedList = new ArrayList<>();
		ArrayList<Point> path = new ArrayList<>();
		Heapsort heapSort = Heapsort.getInstance();
		
		ExecutorService executor;

		Point unitLocation = unit.getDestination();
		Point unitDestination = unit.getLocation();
		
		double edgeCosts = tileMap[(int) unitLocation.getX()][(int) unitLocation.getY()].getCosts();	
		double estimatedHeuristicCosts = Math.sqrt(unitLocation.distanceSq(unitDestination));
		
		AStarNode startNode = new AStarNode(null, edgeCosts, estimatedHeuristicCosts, (int) unitLocation.getX(), (int) unitLocation.getY());

		openList.add(startNode);
		
		while (!openList.isEmpty()) {

			heapSort.heapsort(openList);
			AStarNode currentNode = openList.remove(0);
	
			if (currentNode.getX() == unitDestination.getX() && currentNode.getY() == unitDestination.getY()) {
				
				/** Saves the path from the unit location to the destination of a unit
				 *  into a path ArrayList */
				while (currentNode.getPredecessor() != null) {
					currentNode = currentNode.getPredecessor();
					Point point = new Point(currentNode.getX(), currentNode.getY());
					path.add(point);
				}


				/** Path is returned */
				return path;
			}

			/** If the currentNode is not the goal than add it to the closedList and continue with the algorithm */
			closedList.add(currentNode);
			
			executor = Executors.newFixedThreadPool(8);
			
			final AStarNode currentNodeCopy = currentNode;

			/** Examine all eight neighbor around the currentNode */
			for(int x = -1; x < 2; x++){
				for(int y = -1; y < 2; y++){
					if(x == 0 && y == 0){
						continue;
					}
					
					final int xCopy = x;
					final int yCopy = y;
					
					executor.submit(new Runnable() {
						@Override
						public void run() {
							examineNeighbours(currentNodeCopy, currentNodeCopy.getX() - xCopy, currentNodeCopy.getY() - yCopy, tileMap, unit, openList, closedList);
						}
					});
					
				}
			}
			
			executor.shutdown();
			try {
				executor.awaitTermination(1, TimeUnit.DAYS);
			} catch (InterruptedException e) {}

		}
		/** If no path is found the algorithm returns a null value */
		return null;
	}

	/**
	 * Method checks the neighbor nodes and calculates the edge, heurisitic and sum costs.
	 * If the node which is beeing examined is already in the openList oder closedList the
	 * method terminates. 
	 * If the node is not in the openList the node is added to it. 
	 * 
	 * @param currentNode
	 * @param x
	 * @param y
	 * @param tileMap
	 * @param unit
	 * @param openList
	 * @param closedList
	 * 
	 */

	private void examineNeighbours(AStarNode currentNode, int x, int y, Tile[][] tileMap, Unit unit, ArrayList<AStarNode> openList, ArrayList<AStarNode> closedList){
		
		Point unitDestination = unit.getLocation();
		
		try{
			
			if(tileMap[x][y].isWalkable(unit.getType()) && (tileMap[x][y].getWorldObject() == null) || unitDestination.equals(new Point(x,y))){
				
				double edgeCosts = tileMap[x][y].getCosts();
				double diagonalMovingCosts = Math.sqrt(2) * edgeCosts;
				double heuristicCost = calcEstimatedHeuristicCosts(currentNode, unitDestination);
				
				AStarNode node = new AStarNode(currentNode, x, y);
				
				/** If the node is in the closedList the rest of the code will be skipped
				 *  The Query is at the start to optimize the run time of the algorithm	 */
				for(AStarNode compareNode : closedList){
					if(compareNode.getX() == node.getX() && compareNode.getY() == node.getY()){
						return;
					}
					
				}

				/** If the node is already in the openList the rest of the code will be skipped	
				 *  The Query is at the start to optimize the run time of the
				 *  algorithm			 */
				for(AStarNode compareNode : openList){
					if(compareNode.getX() == node.getX() && compareNode.getY() == node.getY()){
						return;
					}
				}
				
				/** If the node is a diagonal node it costs are set in the next four
				 *  queries.
				 *  If the node is a vertical or a horizontal the costs are set in 
				 *  the else statement. */
				if (node.getX() - 1 == currentNode.getX() && node.getY() - 1  == currentNode.getY()){
					node.setEdgeCosts(diagonalMovingCosts);
					node.setEstimatedHeuristicCosts(heuristicCost);
					node.setSumCosts(heuristicCost + node.getEdgeCosts());
				}else if(node.getX() - 1 == currentNode.getX() && node.getY() + 1 == currentNode.getY()){
					node.setEdgeCosts(diagonalMovingCosts);
					node.setEstimatedHeuristicCosts(heuristicCost);
					node.setSumCosts(node.getEdgeCosts() + node.getEstimatedHeuristicCosts());
				}else if(node.getX() + 1 == currentNode.getX() && node.getY() - 1 == currentNode.getY()){
					node.setEdgeCosts(diagonalMovingCosts);
					node.setEstimatedHeuristicCosts(heuristicCost);
					node.setSumCosts(node.getEdgeCosts() + node.getEstimatedHeuristicCosts());
				}else if(node.getX() + 1 == currentNode.getX() && node.getY() + 1 == currentNode.getY()){
					node.setEdgeCosts(diagonalMovingCosts);
					node.setEstimatedHeuristicCosts(heuristicCost);
					node.setSumCosts(node.getEdgeCosts() + node.getEstimatedHeuristicCosts());
				}else{
					node.setEdgeCosts(edgeCosts);
					node.setEstimatedHeuristicCosts(heuristicCost);
					node.setSumCosts(node.getEdgeCosts() + node.getEstimatedHeuristicCosts());
				}
				
				/** If the node is not in the openList it costs are calculated and it
				 * is added to the openList */
				node.setEdgeCosts(edgeCosts + node.getPredecessor().getEdgeCosts());
				   node.setEstimatedHeuristicCosts(calcEstimatedHeuristicCosts(node,unitDestination));
				node.setSumCosts(node.getEdgeCosts() +node.getEstimatedHeuristicCosts());
				
				synchronized(this) {
					openList.add(node);
				}
			}
			
		}catch(ArrayIndexOutOfBoundsException aioobe){
		}
		
	}
	
	/**
	 * Calculates the estimated heuristic costs using euclidean distance from
	 * currentNode to the endPoint node.
	 * 
	 * @param currentNode
	 * @param endPoint
	 * @return estimatedHeuristicCosts
	 * 
	 */
	private double calcEstimatedHeuristicCosts(AStarNode currentNode, Point endPoint) {

		int distanceX = Math.abs(currentNode.getX() - endPoint.x);
		int distanceY = Math.abs(currentNode.getY() - endPoint.y);
		return Math.sqrt(Math.pow(distanceX, 2) + Math.pow(distanceY, 2));
	}

	/** Returns an instance of the singleton class */
	public static AStar getInstance() {
		return aStar;
	}

}
 

Cola_Colin

Top Contributor
Ich würde vermuten, dass die Kosten einen 8-Threads Executor zu starten und zu beenden viel höher sind, als ein paar kleine Berechnungen zu machen.

Du solltest auf jeden Fall darauf abzielen, dass du nur einmal einen Executor anlegst.
Wie man A* effektiv auf viele Kerne verteilt, weiß ich nicht, nie probiert. Vermutlich ist es am effektivsten, wenn man das ganze auf höherer Ebene als den 8 Nachbarn eines Feldes angeht.
 

Marco13

Top Contributor
Der Code und was dort gemacht wird ist beim Überfliegen erstmal schwer nachzuvollziehen, da müßte man mehr Zeit aufwenden. Wie viel Parallelität durch ein verstecktes "synchronized(this)" kaputt geht müßte man genauer prüfen. Auf jeden Fall gibt es einige... Dinge die auf jeden Fall ungünstig sind. Spontan z.B. dass der Executor bei jedem Durchlauf neu erstellt wird. Außerdem glaube ich, dass der Executor an sich falsch angewendet wird, aber auch da müßte man nochmal genauer schauen. Ich finde es bei sowas am praktischsten, den Executor EINmal zu erstellen, und ihm in jedem Durchlauf nur mit invokeAll die Liste seiner Tasks zu übergeben (dann wartet er automatisch, bis alle fertig sind). Ein Beispiel in sehr allgemeiner Form ist die Methode "doitMT" hier: http://www.java-forum.org/java-basics-anfaenger-themen/127689-laufzeit-verkuerzen.html#post830791

Abgesehen davon... gibt es Dinge, die das ganze auch OHNE Multihreading deutlich schneller machen können... beim Überfliegen mit am schmerzvollsten war
Java:
    private double calcEstimatedHeuristicCosts(AStarNode currentNode, Point endPoint) {
 
        int distanceX = Math.abs(currentNode.getX() - endPoint.x);
        int distanceY = Math.abs(currentNode.getY() - endPoint.y);
        return Math.sqrt(Math.pow(distanceX, 2) + Math.pow(distanceY, 2));
    }
was man zu
Java:
    // Returns the squared value, but that does not influence comparisons
    // Comparisons with real distances should be
    // if (realDistance * realDistance < calcEstimatedHeuristicCostsSquared(...)) 
    private double calcEstimatedHeuristicCostsSquared(AStarNode currentNode, Point endPoint) {
 
        int distanceX = currentNode.getX() - endPoint.x;
        int distanceY = currentNode.getY() - endPoint.y;
        return distanceX*distanceX + distanceY*distanceY;
    }
ändern können sollte, um viele, viele "pow(x,2)" (=x*x) und vor allem viele teure Wurzelberechnungen zu sparen...
 

Superbyte

Mitglied
Vielen Dank für deine Antwort @Marco13. Leider kann ich die Wurzelberechnung nicht rausnehmen, weil der A* für die Wegberechnung eine Heuristik braucht. Ich habe leider nicht so viel Erfahrung mit dem ExecutorService. Könntest du mir da vllt genau sagen was ich da verändern kann? Wäre sehr freundlich von dir :)

EDIT: Hab jetzt die Wurzelberechnung wie von dir vorgeschlagen rausgenommen aus der Methode rausgenommen. Aber wirklich verbessert hat sich die Laufzeit nicht. Ich habs jetzt mehrfach mal ausgeführt und es knapp 100 ms für die Wegberechnung verbraucht. Das war auch der gleiche Wert wie vorher :)
 
Zuletzt bearbeitet:

Cola_Colin

Top Contributor
Du kannst die Wurzel rausnehmen weil gilt:

a^2 > b^2 wenn a > b

Da dich nur das Verhältnis der Zahlen interessiert, brauchst du also aus a und b keine Wurzel ziehen, um sie zu vergleichen.

Um den Executor mehrfach zu verwenden, schaue dir doch den Link von Marco an.

EDIT:
Es kommt sicher auf die Inputgröße an und auf die Frage, ob dein Executor noch unverändert drinne ist, ob es irgendeinen Unterschied macht, die Wurzel drinne zu haben oder nicht.
 
J

JohannisderKaeufer

Gast
Java:
				AStarNode node = new AStarNode(currentNode, x, y);
				
				/** If the node is in the closedList the rest of the code will be skipped
				 *  The Query is at the start to optimize the run time of the algorithm	 */
				for(AStarNode compareNode : closedList){
					if(compareNode.getX() == node.getX() && compareNode.getY() == node.getY()){
						return;
					}
					
				}

				/** If the node is already in the openList the rest of the code will be skipped	
				 *  The Query is at the start to optimize the run time of the
				 *  algorithm			 */
				for(AStarNode compareNode : openList){
					if(compareNode.getX() == node.getX() && compareNode.getY() == node.getY()){
						return;
					}
				}
Ich würde fast behaupten, wenn man In AStarNode equals(o){x == o.x && y == o.y} und hashCode( x+y oder x* FAKTOR_GROESSER_ALS_DAS_MAXIMALE_Y + y) überschreibt, dann kann man auf die Schleife verzichten und evtl. was Sinnigeres machen wie
Java:
if(closedList.contains(node)) return;
if(openList.contains(node)) return;
Kein Iterieren durch die Liste. Direkter Zugriff über den HashCode.

Java:
				/** If the node is a diagonal node it costs are set in the next four
				 *  queries.
				 *  If the node is a vertical or a horizontal the costs are set in 
				 *  the else statement. */
				if (node.getX() - 1 == currentNode.getX() && node.getY() - 1  == currentNode.getY()){
					node.setEdgeCosts(diagonalMovingCosts);
					node.setEstimatedHeuristicCosts(heuristicCost);
					node.setSumCosts(heuristicCost + node.getEdgeCosts());
				}else if(node.getX() - 1 == currentNode.getX() && node.getY() + 1 == currentNode.getY()){
					node.setEdgeCosts(diagonalMovingCosts);
					node.setEstimatedHeuristicCosts(heuristicCost);
					node.setSumCosts(node.getEdgeCosts() + node.getEstimatedHeuristicCosts());
				}else if(node.getX() + 1 == currentNode.getX() && node.getY() - 1 == currentNode.getY()){
					node.setEdgeCosts(diagonalMovingCosts);
					node.setEstimatedHeuristicCosts(heuristicCost);
					node.setSumCosts(node.getEdgeCosts() + node.getEstimatedHeuristicCosts());
				}else if(node.getX() + 1 == currentNode.getX() && node.getY() + 1 == currentNode.getY()){
					node.setEdgeCosts(diagonalMovingCosts);
					node.setEstimatedHeuristicCosts(heuristicCost);
					node.setSumCosts(node.getEdgeCosts() + node.getEstimatedHeuristicCosts());
				}else{
					node.setEdgeCosts(edgeCosts);
					node.setEstimatedHeuristicCosts(heuristicCost);
					node.setSumCosts(node.getEdgeCosts() + node.getEstimatedHeuristicCosts());
				}

Dies kann man auch umdrehen damit es lesbarer wird
Java:
double currentEdgeCost;

if (node.getX() == currentNode.getX() || node.getY() == currentNode.getY()){
  currentEdgeCost = diagonalMovingCosts;
}else{
  currentEdgeCost = edgeCosts;
}
node.setEdgeCosts(currentEdgeCost);
node.setEstimatedHeuristicCosts(heuristicCost);
node.setSumCosts(heuristicCost + node.getEdgeCosts());
Dies spart im Endeffekt bis zu 7 Überprüfungen, die zwar billig sind, aber dennoch vorhanden.
 

Superbyte

Mitglied
Danke JohannisderKaeufer für dein Feedback, wir werden das auf jedenfall noch ändern :)

100ms ist auch recht wenig, da kann man ja kaum was messen. Hattest du den verlinkten Ansatz mal probiert?

Ja wir haben den Ansatz jetzt mal ausprobiert, hatten vorher eine Laufzeit von ca. 59 ms (PC von einem aus meiner Gruppe) und haben danach eine Laufzeit von ca. 83 ms :(

Nach dem Aufruf executor.invokeAll(tasks); wartet er doch so lange bis die Tasks auch abgearbeitet wurden oder?

Hier mal der Code (nur der relevante Teil, rest ist gleich wie zuvor), vllt haben wir ja iwas falsch gemacht:
Java:
public class AStar{

	public ArrayList<Point> getPath(final Tile[][] tileMap, final Unit unit) {
		final ArrayList<AStarNode> openList = new ArrayList<AStarNode>();
		final ArrayList<AStarNode> closedList = new ArrayList<AStarNode>();
		Heapsort heapSort = Heapsort.getInstance();
		
		/** ExecutorService wird nun nur einmal initialisiert
		* mit 8 Threads, weil wir ja immer nur 8 Nachbarn haben
		* die gleichzeitig geprueft werden koennen
		*/
		ExecutorService executor = Executors.newFixedThreadPool(8);

		Point unitLocation = unit.getDestination();
		Point unitDestination = unit.getLocation();
		
		double edgeCosts = tileMap[(int) unitLocation.getX()][(int) unitLocation.getY()].getCosts();	
		double estimatedHeuristicCosts = Math.sqrt(unitLocation.distanceSq(unitDestination));
		
		AStarNode startNode = new AStarNode(null, edgeCosts, estimatedHeuristicCosts, (int) unitLocation.getX(), (int) unitLocation.getY());

		openList.add(startNode);
		
		while (!openList.isEmpty()) {

			heapSort.heapsort(openList);
			AStarNode currentNode = openList.remove(0);
	
			if (currentNode.getX() == unitDestination.getX() && currentNode.getY() == unitDestination.getY()) {
				ArrayList<Point> path = new ArrayList<Point>();
				
				while (currentNode.getPredecessor() != null) {
					currentNode = currentNode.getPredecessor();
					Point point = new Point(currentNode.getX(), currentNode.getY());
					path.add(point);
				}

				return path;
			}

			closedList.add(currentNode);

			/** Liste der Tasks wird initialisiert */
			List<Callable<Object>> tasks = new ArrayList<Callable<Object>>();
			
			for(int x = -1; x < 2; x++){
				for(int y = -1; y < 2; y++){
					if(x == 0 && y == 0){
						continue;
					}
					
					final AStarNode node = currentNode;
					final int x1 = x;
					final int y1 = y;
					
		            Runnable runnable = new Runnable() {
		                @Override
		                public void run()
		                {
		                	examineNeighbours(node, node.getX() - x1, node.getY() - y1, tileMap, unit, openList, closedList);
		                }
		            };
		            tasks.add(Executors.callable(runnable));
					
				}
			}
			
			/** Tasks werden abgearbeitet */
			try {
				executor.invokeAll(tasks);
			} catch (InterruptedException e) {
				Thread.currentThread().interrupt();
			}
			
			/** Hier muessen alle 8 Tasks abgearbeitet sein bevor es weitergeht */

		}
		
		return null;
	}

}
 
Zuletzt bearbeitet:

Marco13

Top Contributor
Das an sich sieht richtig aus... Ich bin nicht sicher, ob der Arbeitsaufwand für die einzelnen Tasks nicht zu gering ist ... soo viel wird in examineNeighbors ja nicht genaucht. Kann man da ein KSKB draus basteln, ggf. mit künstlich generierten Daten, oder ist das zu aufwändig?
(Hab' noch kurz überlegt, ob man wegen des teilweise hierarchischen Charakters da nicht mit einem ForkJoinPool was machen könnte, aber da müßte man genauer drüber nachdenken...)
 

ThreadPool

Bekanntes Mitglied
Für jeden offenen Knoten ein Heapsort durchzuführen ist nicht sehr ökonomisch. HS braucht IMHO auch im besten Fall n log n. Tauscht das mal gegen einen Java PriorityQueue aus oder einen einfachen binären Heap, dass Min/Max-Element (abhängig von der Heapart) ist konstant zu finden und entfernen kostet im Bereich log n.
 

Bile Demon

Bekanntes Mitglied
um viele, viele "pow(x,2)" (=x*x) [...] zu sparen...

Tut mir leid, weil es nicht ganz zum Thema passt, aber das wundert mich nun doch. Ich habe selbst immer Math.pow(x,2) und Math.pow(x,3) usw. aufgerufen anstelle von (x*x) und (x*x*x) etc. Ich habe das immer für guten Stil gehalten und schon allein deshalb verwendet.

Ab welchem Grad lohnt sich das denn, Math.pow aufzurufen anstatt den Term auszuschreiben?
 

Marco13

Top Contributor
Ab welchem Grad lohnt sich das denn, Math.pow aufzurufen anstatt den Term auszuschreiben?

Das ist eine gute Frage. (D.h. eine, die schwierig zu beantworten ist). Natürlich könnte man halb-subjektiv das "pow" irgendwie "schöner" finden (auch wenn ich speziell x*x da noch deutlich übersichtlicher finde), und in 99% der Fälle ist das sowieso vollkommen egal.

Ein nur in der Mittagspause schnell hingeschriebener Benchmark suggeriert, dass es wohl irgendwo zwischen einem Exponenten von 100 und 1000 effizienter wird, "pow" zu verwenden, aber das ist nur sehr begrenzt aussagekräftig - wie bei Microbenchmarks generell (obwohl ich das übliche "Microbenchmark-Pattern" verwendet habe), aber speziell in diesem Fall, weil die zu testende Operation eigentlich vernachlässigbar wenig Aufwand bedeutet, und der Compiler da natürlich SEHR leicht Optimiere kann, was das ganze ad absurdum führt...
Java:
import java.util.Arrays;


public class PowBench
{
    public static void main(String[] args)
    {
        for (int size=10000; size<=10000000; size*=10)
        {
            double input[] = new double[size];
            Arrays.fill(input, 2.0);
            
            runTest(input, POW_2);
            runTest(input, PRODUCT_2);
            runTest(input, POW_10);
            runTest(input, PRODUCT_10);
            runTest(input, POW_100);
            runTest(input, PRODUCT_100);
            runTest(input, POW_1000);
            runTest(input, PRODUCT_1000);
        }
    }
    
    
    interface Function
    {
        double compute(double value);
    }
    
    private static final Function POW_2 = new Function()
    {
        @Override
        public double compute(double value)
        {
            return Math.pow(value, 2);
        }
        
        @Override
        public String toString()
        {
            return "POW_2       ";
        }
    };

    private static final Function PRODUCT_2 = new Function()
    {
        @Override
        public double compute(double value)
        {
            return value * value;
        }

        @Override
        public String toString()
        {
            return "PRODUCT_2   ";
        }
    };
    
    
    private static final Function POW_10 = new Function()
    {
        @Override
        public double compute(double value)
        {
            return Math.pow(value, 10);
        }
        
        @Override
        public String toString()
        {
            return "POW_10      ";
        }
        
    };


    private static final Function PRODUCT_10 = new Function()
    {
        @Override
        public double compute(double value)
        {
            return 
                value * value * value * value * value * value * value * value * value * value;
        }
        
        @Override
        public String toString()
        {
            return "PRODUCT_10  ";
        }
        
        
    };
    
    
    private static final Function POW_100 = new Function()
    {
        @Override
        public double compute(double value)
        {
            return Math.pow(value, 100);
        }
        
        @Override
        public String toString()
        {
            return "POW_100     ";
        }
        
    };


    private static final Function PRODUCT_100 = new Function()
    {
        @Override
        public double compute(double value)
        {
            return 
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value;
        }
        
        @Override
        public String toString()
        {
            return "PRODUCT_100 ";
        }
        
        
    };
    
    private static final Function POW_1000 = new Function()
    {
        @Override
        public double compute(double value)
        {
            return Math.pow(value, 1000);
        }
        
        @Override
        public String toString()
        {
            return "POW_1000    ";
        }
        
    };


    private static final Function PRODUCT_1000 = new Function()
    {
        @Override
        public double compute(double value)
        {
            return 
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value *
                value * value * value * value * value * value * value * value * value * value
                ;
        }
        
        @Override
        public String toString()
        {
            return "PRODUCT_1000";
        }
        
        
    };
    
    
    
    private static void runTest(double input[], Function f)
    {
        long before = System.nanoTime();
        double result = compute(input, f);
        long after = System.nanoTime();
        System.out.println(
            "Using "+f+" for " + String.format("%12s", input.length)+
            " elements gives "+ String.format("%12s", result)+
            " duration "+(after-before)/1e6+" ms");
    }
    
    private static double compute(double input[], Function f)
    {
        double result = 0;
        for (int i=0; i<input.length; i++)
        {
            double value = input[i];
            result += f.compute(value);
        }
        return result;
    }
    
}


Pauschal kann man wohl sagen: Wenn es nur um den Exponenten 2 geht, ist x*x eigentlich immer schneller (und subjektiv besser, weil auch übersichtlicher). Bei höheren Exponenten ist es primär die Frage, wie wichtig einem Performance im Vergleich zu subjektiver Lesbarkeit ist. Ich fände sowas wie
Java:
double xPow5 = x * x * x * x * x;
computeWith(xPow5);
noch OK, auf jeden Fall ist so eine temporäre Variable IMHO ohnehin um Längen besser, als 120 Zeichen lange Zeilen wie
Java:
double a = Math.pow(b, 2) + Math.pow(c, 3) * Math.pow(b, 2) ...

Und wenn es um größere Exponenten ginge, wäre es wohl auch noch effizienter, die Binäre Exponentiation ? Wikipedia in einer eigenen Methode zu schreiben, statt Math.pow zu verwenden.

Aber, der Vollständigkeit halber: Das alles funktioniert natürlich nur für ganzzahlige Exponenten, und Math.pow ist ja nicht zuletzt für nicht-ganzzahlige gedacht...
 

Bile Demon

Bekanntes Mitglied
Wow, danke für die ausführliche Antwort.

Da empfehle ich doch glatt, deinen Beitrag in einen eigenen Blog-Beitrag zu dem Thema o.ä. zu integrieren. Ist jedenfalls viel zu schade für eine Randnotiz in einem Unterforum, die dann im Endeffekt von einer handvoll Personen gelesen wird, oder?

Gut zu wissen, dass ich Math.pow bislang falsch verwendet habe. Dann werde ich das doch besser künftig meiden.
 

Marco13

Top Contributor
Eine Liste mit bemerkenswert hilfreichen und außergewöhnlich wertvollen Beiträgen bekommt man über diese Suchanfrage :smoke:

:joke:

Ja, es geht gelegentlich schon was unter, aber speziell in diesem Fall nochmal die Betonung: Diesen Benchmark sollte man mit noch-etwas-mehr Skepsis betrachten, als andere Microbenchmarks. Die Quintessenz (x*x statt pow, und bei ganzzahligen Exponenten eine eigene Implementierung der binären Exponentiation in Erwägung zu ziehen) würde ich aber so stehen lassen.
 

Ähnliche Java Themen


Oben