关于算法:生产就绪的算法以随机句子为例

26次阅读

共计 12512 个字符，预计需要花费 32 分钟才能阅读完成。

本文记述笔者的算法学习心得，因为笔者不相熟算法，如有谬误请不吝指正。

随机句子问题

这几天得见一个算法题：生成随机句子。揣测这道题可能来源于某搜索引擎公司的工作实际？

题意为：输出一个句子（即一个单词序列）和一个预期长度，需从输出句子随机抽取单词组成一个新句子（只是一个单词序列，不思考语法），新句子的单词数量等于预期长度。随机抽取的具体规定为：随机取一个单词作为首个单词退出新句子，每当新句子退出一个单词，对于这个单词在输出句子中的所有呈现地位，随机抉择一个呈现地位的下一个单词（即下邻单词）退出新句子，这一退出又会引起新单词的退出，由此类推，直到新句子达到预期长度，则输入新句子。也就是要实现一个函数 String generateSentence(String sentence, int length)。

例如，输出 sentence=”this is a sentence it is not a good one and it is also bad” length=5，若 ”sentence” 被选为首个单词，则下一个单词只有一个抉择 ”it”，而后 ”it” 的下一个单词能够在两个地位抉择，但这两个地位都刚好是 ”is”，而 ”is” 的下一个单词就能够抉择 ”not” 或 ”also”，若抉择 ”not”，则下一个单词只有一个抉择 ”a”，此时凑足了 5 个单词，失去新句子 ”sentence it is not a”。

以上是此题的根底版，它还有一个难度加强版：对现有规定做一个批改，再给定一个输出 m，首次随机取输出句子的间断 m 个单词退出新句子，之后每次仍退出一个单词，每当新句子退出一个单词，不再是找到这个单词在输出句子中的呈现地位，而是对于新句子的“最初 m 个单词所造成的词组”在输出句子中的所有呈现地位，随机抉择一个呈现地位的下邻单词退出新句子。根底版可看做 m = 1 的非凡状况。

根底版的解法

解法基本上遵循如此构造：

  1. 将输出句子转换为单词序列(String -> String[]，即 tokenize)，为新句子筹备一个内存缓冲区。
  2. 随机抉择首个单词，放入内存缓冲区。
  3. 循环搜寻上一个被抉择的单词在输出句子中的所有地位，随机抉择一个地位，将其下邻单词放入内存缓冲区，直到新句子达到预期长度，则进行并输入新句子。

留神，把输出句子当作一个环，若搜寻到输出句子的句尾单词，则其下邻单词是句首单词，即从句尾跳回了句首。为了在计算下邻地位时做环跳转的解决，我起初是这么写的（在越界时减一次句子总长）：

int nextPos(int pos, String[] words) {
  int next = pos + 1;
  if (next >= words.length) {next -= words.length;}
  return next;
}

起初据说取模就能够了，即：

int nextPos(int pos, String[] words) {return (pos + 1) % words.length;
}

对于根底版，减法是 OK 的，但对于难度加强版呢？如果 m >= 输出句子长度（尽管这种输出不是很正当），则下邻地位可能跨环两次，须要减两次才正确。因而，取模的确更简洁优雅，更 sound。

当初介绍三种算法实现。第一种是暴力搜寻法，每次遍历输出句子，找到给定单词的所有地位。第二种是优化搜寻法，对暴力搜寻法做了优化，每次不是找到给定单词的所有地位，而是从一个随机地位起步，找到给定单词的某一个地位。第三种是哈希索引法，为输出句子预构建一个哈希表，能疾速查找任一个单词对应的下邻单词。

要提前申明，优化搜寻法的随机抉择可能是不偏心的。例如，间断 2 个雷同单词如 ”go go”，从左到右的搜寻简直总会选中右边那个。这个问题能解决，每次随机决定搜寻方向即可（从左到右或从右到左）。然而，间断 3 个雷同单词如 ”go go go “ 呢？两头的单词被选中的概率微不足道。我想过”素数跳跃搜寻法“等办法，但都没有解决，因而优化搜寻法无奈成为支流算法。

暴力搜寻法的实现代码

class Solution1 {public static void main(String[] args) {
    System.out.println(generateSentence("this is a sentence it is not a good one and it is also bad", 5));
  }

  public static String generateSentence(String sentence, int length) {String[] words = sentence.split(" ");
    if (words.length == 0) {return sentence;}

    List<String> newWords = new ArrayList<>();

    int randIdx = new Random().nextInt(words.length);
    String prev = words[randIdx];
    newWords.add(prev);

    for (int i = 1; i < length; i++) {List<Integer> nexts = searchNexts(words, prev);
      int chosen = new Random().nextInt(nexts.size());
      String chosenWord = words[nexts.get(chosen)];
      newWords.add(chosenWord);
      prev = chosenWord;
    }

    return String.join(" ", newWords);
  }

  // 在 words 中找到 prev 的所有呈现地位，收集其下邻地位(nexts)
  private static List<Integer> searchNexts(String[] words, String prev) {List<Integer> nexts = new ArrayList<>();
    for (int i = 0; i < words.length; i++) {if (words[i].equals(prev)) {nexts.add(nextPos(i, words));
      }
    }

    return nexts;
  }

  private static int nextPos(int pos, String[] words) {return (pos + 1) % words.length;
  }
}

优化搜寻法的实现代码

class Solution1 {public static void main(String[] args) {
    System.out.println(generateSentence("this is a sentence it is not a good one and it is also bad", 5));
  }

  public static String generateSentence(String sentence, int length) {String[] words = sentence.split(" ");
    if (words.length == 0) {return sentence;}

    List<String> newWords = new ArrayList<>();

    int randIdx = new Random().nextInt(words.length);
    String prev = words[randIdx];
    newWords.add(prev);

    for (int i = 1; i < length; i++) {String chosenWord = randomNextWord(words, prev);
      newWords.add(chosenWord);
      prev = chosenWord;
    }

    return String.join(" ", newWords);
  }

  private static String randomNextWord(String[] words, String prev) {int randomBeginIndex = new Random().nextInt(words.length);

    for (int _i = 0; _i < words.length; _i++) {int idx = (randomBeginIndex + _i) % words.length;
      if (words[idx].equals(prev)) {return words[nextPos(idx, words)];
      }
    }

    return null;
  }

  private static int nextPos(int pos, String[] words) {return (pos + 1) % words.length;
  }
}

哈希索引法的实现代码

class Solution1 {public static void main(String[] args) {
    System.out.println(generateSentence("this is a sentence it is not a good one and it is also bad", 5));
  }

  public static String generateSentence(String sentence, int length) {String[] words = sentence.split(" ");
    if (words.length == 0) {return sentence;}

    Table table = new Table(words);

    List<String> newWords = new ArrayList<>();

    int randIdx = new Random().nextInt(words.length);
    String prev = words[randIdx];
    newWords.add(prev);

    for (int i = 1; i < length; i++) {String chosenWord = table.randomNextWord(prev);
      newWords.add(chosenWord);
      prev = chosenWord;
    }

    return String.join(" ", newWords);
  }

  private static int nextPos(int pos, String[] words) {return (pos + 1) % words.length;
  }

  static class Table {private Map<String, List<String>> map = new HashMap<>();

    Table(String[] words) {for (int i = 0; i < words.length; i++) {List<String> nexts = map.computeIfAbsent(words[i], key -> new ArrayList<>());
        nexts.add(words[nextPos(i, words)]);
      }
    }

    String randomNextWord(String word) {List<String> nexts = map.get(word);
      int chosen = new Random().nextInt(nexts.size());
      return nexts.get(chosen);
    }
  }
}

哈希索引法引入一个 Table 构造来封装建表和查问的逻辑，岂但实践上更高效，代码也更易了解。
算法复杂度怎么剖析呢？设 n =words.length，l=length，则：

  1. 暴力搜寻法次要花工夫在 n 次迭代中每次都要遍历搜寻 n 个单词，工夫复杂度为 O(n^2 + l)，空间复杂度为 O(1)。
  2. 优化搜寻法次要花工夫在 n 次迭代中每次都要遍历搜寻均匀 n /(k+1)个单词，k 为被搜寻单词的呈现次数（只呈现一次时 k =1，则均匀遍历 n / 2 个单词，即半个句子），工夫复杂度为 O(n^2/k + l)，空间复杂度为 O(1)。k 个别比拟小，因而只是常数级优化，实际效果待测试。
  3. 哈希索引法次要花工夫在构建一个大小为 n 的哈希表，工夫复杂度为 O(n + l)，空间复杂度为 O(n)。事实上，如果对于雷同输出重复调用，因为哈希表能够重用，其工夫老本摊销后可忽略不计，即 O(1)。

难度加强版的解法

解法基本上遵循如此构造：

  1. 将输出句子转换为单词序列(String -> String[]，即 tokenize)，为新句子筹备一个内存缓冲区。
  2. 随机抉择间断 m 个单词，放入内存缓冲区。
  3. 循环搜寻新句子“最初 m 个单词所造成的词组”在输出句子中的所有地位，随机抉择一个地位，将其下邻单词放入内存缓冲区，直到新句子达到预期长度，则进行并输入新句子。

若用 m 作为输出参数的变量名，岂不毫无含意？按 m 的语义，此变量可名为 lookBack，即“回向查看的项数”（在此顺带一提，编译器的语法分析有一概念叫 lookAhead，即“前向查看的项数”）。

当初，咱们发现能够重构代码，使其更平安优雅：解决环跳转时，对 nextPos 取模是怕数组越界，既然如此，那就对数组拜访都加一道平安防线，数组偏移量都取模不就好了么！
设计这个可复用的数组拜访助手函数以代替 nextPos 函数：

String safeGetWord(String[] words, int index) {return words[index % words.length];
}

当初再次实现三种算法。

暴力搜寻法的实现代码

class Solution2 {public static void main(String[] args) {
    System.out.println(generateSentence("this is a sentence it is not a good one and it is also bad", 5, 2));
  }

  public static String generateSentence(String sentence, int length, int lookBack) {String[] words = sentence.split(" ");
    if (words.length == 0) {return sentence;}
    if (lookBack > length) {throw new IllegalArgumentException("lookBack exceeds length");
    }

    List<String> newWords = new ArrayList<>();

    generateLeading(newWords, words, lookBack);

    for (int _i = lookBack; _i < length; _i++) {List<String> prevs = newWords.subList(newWords.size() - lookBack, newWords.size());
      List<Integer> nexts = searchNexts(words, prevs);

      int chosen = new Random().nextInt(nexts.size());
      String chosenWord = safeGetWord(words, nexts.get(chosen));
      newWords.add(chosenWord);
    }

    return String.join(" ", newWords);
  }

  // 生成最后的几个单词
  private static void generateLeading(List<String> newWords, String[] words, int lookBack) {int randIdx = new Random().nextInt(words.length);
    for (int i = 0; i < lookBack; i++) {newWords.add(safeGetWord(words, randIdx + i));
    }
  }

  private static List<Integer> searchNexts(String[] words, List<String> prevs) {List<Integer> nexts = new ArrayList<>();

    for (int i = 0; i < words.length; i++) {
      // 试匹配一个词组
      int matchedCount = 0;

      for (int j = 0; j < prevs.size(); j++) {if (!safeGetWord(words, i + j).equals(prevs.get(j))) {
          matchedCount = -1;
          break;
        }

        matchedCount++;
      }

      if (matchedCount == prevs.size()) {nexts.add(i + prevs.size());
      }
    }

    return nexts;
  }

  private static String safeGetWord(String[] words, int index) {return words[index % words.length];
  }
}

优化搜寻法的实现代码

class Solution2 {public static void main(String[] args) {
    System.out.println(generateSentence("this is a sentence it is not a good one and it is also bad", 5, 2));
  }

  public static String generateSentence(String sentence, int length, int lookBack) {String[] words = sentence.split(" ");
    if (words.length == 0) {return sentence;}
    if (lookBack > length) {throw new IllegalArgumentException("lookBack exceeds length");
    }

    List<String> newWords = new ArrayList<>();

    generateLeading(newWords, words, lookBack);

    for (int ig = lookBack; ig < length; ig++) {List<String> prevs = newWords.subList(newWords.size() - lookBack, newWords.size());
      String chosenWord = randomNextWord(words, prevs);
      newWords.add(chosenWord);
    }

    return String.join(" ", newWords);
  }

  // 生成最后的几个单词
  private static void generateLeading(List<String> newWords, String[] words, int lookBack) {int randIdx = new Random().nextInt(words.length);
    for (int i = 0; i < lookBack; i++) {newWords.add(safeGetWord(words, randIdx + i));
    }
  }

  private static String randomNextWord(String[] words, List<String> prevs) {int randomBeginIndex = new Random().nextInt(words.length);

    for (int _i = 0; _i < words.length; _i++) {
      int idx = randomBeginIndex + _i;
      // 试匹配一个词组
      int matchedCount = 0;

      for (int j = 0; j < prevs.size(); j++) {if (!safeGetWord(words, idx + j).equals(prevs.get(j))) {
          matchedCount = -1;
          break;
        }

        matchedCount++;
      }

      if (matchedCount == prevs.size()) {return safeGetWord(words, idx + prevs.size());
      }
    }

    return null;
  }

  private static String safeGetWord(String[] words, int index) {return words[index % words.length];
  }
}

哈希索引法的实现代码

class Solution2 {public static void main(String[] args) {
    System.out.println(generateSentence("this is a sentence it is not a good one and it is also bad", 5, 2));
  }

  public static String generateSentence(String sentence, int length, int lookBack) {String[] words = sentence.split(" ");
    if (words.length == 0) {return sentence;}
    if (lookBack > length) {throw new IllegalArgumentException("lookBack exceeds length");
    }

    Table table = new Table(words, lookBack);

    List<String> newWords = new ArrayList<>();

    generateLeading(newWords, words, lookBack);

    for (int ig = lookBack; ig < length; ig++) {Phrase phrase = new Phrase(newWords.subList(newWords.size() - lookBack, newWords.size()));
      String chosenWord = table.randomNextWord(phrase);
      newWords.add(chosenWord);
    }

    return String.join(" ", newWords);
  }

  private static void generateLeading(List<String> newWords, String[] words, int lookBack) {int randIdx = new Random().nextInt(words.length);
    for (int i = 0; i < lookBack; i++) {newWords.add(safeGetWord(words, randIdx + i));
    }
  }

  private static String safeGetWord(String[] words, int index) {return words[index % words.length];
  }

  static class Phrase {
    private List<String> elements;

    Phrase(List<String> elements) {Objects.requireNonNull(elements);
      // TODO 该当拷贝一份以确保不可变性
      this.elements = elements;
    }

    Phrase(int lookBack, String[] words, int beginIndex) {elements = new ArrayList<>(lookBack);
      for (int j = 0; j < lookBack; j++) {elements.add(safeGetWord(words, beginIndex + j));
      }
    }

    @Override
    public boolean equals(Object o) {if (this == o) return true;
      if (!(o instanceof Phrase)) return false;
      Phrase phrase = (Phrase) o;
      return elements.equals(phrase.elements);
    }

    @Override
    public int hashCode() {return elements.hashCode();
    }
  }

  static class Table {private Map<Phrase, List<String>> map = new HashMap<>();

    Table(String[] words, int lookBack) {for (int i = 0; i < words.length; i++) {Phrase phrase = new Phrase(lookBack, words, i);

        List<String> nexts = map.computeIfAbsent(phrase, key -> new ArrayList<>());
        nexts.add(safeGetWord(words, i + lookBack));
      }
    }

    String randomNextWord(Phrase phrase) {List<String> nexts = map.get(phrase);
      int chosen = new Random().nextInt(nexts.size());
      return nexts.get(chosen);
    }
  }
}

这一回，哈希索引法又引入了一个 Phrase 构造来作为 HashMap key。为什么不间接用 List<String> 作为 key 呢？有两个起因：

  1. 可读性更好。
  2. key 该当是不可变的（immutable），若写入 HashMap 用的 key 值不同于查问用的 key 值，就会查问不到数据。Phrase 是一个不可变对象，将 List<String> 封装了起来。
  3. Phrase 的 hashCode 办法是能够批改的，将来能够优化它以进步性能。当初的 hashCode 是用 List<String> 实现的，算法全程的 hashCode 计算成本为 O(mn)，m 即 lookBack。String 会缓存 hashCode，因而次要老本在于将每个 String 的 hashCode 相加，其实性能还好。

算法复杂度怎么剖析呢？设 n =words.length，l=length，m=lookBack，则：

  1. 暴力搜寻法，工夫复杂度为 O(mn^2 + l)，空间复杂度为 O(1)。
  2. 优化搜寻法，工夫复杂度为 O(mn^2/k + l)，空间复杂度为 O(1)。
  3. 哈希索引法次要花工夫在构建一个大小为 n 的索引表，工夫复杂度为 O(mn + l)，空间复杂度为 O(mn)。

向生产就绪进发

以上的算法达到生产就绪 (production ready) 了吗？让咱们来考查。

正确性

优化搜寻法因为某些状况不偏心，在满足性能需要上有所折扣。哈希索引法既高效又易了解，容易正确实现，预计适宜用于生产环境。

算法的实现正确吗？须要做功能测试。算法很适宜单元测试，然而蕴含随机数，怎么稳固重现呢，更特地地说，怎么确保测到边界条件呢？
就不放代码了，只说最重要的问题：怎么稳固重现，乃至确保测到边界条件。
答案很简略：该当 mock 随机数。将用于生成随机数的代码抽成一个函数，在单元测试中将它 mock 为返回确定的数值。这是因为随机性质不须要放在一起测试，须要被测试的是其余性质。

随机性

留神，随机数的生成要引入熵，才有足够的随机性。以 Java 的 Random 伪随机数为例，若全程共用一个 Random 对象，就只是伪随机，若屡次 new Random()，因为两头的间隔时间可能随机稳定，就引入了工夫熵，失去真随机数。也能够全程共用一个 SecureRandom 对象，这个能提供真随机数，然而速度稍慢一些。

性能

哈希索引法在实践上快 n 倍，理论有多快呢？
理论性能如何，该当做性能测试，俗话说跑个分（benchmark）。
咱们做一个小的性能测试，再做一个大的性能测试，以暴力搜寻法为基准来评估性能。

小的性能测试（测试代码略）：
将例句反复 8 遍失去一个 8 倍长的句子，其余参数不变（length=5，lookBack=2）。将算法预热 5 万遍，再执行 20 万遍，屡次测试取平均值。（20 万遍）破费工夫如下：

  1. 根本版：

    1. 暴力搜寻法：1358ms
    2. 优化搜寻法：850ms
    3. 哈希索引法：（不重用哈希表）1212ms，（重用哈希表）699ms

  2. 难度加强版：

    1. 暴力搜寻法：1186ms
    2. 优化搜寻法：480ms
    3. 哈希索引法：（不重用哈希表）1032ms，（重用哈希表）382ms

后果让人诧异，哈希索引法（不重用哈希表）没有显著快于基准（暴力搜寻法）！优化搜寻法令体现很好，简直快 1 倍！
可能是数据量太小，没有施展哈希表的劣势，那么试一试更大数据量吧！

大的性能测试：
加大数据量，将例句随机重排词序，并反复 100 遍失去一个 100 倍长的句子，length=100，lookBack=2。将算法预热 1 千遍，再执行 5 千遍，屡次测试取平均值。
测试代码要简单一些，因而提供代码如下：

public static void main(String[] args) {
  String sentence = "this is a sentence it is not a good one and it is also bad";
  sentence = times(sentence, 100);

  // 预热
  for (int i = 0; i < 1000; i++) {
    generateSentence(sentence, 100, 2);
  }

  // 测试
  long start = System.currentTimeMillis();
  for (int i = 0; i < 5000; i++) {
    generateSentence(sentence, 100, 2);
  }
  long cost = System.currentTimeMillis() - start;
  System.out.println(cost);
}

// 生成长句子
static String times(String input, int n) {List<String> buffer = new ArrayList<>();
  List<String> words = Arrays.asList(input.split(" "));
  for (int i = 0; i < n; i++) {Collections.shuffle(words);
    buffer.addAll(words);
  }
  return String.join(" ", buffer);
}

（5 千遍）破费工夫如下：

  1. 根本版：

    1. 暴力搜寻法：4600ms
    2. 优化搜寻法：450ms
    3. 哈希索引法：（不重用哈希表）500ms，（重用哈希表）405ms

  2. 难度加强版：

    1. 暴力搜寻法：10000ms
    2. 优化搜寻法：1000ms
    3. 哈希索引法：（不重用哈希表）1000ms（重用哈希表）420ms

总算施展了哈希索引法的劣势！
在这个数据量，优化搜寻法依然不亚于哈希索引法，而且空间复杂度更优！
如果能从实践上解释这一景象，那就更好了。怎么解释呢？因为是把例句（无论是否随机重排词序）反复 100 遍生成的输出句子，使得优化搜寻法的 k≥100，当然会性能很好啊。那么试一试大量生成随机单词，以升高 k 值：优化搜寻法的性能升高了一半，哈希索引法不受影响。

顺便测试了对 hashCode 的优化，若 Phrase 只计算第一个单词的 hashCode，当 lookBack= 2 时性能无晋升，当 lookBack=20 时性能晋升 8%。

论断

哈希索引法的高效性、高稳定性、易了解性，使其成为生产环境的首选。留神几个问题：空间复杂度、哈希表只能对雷同输出重用、随机性、key 不可变、hashCode 可优化。
优化搜寻法的乏味性，使其值得进一步钻研。

正文完
算法
发表至： 算法
2021-08-08
 0
关于算法:个推漫话数据智能-天才基本法中的贝叶斯网络及原理解读
关于算法:R语言JAGS贝叶斯回归模型分析博士生延期毕业完成论文时间
关于算法:动态规划之正则表达
关于自然语言处理:用-RTC-打造一个音乐教育-App需要解决哪些音质难题