[python, java] facebook puzzle

[mad_hhatter]

da qualche tempo mi sto cimentando con i puzzle di facebook. Al moment sono alle prese con questo: http://www.facebook.com/careers/puzzles.php?puzzle_id=17

In soldoni il problema da risolvere è calcolare, data una stringa e una lista di parole valide, quale sia la parola valida più "simile" alla stringa data.

Ho iniziato con una soluzione naive in python, usando l'algoritmo di distanza di Levenshtein e una ricerca completa nello spazio delle parole ammesse.
Ho poi aggiunto un'ottimizzazione basata sugli upper- e lower- bound dell'algoritmo di distanza, in modo da poter filtrare alcune parole della lista senza doverne calcolarne l'effettiva distanza dalla stringa in input.

Dato che la mia implementazione passava tutti i test case proposti nella pagina di discussione relativa al puzzle, ma veniva respinta dal bot di valutazione, ho pensato che il problema fossero le performance.
Ho quindi deciso di provare a implementare la soluzione in Java.

A parità di algoritmo e di test case l'implementazione in Java è drammaticamente più veloce di quella in python (tanto per dare degli ordini di grandezza, con uno specifico test case la versione python termina in 45s, quella in java in 0.8s - sì, quarantacinque contro zero virgola otto!).

Nonostante ciò il bot continua a respingere la soluzione e, confrontando i miei tempi con quelli postati da altri utenti, mi accorgo che ho dei tempi quasi doppi (anche se non viene indicato l'hw usato nei test).

Osservando la lista di parole ammesse, mi accorgo che molte hanno prefissi uguali. Decido quindi di aggiungere una nuova ottimizzazione: mantenere una hashtable di prefissi e dei corrispondenti vettori di distanza dalla stringa in input in modo da velocizzare il calcolo della distanza.

Inserendo questa strategia nella versione python, l'incremento prestazionale è lampante: con lo stesso test case di cui sopra la nuova versione impiega 22s contro i 45 della versione senza ottimizzazione.

Introducendo la stessa strategia nella versione java ho avuto una spiacevole sorpresa: i tempi crescevano (!) in modo drammatico passando da 0.8s a ben 3s!!!

Ho provato a eliminare parti del codice di ottimizzazione per cercare di isolare il responsabile di un tale disastro e ho concluso che il problema è imputabile

- al metodo String.substring (che, per le dimensioni degli input e per il tipo di implementazione, viene chiamato qualche milione di volte), oppure
- alla gestione della hashtable (ma provando a varianre la initial capacity il tempo varia di poco e non sempre si riduce).
Ho letto in varie pagine web che l'uso di substring in java è sconsigliato proprio per motivi di performance.

Che ne pensate?

grazie :)

[mad_hhatter]

per la cronaca, ho inviato una soluzione rimuovendo l'uso della hashtable e aggiungendo invece una semplice ricerca della stringa in input nella lista delle parole ammesse in modo da ottimizzare il caso in cui la stirnga in input sia valida.

Ho notato infatti che senza questo accorgimento la mia soluzione risultava in linea con i tempi degli altri utenti, ma soffriva pesantemente nei casi in cui, appunto, in input ci fosse un'alta incidenza di stringhe valide (caso in cui è molto più conveniente la ricerca all'interno della lista di parole ammesse piuttosto che il calcolo della distanza rispetto a ciascuna parola in lista).

Vediamo se ora passa...

[]Rik`[]

substring da quello che ricordo è da evitare come la peste, o almeno così mi sembra di ricordare da una vecchia lezione all'uni..

[cdimauro]

Se la substring viene utilizzata per confrontare l'inizio della stringa coincide con una data stringa (visto che si parlava di prefissi), sia in Python che in Java si potrebbe utilizzare il metodo startswith (startsWith in Java) allo scopo.

In entrambi i linguaggi il vantaggio è che non viene continuamente allocata e disallocata memoria, tra l'altro.

Comunque da quel che ho capito il bot boccia la soluzione in base al tempo d'esecuzione, ma non c'è messo un tempo preciso? Ho dato una (molto) rapida occhiata, e non ho trovato criteri di bocciatura.

[mad_hhatter]

Se la substring viene utilizzata per confrontare l'inizio della stringa coincide con una data stringa (visto che si parlava di prefissi), sia in Python che in Java si potrebbe utilizzare il metodo startswith (startsWith in Java) allo scopo.

In entrambi i linguaggi il vantaggio è che non viene continuamente allocata e disallocata memoria, tra l'altro.

Comunque da quel che ho capito il bot boccia la soluzione in base al tempo d'esecuzione, ma non c'è messo un tempo preciso? Ho dato una (molto) rapida occhiata, e non ho trovato criteri di bocciatura.

purtroppo uso substring per cercare e inserire chiavi in una hashtable quindi non credo di poter usare startswith.

non ci sono parametri espliciti, semplicemente nella mail di risposta il bot dice che ha trovato dei bug che possono essere logici o di performance, ma volutamente non specifica i dettagli (per evitare di essere usato come server di debug).

Tra l'altro la mia ultima soluzione è stata nuovamente respinta... devo controllare di non aver lasciato codice di debug, ma a sto punto non so che altro fare.... vedremo.

In ogni caso mi ha sorpreso
1. la differenza di prestazioni tra l'interprete python e la jvm
2. l'efficienza della gestione dei dizionari e delle stringhe in python rispetto a java

[banryu79]

Se già non l'hai fatto un'occhiatina all'implementazione di substring può rendere l'idea, guarda un po' che combina:

public String substring(int beginIndex, int endIndex) {
if (beginIndex < 0) {
throw new StringIndexOutOfBoundsException(beginIndex);
}
if (endIndex > count) {
throw new StringIndexOutOfBoundsException(endIndex);
}
if (beginIndex > endIndex) {
throw new StringIndexOutOfBoundsException(endIndex - beginIndex);
}
return ((beginIndex == 0) && (endIndex == count)) ? this :
new String(offset + beginIndex, endIndex - beginIndex, value);
}

4 salti condizionati + allocazione di un nuovo oggetto String ad ogni chiamata :D


Idea, potresti estendere String con una tua classe a cui aggiungi un metodo, tipo:

public char[] subchars(int beginIndex, int endIndex) {
final int start = this.offset + beginIndex;
final int count = endIndex - beginIndex;
char[] subchars = new char[count];
System.arraycopy(this.value, start, subchars, 0, count);
return subchars;
}

Al max è per verificare se effettivamente così girerebbe più veloce.

[]Rik`[]

allora ricordavo bene, è agghiacciante :D

[banryu79]

Rik`[;34144051']allora ricordavo bene, è agghiacciante :D
No, semplicemente è stata implementata con la massima priorità circa la sicurezza d'uso, e non perchè fosse estremamente prestante.

[cdimauro]

purtroppo uso substring per cercare e inserire chiavi in una hashtable quindi non credo di poter usare startswith.
Ho capito, ma a questo punto non vedo alternative alla substring per quello che ti serve.
non ci sono parametri espliciti, semplicemente nella mail di risposta il bot dice che ha trovato dei bug che possono essere logici
Addirittura. Non è che il bot sia costituito da neuroni reali? :D
o di performance, ma volutamente non specifica i dettagli (per evitare di essere usato come server di debug).
OK, ma almeno un tetto massimo alle prestazioni potevano metterlo.

Anche perché i linguaggi utilizzati sono abbastanza variegati, e differiscono molto a livello prestazionale.
Tra l'altro la mia ultima soluzione è stata nuovamente respinta... devo controllare di non aver lasciato codice di debug, ma a sto punto non so che altro fare.... vedremo.
Io gli scriverei e chiederei di conoscere almeno il tetto massimo oltre il quale scatta il timeout per l'applicazione, e le caratteristiche di massima della macchina in cui gira. Almeno eviterei di proporre soluzioni se so già in partenza che verrebbero bocciate causa inefficienza.
In ogni caso mi ha sorpreso
1. la differenza di prestazioni tra l'interprete python e la jvm
Purtroppo è concreta: quest'ultima utilizza un compilatore JIT di default, mentre la versione mainstream di Python (e quella usata non è nemmeno delle più recenti; da un pezzo è disponibile la 2.7, che è anche più efficiente) non ne usa al momento.
2. l'efficienza della gestione dei dizionari e delle stringhe in python rispetto a java
Perché stringhe e dizionari sono elementi di "prima classe", in quanto alla base di questo linguaggio sia in termini di utilizzo end-user che internamente.

Un consiglio per migliorare le prestazioni: cerca di incapsulare tutto il codice dentro funzioni, e NON accedere a variabili globali, se ti è possibile (al limite passale come parametri durante una chiamata a funzione) ma soltanto se vengono referenziate dentro un loop (se, invece, sono utilizzate "una tantum", per singoli controlli o utilizzi, vanno bene anche globali).

In questo modo tutte le variabili (compresi i parametri passati a una funzione) sono definiti "locali", e il loro accesso (load, store) è di molto più veloce.

Altra cosa: disabilita il garbage collector all'inizio del codice.

[mad_hhatter]

Ho capito, ma a questo punto non vedo alternative alla substring per quello che ti serve.

Addirittura. Non è che il bot sia costituito da neuroni reali? :D


sicuramente è tutto automatizzato, però ovviamente dovranno evitare script che si inloopano e soprattutto avranno bisogno di processare la coda di soluzioni inviate senza far aspettare giorni per avere una risposta (infatti al max il giorno dopo l'invio il bot risponde).

poi è anche divertente sapere che devi confrontarti non solo con la correttezza logica, ma anche con vincoli prestazionali.


OK, ma almeno un tetto massimo alle prestazioni potevano metterlo.

Anche perché i linguaggi utilizzati sono abbastanza variegati, e differiscono molto a livello prestazionale.


sì questo è un po' fastidioso, nel senso che se il vincolo prestazionale fa parte dei requisiti, dovrebbe essere specificato.

E' comunque un buon metodo per capire quale strumento è più adatto a determinati task: finora non avevo mai dovuto confrontarmi più di tanto con l'inadeguatezza di un certo linguaggio nei confronti di un certo problema.


Io gli scriverei e chiederei di conoscere almeno il tetto massimo oltre il quale scatta il timeout per l'applicazione, e le caratteristiche di massima della macchina in cui gira. Almeno eviterei di proporre soluzioni se so già in partenza che verrebbero bocciate causa inefficienza.


infatti credo che farò così


Purtroppo è concreta: quest'ultima utilizza un compilatore JIT di default, mentre la versione mainstream di Python (e quella usata non è nemmeno delle più recenti; da un pezzo è disponibile la 2.7, che è anche più efficiente) non ne usa al momento.


avevo anche provato a compilare il modulo python per ottenre il corrispondente .pyc, ma le prestazioni sono rimaste invariate


Un consiglio per migliorare le prestazioni: cerca di incapsulare tutto il codice dentro funzioni, e NON accedere a variabili globali, se ti è possibile (al limite passale come parametri durante una chiamata a funzione) ma soltanto se vengono referenziate dentro un loop (se, invece, sono utilizzate "una tantum", per singoli controlli o utilizzi, vanno bene anche globali).

In questo modo tutte le variabili (compresi i parametri passati a una funzione) sono definiti "locali", e il loro accesso (load, store) è di molto più veloce.

il codice è già così, ma grazie per il suggerimento!


Altra cosa: disabilita il garbage collector all'inizio del codice.
grazie di nuovo!

[cdimauro]

Un'altra cosa che mi viene in mente è che potresti preallocare una matrice di una certa dimensione per il calcolo della distanza di Levenshtein, in modo da non allocare e disallocare ogni volta.

Inoltre (ma è tutta da verificare), forse usando array.array (con 'b' o 'i') per allocare le singole "righe" della matrice potresti guadagnare qualcosa. Quindi potresti usare una tupla i cui elementi sono istanze di array.array e accedervi con m[i][j].