Самый быстрый алгоритм поиска набора символов в заданной строке

Question

Это спор, который у меня возник с одним из моих друзей: какой самый быстрый способ создать метод оценки, который проверяет, содержит ли данная строка один из недопустимых символов

Метод I:простой

char [] invalidChars = "!@#$%^...".toCharArray();
        for (int i = 0; i < myString.length(); i++) {
            char ch = myString.charAt(i);
            for (int j = 0; j < invalidChars.length; j++) {
                if (invalidChars[j] == ch) {
                    return false;
                }
            }
        }

Метод II: использование O карты (1)

Map <String,String> map = new HashMap<String, String>();
        map.put("!", null);
        map.put("@", null);
        map.put("#", null);
        map.put("$", null);
        map.put("^", null);
        ...
        for (int i = 0; i < labels.length(); i++) {
            char ch = labels.charAt(i);
            if (map.containsKey(ch)) {
                return false;
            }
            return true;
        }

Метод I на самом деле N2, но так же хорош, как N, когда invalidChars меньше в числе.Что следует отдавать предпочтение, когда Случай I: Есть много недопустимых символов, Случай II: только несколько недопустимых символов?

Примечание. Я не ищу никаких встроенных java-решений, а просто алгоритм фильтрации нескольких (не все) нетекстовые символы

Answer 1

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

Answer 2

Самый быстрый!HashMap - далеко не самое быстрое решение, только теоретически это O (1).

В java: java.util.BitSet разработан для ваших нужд.В качестве альтернативы можно использовать собственные развернутые массивы long [] / int [] (в зависимости от целевой архитектуры 32/64)

Почему HashMap не годится?Дополнительный багаж, полученный от доступа и создания ведер, выше, чем сам по себе.

Answer 3

Если вы используете HashSet, который дает вам O (1) при добавлении и содержит:

• O (n) для вставки каждого запрещенного символа
• O (м) для каждой операции сравнения

Что приводит к O (m + n), где m - количество запрещенных символов, а n - длина строки. Но я уже вижу ответы, которые работают лучше.

Но, пожалуйста, имейте в виду, что большинство вещей идут с накладными расходами (например, "хэш" в HashSet / HashMap). Таким образом, даже если асимптотическая производительность может быть лучше, наивная реализация может быть быстрее на небольших входах. Я не говорю, что вы должны использовать что-то, имеющее O (n²), но может стоить сравнить решение O (n log n) с решением O (m) для общего набора данных!

Answer 4

Существует простой метод, который даст вам O(n log(m)) сложность времени, где n - длина ввода, а m - количество запрещенных символов.

Сканирование ввода на один символи найдите текущий символ в (отсортированном) массиве запрещенных символов, используя бинарный поиск.

Answer 5

Создание хеш-карты и размещение элементов там относительно дорого. Однако, как вы сказали, поиск элементов в хэш-карте - это O (1).

Итак, у нас есть заполнение хеш-карты: O (n log n) с поиском O (1).

Или стандартным способом (заполните O (1), ищите O (n)).

Однако, поскольку поиск O (n) происходит для каждой строки, первый метод в целом - O (numberOfInvalidChars + strings * NumberofInValidChars), второй - O (numInv log numInv + strings). Что гораздо дешевле, так почти всегда дешевле.