我正在尋找一種用於匹配[大]數據列表中的模式/序列的高效算法。鑑於某些類型:匹配序列的高效算法
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時達到最終狀態。但是,我能看到這樣做的唯一方法是存儲所有其他狀態轉換?
**編輯完**
我以前使用的規則引擎與CEP支持來匹配這些樣的條件,它的性能非常好,但不能處理大量需要的數據(每秒幾十萬個事件)。
有沒有一種有效的方法來解決這個問題?我正在使用Java。
感謝
謝謝你的建議,邁克。我仍然不確定如何按時間關聯這些事件。我用一個例子更新了我的問題。 – dropbear 2012-02-27 20:07:10