Быстрый алгоритм сопоставления списков в Java

У меня есть список правил в форме

L1 → (A, B, C)

L2 → (D, E),

L3 → (F, G, A),

L4 → (C, A)

.....

Этот список содержит ~ 30k таких правил.

У меня есть вход в форме (X, Y, Z)

Это создает метод

List <Rule> matchRules(input)

Что принадлежит классу RuleMatcher

Я начал с очень простого ясного наивного решения, чтобы получить структуру, получить что-то работающее.

public RuleMatcher(Collection<Rule> rules) {
   this.rules = rules;
}

public Collection<Rule> matchRules(List<Token> input) {
   List<Rule> matchingRules = new ArrayList<>();
   for(Rule r: this.rules) {
        if(r.matches(input)) {
            matchingRules.add(r);
        }
   }
   return matchingRules; 
}

Где matches - очень простая функция, которая проверяет, совпадают ли длины, а затем проверяет каждый токен как цикл for.

Эта функция matchRules вызывается в величине миллиардов раз.

---

Очевидно, что это очень плохая реализация. Согласно моему профилировщику, в этой функции совпадений используется не менее половины времени выполнения.

Я думал о двух возможных решениях:

а. Некоторая структура данных Trie, содержащая цепочки правил, которые могут быть сопоставлены.

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

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

Д. Удивительное решение, из которого один из вас придумал.

Я надеюсь, что кто-то может пролить свет на эту проблему.

---

Изменить: токен - это просто объект с уникальным номером. Например, "NN" является токеном. Каждый экземпляр "NN" точно такой же.

Код соответствия:

public boolean rhsMatches(List<Token> tokens) {
   if(tokens.size()!=rhsSize()) return false;
   for(int i = 0;i<rhsSize();i++) {
      if(!rightSide.get(i).equals(tokens.get(i)) {
        return false;
      }
   }
   return true;
}

Это не очень красиво, но просто.

Ответы

Ответ 1

Почему бы не отсортировать список правил для начала. Затем вы можете выполнить двоичный поиск соответствующего правила.

Ответ 2

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