在两个字符串列表之间匹配根的算法

Question

问题:

我正在使用watch服务来监视一个目录的输入，这样我就可以在有两个(半)匹配的输入文件时触发一个事件。我遇到的问题是:如果我有两个列表，每个列表包含可能不同的字符串，我如何在列表之间找到匹配的根

文件名结构如下:

<companyname>-<ordernum><postfix>.csv

所以例如:

list1 could contain: 
    mycomp-1234.csv
    mycomp-4567.csv
    newcomp-7891.csv
    oldcomp-3376.csv
list2 could contain:
    mycomp-2232_items.csv
    newcomp-13123_items.csv
    oldcomp-87078777_items.csv
    mycomp-1234_items.csv

我想要查找，并在列表之间出现匹配时立即触发事件。匹配任何文件名，除了后缀。例如，mycomp-1234将返回两个列表的匹配项。

我在找什么

我正在寻找最有效的方法来做这件事。我知道我可以遍历每个列表来比较值，但我确信有一种更有效的方法可以做到这一点。

我不需要代码，我宁愿自己学习，所以在正确的方向推动是完美的。如果你的手指让你写代码，请写伪代码，这样可以使尽可能多的语言受益。

不，这不是家庭作业。对于那些非常好奇的人来说，这是执行从csv到X12 EDI文件的EDI转换。

Answer 1

按字母顺序对列表进行排序，然后比较值，并在值较小的列表中前进。

Answer 2

两个排序列表的并排比较。

Collections.sort(list1);
Collections.sort(list2);
int i1 = 0;
int i2 = 0;
while (i1 < list1.size() && i2 < list.size()) {
    String name1 = list1.get(i1);
    String name2 = list2.get(i2);
    String[] parts1 = name1.split("[-_.]");
    String[] parts2 = name2.split("[-_.]");
    if (parts1.length < 3) {
        ++i1;
        continue;
    }
    if (parts2.length < 3) {
        ++i2;
        continue;
    }
    int cmp = parts1[0].compareTo(parts1[0]);
    if (cmp == 0) {
        cmp = parts1[1].compareTo(parts1[1]);
    }
    if (cmp < 0) {
        ++i1;
        continue
    }
    if (cmp > 0) {
        ++i2;
        continue
    }
    // Found match:
    ...
    ++i1;
    ++i2;
}

Answer 3

一个在线方法:维护一个包含所有当前文件名的二叉搜索树。使用文件名的相关位作为键。例如，newcomp-7891.csv或newcomp-7891_items的关键字为newcomp-7891。每次watch服务报告一个目录事件时，您都可以删除不再使用的名称，并尝试向树中添加新名称。如果键已经在树中，则触发所需的事件。

哈希表也可以类似地使用，如果哈希实现支持在删除文件名时删除键。

这个问题问的是"做这件事最有效的方式"。请注意，这种方法比每次发生目录事件时从头开始对列表进行排序要有效得多。在有k个添加和删除的事件中，如果数据集有n个条目，它将使用O(k·lg n)时间，因此在平均树大小为n并且发生m个添加/删除的一段时间内，在u个目录事件中，它将做O(m·lg n)的工作。相比之下，在其他答案中建议的每次排序方法将做O(u·n·lgn)的工作，这要多得多。