Я ожидаю медлительности в этом алгоритме для проверки гласных

Question

Скорость следующего алгоритма будет определяться количеством слов в отправлении и количеством символов в каждом слове. Я полагаю, что это O (N ^ 2)? или хуже.

private bool CheckForNoVowels(string sentence)
{
    foreach (string word in sentence.Split(' '))
        foreach (char c in word)
            if (!vowels.Contains(c))
                return true;
}

Есть ли какой-то секрет string.HasVowel Билл Гейтс скрывается от меня? Есть ли лучший, более эффективный способ поиска этого. Спасибо.

Намерение
Я пытаюсь определить, является ли строка компанией или именем, я предполагаю, что если есть слово без гласных, это аббревиатура или аббревиатура и что это компания.

Answer 1

Regex.IsMatch(sentence, "[aoeui]");

Answer 2

Я не уверен, какова его внутренняя реализация (он помечен [MethodImpl (MethodImplOptions.InternalCall) и его алгоритм, похоже, не документирован), но я бы попробовал string.IndexOfAny метод.

Сообщает индекс первого вхождения в этом экземпляре любого символа в указанном массиве символов Юникода.Возвращаемое значение: позиция индекса, начинающаяся с нуля, первого вхождения в этом случае, где был найден любой символ в anyOf;-1, если не найдено ни одного символа в anyOf.

Обратите внимание, что:

Поиск anyOf чувствителен к регистру.Этот метод выполняет порядковый (нечувствительный к культуре) поиск, где символ считается эквивалентным другому символу, только если его скалярное значение в Юникоде совпадает.Чтобы выполнить поиск с учетом культуры, используйте метод CompareInfo.IndexOf.

Пример:

char[] vowels = { 'a', 'e', 'i', 'o', 'u' };
bool hasVowel = word.IndexOfAny(vowels) != -1;

---

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

Answer 3

Нет, это отлично. Это будет считаться O (N) в общем количестве символов на входе. Я не могу себе представить, что это будет узким местом в производительности вашего приложения, но вы должны использовать профилирование, чтобы проверить наверняка.

Answer 4

Если вы хотите, чтобы сложность времени определялась на основе количества слов в предложении и количества символов в каждом слове, то вам нужны две переменные: количество слов и количество символов в каждом слове.Если вы скажете, W - это количество слов, а N - это количество символов в самом длинном слове, тогда ваш алгоритм O (W * N), а не O (N ^2).

Answer 5

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

private static readonly char[] _vowels = "AEIOUaeiou".ToCharArray();
private bool CheckForVowels(string sentence)
{
    return sentence.IndexOfAny(_vowels) != -1;
}

(я не знаю внутреннюю реализацию IndexOfAny. Я думаю, что он должен выполнять именно такой цикл, но есть вероятность, что он будет делать это с использованием неуправляемого и / или небезопасного кода, поэтому по крайней мере так же быстро, как и все, что ты пишешь сам.)

Answer 6

Откуда приходит ^ 2?

Разделение O (N)

foreach (слово ...) foreach (c) - пройти каждый символ ровно один раз - O (N) для обоих «foreach» вместе.

гласные. Содержит константу (если число гласных никогда не меняется) или O (количество гласных).

Как результат O (N) или O (N * количество гласных).

Answer 7

Почему бы не удалить внешнюю foreach? Самая дорогая вещь здесь, кажется, sentence.Split(' '), и устранение, которое просто заставит пробелы проверяться на членство в vowels. В противном случае это выглядит как фрагмент кода O (N).