2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ Thanks a lot for your answer but i don't understand how to create a ThreadPoolExecutor.. \$\endgroup\$ – Quasi Affatto Jan 22 '15 at 18:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.