Grazie a quelle persone che hanno provato Challenge 7. Se tutto va bene, anche se non ne hai avuto la possibilità, hai seguito le discussioni. Come possiamo risolvere questa sfida? Concettualmente, l'approccio più semplice troverebbe duplicati a carattere singolo, quindi duplicati a due caratteri, tre caratteri, ecc., aumentando di un carattere fino a quando non ci sono più duplicati. Il controllo ingenuo di tutte le possibili stringhe per una data lunghezza diventa sempre più dispendioso in termini di lunghezza della sottostringa. Per il genoma Covid-19 con una lunghezza di circa 30.000 caratteri, anche se abbiamo la garanzia di avere duplicati di sottostringhe di sette caratteri con solo 4 7 = 16.384 combinazioni uniche, solo 6889 si verificano (42%). E il numero di duplicati diminuisce man mano che la quantità di possibili duplicati aumenta rapidamente man mano che le sottostringhe si allungano. Affinché questo approccio funzioni, è necessario trovare un metodo efficiente per identificare i duplicati. Torneremo su questo dopo aver esaminato altri modi per affrontare questo problema.
Concentriamoci solo sulla ricerca del duplicato più lungo senza doversi preoccupare di trovare tutti i duplicati. Un approccio semplice consisterebbe nell'iniziare la sottostringa al primo carattere con un duplicato di sette caratteri poiché ne deve esistere uno. Quindi, fai crescere un carattere alla volta fino a quando non ci sono duplicati. Passa al carattere successivo ea una sottostringa duplicata più lunga. Continua finché non sei abbastanza vicino alla fine della stringa di ricerca che non è possibile un duplicato. Nel genoma del Covid-19, una sottostringa di otto caratteri ATTAAAGG può essere costruito a partire dal primo carattere. Passando al secondo carattere, una stringa di 11 caratteri TTAAAGGTTTA fissare la posizione 2 ha un duplicato nella posizione 20063. Non ci sono caratteri duplicati di 11 o più caratteri a partire dalla posizione 3, quindi passiamo alla posizione 4. E così via. Il codice seguente richiede circa 5 secondi per trovare la stringa duplicata più lunga, due stringhe sovrapposte di 32 caratteri di UN S. Si noti che nel codice seguente, quando esiste un duplicato per una sottostringa di lunghezza uguale alla sottostringa più lunga già trovata, Mentre itera almeno un'altra volta prima di terminare. In queste situazioni successivoLen deve essere decrementato di 1.
findLongestDupe = Function({inString,charSet},{parts,nextLen,nextPos=1,longestDupes={""}},
parts = Items(inString,"");
nextLen = Floor(Log(Length(inString))/Log(N Items(charSet)));
While(nextPos <= Length(inString)-nextLen+1,
nextWord = Concat Items(parts[nextPos::(nextPos+nextLen-1)],"");
While(Contains(inString,nextWord,nextPos+1),
nextLen++;
nextWord = Concat Items(parts[nextPos::(nextPos+nextLen-1)],"");
);
nextPos++;
If(Length(nextWord)>Length(longestDupes[1]),
nextLen--; //nextLen will be one more than longest length when Pat Match fails
nextWord = Concat Items(parts[nextPos::(nextPos+nextLen-1)],"");
If(Length(nextWord)==Length(longestDupes[1])+1,
Insert Into(longestDupes,nextWord),
longestDupes = Eval List({nextWord})
);
);
nextChar++;
);
longestDupes;
);
Come con @Craige_Hales ' codice pubblicato nel post di blog precedente, ho provato a implementare l'approccio di cui sopra utilizzando la corrispondenza del modello. Sorprendentemente, i risultati hanno richiesto da cinque a sei volte più tempo. Non so esattamente perché, ma la mia impressione è che (come illustrato l'ultima volta) Contiene è molto più veloce quando il duplicato della sottostringa si verifica meno frequentemente.
Potremmo velocizzare le cose sfruttando la funzione di ricerca duplicati integrata di JMP, the Riepilogo piattaforma da tavolo. Un vantaggio di questo approccio è che possiamo iniziare con qualsiasi lunghezza di sottostringa. Come dovresti costruire le sottostringhe? Due soluzioni possono essere trovate nel post del blog del mese scorso. Il primo atomizza e itera sulla stringa di input.
parts = Items(inString,"");
nInds = Length(inString) - subStringLen + 1;
stringList = {};
For(i=1,i<=nInds,i++,
Insert Into(stringList,Concat Items(parts[i::(i + subStringLen - 1)],""))
);
Dove inString è la stringa di input e subStringLen è la lunghezza delle sottostringhe da costruire. Un approccio non iterativo può essere implementato utilizzando espressioni:
parts = Items(inString,"");
nInds = Length(inString) - subStringLen + 1;
stringList = {};
i=1;
stringList[1::nInds] = Expr(Concat Items(parts[i::(i++ + subStringLen - 1)],""));
stringList = Eval List(stringList);
o la corrispondenza del modello
stringList = {};
Pat Match(inString, Pat Len(subStringLen) >> nextWord+Pat Test(Insert Into(stringList,nextWord);0));
Per testare la velocità di ogni approccio, ho creato sottostringhe di dimensione 4, 9, 15 e 21 su una stringa di input lunga 1.000.000 di caratteri composta da quattro caratteri generati casualmente. Sono state eseguite dieci iterazioni per ciascuna lunghezza. I risultati seguenti mostrano la superiorità del pattern matching. I risultati completi sono disponibili in Prova Build Substrings.JMP .
Algoritmo
|
Tempi di costruzione della lunghezza della stringa (sec)
|
4
|
9
|
15
|
21
|
Espressioni
|
6.91
|
7.35
|
8.19
|
9.01
|
Ciclo continuo
|
2.56
|
2,98
|
3.62
|
4.26
|
Corrispondenza del modello
|
1.09
|
1.12
|
1.10
|
1.11
|
È stata eseguita un'ANOVA che mostra una differenza statistica (p << 0,001) per l'algoritmo, la lunghezza della stringa e l'interazione algoritmo x lunghezza della stringa. I test post hoc utilizzando l'HSD di Tukey hanno indicato che non vi era alcuna differenza statistica tra i livelli di lunghezza delle stringhe per l'algoritmo Pattern Matching. Per vedere come funzionava questo metodo con un set di caratteri più grande, è stato eseguito un test con una stringa lunga 1.000.000 di caratteri composta da 26 caratteri selezionati casualmente. Venti ripetizioni sono state eseguite sulle stesse lunghezze di sottostringa di cui sopra più sottostringhe di 2 e 40 caratteri. Mentre c'erano differenze statistiche, le differenze pratiche erano piccole.
Sottostringa
Lunghezza
|
Tempo (sec)
|
2
|
1.11
|
4
|
1.08
|
9
|
1.09
|
15
|
1.11
|
24
|
1.13
|
40
|
1.53
|
Mettere insieme la costruzione della sottostringa e la ricerca duplicata potrebbe assomigliare al codice qui sotto. Conoscere le righe associate ai duplicati ci consente di identificare la loro posizione nella stringa. Questo funzionerà a nostro vantaggio un po 'più tardi. Rendere i tavoli privati velocizza leggermente le operazioni.
stringList = {};
Pat Match(inString, Pat Len(subStringLen) >> nextWord+Pat Test(Insert Into(stringList,nextWord);0));
tmpTbl = New Table("tmp",New Column("tmp",Character,Values(stringList)),Private);
sumTbl = tmpTbl << Summary(Group(:tmp),Private);
dupeLocs = sumTbl << Get Rows Where(:N Rows > 1);
dupes = Column(sumTbl,1)[dupeLocs];
Close(tmpTbl,No Save);
La tabella seguente fornisce il tempo di esecuzione medio per una singola iterazione basata su 10 esecuzioni utilizzando Covid-19 e 1.000.000 di stringhe di caratteri. Dati i risultati, è facile vedere che l'utilizzo esclusivo di questo approccio e senza l'ottimizzazione delle dimensioni delle sottostringhe sarà problematico man mano che le stringhe e le sottostringhe diventano più grandi.
Sottostringa
Lunghezza
|
COVID-19
|
1M
|
2
|
0,0517
|
1.68
|
4
|
0,0504
|
4.25
|
9
|
0.1837
|
8.29
|
15
|
0,2226
|
8.63
|
21
|
0.2209
|
8.85
|
40
|
0,2957
|
12.30
|
Anche con l'avvio dell'ottimizzazione della dimensione della sottostringa, non possiamo prevedere quanta o poca struttura avranno i dati di input. Un approccio migliore sarebbe quello di impiegare una strategia ibrida. Utilizzo Riepilogo per identificare i duplicati di una determinata dimensione, quindi, utilizzando solo questi duplicati, trova i duplicati più lunghi che possono essere costruiti da essi. Funzionerà, poiché una sottostringa dei duplicati più lunghi deve apparire nell'insieme di duplicati creati da una lunghezza di sottostringa più breve. Esistono diversi approcci possibili. Scelgo un approccio analogo, ma diverso, dal metodo finale da discutere. Ad essere onesti, ho visto il metodo finale prima di elaborare questo approccio e ne sono stato, senza dubbio, fortemente influenzato. La sfida dell'approccio che ho scelto è stata quella di creare una struttura dati per tenere traccia delle posizioni delle sottostringhe originali. Il codice è sorprendentemente breve, circa 50 righe con spaziatura generosa. Sono necessari circa 0,32 secondi per trovare tutti i duplicati nei dati Covid-19 e 13 secondi per la stringa di 1.000.000 di caratteri. Il codice è reperibile in findLongestDupe (Riepilogo).JSL .
Riepilogo viene utilizzato per trovare i duplicati su ogni iterazione. Anche se questo è lento per tabelle di grandi dimensioni, abbiamo solo bisogno di creare tabelle grandi quanto il numero di duplicati del passaggio precedente. A partire da una lunghezza della sottostringa di un carattere oltre la lunghezza minima per garantire i duplicati, è probabile che il numero totale di duplicati diminuisca se non immediatamente, quindi molto rapidamente. Se il numero di righe nelle poche iterazioni non è troppo grande, questo metodo può essere utilizzato senza ulteriori ottimizzazioni, ad esempio iniziando con sottostringhe più lunghe. Un vantaggio di questi metodi è che in queste situazioni è possibile utilizzare un'ulteriore ottimizzazione. L'indicizzazione utilizzata per tenere traccia delle posizioni iniziali delle stringhe funziona in un modo simile a quello che potrebbe essere impiegato con un array associativo, che è ciò che viene utilizzato nel metodo finale da discutere. Inizia trovando le posizioni delle stringhe duplicate di lunghezza iniziale e salvale in un array temporaneo. Costruisci stringhe di un carattere più lunghe partendo da queste posizioni assicurandoti di rimuovere qualsiasi stringa che superi i limiti della stringa di input. Trova le posizioni delle stringhe duplicate in questo elenco. Possiamo ricollegare questi nuovi indici alla posizione originale utilizzandoli come indici all'array salvato in precedenza mantenendo solo quegli elementi che hanno indici. Sostituisci l'array precedente con questo. Continua fino a quando non rimangono più duplicati, momento in cui l'array precedente contiene le posizioni dei duplicati più lunghi.
Come accennato in precedenza, il metodo finale è simile nel sapore al precedente. L'idea di questo approccio è grazie a @brady_brady . Ci sono alcune differenze importanti. Innanzitutto, crea tutte le sottostringhe da un carattere in su. Sebbene ciò sembri inefficiente, utilizzando gli array associativi e indicizzando i singoli caratteri della stringa utilizzando le matrici elimina la ricerca diretta della stringa ed evita combinazioni di caratteri che non esistono. In generale, supera il metodo precedente quando il set di caratteri e la stringa di input diventano grandi. Per confrontare i due approcci sono state effettuate dieci esecuzioni per varie dimensioni di stringhe di input (50 K – 2,5 M) e set di caratteri (da 4 a 72). Di seguito sono riportati i tempi di esecuzione medi per il metodo Summary (1) e il metodo Associative Array (2). I risultati completi possono essere trovati in Confronta i metodi più veloci.JMP.
|
50K
|
100K
|
500K
|
1M
|
2,5 M
|
Dimensione del set di caratteri
|
1
|
2
|
1
|
2
|
1
|
2
|
1
|
2
|
1
|
2
|
4
|
0,5087
|
0,5814
|
0.9081
|
1.2664
|
5.421
|
6.813
|
13.412
|
13.778
|
32.23
|
35,67
|
10
|
0,2724
|
0.4117
|
0,6251
|
0.9207
|
2.850
|
4.509
|
6.998
|
9.503
|
13.61
|
24.70
|
26
|
0,3098
|
0,3748
|
0,6786
|
0,7441
|
3.625
|
3.981
|
7.363
|
8.537
|
21.68
|
19.58
|
52
|
0,4247
|
0,3265
|
1.0617
|
0,7682
|
4.246
|
4.046
|
9.522
|
7.395
|
30.67
|
18.08
|
72
|
0,3186
|
0,3309
|
0,7308
|
0,7079
|
3.533
|
4.236
|
7.192
|
8.917
|
20.14
|
18.97
|
Come con il metodo Summary, questo approccio inizia trasformando la stringa di input in singoli caratteri. Invece di lavorare direttamente con i caratteri, tuttavia, vengono utilizzate le loro posizioni numeriche così come appaiono nel set di caratteri. Ciò consente la creazione di sottostringhe utilizzando operazioni con matrici, che tendono ad essere più veloci delle operazioni con stringhe. Nello specifico, la prima iterazione prende una rappresentazione matriciale di ciascuna posizione del set di caratteri come chiave (ad esempio, [3] per G) per un array associato e usa il vettore delle sue posizioni nella stringa di input come suo valore. Ogni iterazione successiva inizia costruendo un nuovo array associativo trovando i valori della stringa di input in 1 più i valori vettoriali per ogni chiave nell'array precedente, facendo attenzione a non andare oltre l'ultimo elemento nella stringa di input. Il valore corrispondente al primo elemento del vettore incrementato viene utilizzato per cercare duplicati nel resto dei valori del vettore incrementato. Se esistono, le posizioni a cui sono associate vengono utilizzate per il valore nel nuovo elemento dell'array. La chiave per questo elemento viene creata concatenando il valore del set di caratteri dell'elemento duplicato alla chiave originale, semplificando la ricreazione della stringa di caratteri. Il valore di ricerca ei suoi duplicati, se esistono, vengono rimossi dal vettore e la ricerca continua finché non rimangono valori. Questo processo di costruzione si verifica per ogni elemento nell'array precedente. Una volta completato, il nuovo array associato sostituisce il vecchio e inizia la successiva iterazione. Questo continua fino a quando non ci sono nuove chiavi per sostituire l'array precedente. L'array precedente contiene i duplicati più lunghi.
Il codice di Brady può essere trovato in findLongestDupe (AA).JSL . Ho apportato una modifica minore per consentire l'utilizzo di diversi set di caratteri.
Per la prossima volta passeremo dalle stringhe alle liste. Come accennato nel blog precedente, evitare l'iterazione è stato l'argomento di due recenti post della community che hanno coinvolto trasformare gli elementi numerici in carattere E indicizzazione della lista . Due sfide per la prossima volta. Si basano su domande emerse nei post collegati. In entrambi i casi. Stai convertendo valori numerici in stringhe di caratteri.
- Scrivere una funzione che copra un elenco di N elenchi (ciascuno con M io numeri). Non dare per scontato M io è lo stesso per tutte le liste.
- Scrivere una funzione che possa trasporre l'elenco dall'elemento 1. Ecco un piccolo esempio:
inputList = {{12, 11, 16, 1, 15, ., 23, 8, 16, 17}, {1, 10, ., 4, 25, ., 19, 21, ., 3}, {11, 21,
22, 7, 3, ., 24, 10, 21, 20}, {., ., ., ., ., ., ., ., ., .}, {11, ., 3, ., 9, ., 23,
., 3, 16}};
outputList = {{12, 1, 11, ., 11}, {11, 10, 21, ., .}, {16, ., 22, ., 3}, {1, 4, 7, ., .}, {15, 25,
3, ., 9}, {., ., ., ., .}, {23, 19, 24, ., 23}, {8, 21, 10, ., .}, {16, ., 21, ., 3},
{17, 3, 20, ., 16}}
Buona fortuna!
Ecco un modo per affrontare la sfida. Ho deciso "Non dare per scontato mi è lo stesso per tutti gli elenchi" significava che gli elenchi trasversali potrebbero dover essere riempiti con valori mancanti. Ripeti({.},10) produce {.,.,.,.,.,.,.,.,.,.}. Insert() aggiunge gli elementi dalla lista, non dalla lista (vedi Come inserire una lista in un'altra lista .)
inputList = {
{12, 11, 16, 1, 15, ., 23, 8, 16, 17},
{1, 10, ., 4, 25, ., 19, 21, ., 3},
{11, 21, 22, 7, 3, ., 24, 10, 21, 20},
{1}, // odd across-list
{., ., ., ., ., ., ., ., ., .},
{11, ., 3, ., 9, ., 23, ., 3, 16}};
// find rows and max cols of input:
nrows = N Items( inputList );
ncols = 0;
For( irow = 1, irow <= nrows, irow += 1,
ncols = Max( ncols, N Items( inputList[irow] ) )
);
// if the across-lists are not all the same size, add missing values
For( irow = 1, irow <= nrows, irow += 1,
If( ncols > N Items( inputList[irow] ),
Insert Into( inputList[irow], Repeat( {.}, ncols - N Items( inputList[irow] ), . ) )
)
);
// make a table of numbers from the lists
dt = New Table( "temp", invisible, Add Rows( nrows ), <<ADD multiple="" columns=""></ADD>Questo JSL crea una tabella di dati mancanti con un numero sufficiente di righe e colonne numeriche per contenere i valori numerici nell'elenco. L'indice della tabella dati non è soddisfatto delle righe di lunghezza non uniforme e non è soddisfatto della conversione da numerico a carattere durante l'assegnazione. La conversione viene eseguita verso la fine inviando il messaggio SetDataType a un elenco di colonne (evitando un loop JSL esplicito). L'elenco di numeri trasposto viene acquisito poco prima.
Il subscripting della tabella dati vuole essere ottenuto e impostato tramite una matrice numerica quando le colonne sono tutte numeriche, ma sarà felicemente impostato da un elenco di elenchi di numeri. Poiché get restituirà una matrice, ma il requisito del problema è restituire un elenco di numeri trasposto, AsList() esegue il lavoro di riconversione della matrice (dalla tabella dati) in un elenco.
