Increase efficiency and velocity autosuggestion algorithm

Question

In my project, for inserting an autosuggestion function (also in presence of little insertion errors, like Google), I've created this class:

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.SortedSet;
import java.util.TreeSet;
import java.util.logging.Level;
import java.util.logging.Logger;

public class Searcher {

private ArrayList<String> titoli;
private boolean multiThread;
private int numeroCore;
private Thread [] threads;
private int indice;
private String [] testoSplittato;
private SortedSet<String> risultati;
private final Runnable runnable;

public Searcher (ArrayList<String> titoli , boolean multiThread) {
    this.titoli = titoli;
    this.multiThread = multiThread;
    indice = 0;
    risultati = new TreeSet<String> ();
    numeroCore = multiThread ? Runtime.getRuntime().availableProcessors() : 1;
    threads = new Thread [numeroCore];
    runnable = new Runnable () {
        @Override
        public void run () {                    
            String prossimo;
            while ((prossimo = getProssimo ()) != null) {
                if (suggerimentoDaAggiungere (prossimo.toLowerCase()))
                    aggiungiRisultato (prossimo);
            }
        }
    };
    for (int i=0;i<threads.length;i++) {
        threads [i] = new Thread (runnable);
    }
}

public Searcher (ArrayList<String> titoli) {
    this (titoli, false);
}

private synchronized void setIndice (int n) {
    indice = n;
}

private synchronized String getProssimo () {
    try {
        return titoli.get(indice++);
    }catch (IndexOutOfBoundsException ioobe) {
        return null;
    }
}

public synchronized void aggiungiRisultato (String s) {
    risultati.add(s);
}

private boolean mancaUnaLettera (String a , String b) {
    int al = a.length() , bl = b.length();
    if (al < 2 || al >= bl)
        return false;

    //a più corta di b
    int primaLetteraSbagliata = -1;
    for (int i=0;i<al;i++) {
        if (a.charAt (i) != b.charAt(i)) {
            primaLetteraSbagliata = i;
            break;
        }
    }

    return primaLetteraSbagliata >= 0 && (b.substring(0, primaLetteraSbagliata) + b.substring(primaLetteraSbagliata + 1)).indexOf(a) >= 0;
}

private boolean unaLetteraDiTroppo (String a , String b) {
    int al = a.length() , bl = b.length();
    if (al < 3 || al - 1 > bl)
        return false;

    //a più corta o stessa lunghezza di b
    int primaLetteraSbagliata = -1;
    for (int i=0;i<bl;i++) {
        if (a.charAt(i) != b.charAt(i)) {
            primaLetteraSbagliata = i;
            break;
        }
    }

    //non sono sicurissimo di qui
    if (primaLetteraSbagliata == -1 && al + 1 == bl)
        return true;

    return primaLetteraSbagliata >= 0 && b.indexOf ((primaLetteraSbagliata > 0 ? a.substring(0 , primaLetteraSbagliata) : "") + (primaLetteraSbagliata + 1 < al ? a.substring(primaLetteraSbagliata + 1) : "") ) >= 0;
}

private boolean unaLetteraSbagliata (String a , String b) {
    int al = a.length() , bl = b.length();
    if (al < 3 || al > bl)
        return false;

    //a ha lunghezza >= di b
    int primaLetteraSbagliata = -1;
    for (int i=0;i<al;i++) {
        if (a.charAt(i) != b.charAt(i)) {
            primaLetteraSbagliata = i;
            break;
        }
    }

    boolean ok = primaLetteraSbagliata + 1 < al;

    return primaLetteraSbagliata >= 0 && (b.substring(0, primaLetteraSbagliata) + (ok ? b.substring(primaLetteraSbagliata + 1) : "")).indexOf(a.substring(0, primaLetteraSbagliata) + (ok ? a.substring(primaLetteraSbagliata + 1) : "")) >= 0;
}

private boolean presenteConErrore (String chiave , String titolo) {
    String [] titoloSplittato = titolo.split(" ");
    if (titolo.indexOf (chiave) >= 0)
        return true;
    for (String s : titoloSplittato)
        if (mancaUnaLettera (chiave , s) || unaLetteraDiTroppo (chiave, s) || unaLetteraSbagliata (chiave, s))
            return true;

    return false;
}

public boolean suggerimentoDaAggiungere (String titolo) {        
    for (String s : testoSplittato) {
        if (!presenteConErrore (s,titolo))
            return false;
    }

    return true;
}

public SortedSet<String> getSuggerimenti (String testo) {
    for (Thread t : threads) {
        if (/*t != null && */t.isAlive()) {
            t.interrupt();
        }
    }
    testoSplittato = testo.toLowerCase ().split (" ");
    risultati.clear();
    if (testoSplittato.length > 0) {
        setIndice (0);
        for (int i=0;i<threads.length;i++) {
            threads [i] = new Thread (runnable);
            threads [i].setPriority(Thread.MAX_PRIORITY);
            threads [i].start();
        }
    }
    for (Thread t : threads)
        try {
            t.join();
        } catch (InterruptedException ex) {
            Logger.getLogger(Searcher.class.getName()).log(Level.SEVERE, null, ex);
        }
    //System.out.println ("FINITO");

    return risultati;                              
}

public static ArrayList<String> getTitoli () {
    ArrayList<String> restituire = new ArrayList<String> ();
    try {
        BufferedReader br = new BufferedReader (new InputStreamReader (new FileInputStream ("C:/Users/Claudio/Desktop/full-title-list.txt") {}));
        String s;
        while ((s = br.readLine ()) != null) {
            restituire.add (s);
        }
    } catch (Exception ex) {
        Logger.getLogger(Searcher.class.getName()).log(Level.SEVERE, null, ex);
    }

    return restituire;
}

public static void main (String [] args) {
    Searcher s = new Searcher (getTitoli () , true);
    long start = System.nanoTime();
    SortedSet<String> ss = s.getSuggerimenti("comp sciences");
    long end = System.nanoTime();
    for (String s1 : ss)
        System.out.println (s1);

    System.out.println ("TEMPO = " + ((end-start)/1000000) + " ms");
}

}

It's possible to increase efficiency and velocity of this algorithm?If yes, how it's possible? Ps. I know that exist dedicates libraries for these functions (like Lucene) but I can't implement with them the autosuggestion function with insertion errors.

Answer 1

Your risultati is not thread-safe, meaning that different threads tying to push data into it will step on each others' toes and corrupt the tree.

t.interrupt(); doesn't actually do anything if the thread doesn't check itself if it has been interrupted periodically:

while (!Thread.interrupted() && (prossimo = getProssimo ()) != null) {
    if (suggerimentoDaAggiungere (prossimo.toLowerCase()))
        aggiungiRisultato (prossimo);
}

Creating new threads each time you need to query is expensive instead create a ThreadPoolExecutor. You can get one from the static factory methods in Executors.

This allows something like:

Callable<Set<String>> callable = new Callable<Set<String>>(){
    public Set<String> call(){
        Set<String> result = new HashSet<String>();
        String prossimo;
        while (!Thread.interrupted() && (prossimo = getProssimo ()) != null) {
            if (suggerimentoDaAggiungere (prossimo.toLowerCase()))
                result.add(prossimo);
        }
        return result;
    }
}

public SortedSet<String> getSuggerimenti (String testo) {
    List<Callable<String>> callables = Collections.nCopies(numberOfThreads, callable);
    testoSplittato = testo.toLowerCase ().split (" ");

    List<Future<String>> results = threadPool.invokeAll(callables);

    SortedSet<String> sortedResult = new TreeSet<String>();

    for(Future<String> future: results){
        try{
            sortedResult.addAll(future.get());
        }catch(InterrupedException ex){
            Logger.getLogger(Searcher.class.getName()).log(Level.SEVERE, null, ex);
        }catch(ExecutionException ex){
            Logger.getLogger(Searcher.class.getName()).log(Level.SEVERE, null, ex);
        }
    }
    return sortedResult;
}