I am writing an app that finds prime numbers within a specified range. Currently i am updating almost every part of the app and i have also changed the way i find prime numbers. The problem is that the new method seems to be much slower. As a test, the old method takes only 8 seconds to find all the primes from 0 - 100,000. The same task takes the new method between 25 - 30 seconds to complete. I'm not sure why the new method is so much slower. Is there anything i can do to make the new method faster, or at least comparable to the old method, while still keeping the functionality (like the ability to pause it).
Since the code is quite long i have posted links to them as well.
Old Method Full class
public class PrimeFinderThread implements Runnable{
//Flow control booleans
public boolean threadRunning = false;
public boolean scanningNumbers = false;
public boolean stoppedScanning = true;
public boolean threadStopped = true;
//Current number being scanned
public long currentNumber = 2;
//Scan progress of current number
public double currentNumberProgress = 0;
//List of all found prime numbers
public List<Long> primeNumbers = new ArrayList<>();
//Buffer for numbers per second
public List<Double> numbersPerSecondArray = new ArrayList<>();
//Times for elapsed time calculation
public long scanStartTime = 0;
public long threadStartTime = 0;
public long pausedTime = 0;
public long elapsedTime = 0;
public long lastUpdateTime = 0;
public long loopStartTime = 0;
public long loopEndTime = 0;
public long lastOneSecondUpdateTime;
//Maximum number to check when scanning for primes
private double sqrtMax = 0;
//Numbers scanned per second
public int numbersPerSecond = 0;
public int numbersSinceLastSecond = 0;
//Prime numbers found per second
public int primesPerSecond = 0;
public int primesSinceLastSecond = 0;
@Override
public void run(){
while (threadRunning){
threadStopped = false;
scanningNumbersLoop: while (scanningNumbers){
stoppedScanning = false;
loopStartTime = System.nanoTime();
currentNumberProgress = 0;
boolean isPrime = true;
sqrtMax = Math.round(Math.sqrt(currentNumber));
for (int i = 2; i <= sqrtMax; i++){
doUpdates(i);
//Check if number is prime
double actualNumber = (double) currentNumber / i;
double roundedNumber = Math.round(actualNumber);
//Number is not prime, break out of the loop
if (actualNumber == roundedNumber){
isPrime = false;
break;
}
if (!threadRunning | !scanningNumbers){
break scanningNumbersLoop;
}
}
//Number is prime, add it to the list
if (isPrime){
primeNumbers.add(currentNumber);
primesSinceLastSecond++;
}
//Stop thread if end value was reached
if (currentNumber == ScanForPrimesFragment.endValue){
scanningNumbers = false;
currentNumberProgress = 100;
sendUpdateMessage("endValueReached");
break;
}
//Increase variables
currentNumber++;
numbersSinceLastSecond++;
loopEndTime = System.nanoTime();
}
//Thread has stopped scanning for prime numbers
stoppedScanning = true;
}
//Thread has stopped completely
threadStopped = true;
}
/**
* Called every few milliseconds to update elapsed time and other stats
* @param i Current iteration of the loop
*/
private void doUpdates(int i){
//Update current number progress
currentNumberProgress = (i / sqrtMax) * 100;
//Update the time elapsed
elapsedTime = System.currentTimeMillis() - scanStartTime;
//Update every second
if (System.currentTimeMillis() - lastOneSecondUpdateTime >= 1000){
numbersPerSecond = numbersSinceLastSecond;
numbersSinceLastSecond = 0;
primesPerSecond = primesSinceLastSecond;
primesSinceLastSecond = 0;
lastOneSecondUpdateTime = System.currentTimeMillis();
}
//Update ui
if (System.currentTimeMillis() - lastUpdateTime >= PrimeNumberFinder.UPDATE_LIMIT_MS){
lastUpdateTime = System.currentTimeMillis();
sendUpdateMessage(null);
}
}
/**
* Send a message to the handler telling the ui to update
*/
private void sendUpdateMessage(String msgData){
Message message = ScanForPrimesFragment.handler.obtainMessage();
Bundle bundle = new Bundle();
bundle.putString("currentNumber", String.valueOf(currentNumber));
bundle.putString("msgData", msgData);
message.setData(bundle);
ScanForPrimesFragment.handler.sendMessage(message);
}
}
New Method Full class
public class FindPrimesTask extends Task{
/**
* Tag used for logging and debugging.
*/
private static final String TAG = "FindPrimesTask";
/**
* List of all prime numbers found.
*/
private final List<Long> primeNumbers = new ArrayList<>();
/**
* Start and end values. The end value can be modified after the task has started if the user
* pauses it first. If the end value is set to {@link #LIMIT_NO_LIMIT}, then the task will run
* forever until stopped by the user or interrupted.
*/
private final long startValue;
private long endValue;
/**
* If the end value is set to this, then the runnable will run forever until stopped by the
* user or interrupted.
*/
public static final int LIMIT_NO_LIMIT = -1;
/**
* The current number we are checking.
*/
private long currentNumber;
/**
* The search progress on the current number as a decimal between 0 and 1.
*/
private float currentProgress = 0;
private long totalCheckTime;
private int numbersChecked;
private final List<EventListener> eventListeners = new ArrayList<>();
private long[] lastUpdateTimes = new long[2];
Map<Long, Long> map;
Map<Long, Long> primesMap;
/**
* Create a new {@link FindPrimesTask} to search for prime numbers within a given range.
*
* @param startValue The beginning of the search range.
* @param endValue The end of the search range.
*/
public FindPrimesTask(final long startValue, final long endValue){
this.startValue = startValue;
this.endValue = endValue;
map = ExpiringMap.builder().expiration(1000, TimeUnit.MILLISECONDS).build();
primesMap = ExpiringMap.builder().expiration(1000, TimeUnit.MILLISECONDS).build();
}
@Override
public void run(){
//The task has started
dispatchStarted();
/**
* Set the current number to the start value. If the start value is less then 2, then set
* it to 2 because that is the lowest prime number.
*/
if (startValue < 3){
if (endValue >= 2){
sendOnPrimeFound(2);
}
currentNumber = 3;
}else{
currentNumber = startValue;
}
int sqrtMax;
boolean isPrime;
boolean running = true;
//Loop forever
while (running){
//Check if the end value has been reached
if (endValue == LIMIT_NO_LIMIT || currentNumber <= endValue){
//Check if the number is divisible by 2
if (currentNumber % 2 != 0){
/**
* Get the square root of the number. We only need to calculate up to the square
* root to determine if the number is prime. The square root of a long will
* always fit inside the value range of an int.
*/
sqrtMax = (int) Math.sqrt(currentNumber);
//Assume the number is prime
isPrime = true;
final long checkStartTime = System.nanoTime();
/**
* Check if the number is divisible by every odd number below it's square root.
*/
for (int i = 3; i <= sqrtMax; i += 2){
//Check if the number divides perfectly
if (currentNumber % i == 0){
isPrime = false;
break;
}
//Calculate current progress
currentProgress = (float) i / sqrtMax;
sendOnProgressChanged(currentProgress);
//Check if we should pause
tryPause();
if (shouldStop()){
running = false;
break;
}
}
numbersChecked++;
totalCheckTime += (System.nanoTime() - checkStartTime);
//Check if the number was prime
if (isPrime){
synchronized (LOCK){
primeNumbers.add(currentNumber);
//primesMap.put(currentNumber, currentNumber);
}
sendOnPrimeFound(currentNumber);
}
}
//Increase currentNumber
currentNumber++;
//map.put(currentNumber, currentNumber);
//Calculate total progress
if (endValue != LIMIT_NO_LIMIT){
setProgress((float) (currentNumber - startValue) / (endValue - startValue));
}
}else{
currentNumber = endValue;
currentProgress = 1f;
setProgress(1);
//isRunning = false;
break;
}
}
dispatchStopped();
//The task has finished
if (currentNumber == endValue){
dispatchFinished();
}
}
public long getAverageCheckTime(){
return (totalCheckTime - getTotalPauseTime()) / numbersChecked;
}
public void setEndValue(long endValue){
this.endValue = endValue;
}
public float getCurrentProgress(){
return currentProgress;
}
public long getCurrentNumber(){
return currentNumber;
}
public long getEndValue(){
return endValue;
}
public long getStartValue(){
return startValue;
}
public long getNumbersPerSecond(){
return map.size();
}
public long getPrimesPerSecond(){
return primesMap.size();
}
public void addEventListener(final EventListener eventListener){
if (!eventListeners.contains(eventListener)) eventListeners.add(eventListener);
}
public interface EventListener{
void onPrimeFound(final long prime);
}
private void sendOnPrimeFound(final long prime){
for (EventListener eventListener : eventListeners){
eventListener.onPrimeFound(prime);
}
}
}
The new method extends from Task, which is just a simple class extending from Thread
Task Full class
public abstract class Task implements Runnable{
/**
* Tag used for logging and debugging.
*/
private static final String TAG = "Task";
/**
* Listeners for task events.
*/
private final List<TaskListener> taskListeners = new ArrayList<>();
/**
* Possible task states.
*/
public enum State{
NOT_STARTED,
RUNNING,
PAUSED,
STOPPED,
FINISHED
}
/**
* Current task state.
*/
private State state = State.NOT_STARTED;
/**
* Total task progress. If ongoing task, progress will remain at 0.
*/
private float progress = 0f;
/**
* Keep track of when the task was started and paused. These values are also used to calculate
* the elapsed time.
*/
private long startTime;
private long lastPauseTime;
private long totalPauseTime;
/**
* Lock used to pause the current thread when the task is paused.
*/
protected final Object LOCK = new Object();
private boolean requestPause = false;
private boolean requestStop = false;
//Override methods
@Override
public abstract void run();
//Utility methods
protected void tryPause(){
if (requestPause){
synchronized (LOCK){
try{
//Pause
dispatchPaused();
Log.e(TAG, "Time elapsed pause: " + getTimeElapsed());
sendOnTaskPaused();
//Wait until notified to resume
LOCK.wait();
//Resume
dispatchResumed();
}catch (InterruptedException e){
if (PrimeNumberFinder.DEBUG)
Log.e(TAG, "Task was interrupted while paused!");
}
}
}
}
protected boolean shouldStop(){
return requestStop;
}
//Lifecycle methods
public void start(){
run();
}
protected void dispatchStarted(){
this.startTime = System.currentTimeMillis();
setState(State.RUNNING);
sendOnTaskStarted();
}
public void pause(){
requestPause = true;
}
private void dispatchPaused(){
requestPause = false;
lastPauseTime = System.currentTimeMillis();
setState(State.PAUSED);
}
public void resume(){
synchronized (LOCK){
LOCK.notify();
}
}
private void dispatchResumed(){
totalPauseTime += (System.currentTimeMillis() - lastPauseTime);
setState(State.RUNNING);
sendOnTaskResumed();
}
protected void dispatchStopped(){
setState(State.STOPPED);
}
protected void dispatchFinished(){
setState(State.FINISHED);
}
public void stop(){
requestStop = true;
}
//Getters and setters
public void addTaskListener(final TaskListener taskListener){
if (!taskListeners.contains(taskListener)) taskListeners.add(taskListener);
}
public long getTimeElapsed(){
if (startTime == 0){
return 0;
}
return System.currentTimeMillis() - startTime - totalPauseTime;
}
public float getProgress(){
return progress;
}
public void setProgress(float progress){
this.progress = progress;
}
public State getState(){
return state;
}
private void setState(State state){
this.state = state;
switch (state){
case PAUSED:
sendOnTaskPaused();
break;
case STOPPED:
sendOnTaskStopped();
break;
case FINISHED:
sendOnTaskFinished();
break;
}
}
protected long getTotalPauseTime(){
return totalPauseTime;
}
//Callbacks
private void sendOnTaskStopped(){
for (TaskListener taskListener : taskListeners){
taskListener.onTaskStopped();
}
}
private void sendOnTaskStarted(){
for (TaskListener taskListener : taskListeners){
taskListener.onTaskStarted();
}
}
private void sendOnTaskPaused(){
for (TaskListener taskListener : taskListeners){
taskListener.onTaskPaused();
}
}
private void sendOnTaskResumed(){
for (TaskListener taskListener : taskListeners){
taskListener.onTaskResumed();
}
}
private void sendOnTaskFinished(){
for (TaskListener taskListener : taskListeners){
taskListener.onTaskFinished();
}
}
protected void sendOnProgressChanged(final float percent){
for (TaskListener taskListener : taskListeners){
taskListener.onProgressChanged(percent);
}
}
}
import java.util.ArrayList;,import java.util.List;etc. Then, make sure all dependencies are included. For example, what isScanForPrimesFragment? Where is it defined? \$\endgroup\$sendOnProgressChanged()was taking a relatively long time, considering it is called every iteration. Removing that helped the performance, but I think i might take your suggestion and implement the sieve. Thanks for the help! \$\endgroup\$