Есть ли более эффективный способ оценки содержания строк?

Question

Я должен выполнить эту строку cose несколько миллионов раз, мне интересно, есть ли способ ее оптимизировать (может быть, предварительно вычислить что-то?).

a.contains(b) || b.contains(a)

Спасибо

edit: код, выполняемый методом contains, уже проверяет a.length public static int indexOf(byte[] value, int valueCount, byte[] str, int strCount, int fromIndex) { byte first = str[0]; int max = (valueCount - strCount); for (int i = fromIndex; i <= max; i++) { [...] } return -1; }

Answer 1

Как я понимаю задачу, вы должны проверить, содержит ли a b или наоборот для каждой пары a и b из набора из примерно 35 миллионов слов. Это много пар, чтобы проверить.

Вы должны быть в состоянии значительно сузить поиск, предварительно вычислив, какие n-граммы содержит слово: если a содержит некоторый n-грамм, то b должен содержать тот же самый n-грамм, если b содержит a. Вы могли бы, например, предварительно вычислить все триграммы, которые содержит каждое слово в списке, и в то же время все слова, которые содержат данную триграмму, тогда вы можете просто найти слова в этих словарях, и с помощью некоторых операций над множествами получить небольшой набор кандидатов для проверки должным образом.

В псевдокоде:

• выберите размер для n-грамм (см. Ниже)
• инициализировать Map<String, Set<String>> ngram_to_word
• первая итерация: для каждого слова a в вашем наборе данных
  • повторять все n-граммы (например, используя какое-то скользящее окно) a
  • для каждого, добавьте a к наборам слов, содержащих эти n-граммы в ngrams_to_words
• вторая итерация: для каждого слова a в вашем наборе данных
  • снова получите все n-граммы a содержит
  • для каждого из них получите набор слов, содержащих этот n-грамм, из ngrams_to_words
  • получить пересечение этих наборов слов
  • для каждого слова b в том пересечении, которое содержит все n-граммы, которые содержит a (но может быть в другом порядке или количестве), должным образом проверьте, содержит ли b a

В зависимости от количества букв в этих n-граммах (например, биграммы, триграммы, ...) их предварительное вычисление будет дороже как во времени, так и в пространстве, но эффект также будет более значительным. В простейшем случае вы могли бы даже просто предварительно вычислить, какие слова содержат данную букву (то есть «1-грамм»); это должно быть быстро и уже значительно сузить слова, чтобы проверить. Конечно, n-граммы не должны быть короче, чем самое короткое из слов в наборе данных, но вы можете даже использовать две длины n-граммов, например, используйте две карты letter_to_words и trigrams_to_words.