CODEWITHSUNDEEP
javaalgorithm
Phantom
Phantom

Reputation: 443

Time Limit Exceeded in Java

The issue:

My program is taking too long when reading a very large input file, like n > 10000. It actually output all the result correctly but spent more than 30 minutes to calculate the last result...

I cannot find out where did I went wrong since there are no error message promoted from the Eclipse console, but I am assuming the problem maybe come from the method of calculating the distance, I am not sure what improvement I can do in my code and what kind of algorithm I should be used.

The purpose of the program:

Given n and the location of each store in term of latitude and longitude, and report the closest pair of stores and the distance between them.

My code for calculating the distance:

    private static void calculateDistances(){
    for (int i = 0; i < noOfStores; i++) {
        double[] distances = new double[noOfStores];
        for (int j = 0; j < noOfStores; j++) {
            if (i == j) {
                distances[j] = Double.POSITIVE_INFINITY;
            } else {
                distances[j] = distance(cities[i].getLatitude(), cities[i].getLongitude(), cities[j].getLatitude(), cities[j].getLongitude(), 'K');
            }
        }
        int minDistanceCity = findMin(distances);
        cities[i].setNearestCity(cities[minDistanceCity].getName());
        cities[i].setMinimumDistance(distances[minDistanceCity]);
    }
}

private static double distance(double lat1, double lon1, double lat2, double lon2, char unit) {
    double theta = lon1 - lon2;
    double dist = Math.sin(deg2rad(lat1)) * Math.sin(deg2rad(lat2)) + Math.cos(deg2rad(lat1)) * Math.cos(deg2rad(lat2)) * Math.cos(deg2rad(theta));
    if (dist > 1) {
        dist = 0;
        }
    else if (dist < -1) {
        dist = Math.PI;
        } else {
        dist = Math.acos(dist);
        }
    dist = rad2deg(dist);
    dist = dist * 60 * 1.1515;
    if (unit == 'K') {
        dist = dist * 1.609344;
        } else if (unit == 'N') {
            dist = dist * 0.8684;
            }
    return (dist);
    }

Upvotes: 0

Views: 606

Answers (1)

Aasmund Eldhuset
Aasmund Eldhuset

Reputation: 37950

Your nested loop will run for n2 iterations, so it will get four times slower each time the input size doubles. There exists an algorithm that uses only about n lg n operations.

Upvotes: 3

Related Questions