有没有更有效的方法来检查大文件中一行是否以另一行结尾

Question

我有一个包含 500,000 行的文件，我想检查每一行 L 同一文件中是否有任何其他行以 L[=25 结尾=].

我已经按照行的长度对文件进行了排序，并编写了以下代码，但是速度很慢：

def main(args: Array[String]): Unit = { val buffer = new BufferedReader(new FileReader("input.txt")) val fw = new FileWriter("output.txt") var line = buffer.readLine() var list = List.empty[String] while (line != null) { if (line.nonEmpty) { list += line } line = buffer.readLine() } buffer.close() list = list.sortBy(s => s.length) for (i <- list.indices) { val endsWith = list(i) for (j <- i + 1 until list.size) { val right = list(j) if (right.endsWith(endsWith)) { fw.write(list(j) + ";" + list(i) + "\n") fw.flush() } } println(i + 1) } fw.close() }

输入文件包含如下条目：
abc/defg
defg
...

有没有更有效的检查线路的方法？

Answer 1

您需要以特定方式对文件进行排序。

尝试下一个算法：

反转每行。
排序列表。
遍历列表并针对每个相邻对检查较短的是否是较长的开始。

Answer 2

我找到了解决问题的方法，方法是使用每行的长度 L 并从其他行中提取该长度。之后，我对 L 和提取的字符串进行哈希处理，并将它们存储在哈希映射中。最后，我检查映射是否包含查询哈希。一旦两条线的长度相同，我只需要检查映射中的散列，这为我节省了很多开销。我还使用了 talex 的想法在散列之前反转每个字符串。

这里是解决方案的代码：

def main(args: Array[String]): Unit = {
    val buffer = new BufferedReader(new FileReader("input.txt"))
    val fw = new FileWriter("output.txt")
    var line = buffer.readLine()
    var map = Map.empty[Int, List[String]]
    while (line != null) {
      if (line.nonEmpty) {
        val len = line.length
        map += len -> (map.getOrElse(len, List.empty[String]) ++ List(line.reverse))
      }
      line = buffer.readLine()
    }
    buffer.close()
    val list = map.keySet.toList.sorted
    for (i <- list.indices) {
      val len = list(i)
      var cutMap = Map.empty[Int, List[String]]
      for (j <- i + 1 until list.size) {
        for (right <- map(list(j))) {
          val took = right.take(len)
          cutMap += took.hashCode -> (cutMap.getOrElse(took.hashCode, List.empty[String]) ++ List(right))
        }
      }
      for (startsWith <- map(len)) {
        val hashCode = startsWith.hashCode
        if (cutMap.contains(hashCode)) {
          for (right <- cutMap(hashCode)) {
            fw.write(right.reverse + ";" + startsWith.reverse + "\n")
            fw.flush()
          }
        }
      }
      println(i + 1)
    }
    fw.close()
  }

如果hashCode函数不够精确，可以用更精确的函数代替。对于更大的文件，可以分离算法以使用文件拆分。

有没有更有效的方法来检查大文件中一行是否以另一行结尾

Is there a more efficient way to check whether one line ends with another line in a large file

scala

large-files

ends-with