-1 
import java.io.*;
import java.util.ArrayList;

public class Ristsumma {
static long numberFromFile;
static long sum1, sum2;
static long number, number2;
static long variable, variable2;
static long counter;

public static void main(String args[]) throws IOException{
    try{
        BufferedReader br = new BufferedReader(new FileReader("ristsis.txt"));
        numberFromFile = Long.parseLong(br.readLine()); 

        br.close();
    }catch(Exception e){
    e.printStackTrace();
    }   

    variable=numberFromFile;
    ArrayList<Long> numbers = new ArrayList<Long>();

    while (variable > 0){
        number = variable %10;
        variable/=10;
        numbers.add(number);
    }

    for (int i=0; i< numbers.size(); i++) {
        sum1 += numbers.get(i);
    }

    ArrayList<Long> numbers2 = new ArrayList<Long>();
    for(long s=1; s<numberFromFile; s++){
        variable2=s;
        number2=0;
        sum2=0;

        while (variable2 > 0){
            number2 = variable2 %10;
            variable2/=10;  
            numbers2.add(number2);
        }

        for (int i=0; i< numbers2.size(); i++) {
            sum2 += numbers2.get(i);
        }

        if(sum1==sum2){
        counter+=1; 
        }

        numbers2.clear();
    }       
PrintWriter pw = new PrintWriter("ristval.txt", "UTF-8");
pw.println(counter);
pw.close();

}
}

所以我有这个代码。它从文件中获取一个数字，将所有数字与该数字分开相加，然后将它们相加（例如，数字是 123，则它给出 1+2+3=6）。在后半部分，它会查看文件中从 1 到该数字的所有数字，并计算有多少不同的数字给出相同的答案。如果数字是 123，总和是 6，代码写出的答案是 9（因为 6、15、24、33、42、51、60、105、114 也给出了相同的答案）。该代码有效，但我的问题是，当文件中的数字例如为 2 222 222 222 时，需要将近半个小时才能得到答案。我怎样才能让它运行得更快？

4

4 回答 4

3

删除不必要的列表创建

您不必要地创建列表

ArrayList<Long> numbers = new ArrayList<Long>();

while (variable > 0){
    number = variable %10;
    variable/=10;
    numbers.add(number);
}

for (int i=0; i< numbers.size(); i++) {
    sum1 += numbers.get(i);
}

这里你创建一个arraylist，只是为了暂时持有Longs，可以消除整个list

while (variable > 0){
    number = variable %10;
    variable/=10;
    sum1 += number
}

其他arraylist numbers2 相同

预选收货人

我们已经消除了数组列表，但如果我们没有，我们可以通过调整数组的大小来提高速度

ArrayList<Long> numbers = new ArrayList<Long>(someGuessAsToSize);

您的猜测是否正确并不重要，arraylist 仍会自动调整大小，但如果猜测大致正确，您将加快代码速度，因为 arraylist 不必定期调整大小。

一般风格

你持有很多（应该是什么）方法变量作为字段

static long numberFromFile;
static long sum1, sum2;
static long number, number2;
static long variable, variable2;
static long counter;

这不太可能影响性能，但这是一件不寻常的事情，并且会降低代码的可读性，并可能产生“隐藏效应”

于 2013-11-12T15:02:42.527 回答
2

你的问题很有趣——它让我想知道它会用线程运行多快。

这是一个线程实现，它将计算第二个问题的任务跨线程拆分。我的笔记本电脑只有两个内核，所以我将线程设置为 4。

public static void main(String[] args) throws Exception {
    final long in = 222222222;
    final long target = calcSum(in);
    final ExecutorService executorService = Executors.newFixedThreadPool(4);
    final Collection<Future<Integer>> futures = Lists.newLinkedList();
    final int chunk = 100;
    for (long i = in; i > 0; i -= chunk) {
        futures.add(executorService.submit(new Counter(i > chunk ? i - chunk : 0, i, target)));
    }
    long res = 0;
    for (final Future<Integer> f : futures) {
        res += f.get();
    }
    System.out.println(res);
    executorService.shutdown();
    executorService.awaitTermination(1, TimeUnit.DAYS);
}

public static final class Counter implements Callable<Integer> {

    private final long start;
    private final long end;
    private final long target;

    public Counter(long start, long end, long target) {
        this.start = start;
        this.end = end;
        this.target = target;
    }

    @Override
    public Integer call() throws Exception {
        int count = 0;
        for (long i = start; i < end; ++i) {
            if (calcSum(i) == target) {
                ++count;
            }
        }
        return count;
    }
}

public static long calcSum(long num) {
    long sum = 0;
    while (num > 0) {
        sum += num % 10;
        num /= 10;
    }
    return sum;
}

222 222 222它会在几秒钟内计算出解决方案作为输入。

我优化了 s 的计算sum以删除List您正在使用的所有 s。

编辑

我添加了一些计时代码，Stopwatch并尝试使用和不使用@Ingo 的优化222222222 * 100作为输入数字。

如果没有优化，代码需要 35 秒。将 calc 方法更改为：

public static long calcSum(long num, final long limit) {
    long sum = 0;
    while (num > 0) {
        sum += num % 10;
        if (limit > 0 && sum > limit) {
            break;
        }
        num /= 10;
    }
    return sum;
}

添加优化后，代码需要 28 秒。

请注意，这是一个高度非科学的基准测试，因为我没有预热 JIT 或运行多次试验（部分是因为我很懒，部分是因为我很忙）。

编辑

摆弄块大小也会产生相当不同的结果。用 1000 次的时间块下降到 17 秒左右。

编辑

如果您想真正花哨，可以使用ForkJoinPool：

public static void main(String[] args) throws Exception {
    final long in = 222222222;
    final long target = calcSum(in);
    final ForkJoinPool forkJoinPool = new ForkJoinPool();
    final ForkJoinTask<Integer> result = forkJoinPool.submit(new Counter(0, in, target));
    System.out.println(result.get());
    forkJoinPool.shutdown();
    forkJoinPool.awaitTermination(1, TimeUnit.DAYS);
}

public static final class Counter extends RecursiveTask<Integer> {

    private static final long THRESHOLD = 1000;
    private final long start;
    private final long end;
    private final long target;

    public Counter(long start, long end, long target) {
        this.start = start;
        this.end = end;
        this.target = target;
    }

    @Override
    protected Integer compute() {
        if (end - start < 1000) {
            return computeDirectly();
        }
        long mid = start + (end - start) / 2;
        final Counter low = new Counter(start, mid, target);
        final Counter high = new Counter(mid, end, target);
        low.fork();
        final int highResult = high.compute();
        final int lowResult = low.join();
        return highResult + lowResult;
    }

    private Integer computeDirectly() {
        int count = 0;
        for (long i = start; i < end; ++i) {
            if (calcSum(i) == target) {
                ++count;
            }
        }
        return count;
    }
}

public static long calcSum(long num) {
    long sum = 0;
    while (num > 0) {
        sum += num % 10;
        num /= 10;
    }
    return sum;
}

在另一台（速度更快）的计算机上，它的运行时间不到一秒，而原始方法的运行时间为 2.8 秒。

于 2013-11-12T15:08:00.430 回答
1

请注意，您根本不需要存储单个数字。

相反，您感兴趣的只是数字的实际总和。

考虑到这一点，类似的方法

static int diagsum(long number)  { ... }

会很好。如果它很容易，JIT 可以内联它，或者至少比你的意大利面条代码优化得更好。

再说一次，您可以从另一种在某个限制处停止计算数字总和的方法中受益。例如，当你有

22222222

总和是 20，这意味着您不需要计算任何其他大于 20 的总和。例如：

45678993

相反，您可以在获得最后 3 位数字（通过您的 diision 方法首先获得）后停止，因为 9+9+3 是 21，而这已经大于 20。

==================================================== ==================

另一个优化：

如果你有一些号码：

123116

很明显，这 6 个数字的所有唯一排列具有相同的数字和，因此

321611, 231611, ... are solutions

然后，对于任何一对单独的数字 ab，一个转换后的数字将在同一位置包含 (a+1)(b-1) 和 (a-1)(b+1)，只要 a+1, .. . 仍在 0..9 范围内。递归应用以获得更多数字。

然后，您可以转向位数较少的数字。显然，要获得相同的数字和，您必须结合原始数字的 2 位数字，如果可能的话，例如

5412 => 912, 642, 741, 552, 561, 543

等等。递归地应用与上面相同的算法，直到不可能进行任何转换和组合。

=========

不过，必须说，上述想法会占用大量内存，因为必须维护一个类似 Set 的数据结构来处理重复项。但是，对于 987_654_321，我们已经得到了 39_541_589 个结果，并且可能更多，甚至更多。因此，以组合方式实际进行的努力是否值得值得怀疑。

于 2013-11-12T15:05:12.460 回答
1

您大部分时间都在检查未通过测试的数字。然而，正如 Ingo 所观察到的，如果你有一个数字 ab，那么 (a-1)(b+1) 的和与 ab 相同。您可以生成它们，而不是检查所有数字：

假设我们的数字是 2 222，总和是 8。方法 #1：自下而上

我们现在生成从最小开始的数字（为了阅读方便，我们用零填充）：0008。下一个是 0017，下一个是 0026、0035、0044、0053、0062、0071、0080、0107 等等。有问题的部分是找到具有此总和的第一个数字。

方法二：自上而下

我们从 2222 开始，下一个较低的数字是 2213，然后是 2204、2150、2141，依此类推。在这里，您没有需要找到最小数字的问题。

我现在没有时间写代码，但是应该有一个算法来实现这两种方法，而不涉及尝试所有的数字。

对于数字 abc，(a)(b-1)(c+1) 是下一个较小的数字，而 (a)(b+1)(c-1) 是下一个较大的数字。唯一有趣/困难的事情是当您需要溢出时，因为 b==9 或 c==9，或 b==0，c==0。如果 b==9，下一个更大的数字是 (a+1)(9)(c-1)，如果 c>0，以及 (a)(8)(0)，如果 c==0。现在去做你的算法，这些例子应该足够了。

于 2013-11-12T16:36:42.887 回答