A faster Search Algorithm in a JTable

Question

I'm trying to implement my own JTable RowFilter, since I'm using Java 1.4 (RowFilter doesn't seem to exist in this version). I still believe however that the algorithm that I'm using can be replaced by a much faster one. I have tried my algorithm on a dummy table that contains 30.000 records and 8 columns, and I'm getting the result in less than a second. But sometimes, there's this little delay that occurs while typing in the Search Criteria (Which is basically a JTextField with a DocumentListener). Here's the algorithm I'm using:

    public void searchList()
    {  

        for(int i=0;i<list.size();i++)
        {
            Employee e=(Employee)list.get(i);

            Pattern pattern=Pattern.compile(search.getText(),Pattern.CASE_INSENSITIVE);
            Matcher matcher=pattern.matcher(e.getFname());
            if(matcher.find())
            {
                result.add(e);
                continue;   
            }
            matcher=pattern.matcher(e.getLname());
            if(matcher.find())
            {
                result.add(e);
                continue;   
            }
            matcher=pattern.matcher(e.getHeight());
            if(matcher.find())
            {
                result.add(e);
                continue;   
            }
            matcher=pattern.matcher(e.getOccupation());
            if(matcher.find())
            {
                result.add(e);
                continue;   
            }
            matcher=pattern.matcher(e.getSize());
            if(matcher.find())
            {
                result.add(e);
                continue;   
            }
            matcher=pattern.matcher(e.getSkills());
            if(matcher.find())
            {
                result.add(e);
                continue;   
            }
            matcher=pattern.matcher(e.getSsn());
            if(matcher.find())
            {
                result.add(e);
                continue;   
            }
            matcher=pattern.matcher(e.getStrength());
            if(matcher.find())
            {
                result.add(e);

            }
        }
        model.fireTableDataChanged();
        table.updateUI();
    }
    }

The main datastructure that I'm using to bind data to my TableModel is an ArrayList that holds objects of a class called "Employee". Another ArrayList called result, contains all the "Employee" objects that matched the search criteria. Bear in mind that the filtering is happening on all 8 columns. The only optimization that I think I did is adding the "Employee" object on the first column match, instead of having to go through the rest of the columns.

Any suggestions regarding this matter? Thanks a lot for the help =)

Answer 1

Since you seem to be searching for the exact same value in all fields, I would just concatenate them and do the matching once.

Also, I don't think there is any good reason why you would compile the pattern in every iteration.

Answer 2

Just to update you guys on my question, I have finally done the following: 1- Concatenated all the fields together with a separator between them ( the "!") 2- Downloaded the SearchString library from this link johannburkard.de/software/stringsearch 3- Converted the concatenated string and the search criteria patten to lowerCase. 4- Used the Boyer Moore, Raita algorithm by doing the following: BoyerMooreHorspoolRaita searchAl=new BoyerMooreHorspoolRaita();

Then I did this: int j=searchAl.searchString(match, search.getText()); if(j!=-1) result.add(e);

I tried comparing the first method that I used with this one, in a table that contained 100000 records, and the results were as follows:

Pattern Matching: FIRST RUN: 1 Character long pattern: Operation took 3.328 seconds to complete 2 Characters long pattern: Operation took 14.14 seconds to complete 3 Characters long pattern: Operation took 11.328 seconds to complete 4 Characters long pattern: Operation took 8.437 seconds to complete 5 Characters long pattern: Operation took 8.344 seconds to complete 6 Characters long pattern: Operation took 8.078 seconds to complete

SECOND RUN: 1 Character long pattern: Operation took 3.281 seconds to complete 2 Characters long pattern: Operation took 14.14 seconds to complete 3 Characters long pattern: Operation took 11.344 seconds to complete 4 Characters long pattern: Operation took 8.375 seconds to complete 5 Characters long pattern: Operation took 8.469 seconds to complete 6 Characters long pattern: Operation took 8.266 seconds to complete

Boyer Moore RAITA: FIRST RUN: 1 Character long pattern: Operation took 11.688 seconds to complete 2 Characters long pattern: Operation took 10.594 seconds to complete 3 Characters long pattern: Operation took 7.563 seconds to complete 4 Characters long pattern: Operation took 4.328 seconds to complete 5 Characters long pattern: Operation took 4.5 seconds to complete 6 Characters long pattern: Operation took 4.969 seconds to complete

SECOND RUN: 1 Character long pattern: Operation took 8.172 seconds to complete 2 Characters long pattern: Operation took 8.312 seconds to complete 3 Characters long pattern: Operation took 5.484 seconds to complete 4 Characters long pattern: Operation took 3.922 seconds to complete 5 Characters long pattern: Operation took 3.922 seconds to complete 6 Characters long pattern: Operation took 4.047 seconds to complete

Notice that Pattern Filtering (The first method ) is faster when it comes to a single character matching. But the Boyer Moore Horspool Raita just SHINES as the length of the pattern increases.

I hope this will help someone somehow. Cheers.