在arraylist中查找与正则表达式匹配的项

Question

我正在尝试开发一个函数，该函数读取string的ArrayList，并且能够查找是否存在至少两个元组，它们从一组索引中具有相同的值，但对于一个补充索引不同。我通过使用正则表达式比较开发了这个函数的一个版本，如下所示：

java prettyprint-override">    public boolean checkMatching(){
        ArrayList<String> rows = new ArrayList<String>();
        rows.add("7,2,2,1,1");
        rows.add("7,3,2,1,1");
        rows.add("7,8,1,1,1");
        rows.add("8,2,1,3,1");
        rows.add("8,2,1,4,1");
        rows.add("8,4,5,1,1");

        int[] indices = new int[] {2,3};
        int supplementaryIndex = 1;

        String regex = "";
        for(String r : rows){
            String[] rt = r.split(",");
            regex = "[a-zA-Z0-9,-.]*[,][a-zA-Z0-9,-.]*[,][" + rt[indices[0]] + "][,][" + rt[indices[1]] + "][,][a-zA-Z0-9,-.]*";

            for(String r2 : rows){
                if(r.equals(r2) == false){              
                    if(Pattern.matches(regex, r2)){
                        String[] rt2 = r.split(",");
                        if(rt[supplementaryIndex].equals(rt2[supplementaryIndex]) == false){
                            return true;
                        }
                    }
                }
            }

        }   
        return false;
    }

但是，它是非常昂贵的，特别是如果有很多排。我曾想过创建一个更复杂的RegEx来考虑多个选择（使用“条件”），如下所示：

    public boolean checkMatching(){
        ArrayList<String> rows = new ArrayList<String>();
        rows.add("7,2,2,1,1");
        rows.add("7,3,2,1,1");
        rows.add("7,8,1,1,1");
        rows.add("8,2,1,3,1");
        rows.add("8,2,1,4,1");
        rows.add("8,4,5,1,1");

        int[] indices = new int[] {2,3};
        int supplementaryIndex = 1;

        String regex = "";
        for(String r : rows){
            String[] rt = r.split(",");
            regex += "[a-zA-Z0-9,-.]*[,][a-zA-Z0-9,-.]*[,][" + rt[indices[0]] + "][,][" + rt[indices[1]] + "][,][a-zA-Z0-9,-.]*"; 
            regex += "|"; //or
        }   

        for(String r2 : rows){
            if(Pattern.matches(regex, r2)){
                //String rt2 = r.split(",");
                //if(rt[supplementaryIndex].equals(rt2[supplementaryIndex]) == false){
                    return true;
                //}
            }
        }

        return false;
    }

但问题是这样我无法比较补充索引值。对于如何定义一个可以直接满足这个条件的正则表达式，您有什么建议吗？或者，是否可以利用Java流来高效地做到这一点？

Answer 1

第一种方法的主要问题是在同一列表上有两个嵌套循环，这会使时间复杂度达到二次。回想一下，这意味着对于包含100个元素的列表，内部循环的主体会被执行10,000次，对于包含1,000个元素的列表，会执行1,000,000次，以此类推。

在内部循环的主体中调用pattern.matches（regex,r2)无济于事。该方法仅用于支持（作为委派目标）string操作r2.matches(r2)，这是一种方便的方法，可以一次性执行pattern.compile（regex）.matcher（input）.matches()。如果必须多次应用相同的正则表达式，则应保留并重用pattern.compile(regex)的结果。

但在这里，使用正则表达式根本没有意义。您已经使用split分解了字符串，并且可以通过纯数组访问来访问每个组件。使用这个起点来组成要再次应用于字符串的正则表达式是复杂的，同时也是昂贵的。

只要用类似的东西

// return true when at least one string has the same values for indices
// but different value for supplementaryIndex

Map<List<String>,String> map = new HashMap<>();

for(String r : rows) {
    String[] rt = r.split(",");
    List<String> key = List.of(rt[indices[0]], rt[indices[1]]);
    String old = map.putIfAbsent(key, rt[supplementaryIndex]);
    if(old != null && !old.equals(rt[supplementaryIndex])) return true;
}
return false;

这将在列表上循环一次，从数组中提取关键元素，并为hashmap组成一个关键字。有各种方法可以做到这一点。但是，虽然仅仅连接这些元素（如rt[index[0]]+“、”+rt[index[1]])是很有吸引力的，但使用列表是更好的，因为它避免了昂贵的字符串连接。

代码将要检查的值放入映射，如果以前遇到过这个键，映射将返回一个以前的值。如果是，则可以比较新旧值，如果不匹配，方法可以立即返回。

使用Java ；8时，必须使用arrays.aslist(RT[Indexs[0]],RT[Indexs[1]])而不是list.of(RT[Indexs[0]],RT[Indexs[1]])。

这可以很容易地扩展，以支持索引的可变长度，方法是更改

List<String> key = List.of(rt[indices[0]], rt[indices[1]]);

至

List<String> key = Arrays.stream(indices).mapToObj(i -> rt[i]).toList();

或者，如果您使用的Java ；版本大于16：

List<String> key
    = Arrays.stream(indices).mapToObj(i -> rt[i]).collect(Collectors.toList());