计算一个数组列表中出现在另一个数组列表中的对象元素的数量

Question

我有两个数组列表保存TCP流对象从pcap文件。一个列表是包含找到的每个唯一数据包的引用列表(没有重复，只有找到的每个唯一数据包)。另一个列表是Flow对象的列表，它们的流在我的程序中被标记为已完成。

我的目标:使用参考列表，计算数据包在完成的流列表中出现的次数或频率。

TCP Flow Object定义如下:

public class Flow {
String destIp;
String sourceIp;
String destPort;
String srcPort;
double arrivalTime;
int completed;
}

每个TCP流对象可以通过destIp, sourceIp, destPort,和srcPort来识别。

我以前发现我可以在集合中使用频率方法，但我必须使用4个不同的元组来识别一行，而不仅仅是一行。我最初的计划是创建一个嵌套的for循环，检查参考列表中的数据包，然后检查完整流列表中的每个数据包，例如:

for(Flow referenceList : refList) {
for(Flow compList : cList) {
if tuples match the one in cList add to count
}
}

是否有更简单或更有效的方法来完成这一点?

Answer 1

需要的时间是N*M，其中N和M是这两个列表的大小。这很贵，快。两个列表各有10k个条目，这将开始花费非常非常长的时间。

假设这些列表并不小，那么您的数据类型就混乱了。如果其中一个是Set，这就是O(M)，那么它只需要大约10k步，这就好得多了。你只发出一次且所有都是唯一的，听起来应该是Set。

无论您走哪条路，必须在这个Flow类上有一个实际的hashCode()和equals()方法。您可以在网上搜索如何编写它们的教程，或者让IDE为您制作它们，或者使用Project Lombok为您制作它们。

Answer 2

您可以使用Map来完成O(n)时间，并将中间计数保存到它。不需要使用两次for

public static class Flow {
String destIp;
String sourceIp;
String destPort;
String srcPort;
double arrivalTime;
int completed;
}
public static void main(String... args) {
Function<Flow, String> getKey = flow ->
String.format("%s|%s|%s|%s",
flow.sourceIp, flow.srcPort, flow.destIp, flow.destPort);
List<Flow> refList = List.of();
List<Flow> cList = List.of();
Map<String, Long> histogram = histogram(refList, cList, getKey);
}
public static Map<String, Long> histogram(List<Flow> refList,
List<Flow> cList, Function<Flow, String> getKey) {
Map<String, Long> map =
refList.stream()
.map(getKey)
.collect(Collectors.groupingBy(Function.identity(),
Collectors.counting()));

Map<String, Long> res = new HashMap<>();
cList.stream()
.map(getKey)
.filter(map::containsKey)
.forEach(key -> res.put(key, map.get(key) + 1));
return map;
}