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

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

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

char [] invalidChars = "[email protected]#$%^...".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; 
     }

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

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

источник

2011-02-01 Taranfx

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

источник

2011-02-01 08:29:10

Хотя это может быть решение, на самом деле это не ответ на вопрос. –

@ Roy: Почему это не ответ? Это O (1) «алгоритм», учитывая определенные ограничения. –

Простите, я неправильно понял, вы правы, я подтвердил ваш комментарий. Я думал, он только хотел узнать, какая из двух быстрее. –

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

Итак, у нас есть hashmap fill: O (n log n) с поиском O (1).

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

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

источник

2011-02-01 08:31:52

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

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

источник

2011-02-01 08:33:49 NPE

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

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

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

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

источник

2011-02-01 08:46:32

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

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

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

источник

2011-02-01 09:04:55 bestsss

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

ответ

Смежные вопросы