2

问题：

我正在使用监视服务来监视输入目录，因此一旦我有两个（半）匹配的输入文件，我就可以触发事件。我遇到的问题是：如果我有两个列表，每个列表都包含可能不同的字符串，我如何在列表之间找到匹配的根。

文件名结构如下所示：

<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 转换。

4

3 回答 3

3

按字母顺序对列表进行排序，然后比较值并在具有较小值的列表中前进。如果列表有任何共同的元素，则值将匹配。

于 2013-05-07T14:33:47.403 回答
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;
}
于 2013-05-07T14:41:56.973 回答
-1

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

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

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

于 2013-05-07T15:58:33.920 回答