如何计算对的数量并找到未配对的？

Question

我有一个关于文本处理的问题，但没有可靠的想法。

有一个包含所有程序执行信息的日志文件，例如：

12:34:21 End   ./calc
12:34:25 Start ./gemm
12:34:26 Start ./gemm
12:34:27 Start ./jacobi
12:34:46 End   ./gemm
12:34:51 Start ./fab
12:35:02 End   ./jacobi

所以在这种情况下，我试图为特定程序找到 "Start" 和 "End" 对。例如，jacobi 会配对，因为它有开始和结束。 fab 没有配对，因为我们找不到它的结束信息。 gemm 有两个起点和一个终点。因此，Start 之一配对。我可以设置一个规则，比如说，先执行先完成，然后第二行 gemm 不配对。 calc 没有配对，因为它没有开始信息。

使用bash，我可以grep开始或结束，然后对结果进行排序和比较。真的不认为这是一个可靠的解决方案。有什么想法吗？

提供bash代码就好，算法也欢迎！

预期输出：

12:34:21 End   ./calc     (unpaired)
12:34:25 Start ./gemm     (paired)
12:34:26 Start ./gemm     (unpaired)
12:34:27 Start ./jacobi   (paired)
12:34:46 End   ./gemm     (paired)
12:34:51 Start ./fab      (unpaired)
12:35:02 End   ./jacobi   (paired)

谢谢。

Answer 1

您可以在 bash v4 中使用关联数组以与以下小 awk 程序完全相同的方式执行此操作，但 awk 程序更容易一些并且不依赖于您是否有新的bash版本。

它基本上为第三个字段的每个值设置了一个队列。 Start 条目的行号被添加到队列的末尾。当遇到 End 时，如果可能的话，Start 条目被移出队列的前面，并且两个条目都被标记为匹配。

awk '
  { line[NR] = [=10=]; s = start[] }
  =="End" && s {
      matched[s] = 1; matched[NR] = 1; start[] = link[s]
  }
  =="Start" {
      if (s) link[end[]] = NR; else start[] = NR;             
      end[] = NR;
  }    
  END {
      for (i = 1; i <= NR; ++i)
          printf "%s (%spaired)\n", line[i], matched[i] ? "" : "un"
  }'

如何计算对的数量并找到未配对的？

How to count the number of pairs and find the unpaired one?

algorithm

bash

shell

pattern-matching