JESS: [EXTERNAL] question on sorting

classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

JESS: [EXTERNAL] question on sorting

Felix Chan-2

Hi,

I need to rank a set of facts based on a score. I came up with the idea that I first find the top ranked fact using one rule, followed by ranking the remaining facts using another rule.

It works. But I suspect that this method will not be very efficient if I have to rank thousands of facts, rather than just 4 as in my example below. I also suspect that someone must have solved this sorting problem in a much better way.

Any recommendation would be much appreciated. Many thanks.

Felix

 

/******************************************************************/

(deftemplate driver (slot driverId) (slot score) (slot rank))

(defrule rankFirstDriver
    "find top ranked driver if none has been ranked"
    (not (driver (rank ~nil)))               ; if no drivers have been ranked
    ?d1 <- (driver (score ?s1))              ; if we can find a driver with score s1
    (not (driver (score ?s2&:(> ?s2 ?s1))))  ; but no other drivers have a score higher than s1
    =>
    (modify ?d1 (rank 1))
    )

(defrule rankOtherDrivers
    "rank other drivers after top ranked drivers have been found"
    (driver (rank 1)) ; if top ranked driver has been found
   
    ; find lowest ranked driver
    (driver (rank ?r1&~nil))
    (not (driver (rank ?r2&~nil&:(> ?r2 ?r1))))
   
    ; find unranked driver with highest score
    ?d <- (driver (score ?s1) (rank nil))
    (not (driver (score ?s2&:(> ?s2 ?s1)) (rank nil)))
   
    =>
    (modify ?d (rank (+ ?r1 1)))
    )

(reset)
(assert (driver (driverId 1) (score 100)))
(assert (driver (driverId 2) (score 50)))
(assert (driver (driverId 3) (score 200)))
(assert (driver (driverId 4) (score 75)))

(run)
(facts)

 

/*********************************/

/***** OUTPUT **************/


f-0   (MAIN::initial-fact)
f-1   (MAIN::driver (driverId 1) (score 100) (rank 2))
f-2   (MAIN::driver (driverId 2) (score 50) (rank 4))
f-3   (MAIN::driver (driverId 3) (score 200) (rank 1))
f-4   (MAIN::driver (driverId 4) (score 75) (rank 3))
For a total of 5 facts in module MAIN.

Reply | Threaded
Open this post in threaded view
|

Re: JESS: [EXTERNAL] question on sorting

Friedman-Hill, Ernest
That's about the best you can do purely with rules, I'm afraid. The only way to do better would be to query for all the facts, sort them using an explicit sort, and then run through the list, modifying them one at a time. That wouldn't be too hard to code up in Java.

Now that I'm saying this, it seems like it should be possible to write a generic Userfunction which sorted facts based on some given criteria. That would be an interesting addition to Jess's library.

From: Felix Chan <[hidden email]>
Reply-To: <[hidden email]>
Date: Mon, 5 Mar 2012 17:57:25 -0800
To: <[hidden email]>
Subject: JESS: [EXTERNAL] question on sorting

Hi,

I need to rank a set of facts based on a score. I came up with the idea that I first find the top ranked fact using one rule, followed by ranking the remaining facts using another rule.

It works. But I suspect that this method will not be very efficient if I have to rank thousands of facts, rather than just 4 as in my example below. I also suspect that someone must have solved this sorting problem in a much better way.

Any recommendation would be much appreciated. Many thanks.

Felix

 

/******************************************************************/

(deftemplate driver (slot driverId) (slot score) (slot rank))

(defrule rankFirstDriver
    "find top ranked driver if none has been ranked"
    (not (driver (rank ~nil)))               ; if no drivers have been ranked
    ?d1 <- (driver (score ?s1))              ; if we can find a driver with score s1
    (not (driver (score ?s2&:(> ?s2 ?s1))))  ; but no other drivers have a score higher than s1
    =>
    (modify ?d1 (rank 1))
    )

(defrule rankOtherDrivers
    "rank other drivers after top ranked drivers have been found"
    (driver (rank 1)) ; if top ranked driver has been found
   
    ; find lowest ranked driver
    (driver (rank ?r1&~nil))
    (not (driver (rank ?r2&~nil&:(> ?r2 ?r1))))
   
    ; find unranked driver with highest score
    ?d <- (driver (score ?s1) (rank nil))
    (not (driver (score ?s2&:(> ?s2 ?s1)) (rank nil)))
   
    =>
    (modify ?d (rank (+ ?r1 1)))
    )

(reset)
(assert (driver (driverId 1) (score 100)))
(assert (driver (driverId 2) (score 50)))
(assert (driver (driverId 3) (score 200)))
(assert (driver (driverId 4) (score 75)))

(run)
(facts)

 

/*********************************/

/***** OUTPUT **************/


f-0   (MAIN::initial-fact)
f-1   (MAIN::driver (driverId 1) (score 100) (rank 2))
f-2   (MAIN::driver (driverId 2) (score 50) (rank 4))
f-3   (MAIN::driver (driverId 3) (score 200) (rank 1))
f-4   (MAIN::driver (driverId 4) (score 75) (rank 3))
For a total of 5 facts in module MAIN.

Reply | Threaded
Open this post in threaded view
|

Re: JESS: [EXTERNAL] question on sorting

Wolfgang Laun-2
This will not improve efficiency but here's a single rule doing the job, at the cost of one additional fact.

(deftemplate driver (slot driverId) (slot score) (slot rank))
(deftemplate rover  (slot rank))

(defrule rank-drivers
   ?d <- (driver (score ?s1) (rank nil))
   (not (driver (score ?s2&:(> ?s2 ?s1)) (rank nil)))
   ?r <- (rover (rank ?x))
=> 
   (modify ?d (rank ?x))
   (modify ?r (rank (++ ?x)))
)

(reset)
...
(assert (rover (rank 1)))

Cheers
Wolfgang

On 6 March 2012 16:55, Friedman-Hill, Ernest <[hidden email]> wrote:
That's about the best you can do purely with rules, I'm afraid. The only way to do better would be to query for all the facts, sort them using an explicit sort, and then run through the list, modifying them one at a time. That wouldn't be too hard to code up in Java.

Now that I'm saying this, it seems like it should be possible to write a generic Userfunction which sorted facts based on some given criteria. That would be an interesting addition to Jess's library.

From: Felix Chan <[hidden email]>
Reply-To: <[hidden email]>
Date: Mon, 5 Mar 2012 17:57:25 -0800
To: <[hidden email]>
Subject: JESS: [EXTERNAL] question on sorting

Hi,

I need to rank a set of facts based on a score. I came up with the idea that I first find the top ranked fact using one rule, followed by ranking the remaining facts using another rule.

It works. But I suspect that this method will not be very efficient if I have to rank thousands of facts, rather than just 4 as in my example below. I also suspect that someone must have solved this sorting problem in a much better way.

Any recommendation would be much appreciated. Many thanks.

Felix

 

/******************************************************************/

(deftemplate driver (slot driverId) (slot score) (slot rank))

(defrule rankFirstDriver
    "find top ranked driver if none has been ranked"
    (not (driver (rank ~nil)))               ; if no drivers have been ranked
    ?d1 <- (driver (score ?s1))              ; if we can find a driver with score s1
    (not (driver (score ?s2&:(> ?s2 ?s1))))  ; but no other drivers have a score higher than s1
    =>
    (modify ?d1 (rank 1))
    )

(defrule rankOtherDrivers
    "rank other drivers after top ranked drivers have been found"
    (driver (rank 1)) ; if top ranked driver has been found
   
    ; find lowest ranked driver
    (driver (rank ?r1&~nil))
    (not (driver (rank ?r2&~nil&:(> ?r2 ?r1))))
   
    ; find unranked driver with highest score
    ?d <- (driver (score ?s1) (rank nil))
    (not (driver (score ?s2&:(> ?s2 ?s1)) (rank nil)))
   
    =>
    (modify ?d (rank (+ ?r1 1)))
    )

(reset)
(assert (driver (driverId 1) (score 100)))
(assert (driver (driverId 2) (score 50)))
(assert (driver (driverId 3) (score 200)))
(assert (driver (driverId 4) (score 75)))

(run)
(facts)

 

/*********************************/

/***** OUTPUT **************/


f-0   (MAIN::initial-fact)
f-1   (MAIN::driver (driverId 1) (score 100) (rank 2))
f-2   (MAIN::driver (driverId 2) (score 50) (rank 4))
f-3   (MAIN::driver (driverId 3) (score 200) (rank 1))
f-4   (MAIN::driver (driverId 4) (score 75) (rank 3))
For a total of 5 facts in module MAIN.