Info:

twitter

Ultimi commenti: Comment feed

Tags:

Sponsor:

Archivio 2018:

Giu Mag Feb Gen

Archivio 2017:

Dic Nov Ott Mag Apr Mar Feb Gen

Archivio 2016:

Dic Nov Ott Ago Mag Mar Feb Gen

Archivio 2015:

Nov Ott Set Mar Gen

Archivio 2014:

Dic Nov Ott Set Lug Giu Mag Apr Gen

Archivio 2013:

Dic Nov Set Ago Lug Giu Mag Apr Feb Gen

Archivio 2012:

Dic Nov Ott Set Ago Giu Mag Apr Mar Feb Gen

Archivio 2011:

Dic Nov Ott Set Ago Lug Giu Mag Apr Mar Feb Gen

Archivio 2010:

Dic Nov Ott Set Ago Lug Giu Mag Apr Mar Feb Gen

Archivio 2009:

Dic Nov Ott Set Ago Lug Giu Mag Apr Mar Feb Gen

Archivio 2008:

Dic Nov Ott Set Ago Lug Giu Mag Apr Mar Feb Gen

Archivio 2007:

Dic Nov Ott Set Ago Lug Giu Mag Apr Mar Feb Gen

Archivio 2006:

Dic Nov Ott Set Ago Lug Giu Mag Apr Mar Feb Gen

Se voi foste il developer - Ottobre 2008

Prendo spunto dalla settimana enigmistica e la rubrica (?) “se voi foste il giudice” con un quizzillo per programmatori ispiratomi da un libro[1] molto bello (quanto accademico).

Data una stringa in input (S) e un insieme noto a priori di prefissi (xyz, abc, …) scrivere un algoritmo estremamente efficiente che ritorni il prefisso giusto se la stringa S comincia per uno dei prefissi.

Nota: i prefissi hanno lunghezza diversa. Se la stringa matcha due prefissi diversi, restituire il prefisso più lungo.

-quack


[1] Il libro si chiama “Algorithms on strings”: Algorithms on strings

Potrebbero interessarti anche:
Commenti (8):
1. Blackstorm
giovedì 16 ottobre 2008 alle 10:21 PM - unknown unknown unknown
   

Uhm...

1. memorizzare i prefissi in ordine crescente di lunghezza e alfabetico in una struttura statica tipo array, aggiungendo dei marker per la lunghezza (esempio: l'ultimo prefisso di lunghezza 3 è tuy, il primo di lunghezza 4 è abcd, l'array avrà a[X-1]=tuy, a[X]="quattro" (o altro marcatore distintivo adeguato), e a[X+1]=abcd).

2. selezionare l'n-simo carattere della stringa partendo n=0, e cercane la prima e l'ultima occorrenza di quel carattere al carattere n-simo della stringa di prefissi nel gruppo di prefissi più lunghi (esempio se sto cercando tuy, selezionando la u cercherò nel gruppo più lungo la prima e l'ultima occorrenza di tutti i prefissi di lunghezza X la cui seconda lettera è u).

3. Se esiste una corrispondenza, selezionare il carattere n+1 della stringa, ponendo n=n+1, e ripetere il punto 2.  Se si è nel gruppo di prefissi a lunghezza m e l'm-simo carattere della stringa S ha una corrispondenza, restituire il prefisso corrispondente all'indice dell'array.

4. Se non esiste una corrispondenza, ripetere dal punto uno cercando nel gruppo precedente. Se si è al primo gruppo di prefissi, restituire NULL.

   
2. Blackstorm
giovedì 16 ottobre 2008 alle 11:51 PM - unknown unknown unknown
   

Forse, pensandoci, l'efficienza si può aumentare scorrendo in parallelo tutti i gruppi... Non so bene perchè ma credo di aver preso la strada più contorta... anche se un conto ad occhio mi dovrebbe dare un tempo di ricerca medio di nklog(m), con n lunghezza dell'array, k lunghezza del prefisso e m numero dei prefissi ocn lunghezza k... forse un po' tantino...

 

Probabilmente è molto più efficiente ordinare i gruppi in maniera alfabetica, in modo da cercare ogni carattere della stringa in maniera sequenziale, senza separarli per gruppi dato che cmq i prefissi più lunghi vengono dopo quelli più corti che cominciano con la stessa lettera ma prima di quelli più corti che cominciano con la successiva. A quel punto basta cercare prima e ultima occorrenza del carattere in questione restringendo il campo ogni volta. In fondo, se n-simo carattere non ha corrispondenze nel sottoinsieme di ricerca, si ritorna all'indice di array precedente, di cui si è tenuta traccia... dovrebbe funzionare, no?

   
3. Phenix
venerdì 17 ottobre 2008 alle 12:25 AM - unknown unknown unknown
   

Dal contesto presumo che si tratti di stringhe composte da lettere dell'alfabeto per cui opto per un pattern matching di Boyer-Moore quando si tratta di fare confronti tra il testo T e i vari pattern P (i prefissi passati).

Non ho voglia (XD) di fare conti se è più conveniente o meno ordinare in ordine di lunghezza i prefissi prima di passare a controntarli con il testo T. Ad occhio penso che per quanto riguarda "il caso medio" sia equivalente.

Quindi, prendo un prefisso alla volta e con Boyer-Moore faccio il controllo del matching. Se il pattern P matcha il testo T lo assegno ad una variabile temporanea nel caso sia più lungo dell'ultimo pattern che ha dato match (avendo cura di sistemare il caso del "primo match").

Finiti i prefissi, se ho avuto almeno un match, restituisco la variabile temporanea (che conterrà il prefisso più lungo che ha fatto match); altrimenti "tanti saluti"

   
4. Phenix
venerdì 17 ottobre 2008 alle 12:27 AM - unknown unknown unknown
   

Dal contesto presumo che si tratti di stringhe composte da lettere dell'alfabeto per cui opto per un pattern matching di Boyer-Moore quando si tratta di fare confronti tra il testo T e i vari pattern P (i prefissi passati).

scritto malissimo, sostiutiamo con:

Dal contesto presumo che si tratti di stringhe composte da lettere dell'alfabeto per cui opto per un pattern matching di Boyer-Moore che quando si tratta di fare confronti in un testo con alfabeto ragionevolmente limitato è molto efficente.

   
5. Stefano
venerdì 17 ottobre 2008 alle 10:01 AM - unknown unknown unknown
   

Si utilizza un bell'automa a stati finiti che inizia a leggere la stringa dal primo carattere e riconosce la stringa in un numoer di passi circa pari alla lunghezza del prefisso

   
6. Gabriele
giovedì 23 ottobre 2008 alle 9:05 PM - unknown unknown unknown
   

Perché non usare un trie?

   
7. Gabriele
giovedì 23 ottobre 2008 alle 9:27 PM - unknown unknown unknown
   

@paperino

>Lo stesso problema l'ho avuto con un'altra Distro che su un HD virtuale mi ha costretto alla reinstallazione dell'OS sempre per problemi di DHCP

A parte che Ubuntu 6.06 è vecchia di due anni... non esiste reinstallare il SO per un problema di rete. Proprio non esiste. Se poi c'è qualcosa che funziona quasi sempre è l'interfaccia di rete e dhcpclient. Mi sa che avevi pasticciato parecchio con i file di configurazione o aver avuto un hw non ben supportato (è raro ma può capitare)...

Riguardo poi la questione dell'autotuning.

Non è chiaro capire dove faccia meglio. Si vede invece dove fa peggio. Però se mi spiegano cosa effettivamente faccia e perché non funziona bene con le scelte di default di Debian leggerei volentieri qualcosa.

Non facciamo per forza i talebani. Se gli amici di Redmond spiegassero al mondo le proprie scelte invece di imporle (e chissenefrega degli standard) sono sicuro che nascerebbe un flag otherPCusesVista in Debian che farebbe felici entrambi. In questo senso Samba docet.

   
8. Paperino
giovedì 23 ottobre 2008 alle 11:07 PM - unknown unknown unknown
   

A parte che Ubuntu 6.06 è vecchia di due anni... non esiste reinstallare il SO per un problema di rete. Proprio non esiste. Se poi c'è qualcosa che funziona quasi sempre è l'interfaccia di rete e dhcpclient. Mi sa che avevi pasticciato parecchio con i file di configurazione o aver avuto un hw non ben supportato (è raro ma può capitare)...

L'ho provato 2 anni fa, la 6.06 era appena uscita. L'installazione è stata liscia niente di strano. Il DHCP ha smesso di funzionare di tutto punto ed il portatile era a circa 60 Km di distanza. La formichina era inviperita e le ho installato XP.

Se gli amici di Redmond spiegassero al mondo le proprie scelte invece di imporle (e chissenefrega degli standard) sono sicuro che nascerebbe un flag otherPCusesVista in Debian che farebbe felici entrambi. In questo senso Samba docet.

Il link era contenuto nell'articolo di technet linkato nel "cioccolatino". Lo ripropongo qui: www.microsoft.com/.../details.aspx

This white paper describes networking and TCP/IP performance enhancements in Windows Vista. It also provides details about migrating to IPv6 and configuring IPv6 by using Teredo, 6to4, and other methods.

   
Lascia un commento:
Commento: (clicca su questo link per gli smiley supportati; regole di ingaggio per i commenti)
(opzionale, per il Gravatar)