Я ищу эффективный алгоритм сопоставления шаблонов/последовательностей в [большом] списке данных. Учитывая некоторый тип:
class Data implements Event {
int valueA;
int valueB;
int valueC;
long timestamp;
...
}
Я хотел бы сопоставить такие ситуации, как следующие.
valueA == 1 for 10 seconds
then valueB == 2 for 10 seconds
then valueC == 3 for 10 seconds.
Я реализовал очень простой конечный автомат, соответствующий такому шаблону, который работает очень хорошо и имеет очень приемлемую пропускную способность. Однако, если я хочу добавить дополнительные временные ограничения, например. Второй шаблон должен появиться через X секунд после первого
a : valueA == 1 for 10 seconds
b : valueB == 2 for 10 seconds [ 10 seconds after a ]
c : valueC == 3 for 10 seconds [ 10 seconds after b ]
Концепция конечного автомата больше не кажется подходящей, так как будет необходимо оценивать (и переоценивать уже совпадающие условия) и сохранять состояния в памяти, а затем пытаться сопоставить их. Таких «правил» в системе будет около 1000.
** РЕДАКТИРОВАТЬ **
Чтобы уточнить, пытался ли я сопоставить последовательность, например следующую:
x changed to 1
1 second passed
y changed to 1
3 seconds passed
z changed to 1
И учитывая входные данные:
[ x=0, y=0, z=0, t=0 sec ]
[ x=1, y=0, z=0, t=1 sec ]
[ x=0, y=1, z=0, t=2 sec ]
[ x=1, y=0, z=0, t=3 sec ]
[ x=0, y=1, z=0, t=4 sec ]
[ x=1, y=0, z=0, t=5 sec ]
[ x=0, y=1, z=0, t=6 sec ]
[ x=0, y=0, z=1, t=7 sec ]
Я ожидаю, что это достигнет своего конечного состояния при t = 7. Но единственный способ сделать это — сохранить все остальные переходы состояний?
** КОНЕЦ РЕДАКТИРОВАНИЯ **
Раньше я использовал Rule Engine с поддержкой CEP для соответствия таким условиям, который работает достаточно хорошо, но не может обрабатывать большие объемы необходимых данных (несколько сотен тысяч событий в секунду).
Есть ли эффективный способ решить эту проблему? Я использую Java.
Спасибо