Самый оптимальный способ проверить, какие конкретные символы отображаются только в строке

Question

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

У меня есть рабочее решение ниже, однако, производительность очень важна для меня.

Допущения:

• Может быть любая строка любой длины.
• Важен регистр

Есть ли более оптимальное решение?

Мой текущий код и ожидаемые тестовые случаи.

    public static bool ContainsOnlyChars(string strValue, params char[] charValues)
    {
        if (string.IsNullOrEmpty(strValue))
            throw new ArgumentNullException("String cannot be null or empty.");

            for (int i = 0; i < strValue.Length; i++)
            {
                if (!charValues.Any(c=> c == strValue[i]))
                {
                    return false;
                }
            }

            return true;
        }
    }

Контрольные примеры выглядели бы так, у меня есть много, но вот несколько.

// should return true
Console.WriteLine(ContainsOnlyChars("\n", '\n'));
Console.WriteLine(ContainsOnlyChars("\n\n", '\n'));
Console.WriteLine(ContainsOnlyChars("\n\n ", '\n', ' '));
Console.WriteLine(ContainsOnlyChars("ab", 'a', 'b'));

Console.WriteLine();

// should return false
Console.WriteLine(ContainsOnlyChars("\nz", '\n')); // because of z
Console.WriteLine(ContainsOnlyChars("z\n\n", '\n')); // because of z
Console.WriteLine(ContainsOnlyChars("\n\n z", '\n', ' ')); // because of z
Console.WriteLine(ContainsOnlyChars("abz", 'a', 'b')); // because of z

Фактические тестовые случаи, которые немного отличаются, принимают только строку и массив фиксированных символов. https://pastebin.com/xS0sRC4n

Answer 1

Ваше текущее решение - O (MN), создайте поиск ваших строковых значений и проверьте их.

public static bool ContainsOnlyChars(string strValue, params char[] charValues)
{
    if (string.IsNullOrEmpty(strValue))
        throw new ArgumentNullException("String cannot be null or empty.");

    var chrLookup = charValues.ToLookup(c => c);

    for (int i = 0; i < strValue.Length; i++)
    {
        if (!chrLookup.Contains(strValue[i]))
        {
            return false;
        }
    }

    return true;
}

Answer 2

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

В вашем случае вы можете создать словарь из исходной строки со временем O(n), а затем проверить каждыйдругих элементов в этом словаре со временем O(m), что делает его алгоритмом O(n + m)

public static bool ContainsOnlyChars(string strValue, params char[] charValues)
{
    if (string.IsNullOrEmpty(strValue))
        throw new ArgumentNullException("String cannot be null or empty.");

    // The O(n) part
    var dic = new Dictionary<char, bool>();
    foreach (var ch in strValue)
        if (!dic.ContainsKey(ch))
            dic.Add(ch,1);

    // The O(m) part
    foreach (var ch in charValues)
        if(!dic.ContainsKey(ch))
            return false;
    return true;
}

Отказ от ответственности: я написал код в браузере.

Answer 3

Альтернативой для рассмотрения будет:

public static bool ContainsOnlyChars(string strValue, params char[] charValues)
{
    if (string.IsNullOrEmpty(strValue))
        throw new ArgumentNullException("String cannot be null or empty.");

    return !strValue.Except(charValues).Any();
}

В основном код возвращает false, если в strValue есть символы, которых нет в charValues.

Answer 4

Решение

Вы можете просто проанализировать символы строки и проверить, содержат ли они предоставленные символы.

Вы получите наилучшую скорость и производительность памяти.

Использование метода расширения

static public class StringHelper
{
  static public bool ContainsOnlyChars(this string strValue, params char[] charValues)
  {
    if ( string.IsNullOrEmpty(strValue) )
      throw new ArgumentNullException("String cannot be null or empty.");
    if ( charValues == null )
      throw new ArgumentNullException("Chars cannot be null.");
  for ( int index = 0; index < strValue.Length; index++ )
    if ( !charValues.Contains(strValue[index]) )
        return false;
    return true;
  }
}

Исполнение на короткой строке

С IndexOf

var chrono = new Stopwatch();
chrono.Start();
for ( int index = 0; index < 10000000; index++ )
{
  "This a test string".ContainsOnlyChars('a', 'b', 'c', 'd');
}
chrono.Stop();
Console.WriteLine("Elapsed: " + chrono.ElapsedMilliseconds);

Debug Elapsed: 510
Release Elapsed: 178

с любым

Debug Elapsed: 747
Release Elapsed: 281

со всем

Debug Elapsed: 1193
Release Elapsed: 644

с ToLookup

Debug Elapsed: 1542
Release Elapsed: 870

С исключением, кроме

Debug Elapsed: 2195
Release Elapsed: 1423

со словарем

Debug Elapsed: 2947
Release Elapsed: 1900

Производительностьна большой строке

С IndexOf

var random = new Random();
string str = "";
for ( int index = 0; index < 10000; index++)
  str += (char)random.Next(48, 127);
chrono.Start();
for ( int index = 0; index < 10000000; index++ )
{
  str.ContainsOnlyChars('a', 'b', 'c', 'd', 'd', 'e', 'f', 'g', 'h');
}
chrono.Stop();
Console.WriteLine("Elapsed: " + chrono.ElapsedMilliseconds);

Release Elapsed: 327

С любым

Release Elapsed: 469

со всеми

Release Elapsed: 3733

с ToLookup

Release Elapsed: 4280

с исключением

Release Elapsed: 180562

Со словарем

Release Elapsed: 284176

Контрольный показатель фрагмента скрипта

Соображения

Дизайн скважиныЦикл d for всегда будет самым быстрым и менее жадным в памяти, чем любой foreach или Linq.

Доказательство содержится в коде IL.

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

Linq предназначен для уменьшения количества строк, а также для улучшения обслуживания и уменьшения сложности, но для этого требуется много байтов, герц и времени.