Danke an die Leute, die Challenge 7 ausprobiert haben. Hoffentlich haben Sie, auch wenn Sie keine Chance hatten, die Diskussionen verfolgt. Wie können wir diese Herausforderung lösen? Konzeptionell würde der einfachste Ansatz Duplikate mit einem einzigen Zeichen finden, dann Duplikate mit zwei Zeichen, drei Zeichen usw., wobei um ein Zeichen erhöht wird, bis keine Duplikate mehr vorhanden sind. Das naive Überprüfen aller möglichen Zeichenfolgen auf eine bestimmte Länge wird mit zunehmender Länge der Teilzeichenfolge zunehmend zeitaufwändig. Für das Covid-19-Genom mit einer Länge von ungefähr 30.000 Zeichen, obwohl wir garantiert sieben Zeichen Substring-Duplikate mit nur 4 haben 7 = 16.384 einzigartige Kombinationen, nur 6889 kommen vor (42%). Und die Anzahl der Duplikate nimmt ab, wenn die Menge möglicher Duplikate schnell zunimmt, wenn die Teilstrings länger werden. Damit dieser Ansatz funktioniert, muss eine effiziente Methode zur Identifizierung von Duplikaten gefunden werden. Wir werden darauf zurückkommen, nachdem wir andere Möglichkeiten untersucht haben, dieses Problem anzugehen.
Konzentrieren wir uns darauf, nur das längste Duplikat zu finden, ohne uns darum kümmern zu müssen, alle Duplikate zu finden. Ein einfacher Ansatz wäre, die Teilzeichenfolge beim ersten Zeichen mit einem siebenstelligen Duplikat zu beginnen, da eines vorhanden sein muss. Erweitern Sie es dann um ein Zeichen nach dem anderen, bis es kein Duplikat mehr gibt. Wechseln Sie zum nächsten Zeichen und zu einer längeren doppelten Teilzeichenfolge. Fahren Sie so fort, bis Sie nahe genug am Ende der Suchzeichenfolge sind, dass ein Duplikat nicht möglich ist. Im Covid-19-Genom eine achtstellige Teilzeichenfolge ATTAAAGG kann ab dem ersten Zeichen gebaut werden. Gehen Sie zum zweiten Zeichen, einer 11-stelligen Zeichenfolge TTAAAGGTTTA starrt auf Position 2 hat ein Duplikat an Position 20063. Es gibt keine doppelten 11-stelligen oder längeren Zeichen, die an Position 3 beginnen, also bewegen wir uns zu Position 4. Usw. Der folgende Code benötigt etwa 5 Sekunden, um die längste duplizierte Zeichenfolge zu finden, zwei sich überschneidende Zeichenfolgen mit 32 Zeichen A S. Beachten Sie, dass im folgenden Code, wenn ein Duplikat für eine Teilzeichenfolge mit der gleichen Länge wie die längste bereits gefundene Teilzeichenfolge vorhanden ist, Während iteriert mindestens noch einmal, bevor es beendet wird. In diesen Situationen nextLen muss um 1 dekrementiert werden.
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;
);
Wie bei @Craige_Hales '-Code, der im vorherigen Blogeintrag gepostet wurde, habe ich versucht, den obigen Ansatz mithilfe von Musterabgleich zu implementieren. Überraschenderweise dauerte das Ergebnis fünf- bis sechsmal länger. Ich bin mir nicht sicher, warum, aber meine Vermutung ist, dass (wie letztes Mal gezeigt) Enthält ist viel schneller, wenn das Duplikat der Teilzeichenfolge seltener auftritt.
Wir könnten die Dinge beschleunigen, indem wir den integrierten Duplikatfinder von JMP nutzen, den Zusammenfassung Tischplattform. Ein Vorteil dieses Ansatzes besteht darin, dass wir mit einer beliebigen Teilstringlänge beginnen können. Wie sollten Sie die Teilstrings aufbauen? Zwei Lösungen finden Sie im Blogbeitrag vom letzten Monat. Die erste atomisiert und iteriert über die Eingabezeichenfolge.
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)],""))
);
Wo inString ist die Eingabezeichenfolge und subStringLen ist die Länge der zu erstellenden Teilzeichenfolgen. Ein nicht iterativer Ansatz kann mithilfe von Ausdrücken implementiert werden:
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);
oder Musterabgleich
stringList = {};
Pat Match(inString, Pat Len(subStringLen) >> nextWord+Pat Test(Insert Into(stringList,nextWord);0));
Um die Geschwindigkeit jedes Ansatzes zu testen, habe ich Teilzeichenfolgen der Größe 4, 9, 15 und 21 auf einer 1.000.000 Zeichen langen Eingabezeichenfolge erstellt, die aus vier zufällig generierten Zeichen bestand. Bei jeder Länge wurden zehn Iterationen durchgeführt. Die folgenden Ergebnisse zeigen die Überlegenheit des Musterabgleichs. Die vollständigen Ergebnisse finden Sie in Test Build Substrings.JMP .
Algorithmus
|
Saitenlänge Aufbauzeiten (Sek.)
|
4
|
9
|
15
|
21
|
Ausdrücke
|
6.91
|
7.35
|
8.19
|
9.01
|
Schleife
|
2.56
|
2,98
|
3.62
|
4.26
|
Musterabgleich
|
1.09
|
1.12
|
1.10
|
1.11
|
Es wurde eine ANOVA durchgeführt, die einen statistischen Unterschied (p << 0,001) für Algorithmus, Zeichenfolgenlänge und die Interaktion Algorithmus x Zeichenfolgenlänge zeigte. Post-hoc-Tests mit Tukeys HSD zeigten, dass es keinen statistischen Unterschied zwischen den String-Längenstufen für den Pattern-Matching-Algorithmus gab. Um zu sehen, wie sich diese Methode mit einem größeren Zeichensatz verhält, wurde ein Test mit einer 1.000.000 Zeichen langen Zeichenfolge durchgeführt, die aus 26 zufällig ausgewählten Zeichen zusammengestellt wurde. Zwanzig Wiederholungen wurden mit den gleichen Teilkettenlängen wie oben plus 2- und 40-Zeichen-Teilketten durchgeführt. Während es statistische Unterschiede gab, waren die praktischen Unterschiede gering.
Teilzeichenfolge
Länge
|
Zeit (Sek.)
|
2
|
1.11
|
4
|
1.08
|
9
|
1.09
|
15
|
1.11
|
24
|
1.13
|
40
|
1.53
|
Das Zusammenfügen von Teilstring-Konstruktion und Duplikatsuche könnte in etwa so aussehen wie im folgenden Code. Wenn wir die mit den Duplikaten verknüpften Zeilen kennen, können wir ihre Position in der Zeichenfolge identifizieren. Dies wird sich wenig später zu unserem Vorteil auswirken. Wenn Sie die Tabellen privat machen, werden die Vorgänge etwas beschleunigt.
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);
Die folgende Tabelle gibt die durchschnittliche Laufzeit für eine einzelne Iteration basierend auf 10 Läufen unter Verwendung von Covid-19 und 1.000.000 Zeichenketten an. Angesichts der Ergebnisse ist leicht zu erkennen, dass die ausschließliche Verwendung dieses Ansatzes und ohne Optimierung der Teilstringgröße problematisch sein wird, wenn Strings und Teilstrings größer werden.
Teilzeichenfolge
Länge
|
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
|
Selbst wenn wir mit der Optimierung der Teilstringgröße beginnen, können wir nicht vorhersagen, wie viel oder wenig Struktur die Eingabedaten haben werden. Ein besserer Ansatz wäre die Verwendung einer Hybridstrategie. Verwenden Zusammenfassung Um Duplikate einer bestimmten Größe zu identifizieren, finden Sie dann unter Verwendung dieser Duplikate allein die längsten Duplikate, die daraus erstellt werden können. Dies funktioniert, da eine Teilzeichenfolge der längsten Duplikate in der Gruppe von Duplikaten erscheinen muss, die aus einer kürzeren Teilzeichenfolge erstellt wurden. Es gibt mehrere mögliche Vorgehensweisen. Ich wähle einen Ansatz, der der abschließend zu diskutierenden Methode entspricht, sich aber von ihr unterscheidet. Um ehrlich zu sein, habe ich die endgültige Methode gesehen, bevor ich diesen Ansatz entwickelt habe, und war zweifellos stark davon beeinflusst. Die Herausforderung des von mir gewählten Ansatzes bestand darin, eine Datenstruktur zu erstellen, um die ursprünglichen Teilstringpositionen zu verfolgen. Der Code ist überraschend kurz, etwa 50 Zeilen mit großzügigen Abständen. Es dauert etwa 0,32 Sekunden, um alle Duplikate in den Covid-19-Daten zu finden, und 13 Sekunden für die Zeichenfolge mit 1.000.000 Zeichen. Den Code finden Sie in findLongestDupe (Zusammenfassung).JSL .
Zusammenfassung wird verwendet, um die Duplikate bei jeder Iteration zu finden. Während dies bei großen Tabellen langsam ist, müssen wir nur Tabellen erstellen, die so groß sind wie die Anzahl der Duplikate aus dem vorherigen Schritt. Beginnend mit einer Teilzeichenfolge, die ein Zeichen über der Mindestlänge liegt, um Duplikate zu garantieren, nimmt die Gesamtzahl der Duplikate wahrscheinlich ab, wenn nicht sofort, dann sehr schnell. Wenn die Anzahl der Zeilen in den wenigen Iterationen nicht zu groß ist, kann diese Methode ohne weitere Optimierung verwendet werden, z. B. das Starten mit längeren Teilzeichenfolgen. Ein Vorteil dieser Methoden besteht darin, dass in diesen Situationen eine zusätzliche Optimierung verwendet werden kann. Die Indizierung, die verwendet wird, um die anfänglichen Zeichenfolgenpositionen zu verfolgen, funktioniert in einer Weise, wie sie mit einem assoziativen Array verwendet werden könnte, was in der abschließenden zu diskutierenden Methode verwendet wird. Beginnen Sie damit, die Positionen der doppelten Zeichenfolgen der ursprünglichen Länge zu finden, und speichern Sie sie in einem temporären Array. Erstellen Sie Zeichenfolgen ausgehend von diesen Stellen um ein Zeichen länger und achten Sie darauf, alle Zeichenfolgen zu entfernen, die die Grenzen der Eingabezeichenfolge überschreiten würden. Suchen Sie die Positionen der doppelten Zeichenfolgen in dieser Liste. Wir können diese neuen Indizes wieder mit dem ursprünglichen Speicherort verknüpfen, indem wir sie als Indizes für das zuvor gespeicherte Array verwenden und nur die Elemente behalten, die Indizes haben. Ersetzen Sie das vorherige Array durch dieses. Fahren Sie fort, bis keine Duplikate mehr übrig sind, zu welchem Zeitpunkt das vorherige Array die Positionen der längsten Duplikate enthält.
Wie oben erwähnt, ähnelt die endgültige Methode der vorherigen. Die Idee zu diesem Ansatz ist zu verdanken @brady_brady . Es gibt ein paar wichtige Unterschiede. Zuerst baut es alle Teilstrings von einem Zeichen aufwärts auf. Dies klingt zwar ineffizient, aber durch die Verwendung von assoziativen Arrays und die Indizierung der einzelnen Zeichenfolgenzeichen mithilfe von Matrizen entfällt das direkte Durchsuchen der Zeichenfolge und es werden nicht vorhandene Zeichenkombinationen vermieden. Im Allgemeinen übertrifft es die vorherige Methode, wenn der Zeichensatz und die Eingabezeichenfolge groß werden. Zehn Läufe für verschiedene Eingangsstringgrößen (50K – 2,5M) und Zeichensätze (4 bis 72) wurden durchgeführt, um die beiden Ansätze zu vergleichen. Die mittleren Laufzeiten sind unten für die Summary-Methode (1) und die Associative Array-Methode (2) angegeben. Vollständige Ergebnisse finden Sie unter „Schnellste Methoden vergleichen.JMP“.
|
50K
|
100.000
|
500.000
|
1M
|
2,5 Mio
|
Zeichensatzgröße
|
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
|
Wie bei der Zusammenfassungsmethode beginnt dieser Ansatz damit, die Eingabezeichenfolge in einzelne Zeichen umzuwandeln. Anstatt direkt mit den Zeichen zu arbeiten, werden jedoch ihre numerischen Positionen verwendet, wie sie im Zeichensatz erscheinen. Dies ermöglicht das Erstellen von Teilzeichenfolgen mithilfe von Matrixoperationen, die tendenziell schneller sind als Zeichenfolgenoperationen. Insbesondere nimmt die erste Iteration eine Matrixdarstellung jeder Zeichensatzposition als Schlüssel (z. B. [3] für G) zu einem zugeordneten Array und verwendet den Vektor seiner Positionen in der Eingabezeichenkette als seinen Wert. Jede nachfolgende Iteration beginnt mit dem Erstellen eines neuen assoziativen Arrays, indem die Eingabezeichenfolgenwerte bei 1 plus die Vektorwerte für jeden Schlüssel im vorherigen Array gesucht werden, wobei darauf geachtet wird, dass das letzte Element in der Eingabezeichenfolge nicht überschritten wird. Der dem ersten Element des inkrementierten Vektors entsprechende Wert wird verwendet, um den Rest der inkrementierten Vektorwerte nach Duplikaten zu durchsuchen. Wenn sie vorhanden sind, werden die Positionen, denen sie zugeordnet sind, für den Wert im neuen Array-Element verwendet. Der Schlüssel für dieses Element wird erstellt, indem der Zeichensatzwert des duplizierten Elements mit dem ursprünglichen Schlüssel verkettet wird, was es einfach macht, die Zeichenfolge neu zu erstellen. Der Suchwert und seine Duplikate, falls vorhanden, werden aus dem Vektor entfernt und die Suche wird fortgesetzt, bis keine Werte mehr übrig sind. Dieser Erstellungsprozess findet für jedes Element im vorherigen Array statt. Nach Abschluss ersetzt das neue assoziierte Array das alte und die nächste Iteration beginnt. Dies wird fortgesetzt, bis keine neuen Schlüssel vorhanden sind, um das vorherige Array zu ersetzen. Das vorherige Array enthält die längsten Duplikate.
Bradys Code findet sich in findLongestDupe (AA).JSL . Ich habe eine kleine Anpassung vorgenommen, um die Verwendung verschiedener Zeichensätze zu ermöglichen.
Beim nächsten Mal werden wir von Strings zu Listen wechseln. Wie im vorherigen Blog erwähnt, war das Vermeiden von Iterationen das Thema zweier neuerer Community-Beiträge Numerische Elemente in Zeichen umwandeln Und Listenindizierung . Zwei Herausforderungen für das nächste Mal. Sie basieren auf Fragen, die in den verlinkten Beiträgen auftauchten. In beiden Fällen. Sie wandeln numerische Werte in Zeichenfolgen um.
- Schreiben Sie eine Funktion, die eine Liste von umwandelt N Listen (jeweils mit M ich Zahlen). Vermute nicht M ich ist für alle Listen gleich.
- Schreiben Sie eine Funktion, die die Liste von Punkt 1 transponieren kann. Hier ein kleines Beispiel:
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}}
Viel Glück!
Hier ist eine Möglichkeit, die Herausforderung anzugehen. Ich beschloss: „Nicht annehmen mi ist für alle Listen gleich" bedeutete, dass die listenübergreifenden Listen möglicherweise mit fehlenden Werten aufgefüllt werden müssen. Repeat({.},10) erzeugt {.,.,.,.,.,.,.,.,.,.}. Insert() fügt die Elemente aus der Liste hinzu, nicht die Liste (siehe So fügen Sie eine Liste in eine andere Liste ein .)
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>Diese JSL erstellt eine vollständig fehlende Datentabelle mit genügend Zeilen und numerischen Spalten, um die numerischen Werte in der Liste aufzunehmen. Die Subskription von Datentabellen ist mit Zeilen ungleicher Länge und der Umwandlung von Zahlen in Zeichen während der Zuweisung unzufrieden. Die Konvertierung erfolgt gegen Ende, indem die SetDataType-Nachricht an eine Liste von Spalten gesendet wird (wodurch eine explizite JSL-Schleife vermieden wird). Die transponierte Zahlenliste wird kurz davor erfasst.
Die Subskription von Datentabellen möchte über eine numerische Matrix abgerufen und festgelegt werden, wenn die Spalten alle numerisch sind, wird jedoch gerne aus einer Liste von Zahlenlisten festgelegt. Da get eine Matrix zurückgeben wird, die problematische Anforderung jedoch darin besteht, eine transponierte Liste von Zahlen zurückzugeben, übernimmt AsList() die Aufgabe, die Matrix (aus der Datentabelle) zurück in eine Liste zu konvertieren.
