并发编程之Callable/Future接口（以单词最佳匹配算法为例）

蔚落 2023-01-12 11:53 115阅读 0赞

**目录**

一、认识Callable接口

二、认识Future接口

三、实例：单词最佳匹配

1、最短编辑距离算法实现

2、存放最佳匹配结果

3、加载词典

四、串行版本

五、并发版本

1、BestMatchingBasicTask类

2、BestMatchingBasicConcurrentCalculation类

3、BestMatchingConcurrentMain类

六、验证结果

1、串行版本结果

2、并发版本结果

--------------------

# 一、认识Callable接口 #

Java多线程的知识很丰富，在此之前，只对于实现Runnable接口的执行任务有所了解，现在进一步学习，才发现其实Java中还有另一个功能很相似的多线程任务接口，这就是**Callable接口**。

Runnable和Callable接口的相异之处在于，后者实现接口的call方法之后提供了返回值，接口方法差别如下：

**Runnable接口**

public class A implements Runnable{
        /**
         * @param 
         * @return void
         * @author Charzous
         * @date 2021/1/28 14:59
         *
         */
        @Override
        public void run() {
    
        }
    }

**Callable接口**

public class A implements Callable {
        /**
         * @param 
         * @return java.lang.Object
         * @author Charzous
         * @date 2021/1/28 15:00
         *
         */
        @Override
        public Object call() throws Exception {
            return null;
        }
    }

这篇学习记录将介绍Callable接口的特定和应用。

> **Callable接口主要特征：**
> 
> 1.  是一个通用接口，call方法返回类型与类型参数一致。
> 2.  声明了call方法，执行器执行任务时候会执行该方法。
> 3.  可以抛出任何一种校验异常，应该算较高级应用。

# 二、认识Future接口 #

Future接口与Callable接口是同时出现在一个执行任务中，体现在Callable接口的处理结果要用Future接口来打包，Future接口描述了异步计算的结果。

当我们向执行器发送Callable任务时，将返回一个Future接口的实现，可以通过这控制任务的执行和任务状态，获取结果。

> **Future接口主要特征：**
> 
> 1.  可以使用cancel方法撤销执行任务。
> 2.  查看任务状态：isCancelled方法是否撤销，isDone()方法是否结束。
> 3.  使用get()方法获取任务返回值。

# 三、实例：单词最佳匹配 #

这里从简单的案例出发，学习Callable接口和Future接口在实际应用中的实现过程。

**单词最佳匹配算法**，也可以说是**最短编辑距离问题**的一个具体应用，目标是计算两个字符串之间的最小距离，简而言之，就是将第一个字符串变为第二个字符串的最少修改字符次数。

在单词匹配任务中，则是找到给定字符串单词在词典中最相似的单词。

准备工作包括：

1.  英文词典：**英国高级疑难词典UKACD**，该词典包含了25万多个单词和习惯用语，专门用于填字游戏。
2.  单词之间相似性度量指标：**Lenvenshtein距离**，指的是第一个字符串转换成第二个字符串所需进行的最少的插入、删除或替换操作次数。也就是上面说到的最短编辑距离，算法使用**动态规划**实现。

接下来是具体实现单词最佳匹配案例的算法，有串行和并发版本，可以比较算法效率。两种算法的公共类包括最短编辑距离算法的实现、存放最佳匹配算法的结果和词典加载。

## **1、最短编辑距离算法实现** ##

算法使用动态规划完成m\*n二维数组的填写，最后得到最短距离保存在a\[m\]\[n\]对应的值。

public class LevenshteinDistance {
        /**
         * @param string1
         * @param string2
         * @return int
         * @author Charzous
         * @date 2021/1/28 11:10
         */
        public static int calculate(String string1, String string2) {
            int[][] distances = new int[string1.length() + 1][string2.length() + 1];
            for (int i = 1; i <= string1.length(); i++)
                distances[i][0] = i;
    
            for (int j = 1; j <= string2.length(); j++)
                distances[0][j] = j;
            //动态规划填表
            for (int i = 1; i <= string1.length(); i++) {
                for (int j = 1; j <= string2.length(); j++) {
                    if (string1.charAt(i - 1) == string2.charAt(j - 1))
                        distances[i][j] = distances[i - 1][j - 1];
                    else
                        distances[i][j] = minimum(distances[i - 1][j], distances[i][j - 1], distances[i - 1][j - 1]) + 1;
                }
            }
    //测试
    //        for (int i=0;i<=string1.length();i++){
    //            for (int j=0;j<=string2.length();j++)
    //                System.out.print(distances[i][j]+" ");
    //            System.out.println();
    //        }
            return distances[string1.length()][string2.length()];
        }
    
        private static int minimum(int i, int j, int k) {
            return Math.min(i, Math.min(j, k));
        }
    /**类内测试
    public static void main(String[] args) {
    String s1="lonx";
    String s2="long";
    int d=LevenshteinDistance.calculate(s1,s2);
    System.out.println(d);
    }
     */
    }

## **2、**存放最佳匹配结果 ##

import java.util.List;
    
    public class BestMatchingData {
        private int distance;
        private List<String> words;
    
        public int getDistance() {
            return distance;
        }
    
        public List<String> getWords() {
            return words;
        }
    
        public void setDistance(int distance) {
            this.distance = distance;
        }
    
        public void setWords(List<String> words) {
            this.words = words;
        }
    }

## **3、加载词典** ##

import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStream;
    import java.io.InputStreamReader;
    import java.nio.file.Files;
    import java.nio.file.Path;
    import java.nio.file.Paths;
    import java.util.ArrayList;
    import java.util.List;
    
    public class WordsLoader {
        /**
         * @param path
         * @return java.util.List<java.lang.String>
         * @author Charzous
         * @date 2021/1/28 11:10
         */
        public static List<String> load(String path) {
            Path file = Paths.get(path);
            List<String> data = new ArrayList<String>();
            try (
                    InputStream in = Files.newInputStream(file);
                    BufferedReader reader = new BufferedReader(new InputStreamReader(in))) {
                String line = null;
                while ((line = reader.readLine()) != null)
                    data.add(line);
            } catch (IOException e) {
                e.printStackTrace();
            }
            return data;
        }
    }

# 四、串行版本 #

首先，实现简单的串行版本，后续用于验证并发处理的性能。实现的思路比较简单，将给定的字符串与词典每个单词进行距离的计算，然后把最佳结果保存到List中。

import java.util.ArrayList;
    import java.util.List;
    
    public class BestMatchingSerialCalculation {
        /**
         * @param word
         * @param dictionary
         * @author Charzous
         * @date 2021/1/28 11:19
         */
        public static BestMatchingData getBestMatchingWords(String word, List<String> dictionary) {
            List<String> results = new ArrayList<String>();
            int minDistance = Integer.MAX_VALUE;
            int distance;
            for (String str : dictionary) {
                distance = LevenshteinDistance.calculate(word, str);
                if (distance < minDistance) {
                    results.clear();
                    minDistance = distance;
                    results.add(str);
                } else if (distance == minDistance) {
                    results.add(str);
                }
    
            }
            BestMatchingData result = new BestMatchingData();
            result.setWords(results);
            result.setDistance(minDistance);
    
            return result;
        }
    
    }

下面实现可执行的主类main，加载词典文件，打印最佳匹配结果以及相关信息。

import java.util.Date;
    import java.util.List;
    
    public class BestMatchingSerialMain {
        public static void main(String[] args) {
            Date startTime,endTime;
            List<String> dictionary= WordsLoader.load("data/UK Advanced Cryptics Dictionary.txt");
            System.out.println("Dictionary Size:"+dictionary.size());
    
            String word="stitter";//待匹配单词
            if (args.length==1)
                word=args[0];
    
            startTime=new Date();
            BestMatchingData result=BestMatchingSerialCalculation.getBestMatchingWords(word,dictionary);
            endTime=new Date();
            List<String> results=result.getWords();
            System.out.println("Word: "+word);
            System.out.println("Minimum distance: "+result.getDistance());
            System.out.println("耗时："+(endTime.getTime()-startTime.getTime())+" ms");
            System.out.println("List of best matching words: "+results.size());
            results.forEach(System.out::println);
        }
    }

结果会在后面进行比较。

# 五、并发版本 #

到这里，将基于Callable接口实现执行器任务，利用call方法返回值，得到最佳匹配单词结果，包括3个实现类，具体如下介绍：

## 1、BestMatchingBasicTask类 ##

这里将执行在执行器中实现了Callable接口的任务。

import java.util.ArrayList;
    import java.util.List;
    import java.util.concurrent.Callable;
    
    public class BestMatchingBasicTask implements Callable<BestMatchingData> {
        private int startIdx;
        private int endIdx;
        private List<String> dictionary;
        private String word;
        /**
         * @param startIdx
         * @param endIdx
         * @param dictionary
         * @param word
         * @return 
         * @author Charzous
         * @date 2021/1/28 16:24
         *
         */
        public BestMatchingBasicTask(int startIdx, int endIdx, List<String> dictionary, String word) {
            this.startIdx = startIdx;
            this.endIdx = endIdx;
            this.dictionary = dictionary;
            this.word = word;
        }
    
        @Override
        public BestMatchingData call() throws Exception {
            List<String> results = new ArrayList<String>();
            int minDistance = Integer.MAX_VALUE;
            int distance;
            for (int i = startIdx; i < endIdx; i++) {
                distance = LevenshteinDistance.calculate(word, dictionary.get(i));//计算给出单词与词典中单词的距离
                //保存最佳匹配结果的单词
                if (distance < minDistance) {
                    results.clear();
                    minDistance = distance;
                    results.add(dictionary.get(i));
                } else if (distance == minDistance)
                    results.add(dictionary.get(i));
            }
            //将结果保存并返回
            BestMatchingData result = new BestMatchingData();
            result.setWords(results);
            result.setDistance(minDistance);
            return result;
        }
    }

## 2、BestMatchingBasicConcurrentCalculation类 ##

该类创建执行器和必要的任务，将任务发送给执行器。

import java.util.ArrayList;
    import java.util.List;
    import java.util.concurrent.ExecutionException;
    import java.util.concurrent.Executors;
    import java.util.concurrent.Future;
    import java.util.concurrent.ThreadPoolExecutor;
    
    public class BestMatchingBasicConcurrentCalculation {
        /**
         * @param word
         * @param dictionary
         * @author Charzous
         * @date 2021/1/28 16:27
         *
         */
        public static BestMatchingData getBestMatchingWords(String word, List<String> dictionary) throws ExecutionException, InterruptedException {
    
            int numCores = Runtime.getRuntime().availableProcessors();
            ThreadPoolExecutor executor = (ThreadPoolExecutor) Executors.newFixedThreadPool(numCores);
            int size = dictionary.size();
            int step = size / numCores;
            int startIdx, endIdx;
            List<Future<BestMatchingData>> results = new ArrayList<>();
    
            for (int i = 0; i < numCores; i++) {
                startIdx = i * step;
                if (i == numCores - 1)
                    endIdx = dictionary.size();
                else
                    endIdx = (i + 1) * step;
                //创建任务
                BestMatchingBasicTask task = new BestMatchingBasicTask(startIdx, endIdx, dictionary, word);
                Future<BestMatchingData> future = executor.submit(task);//执行器提交任务并获取Future接口返回结果
                results.add(future);
            }
            executor.shutdown();
    
            List<String> words = new ArrayList<String>();
            int minDistance = Integer.MAX_VALUE;
            for (Future<BestMatchingData> future : results) {
                BestMatchingData data = future.get();
                if (data.getDistance() < minDistance) {
                    words.clear();
                    minDistance = data.getDistance();
                    words.addAll(data.getWords());
                } else if (data.getDistance() == minDistance)
                    words.addAll(data.getWords());
            }
            BestMatchingData result = new BestMatchingData();
            result.setDistance(minDistance);
            result.setWords(words);
            return result;
        }
    }

## 3、BestMatchingConcurrentMain类 ##

实现可执行主类main，打印结果。

import java.util.Date;
    import java.util.List;
    import java.util.concurrent.ExecutionException;
    
    public class BestMatchingConcurrentMain {
        public static void main(String[] args) {
            try {
                Date startTime,endTime;
                List<String> dictionary= WordsLoader.load("data/UK Advanced Cryptics Dictionary.txt");
                System.out.println("Dictionary Size:"+dictionary.size());
    
                String word="stitter";//待匹配单词
                if (args.length==1)
                    word=args[0];
    
                startTime=new Date();
                BestMatchingData result=BestMatchingBasicConcurrentCalculation.getBestMatchingWords(word,dictionary);
                endTime=new Date();
                List<String> results=result.getWords();
                System.out.println("Word: "+word);
                System.out.println("Minimum distance: "+result.getDistance());
                System.out.println("耗时："+(endTime.getTime()-startTime.getTime())+" ms");
                System.out.println("List of best matching words: "+results.size());
                results.forEach(System.out::println);
            } catch (InterruptedException e) {
                e.printStackTrace();
            } catch (ExecutionException e) {
                e.printStackTrace();
            }
        }
    }

# 六、验证结果 #

## 1、串行版本结果 ##

测试字符串stitter，查找词典得到最佳匹配结果有9个单词：

为了避免偶然性，进行了多次测试运行，串行方法耗时在240ms左右。

***sitter  
skitter  
slitter  
spitter  
stilter  
stinter  
stotter  
stutter  
titter***

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NoYXJ6b3Vz_size_16_color_FFFFFF_t_70][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NoYXJ6b3Vz_size_16_color_FFFFFF_t_70 1][]

## 2、并发版本结果 ##

并发版本多次测试运行结果，耗时在120ms左右，相当于串行的一半耗时，性能有提升。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NoYXJ6b3Vz_size_16_color_FFFFFF_t_70 2][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NoYXJ6b3Vz_size_16_color_FFFFFF_t_70 3][]

以单词最佳匹配算法为例，学习Java并发编程之Callable接口和Future接口，更深入具体地理解内部运行机制，同时也通过这个实际应用更好温故掌握知识，动态规划、最短编辑距离算法。

**如果觉得不错欢迎“一键三连”哦，点赞收藏关注，有问题直接评论，交流学习！**

--------------------

我的CSDN博客：[https://blog.csdn.net/Charzous/article/details/113338669][https_blog.csdn.net_Charzous_article_details_113338669]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NoYXJ6b3Vz_size_16_color_FFFFFF_t_70]: /images/20221119/5cc148faf9a14ba2ab991f928b4a9765.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NoYXJ6b3Vz_size_16_color_FFFFFF_t_70 1]: /images/20221119/68935dcf1f9e4f19b5e2fc3640fc57fc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NoYXJ6b3Vz_size_16_color_FFFFFF_t_70 2]: /images/20221119/6c0f4d9d97c54430adf01c44cae5a0ec.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NoYXJ6b3Vz_size_16_color_FFFFFF_t_70 3]: /images/20221119/2f67ce90d0134676a0c972b699cd6ae0.png
[https_blog.csdn.net_Charzous_article_details_113338669]: https://blog.csdn.net/Charzous/article/details/113338669