1

我写了一个程序来解决丢番图方程的形式

A 5 + B 5 + C 5 + D 5 + E 5 = 0；

它应该在 N 3 long(N) 时间内运行，但输入大小为 100 通常需要大约 10 分钟。谁能告诉我有什么问题吗？

public class EquationSolver {

//Solves Equations of type: A^5 + B^5 + C^5 + D^5 + E^5 = F^5

public static void main(String[] args) {
    Scanner input = new Scanner(System.in);
    System.out.println("Enter a max value: ");
    int N = input.nextInt();
    long START_TIME = System.nanoTime();
    SLinkedList test = new SLinkedList();
    SLinkedList test2 = new SLinkedList();
    test = setupLeftList(N);
    test2 = setupRightList(N);
    System.out.println("Note: This program takes about 7 minutes to complete for input of 100");
    test = mergeSort(test);
    test2 = mergeSort(test2);
    long END_TIME2 = System.nanoTime() - START_TIME;
    System.out.println("Total Time:" + END_TIME2/1000000000.0);
    checkEquality(test, test2);
    long END_TIME3 = System.nanoTime() - START_TIME;
    System.out.println("Total Time:" + END_TIME3/1000000000.0);

}


public static SLinkedList setupLeftList(long boundary)
{
    //Creates and returns an linkedList of all possible A,B,C values and their sums
    SLinkedList leftSums = new SLinkedList();
    for(long c = 0; c < boundary; c++)
    {
        for(long b = 0; b < c; b++)
        {
            for(long a = 0; a < b; a++)
            {
                    long sum = (long)(Math.pow(a+1,5)) + (long)(Math.pow(b+1, 5)) + (int)(Math.pow(c+1, 5));
                    Node current = new Node (sum, a+1, b+1, c+1, null);
                    //System.out.println(sum);
                    leftSums.addLast(current);
            }
        }
    }
    return leftSums;
}
public static SLinkedList setupRightList(long boundary)
{
    //Creates and returns an linkedList of all possible D,E,F values and their sums
    SLinkedList rightSums = new SLinkedList();
    for(int f = 0; f < boundary; f++)
    {
        for(int e = 0; e < f; e++)
        {
            for(int d = 0; d < e; d++)
            {   
                long sum = (long)(Math.pow(f+1, 5)) - ((long)(Math.pow(d+1, 5)) + (long)(Math.pow(e+1,5)));

                    Node current = new Node (sum, d+1, e+1, f+1, null);
                    //System.out.println(current.getSum());
                    rightSums.addLast(current); 

            }
        }
    }
    return rightSums;
}

public static SLinkedList mergeSort(SLinkedList sums)
// Sorts each list by the value of the sum
{

    if (sums.length() > 1 )
    {

    SLinkedList[] splitList = split(sums);
    SLinkedList s1 = mergeSort(splitList[0]);
    SLinkedList s2 = mergeSort(splitList[1]);
    sums = merge(s1, s2);

    }
    return sums;
}

public static SLinkedList[] split(SLinkedList sums)
{
    // Splits a linked list into two (somewhat) equal halves
    long midpoint = sums.length()/2;

    Node midPoint = sums.elementAt(midpoint); 

    SLinkedList s1 = new SLinkedList(sums.head, midPoint, midpoint);
    SLinkedList s2 = new SLinkedList(midPoint, sums.tail, midpoint);
    SLinkedList[] both = new SLinkedList[]{s1, s2};
    return both;
}

public static SLinkedList merge(SLinkedList s1, SLinkedList s2)
{
    // Merges two sorted lists of elements
    SLinkedList sMerged = new SLinkedList();
    while(!s1.isEmpty() && !s2.isEmpty())
    {
        if (s1.getFirst().getSum() < s2.getFirst().getSum())
        {
            sMerged.addLast(s1.removeFirst());
        }
        else
        {
            sMerged.addLast(s2.removeFirst());
        }
    }
    while(!s1.isEmpty())
    {
        sMerged.addLast(s1.removeFirst());
    }
    while(!s2.isEmpty())
    {
        sMerged.addLast(s2.removeFirst());
    }
    return sMerged;
}

public static void checkEquality(SLinkedList left, SLinkedList right)
{
    // Checks two linked lists for nodes that contain the same Sum value
    boolean ans = false;
    while (left.isEmpty() == false && right.isEmpty() == false)
    {
        long currentLeft = left.getFirst().getSum();
        long currentRight = right.getFirst().getSum();
        if (currentLeft > currentRight)
        {
            right.removeFirst();
        }
        else if(currentLeft < currentRight)
        {
            left.removeFirst();
        }
        else
        {
            if (left.getFirst().getC() <= right.getFirst().getA())
            {
                System.out.println("Answer Found: " + "A: " + left.getFirst().getA() + " B: " + left.getFirst().getB() + " C: " 
                    + left.getFirst().getC() + " D: " + right.getFirst().getA() + " E: " + right.getFirst().getB() + " F: " + right.getFirst().getC());
                ans = true;
            }

            Node temp = left.getFirst().getNext();

            while (temp.getSum() == currentRight)
            {
                if (temp.getC() <= right.getFirst().getA())
                {
                    System.out.println("Answer Found: " + "A: " + left.getFirst().getA() + " B: " + left.getFirst().getB() + " C: " 
                        + left.getFirst().getC() + " D: " + right.getFirst().getA() + " E: " + right.getFirst().getB() + " F: " + right.getFirst().getC());
                    ans = true;

                }
                temp = temp.getNext();

            }

            right.removeFirst();
            left.removeFirst();

        }
    }
    if (ans == false)
    {
        System.out.println("No answer found.");
    }

}

}

4

1 回答 1

2

明确的答案是：使用分析器并查看导致瓶颈的原因......

但是我看到您有Math.pow()调用，所有调用都带有 long 和它们的 5 次方。

你可以做得更快，甚至检测到溢出：

public static long pow5(long base) {
  if(base <=6208 && base >=-6208) {
    return base*base*base*base*base;
  } else {
    throw new IllegalArgumentException("Overflow!");
  }
}

（幻数免责声明： 6208 5是 ~2 63，是一个大于那个的数字，5 次方不适合 64 位......）

Math.pow 使用双精度数，这本身意味着很多转换......

此外，@Floris指出，它甚至不值得一遍又一遍地计算 - 它可以放入一个不错的数组中，然后索引它

public static long[] pow5 = getPow5(100);

public static long[] getPow5(long numElements) {
    long[] toReturn = new long[numElements];

    for(long i=0;long<numElements;long++) {
        toReturn[i] = i*i*i*i*i;
    }
    return toReturn;
}

在需要的地方，而不是Math.pow(x, 5)仅仅使用pow5[x]

于 2013-10-04T20:04:29.937 回答