列表推导式查找多行重复块问题：blockSize≥4时匹配异常

问题描述 #

需要识别一组文件中的重复代码块，将所有文件的行读取到list[str]中进行分析。一个块由若干连续行组成，变量blockSize表示块的行数。定义的列表推导式在blockSize为2或3行时能正常工作，但当blockSize≥4行时失效，仅能找到第一个匹配项（即自身）。

相关代码片段：

list[str] searchFor = (linesToCheck[lineIndex..lineIndex+blockSize]);
list[int] theMatches = [ a | a <- [lineIndex..(totalLines-blockSize+1)], linesToCheck[a..(a+blockSize)] == searchFor ] ;

逻辑是从lineIndex=0开始，取blockSize行，检查其在文件中的出现次数。当blockSize为2或3时能找到正确的重复数，≥4时仅能找到当前lineIndex对应的块。

测试用完整代码：

module duplication::myTest

import IO;
import List;
import String;

void myTest() {
  list[str] linesToCheck = 
    ["line a","line bb","line ccc","line dddd","line eeeee","line ffffff",
     "line a","line bb","line ccc","line dddd","line eeeee","line ffffff",
     "line a","line bb","line ccc","line dddd","line eeeee","line ffffff"];

  int blockSize = 3;
  int lineIndex = 0;
  int totalLines = size(linesToCheck);
  list[int] duplicates = [];        // to store index of duplicate lines

  while (lineIndex < (totalLines - blockSize)) {
    if (lineIndex in duplicates) {  // this lines has already been counted as a duplicate
      lineIndex += 1;
      continue;
    }
    list[str] searchFor = (linesToCheck[lineIndex..lineIndex+blockSize]);

    list[int] theMatches = [ a | a <- [lineIndex..(totalLines-blockSize+1)], linesToCheck[a..(a+blockSize)] == searchFor ] ;
    int count = size(theMatches);
    println("LineIndex = <lineIndex> ; matches = <theMatches> ; \t(result for <searchFor>) ");

    if (count == 1) {   // no duplicates
      lineIndex += 1;
    }
    else if (count >= 2) {
      for (match <- theMatches) {
        if (match == lineIndex)       // skip the current one
          continue;
        duplicates += [ a | a <- [match..match+blockSize] ] ; // store index of duplicate lines
      }
      lineIndex += blockSize;
    }
    else if (count == 0) {
      println("ERROR: count == 0; This should not have happened!!!!");
      lineIndex += 1;
    }
  }
}

问题分析与修复方案 #

错误原因 #

核心问题出在列表推导式的匹配逻辑和循环边界：

1. 当blockSize≥4时，部分a值对应的切片linesToCheck[a..(a+blockSize)]会超出列表长度，导致切片长度不足blockSize，与searchFor比较时返回false，仅自身切片能完全匹配。
2. while循环的终止条件lineIndex < (totalLines - blockSize)会漏掉最后一个有效块（当lineIndex = totalLines - blockSize时，仍可取出完整的blockSize行）。

修复步骤 #

1. 添加切片长度校验：在列表推导式中增加条件，确保只有长度等于blockSize的切片才参与比较，避免无效匹配。
2. 修正循环终止条件：改为lineIndex <= (totalLines - blockSize)，覆盖所有有效块的起始索引。
3. 优化重复行存储：使用union方法去重，避免duplicates列表中出现重复索引，提升判断准确性。

修改后的完整代码 #

module duplication::myTest

import IO;
import List;
import String;

void myTest() {
  list[str] linesToCheck = 
    ["line a","line bb","line ccc","line dddd","line eeeee","line ffffff",
     "line a","line bb","line ccc","line dddd","line eeeee","line ffffff",
     "line a","line bb","line ccc","line dddd","line eeeee","line ffffff"];

  int blockSize = 4; // 可测试任意blockSize值
  int lineIndex = 0;
  int totalLines = size(linesToCheck);
  list[int] duplicates = [];        // to store index of duplicate lines

  // 修正循环终止条件：包含最后一个有效块的起始索引
  while (lineIndex <= (totalLines - blockSize)) {
    if (lineIndex in duplicates) {  // 跳过已标记为重复的块起始行
      lineIndex += 1;
      continue;
    }
    list[str] searchFor = linesToCheck[lineIndex..lineIndex+blockSize];

    // 修正列表推导式：添加切片长度检查，确保仅比较完整的blockSize行
    list[int] theMatches = [ 
      a | a <- [lineIndex..(totalLines - blockSize + 1)], 
      size(linesToCheck[a..a+blockSize]) == blockSize, 
      linesToCheck[a..a+blockSize] == searchFor 
    ] ;
    int count = size(theMatches);
    println("LineIndex = <lineIndex> ; matches = <theMatches> ; \t(result for <searchFor>) ");

    if (count == 1) {   // 无重复，移动到下一行
      lineIndex += 1;
    }
    else if (count >= 2) {
      for (match <- theMatches) {
        if (match == lineIndex)       // 跳过当前块
          continue;
        // 合并重复行索引并去重
        duplicates = union(duplicates, [a | a <- [match..match+blockSize]]);
      }
      lineIndex += blockSize;
    }
    else if (count == 0) {
      println("ERROR: count == 0; This should not have happened!!!!");
      lineIndex += 1;
    }
  }
}

关键修改点说明 #

• 列表推导式中新增size(linesToCheck[a..a+blockSize]) == blockSize条件，过滤掉长度不足的无效切片，确保只有完整的块参与比较。
• while循环条件改为lineIndex <= (totalLines - blockSize)，覆盖所有能取出完整blockSize行的起始索引。
• 使用List::union合并重复行索引，避免duplicates列表中出现重复值，提升后续跳过重复块的判断效率。

内容的提问来源于stack exchange，提问作者Ad Versteeg