java - 固定线程池和大量任务的线程问题

Question

我正在使用一个程序来运行数学中的 Collat​​z 猜想 (http://en.wikipedia.org/wiki/Collatz_conjecture)。我已经实现了一个运行猜想算法(并返回输出)的类和一个创建固定线程池(我的处理器数量:8)并接受 Callable 的类。 s 是对猜想算法的调用。

我创建了一个 HashSet<Callable>对于 1(输入类型必须是正整数)和 400,000 之间的所有数字。这(似乎)永远挂起，但较低的数字很好，这很奇怪。更奇怪的是，运行它处理这些调用所花费的时间似乎比用单个线程处理相同数量的信息所花费的时间要长；它还会显着增加内存。

例如，在我的计算机上，程序用 400,000(最终值)执行算法(仅一次迭代)需要不到一秒钟的时间，并且所有较低的值都需要更少的时间来计算(可能除了素数，这需要更长的时间)我正在运行 Windows 8.1，内存为 8GB，逻辑处理器频率为 8 个 2.2Ghz。

代码:

private static void initThreads() throws InterruptedException {
    //Files.createDirectories(SEQUENCER_FOLDER_PATH);
    //Files.createFile(SEQUENCER_FILE_PATH);
    ExecutorService service = Executors.newFixedThreadPool(8, new ThreadFactory() {
        private BigInteger count = BigInteger.ZERO;

        @Override
        public Thread newThread(Runnable r) {
            count = count.add(BigInteger.ONE);
            return new Thread(r, "Collatz Sequencer Thread: " + count);
        }
    });
    int finalNumber = 400_000;
    final HashSet<Callable<Void>> tasks = new HashSet<>(finalNumber);
    for (long l = 1; l <= finalNumber; l++) {
        final BigInteger number = BigInteger.valueOf(l);
        tasks.add(() -> {
            CollatzSequencer sequencer = new CollatzSequencer(new BigInteger(number.toString()));
            synchronized (dataSet) {
                dataSet.put(number, sequencer.init());
            }
            return null;
        });
    }
    service.invokeAll(tasks);
    Thread dataThread = new Thread(() -> {
        while (true) {
            synchronized (dataSet) {
                if (dataSet.size() == finalNumber) {
                    System.err.println("Values: \n");
                    for (CollatzSequencer.FinalSequencerReport data : dataSet.values()) {
                        System.err.println("Entry: " + data.getInitialValue() + ", " + data.getIterations());
                    }
                    System.exit(0);
                }
            }
        }
    }, "Collatz Conjecture Data Set Thread");
    dataThread.start();
}

Collat​​z 猜想算法:

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package com.collatzsequencer.core;

import java.math.BigInteger;

/**
 * A sequencer used for computing the collatz sequence.
 *
 * @author Sarah Szabo
 * @version 1.0
 */
public class CollatzSequencer {

private final BigInteger initialValue;

public CollatzSequencer(BigInteger currentValue) {
    if (currentValue == null) {
        throw new NullPointerException("Value passed can't be null");
    } else if (currentValue.compareTo(new BigInteger("1")) < 0) {
        throw new NumberFormatException("The value passed to the constructor must be a natural number.");
    }
    this.initialValue = currentValue;
}

public FinalSequencerReport init() {
    return new FinalSequencerReport(performOperation(new SequencerReport(this.initialValue)), this.initialValue);
}

private SequencerReport performOperation(SequencerReport report) {
    if (report.getResult().equals(new BigInteger("1"))) {
        return new SequencerReport(report.getResult(), report.getIterations(), report.getSequence().length() > 1
                ? report.getSequence().substring(0, report.getSequence().length() - 3) : "The sequence starts and ends at 1 <Nothing Done>");
    } else if (report.getResult().mod(new BigInteger("2")).equals(new BigInteger("0"))) {
        BigInteger value = report.getResult().divide(new BigInteger("2"));
        return performOperation(new SequencerReport(value, report.getIterations().add(new BigInteger("1")),
                report.getSequence() + " " + report.getResult() + "/2 -> " + value + " ->"));
    } else {
        BigInteger value = report.getResult().multiply(new BigInteger("3")).add(new BigInteger("1"));
        return performOperation(new SequencerReport(value, report.getIterations()
                .add(new BigInteger("1")), report.getSequence() + report.getResult() + " * 3 + 1 ->" + value + " ->"));
    }
}

public static final class FinalSequencerReport extends SequencerReport {

    private final BigInteger initialValue;
    private final String finalFormattedString;

    public FinalSequencerReport(SequencerReport finalReport, BigInteger initialValue) {
        super(finalReport.getResult(), finalReport.getIterations(), finalReport.getSequence());
        this.initialValue = initialValue;
        this.finalFormattedString = "Initial Value: "
                + getInitialValue() + "\nFinal Value: " + getResult() + "\nIterations:  "
                + getIterations() + "\nAlgebraic Sequence:\n" + getSequence();
    }

    public String getFinalFormattedString() {
        return finalFormattedString;
    }

    public BigInteger getInitialValue() {
        return initialValue;
    }
}

public static class SequencerReport {

    private final BigInteger result, iterations;
    private final String sequence;

    public SequencerReport(BigInteger result) {
        this(result, new BigInteger("0"), "");
    }

    public SequencerReport(BigInteger result, BigInteger iterations, String sequence) {
        this.result = result;
        this.iterations = iterations;
        this.sequence = sequence;
    }

    public BigInteger getResult() {
        return this.result;
    }

    public BigInteger getIterations() {
        return this.iterations;
    }

    public String getSequence() {
        return this.sequence;
    }

  }
}

Answer 1

如您所说，您的代码有效；问题可能只是性能。我会尝试的一些事情:

1. 使用 long 而不是 BigInteger。 BigInteger 非常慢。
2. 代替mod 2(或% 2)，使用 & 1。二进制 AND 的结果实际上相同，而且速度更快。
3. 您对 String 的操作太多了。覆盖 sequencerReport.toString() 并让它在您打印数据时执行所有 toString 调用。
4. 不要执行 new ThreadFactory()。使用 Guava's ThreadFactoryBuilder .
   • 永远不要在代码中调用 new Thread()，除非您真的知道自己在做什么，这意味着不要这样做。
5. 为 dataThread 添加等待/通知机制，而不是忙循环。工作完成后调用 dataSet.notify() 并在 dataThread 主体内调用 dataSet.wait()。