5.2　第一个例子：单词最佳匹配算法

5.2　第一个例子：单词最佳匹配算法

单词最佳匹配算法的主要目标是找出与作为参数的字符串最相似的单词。要实现一个这样的算法，需要做如下准备。

单词列表：在我们的例子中使用了英国高级疑难词典（UKACD），这是专门为填字游戏社区编纂的一个单词列表，有250 353个单词和习惯用语。
用于评估两个单词之间相似度的指标：我们使用Levenshtein距离来度量两个字符序列的差异。Levenshtein距离是指，将第一个字符串转换成第二个字符串所需进行的最少的插入、删除或替换操作次数。你可以查看维基百科关于“Levenshtein distance”的解释，找到对这一指标的简要描述。

在我们的例子中，你可以实现如下两个操作。

第一个操作使用Levenshtein距离返回与某个字符序列最相似的单词列表。
第二个操作是使用Levenshtein距离来判定我们的字典当中是否存在某个字符序列。如果我们使用equals()方法，速度将会更快。但是就本书的目的而言，我们的版本则是更好的选择。

你将实现上述操作的串行版本和并发版本，以便验证在本例中使用并发处理是否确实有帮助。

5.2.1　公共类

在本例实现的所有任务中，都将用到下面三个基类。

WordsLoader类：用于将单词列表加载到字符串对象列表中。
LevenshteinDistance类：用于计算两个字符串之间的Levenshtein距离。
BestMatchingData类：用于存放最佳匹配算法的结果。它存储了单词列表以及这些单词与输入字符串之间的距离。

UKACD在文件中是按照每行一个单词的形式存放的，这样实现load()静态方法的WordsLoader类在接收到单词列表文件的路径之后，就会返回一个含有250 353个单词的字符串对象列表。

LevenshteinDistance类实现了calculate()方法，该方法接收两个字符串对象作为参数，并且返回一个int值来表示两个单词之间的距离。这种分类操作的代码如下。

public class LevenshteinDistance {
  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;
        }
      }
    }
    return distances[string1.length()][string2.length()];
  }
  private static int minimum(int i, int j, int k) {
    return Math.min(i,Math.min(j, k));
  }
}

BestMatchingData类只有两个属性：一个用于存储单词列表的字符串对象列表，以及一个名为distance的整型属性，该属性存放了这些单词与输入字符串之间的距离。

5.2.2　最佳匹配算法：串行版本

首先，我们将实现最佳匹配算法的串行版本。我们将使用该版本作为并发版本的起点，然后将比较两个版本的执行时间，以此来验证并发处理是否可以帮助我们获得更好的性能。

我们在下面两个类中实现了最佳匹配算法的串行版本。

BestMatchingSerialCalculation类，用于计算与输入字符串最相似的单词的列表。
BestMatchingSerialMain类，其中包含main()方法，它用于执行算法、测量执行时间并且在控制台显示结果。

让我们分析一下以上两个类的源代码。

BestMatchingSerialCalculation类

该类只有一个名为getBestMatchingWords()的方法，该方法接收两个参数：一个作为参照的有序字符串，以及含有字典中所有单词的字符串对象列表。该方法返回一个BestMatchingData对象，其中含有算法执行结果。

public class BestMatchingSerialCalculation {
  public static BestMatchingData getBestMatchingWords(String
                 word, List<String> dictionary) {
    List<String> results=new ArrayList<String>();
    int minDistance=Integer.MAX_VALUE;
    int distance;

在内部变量完成初始化之后，算法处理字典中的所有单词，计算这些单词与参照字符串之间的Levenshtein距离。如果针对一个单词计算得到的距离比实际最小距离更小，那么我们将清空结果列表并且将该单词存放在列表中。如果针对一个单词计算得到的距离与实际最小距离相等，那么将该单词添加到结果列表中。

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对象来返回算法结果。

    BestMatchingData result=new BestMatchingData();
    result.setWords(results);
    result.setDistance(minDistance);
    return result;
  }
}

BestMachingSerialMain类

该类是本例的主类。它加载UKACD文件，调用getBestMatchingWords()方法（该方法以接收到的字符串作为参数），然后在控制台显示结果以及算法执行时间。可参看如下代码。

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());
    startTime=new Date();
    BestMatchingData result= BestMatchingSerialCalculation
                            .getBestMatchingWords
                             (args[0], dictionary);
    List<String> results=result.getWords();
    endTime=new Date();
    System.out.println("Word: "+args[0]);
    System.out.println("Minimum distance: " +result.getDistance());
    System.out.println("List of best matching words: "
                        +results.size());
    results.forEach(System.out::println);
    System.out.println("Execution Time: "+(endTime.getTime()-
                       startTime.getTime()));
  }
}

在此，我们使用Java 8语言提供的一种名叫方法引用（method reference）的新构造，以及用于输出结果的新方法List.forEach()。forEach()方法是一种末端操作，对所有元素会有次生效应。

5.2.3　最佳匹配算法：第一个并发版本

我们实现了两个并发版本的最佳匹配算法。第一个版本基于Callable接口，以及在AbstractExecutorService接口中定义的submit()方法。

我们采用下面三个类来实现这一版本的算法。

BestMatchingBasicTask类：该类执行那些实现Callable接口并且将在执行器中执行的任务。
BestMatchingBasicConcurrentCalculation类：该类创建了执行器和必要的任务，并且将任务发送给执行器。
BestMatchingConcurrentMain类：该类实现了main()方法，执行算法并且在控制台显示结果。

让我们看看这些类的源代码。

BestMatchingBasicTask类

正如前面提到的，该类将实现获取最佳匹配单词列表的任务。该任务将实现采用BestMatchingData类参数化的Callable接口。这意味着该类将实现call()方法，而该方法将返回一个BestMatchingData对象。

每个任务处理一部分字典，并且返回这一部分字典获得的结果。我们用到了如下四个内部属性。

任务要分析的这一部分字典的起始位置（包含）。
任务要分析的这一部分字典的结束位置（不包含）。
以字符串对象列表形式表示的字典。
参照输入字符串。
其代码如下。

public class BestMatchingBasicTask implements Callable
                              <BestMatchingData > {
  private int startIndex;
  private int endIndex;
  private List < String > dictionary;
  private String word;
  public BestMatchingBasicTask(int startIndex, int endIndex,
                      List < String > dictionary, String word) {
    this.startIndex = startIndex;
    this.endIndex = endIndex;
    this.dictionary = dictionary;
    this.word = word;
  }

call()方法处理startIndex和endIndex属性值之间的所有单词，并且计算这些单词与输入字符串之间的Levenshtein距离。该方法仅返回与输入字符串最接近的单词。如果在此过程中它找到了比前一个单词更加接近的单词，将清空结果列表并且将新单词加入到该列表中。如果找到一个与当前查找结果距离相同的单词，那么就将该单词加入到结果列表中，如下所示。

@Override
  public BestMatchingData call() throws Exception {
    List<String> results=new ArrayList<String>();
    int minDistance=Integer.MAX_VALUE;
    int distance;
    for (int i=startIndex; i<endIndex; 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对象并且返回该对象，该对象中含有查找到的单词列表以及这些单词与输入字符串之间的距离。

    BestMatchingData result=new BestMatchingData();
    result.setWords(results);
    result.setDistance(minDistance);
    return result;
  }
}

基于Runnable接口的任务之间的主要差别在于，方法中最后一行的返回语句。run()方法并不返回值，因此那些任务都无法返回值。而call()方法可返回一个对象（该对象的类在其实现语句中定义），因而这种类型的任务可以返回结果。

BestMatchingBasicConcurrentCalculation类

该类负责为处理整个词典创建必需的任务、执行这些任务的执行器，并且在执行器中控制这些任务的执行。

该类只有一个getBestMatchingWords()方法，且该方法有两个输入参数：有完整单词列表的字典和参照字符串。该方法返回一个含有算法执行结果的BestMatchingData对象。首先，我们创建并初始化该执行器。我们将机器的核数作为在此使用的最大线程数。看一看下面这个代码块。

public class BestMatchingBasicConcurrentCalculation {
  public static BestMatchingData getBestMatchingWords(String
         word, List<String> dictionary) throws InterruptedException,
         ExecutionException {
    int numCores = Runtime.getRuntime().availableProcessors();
    ThreadPoolExecutor executor = (ThreadPoolExecutor)
                       Executors.newFixedThreadPool(numCores);

然后，我们计算每个任务要处理的那部分字典的规模，并且创建一个Future对象列表来存储这些任务的结果。当你将一个基于Callable接口的任务发送给执行器时，将得到Future接口的一个实现。你可以使用该对象进行如下操作。

了解任务是否已经执行。
获取任务执行的结果（call()方法返回的对象）。
撤销任务的执行。
其代码如下：

int size = dictionary.size();
int step = size / numCores;
int startIndex, endIndex;
List<Future<BestMatchingData>> results = new ArrayList<>();

然后，我们创建这些任务，使用submit()方法将其发送给执行器，并且将该方法返回的Future对象添加到Future对象列表。submit()方法会立即返回，它并不会一直等待任务执行。我们有如下代码。

for (int i = 0; i < numCores; i++) {
  startIndex = i * step;
  if (i == numCores - 1) {
    endIndex = dictionary.size();
  } else {
    endIndex = (i + 1) * step;
  }
  BestMatchingBasicTask task = new BestMatchingBasicTask(startIndex,
                                   endIndex, dictionary, word);
  Future<BestMatchingData> future = executor.submit(task);
  results.add(future);
}

我们把任务发送给执行器后，可以调用执行器的shutdown()方法来结束其执行，并且对Future对象列表执行迭代操作以获得每个任务的执行结果。我们使用不带任何参数的get()方法。如果任务执行结束，则该方法返回由call()方法返回的对象。如果任务尚未结束，该方法会通过当前线程将调用线程置为休眠状态，直到任务执行结束并且可获得结果为止。

我们将任务的结果组合成一个结果列表，这样就可以仅返回与参照字符串距离最近的单词的列表了，如下所示：

  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对象，其中含有算法执行结果。

    BestMatchingData result=new BestMatchingData();
    result.setDistance(minDistance);
    result.setWords(words);
    return result;
  }
}

　BestMatchingConcurrentMain类和前面介绍的BestMatchingSerialMain类非常相似。唯一的差别是所用的类不同（使用BestMatchingBasicConcurrentCalculation类代替BestMatchingSerialCalculation），所以此处没有给出其源码。请注意，当并发任务工作于各个独立的数据片之上时，我们既没有采用线程安全的数据结构，也没有使用同步机制，而是当并发任务执行完毕后以顺序方式来合并最终结果。

5.2.4　最佳匹配算法：第二个并发版本

我们使用AbstractExecutorService（在ThreadPoolExecutorClass中实现）的invokeAll()方法实现了最佳匹配算法的第二个版本。在前一个版本中我们使用了submit()方法，该方法接收一个Callable对象作为参数，并返回一个Future对象。invokeAll()方法接收一个Callable对象列表作为参数，并且返回一个Future对象列表。其中第一个Future对象和第一个Callable对象相关联，以此类推。这两个方法之间还有另一个重要区别。尽管submit()方法可立即返回，但是invokeAll()方法仅当所有Callable任务都终止执行时才返回。这意味着如果你调用了isDone()方法，那么所有返回的Future对象都会返回true。

要实现该版本的程序，我们使用了在前面例子中实现的BestMatchingBasicTask类，并且实现了BestMatchingAdvancedConcurrentCalculation类。该类与BestMatchingBasicConcurrentTask类的区别在于任务的创建和对结果的处理上。在任务创建方面，现在我们创建一个列表并且用它存放我们要执行的任务。

for (int i = 0; i < numCores; i++) {
  startIndex = i * step;
  if (i == numCores - 1) {
    endIndex = dictionary.size();
  } else {
    endIndex = (i + 1) * step;
  }
  BestMatchingBasicTask task = new BestMatchingBasicTask(startIndex,
                                         endIndex, dictionary, word);
  tasks.add(task);
}

为了处理结果，我们调用invokeAll()方法并且之后遍历返回的Future对象列表。

    results = executor.invokeAll(tasks);
    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;
}

为执行该版本的代码，我们还实现了BestMatchingConcurrentAdvancedMain类。该类的源码与前一个例子中（BestMatchingConcurrentMain）的代码非常类似，此处不再给出。

5.2.5　单词存在算法：串行版本

本例中，我们实现了另一个操作来检查一个字符串是否在我们的单词列表中。为检查一个单词是否存在，我们要再次用到Levenshtein距离。我们认为，如果列表中存在某个单词，那么该单词与列表中的某一单词之间的距离为0。使用equals()方法或者equalsIgnoreCase()方法做对比会更加快捷，或者也可将输入单词读入到一个HashSet中并使用contains()方法（这比我们的版本更加高效），但是这里假定我们的版本更加适合本书的主旨。

正如前面的例子，首先，我们实现该操作的串行版本，将其作为基础来实现并发版本，然后再对比这两个版本的执行时间。

实现串行版程序时，要用到如下两个类。

ExistSerialCalculation类：该类实现existWord()方法来比较输入字符串和字典中的所有单词，直到找到该单词为止。
ExistSerialMain类：该类启动本例并且度量执行时间。

让我们分析一下这两个类的源代码。

ExistSerialCalculation类

该类只有一个方法，就是existWord()方法。该方法接收两个参数：我们要查找的单词与完整的单词列表。该方法查找整个列表，计算输入单词和列表中每个单词之间的Levenshtein距离，直到找到满足条件的单词（距离为0）为止，这种情况下该方法返回true值；或者当结束对单词列表的查找时没有找到单词，此时该方法返回false值。参见如下代码块：

public class ExistSerialCalculation {
  public static boolean existWord(String word, List<String>
                                  dictionary) {
    for (String str: dictionary) {
      if (LevenshteinDistance.calculate(word, str) == 0) {
        return true;
      }
    }
    return false;
  }
}

ExistSerialMain类

该类实现了main()方法，并在其中调用了existWord()方法。该类将main()方法的第一个参数作为我们要查找的单词，并且调用existWord()方法进行查找。该类还度量其执行时间并在控制台显示结果。我们给出下述代码。

public class ExistSerialMain {
  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());
  startTime=new Date();
  boolean result=ExistSerialCalculation.existWord(args[0],
                                                  dictionary);
  endTime=new Date();
  System.out.println("Word: "+args[0]);
  System.out.println("Exists: "+result);
  System.out.println("Execution Time: "+(endTime.getTime()-
                     startTime.getTime()));
  }
}

5.2.6　单词存在算法：并行版本

要实现这一操作的并发版本，我们要考虑其最重要的特征，不需要处理整个单词列表。找到符合条件的单词时，就可以完成该列表的处理并且返回结果。这一操作并不处理整个输入数据，而是满足某个条件时就会停止，这也叫作短路（short-circuit）操作。

AbstractExecutorService接口定义了一个可适应上述想法的操作（在ThreadPoolExecutor类中实现），即invokeAny()方法。该方法接收一个Callable任务列表作为参数，并且将其发送给执行器，然后返回第一个完成执行且没有抛出异常的任务作为结果。如果所有任务都抛出了异常，则该方法抛出一个ExecutionException异常。

正如前面的例子所示，为实现该版本的算法我们还实现了如下这些类。

ExistBasicTask类实现了我们将要在执行器中执行的任务。
ExistBasicConcurrentCalculation类创建了执行器和任务，并且将任务发送给执行器。
ExistBasicConcurrentMain类用于执行示例并且度量其运行时间。
ExistBasicTasks类

该类实现了搜索单词的任务。它实现了以布尔类参数化的Callable接口。如果有任务找到了单词，则其call()方法将返回true值。该类使用了如下四个内部属性。

完整的单词列表。
任务将在列表中处理的第一个单词（包括）。
任务将在列表中处理的最后一个单词（不包括）。
任务要查找的单词。
我们有如下代码。

public class ExistBasicTask implements Callable<Boolean> {
  private int startIndex;
  private int endIndex;
  private List<String> dictionary;
  private String word;
  public ExistBasicTask(int startIndex, int endIndex,
                        List<String> dictionary, String word) {
    this.startIndex=startIndex;
    this.endIndex=endIndex;
    this.dictionary=dictionary;
    this.word=word;
  }

call方法将遍历分配给该任务的那部分列表，计算输入单词和这部分列表中各单词之间的Levenshtein距离。如果找到了该单词，那么它将返回true值。

如果任务处理完分配给它的所有单词之后并没有发现要找的单词，那么它将抛出一个异常以适应invokeAny()方法的行为。在这种情况下，如果该任务返回了false值，invokeAny()方法将返回false值而无须等待剩下的任务。也许另一个任务会找到该单词。

代码如下所示。

  @Override
  public Boolean call() throws Exception {
    for (int i=startIndex; i<endIndex; i++) {
      if (LevenshteinDistance.calculate(word, dictionary.get(i))==0) {
        return true;
    }
  }
  if (Thread.interrupted()) {
    return false;
  }
  throw new NoSuchElementException("The word "+word+"
                                    doesn't exists.");
}

ExistBasicConcurrentCalculation类

该类将执行在完整单词列表中搜索输入单词的过程，创建并执行必要的任务。该类仅仅实现了一个名为existWord()的方法。该方法接收两个参数、输入字符串和完整的单词列表，并且返回一个布尔值，以表明单词是否存在。

首先，创建执行器来执行这些任务。我们使用Executor类并且创建一个ThreadPoolExecutor类，该类的最大线程数由计算机的可用硬件线程数决定，如下所示：

public class ExistBasicConcurrentCalculation {
  public static boolean existWord(String word, List<String> dictionary)
                       throws InterruptedException, ExecutionException{
    int numCores = Runtime.getRuntime().availableProcessors();
    ThreadPoolExecutor executor = (ThreadPoolExecutor)
                           Executors.newFixedThreadPool(numCores);

然后，创建与执行器中运行的线程数目相同的任务。每个任务都处理单词列表中同等的一部分。我们创建这些任务并且将其存放在一个列表中。

  int size = dictionary.size();
  int step = size / numCores;
  int startIndex, endIndex;
  List<ExistBasicTask> tasks = new ArrayList<>();
  for (int i = 0; i < numCores; i++) {
    startIndex = i * step;
  if (i == numCores - 1) {
    endIndex = dictionary.size();
  } else {
    endIndex = (i + 1) * step;
  }
  ExistBasicTask task = new ExistBasicTask(startIndex, endIndex,
                                           dictionary, word);
  tasks.add(task);
}

然后，使用invokeAny()方法在执行器中执行这些任务。如果该方法返回一个布尔值，则单词存在，就返回该值。如果该方法抛出异常，则单词不存在，我们就在控制台打印异常并且返回false值。这两种情况下，我们都调用执行器的shutdown()方法来结束其执行，如下所示：

  try {
    Boolean result=executor.invokeAny(tasks);
    return result;
  } catch (ExecutionException e) {
    if (e.getCause() instanceof NoSuchElementException)
      return false;
      throw e;
    } finally {
      executor.shutdown();
    }
  }
}

除了使用shutdown()方法，我们还可以使用shutdownNow()方法。这两个方法之间的主要区别在于，shutdown()方法在终止执行器执行之前会执行所有待执行任务，而shutdownNow()方法则不再执行待执行任务。

ExistBasicConcurrentMain类

该类实现了本例中的main()方法。它和ExistSerialMain类相当，唯一的区别在于它使用了ExistBasicConcurrentCalculation类来替代ExistSerialCalculation，因此这里不再介绍其源代码。

5.2.7　对比解决方案

让我们比较一下在本节实现的两个操作的不同解决方案（串行和并行）。我们采用JMH框架（请查看名为“Code Tools: jmh”的文章）执行这些示例，该框架允许你用Java实现微型基准测试。使用一个面向基准测试的框架是比较好的解决方案，它直接用currentTimeMillis()方法或者nanoTime()方法来度量时间。我们在两种不同的架构上分别执行这些示例10次。

一台计算机配置了Intel Core i5-5300处理器、Windows 7操作系统和16GB的RAM。该处理器有两个，且每个核可以执行两个线程，这样我们就有四个并行线程。
另一台计算机配置了AMD A8-640处理器、Windows 10操作系统和8GB的RAM。该处理器有四个核。
最佳匹配算法

在本例中，我们实现了该算法的三个版本。

串行版本。
并行版本，一次发送一个任务。
并行版本，使用invokeAll()方法。
为了测试该算法，我们用到了单词列表中不存在的三个字符串。
Stitter。
Abicus。
Lonx。
下面是最佳匹配算法为上述每个单词返回的单词列表。
Stitter：sitter、skitter、slitter、spitter、stilter、stinter、stotter、stutter和titter。
Abicus：abacus和amicus。
Lonx：lanx、lone、long、lox和lynx。
平均执行时间及其标准偏差以毫秒为单位，如下表所示。

算法Intel架构AMD架构 StitterAbicusLonxStitterAbicusLonx 串行版414.56376.34296.81708.98633.61467.03 并行版submit()方法229.56217.76173.89361.97299.26233.22 并行版invokeAll()方法257.31225.82171.98333.93324.08250.06

我们可以得出下面的结论。

在两种架构上，该算法的并行版本的性能都要比串行版本好。
该算法的两个并行版本取得了相似的结果。我们可以使用加速比来比较在查找单词Lonx时并发版本和串行版本的执行速度，由此来观察并发处理如何提升算法的性能。
$\begin{aligned}&S_{{\rm AMD}}=\frac{T_{{\rm serial}}}{T_{{\rm concurrent}}}=\frac{467.03}{232.22}=2.01\\&S_{{\rm Intel}}=\frac{T_{{\rm serial}}}{T_{{\rm concurrent}}}=\frac{296.81}{171.98}=1.72\end{aligned}$

存在算法

在本例中，我们实现了该算法的两个版本。

串行版本。
并行版本，使用invokeAny()方法。
为了测试该算法，我们用到了一些字符串。
单词列表中不存在的字符串xyzt。
在接近单词列表末端处的字符串stutter。
在接近单词列表起始处的字符串abacus。
在单词列表刚刚后一半位置处的字符串lynx。
以毫秒为单位的平均执行时间如下表所示。

算法Intel架构AMD架构单词执行时间（毫秒）单词执行时间（毫秒）串行版abacus69.79abacus94.59 lynx148.46lynx292.86 stutter336.61stutter592.102 xyzt280.93xyzt452.53 并行版abacus73.28abacus76.27 lynx100.51lynx110.51 stutter154.63stutter186.28 xyzt178.33xyzt270.37

我们可以得出下面的结论。

通常，该算法的并发版本可比串行版本提供更好的性能。
单词在列表中的位置是一个关键因素。对于单词abacus来说，它位于单词列表的起始位置，这两个版本算法的执行时间相似；但是对于单词stutter来说，二者的差别就很大了。
使用加速比来比较并发版和串行版查找单词lynx的速度，可得到如下结果。

$\begin{aligned}&S_{{\rm AMD}}=\frac{T_{{\rm serial}}}{T_{{\rm concurrent}}}=\frac{292.86}{110.51}=2.65\\&S_{{\rm Intel}}=\frac{T_{{\rm serial}}}{T_{{\rm concurrent}}}=\frac{148.46}{100.51}=1.48\end{aligned}$

5.2 第一个例子：单词最佳匹配算法