Блог

У меня есть функция, которая позволяет мне находить соответствие между неполным элементом и хотя бы одним элементом в наборе. Примером неполного элемента является 22.2.X.13, в котором есть элемент (определенный с помощью X ), который может принимать любое значение.

Цель этой функции — найти хотя бы один элемент в наборе элементов, который имеет 22 в первой позиции, 2 на второй и 13 на четвертой.

Например, если мы рассмотрим множество:

 {
    20.8.31.13,
    32.3.29.13, 
    24.2.12.13, 
    19.2.37.13, 
    22.2.22.13, 
    27.17.22.13, 
    26.22.32.13, 
    22.3.22.13, 
    20.19.12.13, 
    17.4.37.13, 
    31.8.34.13
} 
  

Выходные данные функции возвращают True, поскольку есть элементы 22.2.22.13 , которые соответствуют 22.2.X.13 .

Моя функция сравнивает каждую пару элементов, таких как строки, и каждый элемент элементов как целое число:

 public boolean containsElement(String element) {
    StringTokenizer strow = null, st = null;
    boolean check = true;
    String nextrow = "", next = "";
    
    for(String row : setOfElements) {
        strow = new StringTokenizer(row, ".");
        st = new StringTokenizer(element, ".");
        
        check = true;
        while(st.hasMoreTokens()) {
            next = st.nextToken();
            if(!strow.hasMoreTokens()) {
                break;
            }
            nextrow = strow.nextToken();
            if(next.compareTo("X") != 0) {
                int x = Integer.parseInt(next);
                int y = Integer.parseInt(nextrow);
                if(x != y) {
                    check = false;
                    break;
                }
            }
        }
        if(check) return true;
    }
    return false;

  

Однако это дорогостоящая операция, особенно если размер строки увеличивается. Можете ли вы предложить мне другую стратегию или структуру данных для быстрого выполнения этой операции?

Мое решение тесно связано со строками. Однако мы можем рассмотреть другие типы элементов (например, массив, список, узел дерева и т. Д.)

Спасибо всем за ваши ответы. Я перепробовал почти все функции, и бенч:

 myFunction: 0ms
hasMatch: 2ms
Stream API: 5ms
isIPMatch; 2ms
  

Я думаю, что основная проблема регулярного выражения — это время для создания шаблона и сопоставления строк.

Вы хотите использовать регулярное выражение, созданное именно для таких задач. Посмотрите демонстрацию.

 22.2.d .13
  

Java 8 и выше

Вы можете использовать Stream API начиная с Java 8, чтобы найти хотя бы один, соответствующий регулярному выражению, используя Pattern Matcher классы и:

 Set<String> set = ... // the set of Strings (can be any collection)

Pattern pattern = Pattern.compile("22\.2\.\d \.13"); // compiled Pattern
boolean matches = set.stream()                           // Stream<String>
                     .map(pattern::matcher)              // Stream<Matcher>
                     .anyMatch(Matcher::matches);        // true if at least one matches
  

Java 7 и ниже

Способ аналогичен Stream API: цикл короткого замыкания для каждого с break инструкцией на случай, если совпадение найдено.

 boolean matches = false;
        
Pattern pattern = Pattern.compile("22\.2\.\d \.13");
for (String str: set) {
    Matcher matcher = pattern.matcher(str);
    if (matcher.matches()) {
        matches = true;
        break;
    }
}
  

Вы можете решить эту проблему, подойдя к проблеме на основе регулярных выражений, как предложил Николас Хараламбидис ( 1), или вы можете сделать это по-другому. Чтобы избежать излишеств с другим ответом, я сосредоточусь здесь на альтернативном подходе, используя метод split .

 public boolean isIPMatch(String pattern[], String input[]) {
    if ((pattern == null) || (input == null) || (pattern.length <> input.length)) return false; //edge cases
    for (int index = 0; index < pattern.length; index  ) {
        if ((!pattern[index].equals("X")) amp;amp; (!pattern[index].equals(input[index]))) return false; //difference
    }
    return true; //everything matched
}
  

И вы можете вызвать описанный выше метод в своем цикле после преобразования элементов для сравнения в String массивы с помощью split .

Для строк регулярные выражения решают задачу намного лучше:

 private boolean hasMatch(String[] haystack, String partial) {
    String patternString = partial.replace("X", "[0-9] ").replace(".", "\.");
    // "22.2.X.13" becomes "22\.2\.[0-9] \.13" 
    Pattern p = Pattern.compile(patternString);
    for (String s : haystack) {
        if (p.matcher(s).matches()) return true;
    }
    return false;
}
  

Для других типов объектов это зависит от их структуры.

• Если есть какой-то порядок, вы могли бы рассмотреть возможность реализации ваших элементов Comparable , а затем вы можете поместить их в a TreeSet (или как ключи в a TreeMap ), которые всегда будут отсортированы. Таким образом, вы можете сравнивать только с элементами, которые могут совпадать: mySortedSet.subSet(fromElement, toElement) возвращает только элементы между этими двумя.
• Если порядка нет, вам просто нужно будет сравнить все элементы с вашим «шаблоном».

Обратите внимание, что строки сопоставимы, но их порядок сортировки по умолчанию игнорирует специальную семантику ваших . -разделителей. Итак, с некоторой осторожностью вы можете реализовать подход, основанный на наборе деревьев, чтобы сделать поиск лучше линейного.