Vielen Dank an die Leute, die Challenge 7 ausprobiert haben. Hoffentlich haben Sie die Diskussionen verfolgt, auch wenn Sie keine Chance hatten. Wie können wir diese Herausforderung lösen? Konzeptionell würde der einfachste Ansatz darin bestehen, Duplikate mit einem einzelnen Zeichen, dann Duplikate mit zwei Zeichen, Duplikate mit drei Zeichen usw. zu finden, wobei die Zahl um ein Zeichen erhöht wird, bis keine Duplikate mehr vorhanden sind. Das naive Überprüfen aller möglichen Zeichenfolgen für eine bestimmte Länge wird mit zunehmender Teilzeichenfolgenlänge immer zeitaufwändiger. Für das Covid-19-Genom mit einer Länge von etwa 30.000 Zeichen, obwohl wir garantiert Duplikate von Teilzeichenfolgen mit sieben Zeichen und nur 4 Zeichen haben 7 = 16.384 einzigartige Kombinationen, nur 6889 kommen vor (42 %). Und die Anzahl der Duplikate nimmt ab, da die Anzahl der möglichen Duplikate mit zunehmender Länge der Teilzeichenfolgen schnell zunimmt. 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, bis kein Duplikat mehr vorhanden ist. Wechseln Sie zum nächsten Zeichen und einer längeren doppelten Teilzeichenfolge. Fahren Sie so fort, bis Sie so weit am Ende der Suchzeichenfolge angelangt sind, dass kein Duplikat mehr möglich ist. Im Covid-19-Genom ein aus acht Zeichen bestehender Teilstring ATTAAAGG kann ab dem ersten Zeichen erstellt werden. Gehen wir zum zweiten Zeichen, einer 11-stelligen Zeichenfolge TTAAAGGTTTA Beim Anstarren auf Position 2 gibt es ein Duplikat an Position 20063. Ab Position 3 gibt es keine Duplikate mit 11 oder mehr Zeichen, daher wechseln wir zu Position 4. Und so weiter. Der folgende Code benötigt etwa 5 Sekunden, um die längste duplizierte Zeichenfolge zu finden, zwei überlappende Zeichenfolgen mit je 32 Zeichen A S. Beachten Sie, dass im folgenden Code, wenn ein Duplikat für einen Teilstring vorhanden ist, der gleich lang ist wie der längste bereits gefundene Teilstring, 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 mit @Craige_Hales '-Code, der im vorherigen Blogeintrag veröffentlicht wurde, habe ich versucht, den oben genannten Ansatz mithilfe des Mustervergleichs zu implementieren. Überraschenderweise dauerte es fünf bis sechs Mal länger, bis die Ergebnisse vorlagen. Ich weiß nicht genau warum, aber ich vermute, dass (wie letztes Mal gezeigt) Enthält ist viel schneller, wenn das Teilstring-Duplikat seltener auftritt.
Wir könnten dafür sorgen, dass alles schneller geht, indem wir den integrierten Duplikat-Finder von JMP nutzen Zusammenfassung Tischplattform. Ein Vorteil dieses Ansatzes besteht darin, dass wir mit jeder Teilstringlänge beginnen können. Wie sollen die Teilstrings aufgebaut werden? Zwei Lösungen finden Sie im Blogbeitrag vom letzten Monat. Der 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 Teilzeichenfolgen, die erstellt werden. 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 Mustervergleich
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 Mustervergleichs. Vollständige Ergebnisse finden Sie in Testen Sie Build Substrings.JMP .
Algorithmus
|
Bauzeiten der Saitenlänge (Sek.)
|
4
|
9
|
15
|
21
|
Ausdrücke
|
6,91
|
7.35
|
8.19
|
9.01
|
Schleife
|
2,56
|
2,98
|
3,62
|
4.26
|
Mustervergleich
|
1.09
|
1.12
|
1.10
|
1.11
|
Es wurde eine ANOVA durchgeführt, die einen statistischen Unterschied (p << 0,001) für Algorithmus, Stringlänge und die Interaktion zwischen Algorithmus und Stringlänge zeigte. Post-hoc-Tests mit Tukeys HSD zeigten, dass es keinen statistischen Unterschied zwischen den Stringlängenstufen für den Pattern-Matching-Algorithmus gab. Um zu sehen, wie diese Methode mit einem größeren Zeichensatz funktioniert, wurde ein Test mit einer 1.000.000 Zeichen langen Zeichenfolge durchgeführt, die aus 26 zufällig ausgewählten Zeichen besteht. Zwanzig Wiederholungen wurden mit den gleichen Teilzeichenfolgenlängen wie oben plus Teilzeichenfolgen mit 2 und 40 Zeichen ausgefü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
|
Die Kombination aus Teilzeichenfolgenkonstruktion und Duplikatsuche könnte in etwa wie im folgenden Code aussehen. Wenn wir die mit den Duplikaten verknüpften Zeilen kennen, können wir deren Position in der Zeichenfolge identifizieren. Das wird sich etwas 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 Durchlä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 Uhr
|
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, ermitteln Sie dann anhand dieser Duplikate die längsten Duplikate, die daraus erstellt werden können. Dies funktioniert, da ein Teilstring der längsten Duplikate in der Menge der Duplikate erscheinen muss, die aus einer kürzeren Teilstringlänge erstellt wurden. Es gibt mehrere mögliche Ansätze. Ich wähle einen Ansatz, der der abschließend zu diskutierenden Methode analog ist, sich jedoch 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, alle Duplikate in den Covid-19-Daten zu finden, und 13 Sekunden für die 1.000.000 Zeichen lange Zeichenfolge. 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 länger ist als die Mindestlänge, 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. indem mit längeren Teilzeichenfolgen begonnen wird. Ein Vorteil dieser Methode besteht darin, dass in diesen Situationen zusätzliche Optimierungen durchgeführt werden können. Die Indizierung, die zum Verfolgen der anfänglichen Zeichenfolgenpositionen verwendet wird, funktioniert auf eine Art und Weise, wie sie bei einem assoziativen Array verwendet werden könnte, das in der letzten zu diskutierenden Methode verwendet wird. Suchen Sie zunächst nach den Positionen der doppelten Zeichenfolgen mit der ursprünglichen Länge und speichern Sie sie in einem temporären Array. Erstellen Sie ab diesen Stellen Zeichenfolgen, die ein Zeichen länger sind, und achten Sie darauf, alle Zeichenfolgen zu entfernen, die die Grenzen der Eingabezeichenfolge überschreiten würden. Suchen Sie in dieser Liste nach den Positionen der doppelten Zeichenfolgen. 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 über Indizes verfügen. Ersetzen Sie das vorherige Array durch dieses. Fahren Sie fort, bis keine Duplikate mehr vorhanden sind. Zu diesem Zeitpunkt enthält das vorherige Array die Positionen der längsten Duplikate.
Wie oben erwähnt, ähnelt die endgültige Methode im Geschmack der vorherigen. Die Idee zu diesem Ansatz stammt von @brady_brady . Es gibt einige wichtige Unterschiede. Zunächst werden alle Teilzeichenfolgen ab einem Zeichen erstellt. Das klingt zwar ineffizient, aber durch die Verwendung assoziativer Arrays und die Indizierung der einzelnen Zeichenfolgenzeichen mithilfe von Matrizen entfällt die direkte Suche in der Zeichenfolge und es werden Zeichenkombinationen vermieden, die nicht vorhanden sind. Im Allgemeinen übertrifft es die vorherige Methode, wenn der Zeichensatz und die Eingabezeichenfolge groß werden. Um die beiden Ansätze zu vergleichen, wurden zehn Durchläufe für verschiedene Eingabezeichenfolgengrößen (50 KB – 2,5 MB) und Zeichensätze (4 bis 72) durchgeführt. Nachfolgend werden die mittleren Laufzeiten für die Zusammenfassungsmethode (1) und die Assoziative Array-Methode (2) angezeigt. Vollständige Ergebnisse finden Sie in „Schnellste Methoden vergleichen“. JMP.
|
50.000
|
100.000
|
500.000
|
1M
|
2,5 Millionen
|
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 Summary-Methode beginnt dieser Ansatz damit, die Eingabezeichenfolge in einzelne Zeichen umzuwandeln. Anstatt jedoch direkt mit den Zeichen zu arbeiten, werden ihre numerischen Positionen verwendet, wie sie im Zeichensatz erscheinen. Dies ermöglicht die Erstellung von Teilzeichenfolgen mithilfe von Matrixoperationen, die tendenziell schneller sind als Zeichenfolgenoperationen. Konkret nimmt die erste Iteration eine Matrixdarstellung jeder Zeichensatzposition als Schlüssel (z. B. [3] für G) für ein zugehöriges Array und verwendet den Vektor ihrer Positionen in der Eingabezeichenfolge als Wert. Jede nachfolgende Iteration beginnt mit der Erstellung eines neuen assoziativen Arrays, indem die Eingabezeichenfolgenwerte bei 1 plus die Vektorwerte für jeden Schlüssel im vorherigen Array ermittelt werden. Dabei ist darauf zu achten, dass nicht über das letzte Element in der Eingabezeichenfolge hinausgegangen wird. Der Wert, der dem ersten Element des inkrementierten Vektors entspricht, wird verwendet, um die restlichen 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 durch Verkettung des Zeichensatzwerts des duplizierten Elements mit dem Originalschlüssel erstellt, sodass die Zeichenfolge einfach neu erstellt werden kann. Der Suchwert und seine Duplikate, falls vorhanden, werden aus dem Vektor entfernt und die Suche wird fortgesetzt, bis keine Werte mehr vorhanden 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 so lange fortgesetzt, bis keine neuen Schlüssel mehr vorhanden sind, die das vorherige Array ersetzen könnten. Das vorherige Array enthält die längsten Duplikate.
Bradys Code finden Sie in findLongestDupe (AA).JSL . Ich habe eine kleine Anpassung vorgenommen, um die Verwendung verschiedener Zeichensätze zu ermöglichen.
Beim nächsten Mal wechseln wir von Strings zu Listen. Wie im vorherigen Blog erwähnt, war die Vermeidung von Iterationen das Thema zweier aktueller 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 aufkamen. In beiden Fällen. Sie konvertieren numerische Werte in Zeichenfolgen.
- Schreiben Sie eine Funktion, die eine Liste von abdeckt N Listen (jeweils mit M ich Zahlen). Gehen Sie nicht davon aus M ich ist für alle Listen gleich.
- Schreiben Sie eine Funktion, die die Liste aus 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: „Gehen Sie nicht davon aus mi „ist für alle Listen gleich“ bedeutet, dass die ü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 aus der 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 Tabelle mit allen fehlenden Daten mit genügend Zeilen und numerischen Spalten, um die numerischen Werte in der Liste aufzunehmen. Die Subskription der Datentabelle ist mit Zeilen ungleicher Länge und der Konvertierung von Zahlen in Zeichen während der Zuweisung nicht zufrieden. Die Konvertierung erfolgt gegen Ende, indem die SetDataType-Nachricht an eine Spaltenliste gesendet wird (wodurch eine explizite JSL-Schleife vermieden wird). Die transponierte Zahlenliste wird unmittelbar 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 über eine Liste von Zahlenlisten festgelegt. Da der Get-Befehl eine Matrix zurückgeben soll, die Problemanforderung jedoch darin besteht, eine transponierte Liste von Zahlen zurückzugeben, übernimmt AsList() die Aufgabe, die Matrix (aus der Datentabelle) zurück in eine Liste umzuwandeln.
