使用java中的多线程基础知识查找[1，n]范围内所有可被3，5或7整除的整数的和

niknxzdl  于 2023-05-05  发布在  Java
关注(0)|答案(6)|浏览(143)

问题解释：你必须写一个多线程程序来查找范围[1，n]中所有能被3，5或7整除的整数。返回所有唯一整数的和作为答案。注意，诸如15（其是3和5的倍数）的整数仅计数一次。正整数n〉0作为输入。创建尽可能多的线程来解决问题。您可以使用线程池获得奖励积分。

Example:
Input: n = 10
Output: sum = 40
Explanation: Numbers in the range [1, 10] that are divisible by 3, 5, or 7 are:
3, 5, 6, 7, 9, 10. The sum of these numbers is 40.

我遇到的问题和问题：在这个程序中，我创建了三个线程，每个线程分别查找被3，5和7整除的整数，然后将它们全部存储在被除数数组列表中，并通过以下代码删除数组列表中重复的整数：

Set<Integer> set = new HashSet<>(dividends);
    dividends.clear();
    dividends.addAll(set);

我使用了我们老师提供的一些测试用例，问题是在测试用例中，n=1000和n=76293的总和不会显示预期的数量：

n=1000
expected sum:272066
actual sum:247377

另一个问题是，每次运行测试用例时，实际的和都在变化。谁能告诉我我的代码有什么问题，我该如何修复它
我的代码：

import java.util.*;
public class FindMultiples
{

public static ArrayList<Integer> dividends = new ArrayList<>();
public static int temp = 0;
public static synchronized void increment(){
    dividends.add(temp);
}
public static class thread implements Runnable{

    public int divisor;
    public int n;

    public thread(int n , int divisor){
        this.n=n;
        this.divisor=divisor;
    }

    @Override
    public void run() {

        for (int i=1 ; i<=n ; i++){
            if (i%divisor==0){
                temp=i;
                increment();
            }
        }
    }
}

public int getSum(int n) {
    int sum = 0;
    Thread thread1 = new Thread(new thread(n,3));
    Thread thread2 = new Thread(new thread(n,7));
    Thread thread3 = new Thread(new thread(n,5));
    
    thread3.start();
    thread2.start();
    thread1.start();
    try {
        thread3.join();
        thread2.join();
        thread1.join();
    }catch (InterruptedException e){

    }
    Set<Integer> set = new HashSet<>(dividends);
    dividends.clear();
    dividends.addAll(set);

    for (int i : dividends){
        sum+=i;
    }

    return sum;
}

public static void main(String[] args) {
}
}
Java

6条答案

按热度按时间
mwngjboj

mwngjboj1#

好吧，我相信下面的解决方案是最优的，因为它只是一个算术公式：

BiFunction<Integer, Integer, Long> sumDivInRange = (to, div) -> {
    int first = (1 / div) * div;
    int last = (to / div) * div;

    return ((long) first + last) * ((last - first) / div + 1) / 2;
};

int n = 100000000;

// not sure we need parallel that
return sumDivInRange.apply(n, 3)
        + sumDivInRange.apply(n, 5)
        + sumDivInRange.apply(n, 7)
        - sumDivInRange.apply(n, 15)
        - sumDivInRange.apply(n, 21)
        - sumDivInRange.apply(n, 35)
        + sumDivInRange.apply(n, 105);
赞(0）分享  回复(0）举报  2023-05-05
iszxjhcz

iszxjhcz2#

最有可能的主要问题是，您正在同步increment（）方法，而不是同步temp变量。当一个线程尝试执行increment（）方法时，第二个线程正在更改temp变量的值。在debug中运行代码并将其 checkout 。
最好将值直接发送到increment（），而不是将其存储在temp中。查看我编辑的代码：

import java.util.*;
public class FindMultiples
{

  public static ArrayList<Integer> dividends = new ArrayList<>();
  public static synchronized void increment(int temp){
     dividends.add(temp);
  }
  
  public static class MyThread implements Runnable{

    public int divisor;
    public int n;

    public MyThread(int n , int divisor){
        this.n=n;
        this.divisor=divisor;
    }

    @Override
    public void run() {

        for (int i=1 ; i<=n ; i++){
            if (i%divisor==0){
                increment(i);
            }
        }
    }
  }

  public int getSum(int n) {
    int sum = 0;
    Thread thread1 = new Thread(new MyThread(n,3));
    Thread thread2 = new Thread(new MyThread(n,7));
    Thread thread3 = new Thread(new MyThread(n,5));

    thread3.start();
    thread2.start();
    thread1.start();
    try {
        thread3.join();
        thread2.join();
        thread1.join();
    }catch (InterruptedException e){
        System.out.println(e.getMessage());
    }
    Set<Integer> set = new HashSet<>(dividends);
    dividends.clear();
    dividends.addAll(set);

    for (int i : dividends){
        sum+=i;
    }

    return sum;
  }

  public static void main(String[] args) {
    FindMultiples findMultiples = new FindMultiples();
    System.out.println(findMultiples.getSum(1000));
  }
}
赞(0）分享  回复(0）举报  2023-05-05
fd3cxomn

fd3cxomn3#

解决这个问题的主要方法是到处丢失static。永远不要使用static，除非你有一个非常好的理由。在这种情况下，您不需要。一般来说，在您第一次遇到可以合法使用static的情况之前，您可能需要几年的Java编程经验。在那之前，不要。
作为一个额外的想法，您可能可以通过不为每个除数创建线程，而是为您想要处理的不同整数范围创建线程来大大减少您必须做的工作量。例如，对于n = 1000，您可以创建两个线程，一个将处理从1到500的数字，另一个将处理从501到1000的数字。这样，每个线程都可以保证产生另一个线程不会产生的数字。

赞(0）分享  回复(0）举报  2023-05-05
yzuktlbb

yzuktlbb4#

你的问题是共享变量temp，它应该在几个语句中保持相同的值。

public static int temp = 0;
public static synchronized void increment() {
    dividends.add(temp);
}

在每个线程中：

temp=i;
increment();

因此，如果thread 1设置了'temp'，那么在thread 1以增量方式使用它之前，它可以被另一个线程更改。
但也没必要了。

public static synchronized void increment(int x) {
    dividends.add(X);
}

然后

increment(i);

其他的答案谈论消除不必要的静电，这是有效的设计批评，但这本身并不能解决你的“临时”问题。即使是一个非静态的'temp'仍然是跨线程共享的-有一个FindMultiples的示例由所有线程示例共享。
这个答案解决了为什么你会得到不同的结果的问题。我在评论中指出，效率可以提高。

赞(0）分享  回复(0）举报  2023-05-05
zphenhs4

zphenhs45#

看我的

n ~= 100,000最好用long getSum(int n)

我们需要调整
内联注解：

package com.example;

import java.util.BitSet;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorCompletionService;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;

public class Test {
    // Our thread pool (e.g...):
    static final ExecutorService THREAD_POOL = Executors.newFixedThreadPool(3);
    // to complete our "tasks" (see javadoc):
    static final ExecutorCompletionService<BitSet> ECS = new ExecutorCompletionService<>(THREAD_POOL);

    static long getSum(int n) throws InterruptedException, ExecutionException { // for brevity: throw
        // start "3 job":
        ECS.submit(() -> findDivisors(3, n));
        // start "5 job":
        ECS.submit(() -> findDivisors(5, n));
        // start "7 job":
        ECS.submit(() -> findDivisors(7, n));

        // collect result:
        BitSet collect = new BitSet(n + 1);
        for (int i = 3; i > 0; i--) { // complete all jobs ...
            BitSet tmpResult = ECS.take().get(); // see javadoc
            if (tmpResult != null) // "or'ing" their results into "collect":
                collect.or(tmpResult);
        }

        // stream over "all set indices" in "collect" and return ...
        return collect.stream()
                // ... (as a long;) their sum 
                .mapToLong(i -> (long) i).sum();
    }

    static BitSet findDivisors(int d, int n) { // MAIN JOB:
        BitSet mem = new BitSet(n + 1); // ignore 0th bit
        for (int i = d; i <= n; i += d) { // set i(th) index to true:
            mem.set(i);
        }
        return mem; // done!
    }

    public static void main(String[] args) throws InterruptedException, ExecutionException {
        // do I/O, more tests...:
        System.out.println(getSum(10));
        System.out.println(getSum(100));
        System.out.println(getSum(1_000));
        System.out.println(getSum(10_000));
        System.out.println(getSum(100_000));
        System.out.println(getSum(1_000_000));
        System.out.println(getSum(10_000_000));
        System.out.println(getSum(100_000_000));
        System.out.println(getSum(1_000_000_000));
        // System.out.println(getSum(2_000_000_000)); // oh-oh
        // finally: release resources:
        THREAD_POOL.shutdown();
    }
}
打印：
40
2838
272066
27152139
2714364277
271428928569
27142867857145
2714285835714288
271428572071428566
1085714285285714288 # ?? <- this looks like (long!) overflow ;(

引用

要点

  • BitSet作为“数据结构”：
  • 类似于boolean[]([])，但是：
  • 更好的内存效率（boolean占用1字节内存（在当前的硬件架构中），而BitSet可以做得更好（由long[]|byte[]支持））
  • 高级API（or, and, xor, cardinality, stream, ...）
  • 为了克服它缺乏多线程支持的问题，我们可以：
  • “同步”
  • 使用多个位集连接/或/和/...他们在一起
  • bitSet_x（3/5/7）集合中的第i个索引，表示：i可被x整除（3/5/7）
  • 挑战从n~=100000开始

而“超轻”版本（关于代码行，性能是另一个章节），灵感来自Andrey B. P.：

[static] long getSum(int n) {
  return IntStream.rangeClosed(1, n) // rangeClosed not range (or +/-1;)
    .parallel() // ok
    .filter(i ->
         (i % 3 == 0 && i % 15 > 0 && i % 21 > 0) // 1.
      || (i % 5 == 0 && i % 35 > 0) // 2.
      || (i % 7 == 0) // 3.
    )
    .mapToLong(i -> (long) i) // for bigger input
    .sum(); // #
}
赞(0）分享  回复(0）举报  2023-05-05
q43xntqr

q43xntqr6#

当你的目标是并行计算时，你应该确保你的解决方案实际上比串行（单线程）更快。不幸的是，您的代码（由Mukhtar Amirkhanov修复）可能比从1到n的天真循环慢得多。这是因为一个简单的解决方案不需要在任何地方存储实际的股息。而且你的多线程程序在每一步上都是同步的，这意味着它实际上不会并行地取得太多的进展。最后，在线程加入之后，程序删除主线程中的重复项--仅这一步就可能比简单循环花费更多的时间。
不幸的是，这个任务定义得很差，因为最快的解决方案只是一个公式（如@Andrey B.Panfilov），它可以在恒定时间O(1)中计算，并且不能通过多线程加速。可能你的老师想通过使用多线程来加速计算，而不是简单的解决方案，所以你应该满足于“第二好”的方法。
@Mike Nakis在他的回答中描述了一种有意义的并行化这些任务的方法。您应该在线程之间划分工作，而不是通过除数，而是通过被除数的范围。您可以定义单独的线程来完成这项工作，在加入它们之后，只需添加它们的结果，或者您可以简单地使用一个并行流（如@Andrey B.Panfilov在注解中，只需使用LongStream而不是IntStream）达到相同的效果（如果在赋值中允许流）。

import java.util.*;
public class FindMultiples
{
  public static final int numberOfThreads = 3;
  public static long[] partialResults = new long[numberOfThreads];

  public static class MyThread implements Runnable{
    public int threadNumber;
    public int n;

    public MyThread(int threadNumber, int n) {
        this.threadNumber = threadNumber;
        this.n = n;
    }

    @Override
    public void run() {
        int start = ((threadNumber - 1) * n / numberOfThreads) + 1;
        int end = threadNumber * n / numberOfThreads;
        long result = 0;
        for (int i = start; i <= end; i++)
            if (i % 3 == 0 || i % 5 == 0 || i % 7 == 0)
                result += i;
        partialResults[threadNumber - 1] = result;
    }
  }

  public long getSum(int n) {
    Thread[] threads = new Thread[numberOfThreads];
    for (int i = 1; i <= numberOfThreads; i++)
        threads[i - 1] = new Thread(new MyThread(i, n));

    for (int i = 1; i <= numberOfThreads; i++)
        threads[i - 1].start();

    try {
        for (int i = 1; i <= numberOfThreads; i++)
            threads[i - 1].join();
    } catch (InterruptedException e) {
        System.out.println(e.getMessage());
    }
    
    long sum = 0;
    for (int i = 1; i <= numberOfThreads; i++)
        sum += partialResults[i - 1];

    return sum;
  }

  public static void main(String[] args) {
    FindMultiples findMultiples = new FindMultiples();
    System.out.println(findMultiples.getSum(1000));
  }
}
赞(0）分享  回复(0）举报  2023-05-05
我来回答

相关问题

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新问答

    更多
    • 蜀ICP备2022004421号-2 NULL123 https://www.null123.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com