Grazie a coloro che hanno provato la Sfida 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 di un singolo carattere, quindi duplicati di due caratteri, tre caratteri, ecc., aumentando di un carattere fino a quando non ci sarebbero più duplicati. Controllare ingenuamente tutte le possibili stringhe per una determinata lunghezza diventa sempre più dispendioso in termini di tempo con la lunghezza della sottostringa. Per il genoma del Covid-19 con una lunghezza di circa 30K caratteri, anche se abbiamo la garanzia di avere duplicati di sottostringhe di sette caratteri con solo 4 7 = 16.384 combinazioni uniche, se ne verificano solo 6889 (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 doverci preoccupare di trovare tutti i duplicati. Un approccio semplice sarebbe quello di iniziare la sottostringa dal primo carattere con un duplicato di sette caratteri poiché deve esisterne uno. Quindi, aumentalo un carattere alla volta finché non ci sono più duplicati. Passa al carattere successivo e a una sottostringa duplicata più lunga. Continua finché non sei abbastanza vicino alla fine della stringa di ricerca da rendere impossibile un duplicato. Nel genoma del Covid-19, una sottostringa di otto caratteri ATTAAAG può essere costruito a partire dal primo carattere. Passando al secondo carattere, una stringa di 11 caratteri TTAAAAGGTTTA fissando la posizione 2 ha un duplicato nella posizione 20063. Non ci sono duplicati di 11 caratteri o più a partire dalla posizione 3, quindi ci spostiamo 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 UN S. Tieni presente che nel codice seguente, quando esiste un duplicato per una sottostringa di uguale lunghezza rispetto alla sottostringa più lunga già trovata, Mentre ripete almeno un'altra volta prima di terminare. In queste situazioni nextLen deve essere diminuito 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 ' pubblicato nel post precedente del blog, ho provato a implementare l'approccio di cui sopra utilizzando la corrispondenza dei modelli. Sorprendentemente, i risultati hanno richiesto da cinque a sei volte più tempo. Non sono sicuro del 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 incorporata di JMP, il 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 ripete la 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 le 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 corrispondenza di modelli
stringList = {};
Pat Match(inString, Pat Len(subStringLen) >> nextWord+Pat Test(Insert Into(stringList,nextWord);0));
Per testare la velocità di ciascun 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à della corrispondenza dei modelli. I risultati completi possono essere trovati in Prova a creare sottostringhe.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 dei modelli
|
1.09
|
1.12
|
1.10
|
1.11
|
È stata eseguita un'ANOVA che mostra una differenza statistica (p << 0,001) per Algoritmo, Lunghezza stringa e interazione Algoritmo x Lunghezza 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 di Pattern Matching. Per verificare le prestazioni di questo metodo con un set di caratteri più ampio, è stato eseguito un test con una stringa lunga 1.000.000 di caratteri composta da 26 caratteri selezionati casualmente. Sono state eseguite venti ripetizioni sulla stessa lunghezza di sottostringa di cui sopra più sottostringhe da 2 e 40 caratteri. Sebbene esistessero differenze statistiche, le differenze pratiche erano piccole.
Sottostringa
Lunghezza
|
Tempo (secondi)
|
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 dei duplicati potrebbe assomigliare al codice seguente. 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 le tabelle Private 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 sulla base di 10 esecuzioni utilizzando il Covid-19 e stringhe da 1.000.000 di caratteri. Considerati i risultati, è facile vedere che l'utilizzo esclusivo di questo approccio e senza l'ottimizzazione della dimensione delle sottostringhe sarà problematico man mano che stringhe e 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'ottimizzazione iniziale della dimensione della sottostringa, non possiamo prevedere quanta o poca struttura avranno i dati di input. Un approccio migliore sarebbe quello di utilizzare 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 sottostringa di lunghezza inferiore. 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, senza dubbio, ne sono stato fortemente influenzato. La sfida dell'approccio che ho scelto è stata quella di creare una struttura dati per tenere traccia delle posizioni originali delle sottostringhe. Il codice è sorprendentemente breve, circa 50 righe con spazi generosi. Occorrono circa 0,32 secondi per trovare tutti i duplicati nei dati Covid-19 e 13 secondi per la stringa da 1.000.000 di caratteri. Il codice può essere trovato in findLongestDupe (Riepilogo).JSL .
Riepilogo viene utilizzato per trovare i duplicati ad ogni iterazione. Sebbene questo sia lento per tabelle di grandi dimensioni, dobbiamo solo 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, molto rapidamente. Se il numero di righe nelle poche iterazioni non è troppo grande, questo metodo può essere utilizzato senza ulteriore ottimizzazione, ad esempio iniziando con sottostringhe più lunghe. Un vantaggio di questo metodo è che in queste situazioni è possibile utilizzare un'ulteriore ottimizzazione. L'indicizzazione utilizzata per tenere traccia delle posizioni iniziali delle stringhe funziona nello stesso modo in cui potrebbe essere utilizzata con un array associativo, che è ciò che verrà utilizzato nel metodo finale da discutere. Inizia trovando le posizioni delle stringhe duplicate di lunghezza iniziale e salvale in un array temporaneo. Costruisci stringhe più lunghe di un carattere partendo da queste posizioni assicurandoti di rimuovere eventuali stringhe che supererebbero i limiti della stringa di input. Trova le posizioni delle stringhe duplicate in questo elenco. Possiamo collegare questi nuovi indici alla posizione originale utilizzandoli come indici nell'array precedentemente salvato mantenendo solo gli elementi che hanno indici. Sostituisci l'array precedente con questo. Continua finché non rimangono più duplicati, momento in cui l'array precedente contiene le posizioni dei duplicati più lunghi.
Come accennato in precedenza, il metodo finale ha un sapore simile al precedente. L'idea per 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 si elimina la ricerca diretta nella stringa ed si evitano 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 analisi per diverse dimensioni di stringhe di input (50K – 2,5M) 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 sono disponibili in Confronta i metodi più veloci.JMP.
|
50K
|
100K
|
500K
|
1M
|
2,5 milioni
|
Dimensione set 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 su matrici, che tendono ad essere più veloci delle operazioni su stringhe. Nello specifico, la prima iterazione prende una rappresentazione matriciale di ciascuna posizione del set di caratteri come chiave (ad esempio, [3] per G) in un array associato e utilizza il vettore delle sue posizioni nella stringa di input come valore. Ogni iterazione successiva inizia costruendo un nuovo array associativo trovando i valori della stringa di input su 1 più i valori del vettore 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 associati 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 e i suoi duplicati, se esistenti, vengono rimossi dal vettore e la ricerca continua finché non rimangono più valori. Questo processo di costruzione avviene per ogni elemento dell'array precedente. Una volta completato, il nuovo array associato sostituisce il vecchio e inizia l'iterazione successiva. Questo continua finché 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 piccola modifica per consentire l'utilizzo di set di caratteri diversi.
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 coinvolgevano trasformare gli elementi numerici in caratteri E indicizzazione degli elenchi . 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.
- Scrivi 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.
- Scrivi una funzione che possa trasporre la lista 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" significa che potrebbe essere necessario riempire gli elenchi trasversali 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 tutti mancanti con sufficienti righe e colonne numeriche per contenere i valori numerici nell'elenco. L'indice della tabella dati non è soddisfatto delle righe di lunghezza irregolare e della conversione insoddisfacente di numeri in caratteri durante l'assegnazione. La conversione viene eseguita verso la fine inviando il messaggio SetDataType a un elenco di colonne (evitando un ciclo JSL esplicito). L'elenco di numeri trasposto viene catturato subito prima.
La sottoscrizione della tabella dati desidera essere ottenuta e impostata tramite una matrice numerica quando le colonne sono tutte numeriche, ma verrà impostata felicemente da un elenco di elenchi di numeri. Poiché get restituirà una matrice, ma il requisito del problema è restituire un elenco di numeri trasposti, AsList() esegue il lavoro di riconversione della matrice (dalla tabella dati) in un elenco.
