Saturday, August 29, 2015

Dynamic programming - The Longest Common Subsequence Problem

The longest common subsequence problem is a simple problem that illustrates dynamic programming.

Longest Common Subsequence Problem

The problem is given two strings A and B of length m and n respectively, determine the length of the longest subsequence that is common in A and B. For example, A = xyxzx and B = zxyzy, then the longest common subsequence of A and B is xyz and the length is 3.

Brute-force Method

One way to solve the problem is to enumerate all the \(2^m\) subsequences of A, and for each subsequence check if it is also a subsequence in B. The time complexity of this method is \(\Theta(n2^m)\).

Dynamic Programming Method

Another way to solve this problem is using dynamic programming. It is easy to observe the formula below. \(a_i\) is the character at index i in A. \(b_j\) is the character at index j in B. L[i, j] is the length of the longest common subsequence in the substring of A[0..i] and the substring of B[0..j]. 
  • If \(a_i = b_j\), L[i, j] = L[i - 1, j - 1] + 1.
  • If \(a_i \neq b_j\), L[i, j] = max{L[i, j - 1], L[i - 1, j]}.
For example, A = xyxzx, B = zxyzy. Consider substring of A[0..2] = xyx and substring of B[0..2] = zxy. The L[2, 2] = 2 and the longest common subsequence is xy. Then consider A[0..3] = xyxz and B[0..3]=zxyz. Because \(a_3\) = z == \(b_3\) = z, it is clear that the L[3, 3] = 3 = L[2, 2] + 1 and the longest common subsequence is xyz. Then let's consider  A[0..3] = xyxz and B[0..4] = zxyzy. Because \(a_3\) = z \(\neq\) \(b_4\) = y, the longest common subsequence should still be xyz and the L[3, 4] = L[3, 3] = 3.

We can use an (m + 1) \(\times\) (n + 1) table to store the values of L[i, j]. And we fill the table row by row using the above observation. Then L[m, n] has the length of the longest common subsequence in A and B. The pseudo code is described in LCS.

Algorithm 6 LCS
Input: Two strings A and B of length m and n respectively.
Output: The length of the longest common subsequence of A and B.
  1. for i = 0 to m
  2.     for j = 0 to n
  3.         if (i == 0 and j == 0) then L[i, j] = 0
  4.         else if (\(a_i\) == \(b_j\)) then L[i, j] = L[i - 1, j - 1] + 1
  5.         else L[i, j] = max{L[i, j - 1], L[i - 1, j]}
  6.         end if
  7.     end for
  8. end for
  9. return L[m, n]
A JAVA implementation of this algorithm can be found on GitHub LCS.

An Example

Running LCS algorithm with input A = "abcdeabcd" and B = "acebde" will generate the table below. The result is 5 and the longest common subsequence is "acebd".

       a  c  e  b  d  e
  [0, 0, 0, 0, 0, 0, 0]
a[0, 1, 1, 1, 1, 1, 1]
b[0, 1, 1, 1, 2, 2, 2]
c[0, 1, 2, 2, 2, 2, 2]
d[0, 1, 2, 2, 2, 3, 3]
e[0, 1, 2, 3, 3, 3, 4]
a[0, 1, 2, 3, 3, 3, 4]
b[0, 1, 2, 3, 4, 4, 4]
c[0, 1, 2, 3, 4, 4, 4]
d[0, 1, 2, 3, 4, 5, 5]


Time Complexity

Filling each entry in the table requires \(\Theta(1)\) time. The size of the table is \(\Theta(mn)\), so the time complexity of LCS algorithm is \(\Theta(mn)\), which is the total time of filling the whole table.

Sunday, August 16, 2015

Spring + Quartz integration example (3) - inject Spring bean into Quartz job instance

In my work of integrating Quartz scheduler with Spring. There is a requirement to pass an object into the Quartz job instance. The object is a Spring bean. I found because the Quartz job instance is created by Quartz thread and it doesn't aware of Spring context, so I couldn't use the Spring bean in the job class directly, it is always null. After googling it a bit, I found three ways to do that. 1. Pass the object into JobDataMap, 2. get it from Spring application context and 3. use Spring to inject the object. Personally, I vote for the third way as the best practice.


1. Passing the object into JobDataMap

This is the easiest way, what we have to do is letting our class implement Serializeble interface. Then the object can be simply passed into the Quartz JobDataMap. However, there is a flaw in this method. If you use a persistent JobStore, the object in it will be serialized. And you will get a class-versioning error if your class definition is changed in future. Quartz recommends only pass primitive and String into JobDataMap. For details, see Quartz lesson 3.

Put object into JobDataMap

   <bean id="object" class="com.package.MyObject"/>  
   <bean class="org.springframework.scheduling.quartz.JobDetailFactoryBean">  
     <property name="jobClass" value="com.package.MyJob"/>  
     <property name="jobDataAsMap">  
       <map>  
         <entry key="myObject" value-ref="object"/>  
       </map>  
     </property>  
     <property name="durability" value="true"/>  
   </bean>

Retrieve object in Quartz job class

...
MyObject obj = jobExecutionContext.getMergedJobDataMap().getString("myObject");
...
>

2. Using Spring application context

In this way, we have to define an application context key in the scheduler bean.
<bean id="scheduler"  
      class="org.springframework.scheduling.quartz.SchedulerFactoryBean">  
     <property name="applicationContextSchedulerContextKey" value="applicationContext"/>  
     <property name="jobDetails">  
       <list>
          ...  
       </list>  
     </property>  
     <property name="triggers">  
       <list>
         ...  
       </list>  
     </property>  
   </bean>
Then in the job class, we can get the Spring application context as below and retrieve any bean via the bean name.
try {
            ApplicationContext context =
                    (ApplicationContext) jobExecutionContext.getScheduler().getContext().get("applicationContext");
            if (context != null) {
                InjectObject obj = (InjectObject) context.getBean("geeksPearls");
                if (obj != null) {
                    System.out.println("[" + new Date() + "] I am saying hello from a Quartz job, " + obj);
                }
            }
        } catch (SchedulerException e) {
            e.printStackTrace();
        }
The completed example can be found on my GitHub Example3. Have a look at InjectTask class and the Spring context XML.


3. Using Spring injection

We can also use Spring injection to inject any object into our job. However, we have to do a bit more work. I found this way in this blog. And I think it's elegant and the Spring guys should use it as the default way.

Firstly, extend the SpringBeanJobFactory class as below.
public class AutowiringSpringBeanJobFactory extends SpringBeanJobFactory implements ApplicationContextAware {

    private transient AutowireCapableBeanFactory beanFactory;

    public void setApplicationContext(final ApplicationContext applicationContext) throws BeansException {
        beanFactory = applicationContext.getAutowireCapableBeanFactory();
    }

    @Override
    protected Object createJobInstance(final TriggerFiredBundle bundle) throws Exception {
        final Object job = super.createJobInstance(bundle);
        beanFactory.autowireBean(job);
        return job;
    }
}
Secondly, override the default jobFactory in Spring's SchedulerFactoryBean.
<bean id="autoWireScheduler"  
      class="org.springframework.scheduling.quartz.SchedulerFactoryBean">  
     <property name="jobFactory" >  
       <bean class="com.geekspearls.quartz.example3.AutowiringSpringBeanJobFactory"/>  
     </property>  
     <property name="jobDetails">  
       <list>  
         <ref bean="injectJob2"/>  
       </list>  
     </property>  
     <property name="triggers">  
       <list>  
         <ref bean="simpleTrigger2"/>  
       </list>  
     </property>  
   </bean>
Then we can autowire any object into Quartz job class.
public class AnotherInjectTask extends QuartzJobBean {

    @Autowired
    private InjectObject injectObject;

    @Override
    protected void executeInternal(JobExecutionContext jobExecutionContext) throws JobExecutionException {
        System.out.println("[" + new Date() + "] I am saying another hello from a Quartz job, " +
                injectObject);
    }

    public void setInjectObject(InjectObject injectObject) {
        this.injectObject = injectObject;
    }
}
Be aware that in order to use the autowire annotation of Spring. Add either <context:annotation-config> or <context:componentscan> in the Spring context XML file. A completed example can be found on my GitHub Example3. Have a look at AnotherInjectTask and the Spring context XML.

In the example, if we run Example3 class as java application. We can see the following output in the console.
...
[Sun Aug 16 16:46:12 AEST 2015] I am saying hello from a Quartz job, GeeksPearls
[Sun Aug 16 16:46:12 AEST 2015] I am saying another hello from a Quartz job, null
[Sun Aug 16 16:46:12 AEST 2015] I am saying another hello from a Quartz job, GeeksPearls
...
The first line is output by the job using the Spring application context way. The second line is output by the job using the default Spring SchedulerFactoryBean. You can see the object is not injected so it outputs null. The third line is output by the job using our AutowiringSpringBeanJobFactory, you can see the object is injected successfully. Enjoy!

Sunday, August 9, 2015

Spring + Quartz integration example (2) - schedule jobs dynamically

Sometimes, we need schedule jobs dynamically. This requires us to use Quartz scheduler in a programming way rather than a static XML configuration way. I'll show in this post about how to do it with a simple example.


Environment

Java 8
Maven 3
Spring 3.2.3
Quartz 2.2.2
SFL4J 1.7.9 (to show Quartz start up information)


Scenario

We need schedule a report generation task for different departments in an organisation. The task is doing the same thing for different departments but needs to be run at different time, and it collects different data from database for different departments. Suppose sales department's report is to be generated at 7:00 am everyday, marketing department's report is to be generated at 8:00 am on Monday every week and engineering department's report is to be generated at 6:00 pm on the last Friday of every month.

It would be a little difficult to configure the tasks in Spring XML file, because it would be tricky to tell the XML file which department it is. Fortunately, Quartz allows us to use a programming way to schedule the task dynamically.


Implementation

The project configuration is as below.
   <dependencies>  
     <dependency>  
       <groupId>org.springframework</groupId>  
       <artifactId>spring-core</artifactId>  
       <version>${spring.version}</version>  
     </dependency>  
     <dependency>  
       <groupId>org.springframework</groupId>  
       <artifactId>spring-context-support</artifactId>  
       <version>${spring.version}</version>  
     </dependency>  
     <!-- Transaction dependency is required with Quartz integration -->  
     <dependency>  
       <groupId>org.springframework</groupId>  
       <artifactId>spring-tx</artifactId>  
       <version>${spring.version}</version>  
     </dependency>  
     <!-- Quartz framework -->  
     <dependency>  
       <groupId>org.quartz-scheduler</groupId>  
       <artifactId>quartz</artifactId>  
       <version>${quartz.version}</version>  
     </dependency>  
     <dependency>  
       <groupId>org.slf4j</groupId>  
       <artifactId>slf4j-api</artifactId>  
       <version>${slf4j.version}</version>  
     </dependency>  
     <dependency>  
       <groupId>org.slf4j</groupId>  
       <artifactId>slf4j-simple</artifactId>  
       <version>${slf4j.version}</version>  
     </dependency>  
   </dependencies>  
   <properties>  
     <spring.version>3.2.3.RELEASE</spring.version>  
     <quartz.version>2.2.1</quartz.version>  
     <slf4j.version>1.7.9</slf4j.version>  
   </properties>
To make it simple here, the task is just print out an information on the console. The task class is as below. the department name is retrieved from the JobDataMap and can be used in the report generation.
public class GenerateReportTask extends QuartzJobBean {

    public static final String DEPARTMENT = "DEPARTMENT";

    @Override
    protected void executeInternal(JobExecutionContext jobExecutionContext) throws JobExecutionException {
        JobDataMap dataMap = jobExecutionContext.getMergedJobDataMap();
        String department = dataMap.getString(DEPARTMENT);
        System.out.println("[" + new Date() + "] Generating report for department " + department);
    }
}
A QuartzScheduler class is used to schedule the task dynamically. The schedule CRON expressions are stored in a schedules map and the map is initialised in init() method. The init() method will be called when Spring initialise the QuartzScheduler bean.

public class QuartzScheduler {

    private Department[] departments = {Department.ENGINEER, Department.MARKETING, Department.SALES};
    private Map schedules = new HashMap();

    public void init() {
        schedules.put(Department.ENGINEER, "0 0 6 ? * 6L");
        schedules.put(Department.MARKETING, "0 0 8 ? * 2");
        schedules.put(Department.SALES, "0 0 7 * * ?");

        for (Department department : departments) {
            schedule(department);
        }
    }

    private enum Department {
        SALES, MARKETING, ENGINEER
    }
}
In the QuartzScheduler class, an instance of org.quartz.Scheduler class will be injected by Spring, it is the real Quartz scheduler to schedule the tasks. And the schedule() method is using Quartz's static method newJob() and newTrigger() to create the jobDetail and Trigger instances, then add the trigger to the scheduler. You might notice that we put the department name into the JobDataMap. As mentioned above, the department name will be used in the GenerateReportTask class.

public class QuartzScheduler {
    private Scheduler scheduler;    
    ...
    private void schedule(Department department) {
        JobDetail job = newJob(GenerateReportTask.class)
                .withIdentity(department.toString(), "reportgen")
                .build();
        job.getJobDataMap().put(GenerateReportTask.DEPARTMENT, department.toString());
        Trigger trigger = newTrigger()
                .withIdentity(department.toString(), "reportgen")
                .withSchedule(cronSchedule(schedules.get(department)))
                .forJob(job).build();
        try {
            scheduler.scheduleJob(job, trigger);
        } catch (SchedulerException e) {
            e.printStackTrace();
        }
    }
    ...
}
Finally, the Spring XML configuration file contains the bean definition of the QuartzScheduler class and the Spring SchedulerFactoryBean bean to create the real Quartz scheduler instance.
<beans xmlns="http://www.springframework.org/schema/beans"  
     xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"  
     xsi:schemaLocation="http://www.springframework.org/schema/beans http://www.springframework.org/schema/beans/spring-beans-3.2.xsd">  
   <bean id="quartzScheduler"  
      class="com.geekspearls.quartz.example2.QuartzScheduler"  
       init-method="init">  
     <property name="scheduler" ref="scheduler"/>  
   </bean>  
   <bean id="scheduler"  
      class="org.springframework.scheduling.quartz.SchedulerFactoryBean"/>  
 </beans>
And the Java application class to test our code.
public class Example2 {

    public static void main(String[] args) {
        ApplicationContext context = new ClassPathXmlApplicationContext("applicationContext-quartz2.xml");
        System.out.println("Application started [" + new Date() + "] ");
    }
}
A complete code can be found on my GitHub here. In order to demo the example, I put the schedules a much shorter period as below.
        schedules.put(Department.ENGINEER, "10 * * * * ?");
        schedules.put(Department.MARKETING, "30 * * * * ?");
        schedules.put(Department.SALES, "50 * * * * ?");
Run the Example2 class as a Java application and you can see the tasks are running at scheduled time on the console. I hope you enjoy it.