Сравните первые три символа двух строк

Question

Строки s1 и s2 всегда будут иметь длину 1 или выше.

Как я могу ускорить это?

int l1 = s1.length();

if (l1 > 3) { l1 = 3; }

if (s2.startsWith(s1.substring(0,l1))) 
{
 // do something..
}

Regex может быть?

Answer 1

Переписать, чтобы избежать создания объекта

Ваши инстинкты были верны. Создание новых объектов (substring ()) не очень быстрое, и это означает, что каждый созданный объект также должен нести дополнительные затраты.

Это может быть намного быстрее:

static boolean fastCmp(String s1, String s2) {
    return s1.regionMatches(0, s2, 0, 3);
}

Answer 2

Это кажется довольно разумным. Это действительно слишком медленно для вас? Вы уверены, что это не преждевременная оптимизация?

Answer 3

if (s2.startsWith(s1.substring(0, Math.min(3, s1.length())) {..};

Кстати, в этом нет ничего медленного. startsWith имеет сложность O(n)

Другой вариант - сравнить значения символов, которые могут быть более эффективными:

boolean match = true;
for (int i = 0; i < Math.min(Math.min(s1.length(), 3), s2.length()); i++) {
    if (s1.charAt(i) != s2.charAt(i)) {
       match = false;
       break;
    }
}

Answer 4

Мой Java не так хорош, поэтому я дам вам ответ на C #:

int len = Math.Min(s1.Length, Math.Min(s2.Length, 3));
for(int i=0; i< len; ++i)
{
    if (s1[i] != s2[i])
       return false;
}
return true;

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

Answer 5

Здесь отсутствует контекст: Что вы пытаетесь сканировать? Какой тип приложения? Как часто ожидается запуск?

Это важно, потому что разные сценарии требуют разных решений:

1. Если это одноразовое сканирование, то это, вероятно, ненужная оптимизация. Даже для текстового файла размером 20 МБ в худшем случае это не займет больше пары минут.
2. Если у вас есть набор входных данных, и для каждого из них вы сканируете все слова в файле размером 20 МБ, возможно, было бы лучше отсортировать / проиндексировать файл размером 20 МБ, чтобы было легче искать совпадения и пропускать 99. % ненужных сравнений. Кроме того, если входные данные имеют тенденцию повторяться, возможно, имеет смысл использовать кэширование.

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

Но если вы сводите его только к сравнению первых 3 символов двух строк, я считаю, что приведенные здесь фрагменты кода хороши, как вы и собираетесь - они все O (1) *, так что есть никакой радикальной оптимизации вы не сможете сделать.

* Единственное место, где это может не выполняться, - это получение длины строки O (n), а не O (1) (что имеет место для функции strlen в C ++), а это не так для строковых объектов Java и C #.

Answer 6

Возможно, вы могли бы сделать это

if (s1.length() > 3 && s2.length() > 3 && s1.indexOf (s2.substring (0, 3)) == 0)
{
  // do something..
}