`

java多线程面试 - 多线程求和

java多线程面试 
阅读更多

        今天面试过程中碰到一个简单的多线程面试题目，竟然一时钻了牛角尖，没有回答上来，结束面试立刻醒悟过来，想想真丢人。

 

        面试题目如下：如何多线程计算 1+2+3+……n，其中n是一个很大的数值，不使用直接的求职公式。

 

        因为总是碰到类似于计数器的问题，（多个线程进行计数），所以思路不自觉的就转到了计数器的处理思路上去了：设置多个线程共享的一个 Integer sum，然后多个线程瓜分 1到n 的整数值，并分别增加共享的sum。当时写的实现思路（只是核心部分）：

 

/**
 *简单示例程序，说明算法，不能编译
 */
public class MultiSum implements Runnable {
    int     min;
    int     max;
    Integer sum;

    MultiSum(int min, int max, Integer sum) {
        this.min = min;
        this.max = max;
        this.sum = sum;
    }

    public void run() {
        synchronized (sum) {
            for (int i = min; i <= max; i++) {
                sum += i;
            }
        }
    }
    
    public static void main(String[] args) {
        Integer sum = 0; 
        //简单使用3个线程计算从1到300的加和
        new Thread(new MultiSum(1, 100, sum) ).start();
        new Thread(new MultiSum(101, 200, sum)).start();
        new Thread(new MultiSum(201, 300, sum)).start();
        
        Thread.sleep(200);
        System.out.println("sum from 1 to 300 is:"+sum);
    }

}

 

        因为对共享的 sum 变量进行加和，需要同步，这里对 sum 的加和就成为了一个瓶颈--多线程完全无法并行计算，只能等待拿到Sum的锁。其实这就变成了一个需要执行线程调度的串行操作，无论如何效率都不会超过单线程执行。

 

       上面的错误的原因就在于片面的理解了使用多线程的原因：多线程不仅可以在阻塞场景下的可以允许调度其他线程执行以便获得更多的 throughput， 而且可以充分的利用现在多核技术（包括分布式环境下），使得多个线程可以并行的计算。

 

       应用在此加和的场景下，其实就是一个简单的分治算法，将 1到n 的加和平均分配到多个线程计算，然后再将加和的结果汇总。下面是写出的程序（注意分割时候边界，注意 Integer的范围：2^(31)-1）：

       

package com.llq.TestJava;

/**
 * 类MultiThreadSum.java的实现描述：多线程执行加和操作
 * 
 * @author llq 2014-3-5 下午10:32:10
 */
public class MultiThreadSum implements Runnable {

    private Integer   sum;
    private final int fromInt;
    private final int toInt;
    private final int threadNo;

    public MultiThreadSum(Integer sum, int fromInt, int toInt, int threadNo) {
        this.sum = sum;
        this.fromInt = fromInt;
        this.toInt = toInt;
        this.threadNo = threadNo;
    }

    /***
     * 对sum进行加和计算，在sum原始值的基础上从 fromInt 开始加和，一直到 toInt 结束（包含fromInt 和 toInt）的数值
     */
    public void run() {
        long current = System.currentTimeMillis();

        for (int i = fromInt; i <= toInt; i++) {
            this.sum += i;
        }

        current = System.currentTimeMillis() - current;
        System.out.println("Thread." + threadNo + " executes sum from " + fromInt + " to " + toInt + " in " + current
                + " milseconds. Sum is " + sum);

    }

    public static void main(String[] args) {
        Integer toMax = 20000; //对从1到20,000进行加和
        Integer sumInteger = 0;
        int threads = 8; //计算线程数

        //每个线程计算一段连续的加和，并将加和结果保存在数组中。
        Integer[] subSum = new Integer[threads];
        for (int i = 0; i < threads; i++) {
            subSum[i] = new Integer(0);
        }

        for (int i = 0; i < threads; i++) {
            int fromInt = toMax * i / threads + 1; //边界条件
            int toInt = toMax * (i + 1) / threads; //边界条件
            new Thread(new MultiThreadSum(subSum[i], fromInt, toInt, i)).start();
        }
        try {
            Thread.sleep(10); //等待加和程序执行结束

            for (int i = 0; i < threads; i++) {
                sumInteger += subSum[i];
            }
            System.out.println("The sum is :" + sumInteger);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

    }
}

 大功告成！执行，结果却出乎意料：

   

Thread.0 executes sum from 1 to 2500 in 1 milseconds. Sum is 3126250
Thread.1 executes sum from 2501 to 5000 in 1 milseconds. Sum is 9376250
Thread.2 executes sum from 5001 to 7500 in 0 milseconds. Sum is 15626250
Thread.4 executes sum from 10001 to 12500 in 0 milseconds. Sum is 28126250
Thread.6 executes sum from 15001 to 17500 in 0 milseconds. Sum is 40626250
Thread.5 executes sum from 12501 to 15000 in 0 milseconds. Sum is 34376250
Thread.3 executes sum from 7501 to 10000 in 0 milseconds. Sum is 21876250
Thread.7 executes sum from 17501 to 20000 in 0 milseconds. Sum is 46876250
The sum is :0

       每个线程的执行都是OK的，但是最后给出的结果是: 0 ！注意了：Integer 等java基本类型的包装类虽然是传递的对象引用，但对象本身是不可变的。String同样如此。对这些对象值的改变，其实改变了引用本身。即变量保存了一个新的引用。 可见写程序一定要小心谨慎，打好基础，否则处处是坑啊。

 

        这种问题的解决非常方便了，只要包装一个类就OK了。修改后的程序：

package com.llq.TestJava;
/**
 * 定义简单的可变int包装类，事例用
*/
class MutableInteger {
    int value;

    MutableInteger(int v) {
        this.value = v;
    }
}


package com.llq.TestJava;

/**
 * 类MultiThreadSum.java的实现描述：多线程执行加和操作
 * 
 * @author llq 2014-3-5 下午10:32:10
 */
public class MultiThreadSum implements Runnable {

    private final MutableInteger sum;
    private final int            fromInt;
    private final int            toInt;
    private final int            threadNo;

    public MultiThreadSum(MutableInteger sum, int fromInt, int toInt, int threadNo) {
        this.sum = sum;
        this.fromInt = fromInt;
        this.toInt = toInt;
        this.threadNo = threadNo;
    }

    /***
     * 对sum进行加和计算，在sum原始值的基础上从 fromInt 开始加和，一直到 toInt 结束（包含fromInt 和 toInt）的数值
     */
    public void run() {
        long current = System.currentTimeMillis();

        for (int i = fromInt; i <= toInt; i++) {
            this.sum.value += i;
        }

        current = System.currentTimeMillis() - current;
        System.out.println("Thread." + threadNo + " executes sum from " + fromInt + " to " + toInt + " in " + current
                + " milseconds. Sum is " + sum.value);

    }

    public static void main(String[] args) {
        Integer toMax = 20000; //对从1到20,000进行加和
        Integer sumInteger = 0;
        int threads = 8; //计算线程数

        //每个线程计算一段连续的加和，并将加和结果保存在数组中。
        MutableInteger[] subSum = new MutableInteger[threads];
        for (int i = 0; i < threads; i++) {
            subSum[i] = new MutableInteger(0);
        }

        for (int i = 0; i < threads; i++) {
            int fromInt = toMax * i / threads + 1; //边界条件
            int toInt = toMax * (i + 1) / threads; //边界条件
            new Thread(new MultiThreadSum(subSum[i], fromInt, toInt, i)).start();
        }
        try {
            Thread.sleep(10); //等待加和程序执行结束

            for (int i = 0; i < threads; i++) {
                sumInteger += subSum[i].value;
            }
            System.out.println("The sum is :" + sumInteger);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

    }
}

 

 

 结果如下，OK！

Thread.1 executes sum from 2501 to 5000 in 0 milseconds. Sum is 9376250
Thread.3 executes sum from 7501 to 10000 in 0 milseconds. Sum is 21876250
Thread.5 executes sum from 12501 to 15000 in 0 milseconds. Sum is 34376250
Thread.7 executes sum from 17501 to 20000 in 0 milseconds. Sum is 46876250
Thread.0 executes sum from 1 to 2500 in 0 milseconds. Sum is 3126250
Thread.2 executes sum from 5001 to 7500 in 0 milseconds. Sum is 15626250
Thread.4 executes sum from 10001 to 12500 in 0 milseconds. Sum is 28126250
Thread.6 executes sum from 15001 to 17500 in 0 milseconds. Sum is 40626250
The sum is :200010000

 

      几个需要注意的地方：

  • 这种通过分治算法，充分利用多核提高性能的多线程程序，在归并的时候，需要进行线程间的同步，同步的策略还需要在研究下（wait,notify, notifyAll 机制是否能满足同步要求？）。这里为了简单，主线程使用了Sleep 的模式，在耗时或者无法估算时间的情况下，肯定是不行的。
  • 如何扩展到多个JVM的场景，即分布式场景下。
  • 如何确定线程的数量，从而达到最高的执行效率。（这个是面试的时候着重问的，完全没有思路。）
分享到：
| 是谁逼走了优秀的设计师？【转发】
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    JAVA技术面试题

    6. **多线程** - **线程创建**：通过Thread类和实现Runnable接口创建线程的方法。 - **同步机制**：理解synchronized关键字、wait()、notify()和notifyAll()的使用，以及死锁的概念。 - **线程池**：...

    今日头条2017校园招聘 java后台岗位面试题(1).pdf

    三面继续深入到Java多线程和MySQL索引，并结合应聘者的项目经验进行提问。最后一轮的HR面试则更加关注个人学习方法和态度，以了解其适应公司文化和团队合作的能力。 【知识点详解】： 1. **链表相加**：这是一个...

    Java基础精品课23-StreamApi.zip

    3. 并行(parallel)：使用多线程并行处理流，提高性能。 4. 聚合(reduce)：将流中的元素组合成单个值，如求和、最大值等。 5. 分组(groupBy)：按照某个属性将元素分组到不同的Map中。 6. 排序(sort)：对流中的元素...

    高级Java工程师的经典面试题.doc

    而StringBuffer（或StringBuilder）是可变对象，适合在多线程环境中动态构建字符串，因为它的append()和insert()等方法不会创建新对象，而是直接修改原有对象。如果频繁进行字符串操作，使用StringBuffer（线程安全...

    《Java十大经典案例》源代码

    7. **多线程**：Java提供了丰富的多线程支持，案例可能涉及到Thread类的使用，或者更高级的ExecutorService和并发工具类，比如Semaphore、CyclicBarrier等。 8. **设计模式**：一些案例可能包含常见的设计模式，如...

    heibernate面试题

    - HQL 可以执行复杂的统计查询，如计数、求和等。 #### 5. Hibernate 性能优化技巧 - **使用二级缓存** - 通过合理配置二级缓存，可以极大地提升应用程序的性能。 - **优化 SQL 语句** - 通过调整 Hibernate ...

    黑马面试宝典知识点复习

    #### 多线程 - **线程创建**：通过继承Thread类或实现Runnable接口来创建线程。 - **Thread类**：直接定义Thread子类，并重写run()方法。 - **Runnable接口**：实现该接口并定义run()方法，然后传递给Thread构造...

    google面试题（部分）

    - **问题描述**：解决生产者消费者问题，这是一个多线程同步问题。 - **知识点**：并发编程，线程同步。 #### 16. 社交网络中的好友推荐 - **问题描述**：在一个社交网络图中实现好友推荐，找出共同好友最多的那个...

    软件测试&oracle的笔试题，很重要

    1. 线程安全性：Vector是线程安全的，内部使用`synchronized`修饰方法，适合多线程环境；而ArrayList不是线程安全的，如果在多线程环境下使用，需要自行同步。 2. 性能：由于线程安全的实现，Vector的性能相对较低，...

    android面试题目及其答案大全

    以上知识点涵盖了Android开发中的多个方面，理解和掌握这些内容对于面试和实际开发都至关重要。在面试准备中，除了掌握这些基础，还需要关注最新技术和最佳实践，以及项目中遇到的具体问题和解决方案。

    长春径点科技笔试，一面，二面题

    二面可能涉及更具体的编程语言知识，如C#的多线程和网络通信（Socket），以及对不同平台项目开发的了解。 总的来说，长春径点科技的笔试和面试考察了应聘者全面的IT技能，包括理论知识、编程能力、问题解决技巧以及...

    SSH面试题总结

    `SessionFactory`是线程安全的，可以被多个`Session`共享。 3. **打开Session**：通过`SessionFactory`创建`Session`，`Session`负责执行数据库操作。 4. **创建事务Transaction**：开始一个新的事务，确保一系列...

    LeetCode-源码.rar

    - **Java**：类和接口，异常处理，集合框架，多线程，以及Java 8以上的新特性，如Lambda表达式。 - **Python**：简洁的语法，动态类型，列表推导式，内置函数和模块，以及面向对象编程。 - **JavaScript**：函数...

    迅雷在线二笔

    根据给定文件的信息，我们可以提炼出与IT相关的知识点，主要涉及算法、文件处理以及多线程编程等几个方面。下面将对这些知识点进行详细的解析。 ### 知识点一：序列求和算法 在描述中提到的一串数字“1, 3, 6, 10,...

    JS 数据库答案.docx

    【JavaScript 知识点】 1. 访问对象属性： 在JavaScript中，可以通过点运算符（.）或方括号运算符（[]）来...如需了解更多Java相关知识，比如类、接口、异常处理、多线程、集合框架等，请提供更具体的信息或问题。

Magicbox
Global site tag (gtag.js) - Google Analytics