Programmierkenntnisse legen nahe, dass die Umwandlung einer zyklischen Programmieraufgabe in eine lineare Aufgabe, die Vektorisierung, die Rechenzeit verbessert. Aber ist das wahr? Unter welchen Bedingungen? Um wie viel? Herausforderung 1 bot eine großartige Gelegenheit, dies herauszufinden. Um die vier Herausforderungsfragen zu beantworten, habe ich beschlossen, dass ich für jeden Satz von sieben Buchstaben Folgendes tun würde:
- Zählen Sie, wie oft jeder Buchstabe in einem Wörterbuchwort vorkommt. Dadurch konnte ich Antworten auf die Punkte 2, 3 und 4 finden.
- Stellen Sie fest, ob ein Wort Buchstaben hatte, die nicht im Sieben-Buchstaben-Satz enthalten waren. Dies wurde für Punkt 1 benötigt.
Herausforderung 1, Versuch 1.JSL führt die Zählung mithilfe von Spaltenformeln durch, die auf den Funktionen „Länge “ und „Regex“ basieren. Um den Code leichter lesbar zu machen, werden einige zusätzliche Spaltenformeln verwendet. Die einzige Schleife wird verwendet, um die Funktionen für jeden Buchstabensatz neu zu bewerten. Die Laufzeit beträgt knapp 29 Sekunden (alle Zeiten sind gemittelt über 10 Läufe). Nicht schlecht, aber nicht großartig. Liegt es an der Komplexität der Formeln oder liegt es daran, dass die Formelauswertung mithilfe einer Schleife (über eine Liste oder Matrix) statt einer Spalte hätte erfolgen sollen? Zur Untersuchung habe ich test simple.JSL und test full.JSL verwendet. Zusätzlich zum Vergleich von Spalte und Schleife habe ich geprüft, ob es schneller ist, die Eingabewerte direkt aus der Tabelle oder aus einer Liste zu lesen. Verlängert es die Zeit, die Werte zunächst aus der Tabelle in eine Liste oder Matrix einzulesen?
Die folgenden Ergebnisse (in Sekunden) zeigen, dass der Unterschied zwischen Formel und Schleife mit zunehmender Komplexität der Formeln weniger deutlich wird. Die zum Erstellen der Formeln verwendeten Funktionen hatten einen viel größeren Einfluss auf die Zeit. Die allgemeinen Suchfunktionen ( Regex und Loc ) waren viel langsamer als spezifische Suchfunktionen ( Contains und Substr ).
|
Funktionen
|
Formel
|
Liste + Listenzugriff
|
Listen- und Tabellenzugriff
|
|
Länge
|
0,0525
|
0,1398
|
0,1311
|
|
Ort + Artikel
|
0,4187
|
0,5462
|
0,5383
|
|
Length + Regex
|
9.3744
|
9.2745
|
9.3911
|
|
Schleifen + Enthält + Substr
|
3.3255
|
3.4139
|
3.5444
|
Um dieses Wissen in die Praxis umzusetzen, habe ich zwei neue Skripte erstellt. Herausforderung 1, Versuch 2. JSL verwendet Formeln mit einer Schleife innerhalb einer Formel, um die Buchstaben zu zählen. Herausforderung 2 Versuchen Sie 3.JSL verwendet Listen statt Formeln. Es macht sich auch die Bedingung zunutze, dass jedes Wort, damit es die Punkte 1, 2 und 3 erfüllt, mindestens einmal alle sieben Buchstaben des Buchstabensatzes enthalten muss. Die Laufzeiten betrugen 15,50 bzw. 10,40 Sekunden. In diesem Fall war die Schleife wahrscheinlich schneller, da weniger Funktionen auszuwerten waren. Beide Verbesserungen sind viel besser als bei meinem ersten Versuch, aber immer noch nicht die schnellsten. Verbesserungen müssten durch schnellere Funktionen, weniger Schleifen/Funktionsauswertungen oder eine andere Methode zur Beantwortung der Herausforderungsfragen erfolgen. Da die ersten beiden Ansätze wahrscheinlich keine fruchtbaren Möglichkeiten zu bieten schienen, wurde nach einer anderen Methode gesucht.
Das Challenge 1 Pattern Matching.JSL- Skript stammt von @Craige_Hales . Craige hat sich kürzlich von JMP Development zurückgezogen, ist aber immer noch sehr aktiv in der Community. Er war für den Mustervergleich und die Funktionalität regulärer Ausdrücke in JMP verantwortlich. Craiges Lösung vektorisiert das Problem, indem sie zunächst die Wörterbuchliste in eine lange Zeichenfolge konvertiert und dann einen Mustervergleich anwendet, um die Wörter in Lösungsbereiche zu analysieren. Es läuft in 3,71 Sekunden und bietet ein großartiges Beispiel für die Breite und Flexibilität des Mustervergleichs. Die schnellste Lösung, die 2,76 Sekunden dauerte, stammte von @brady_brady . Anstatt jeden Buchstabensatz auf die Wörter im Wörterbuch anzuwenden, beginnt er damit, die Anzahl der Vorkommen für jeden Buchstaben des Alphabets in jedem Wort im Wörterbuch zu zählen. Dies erhöht zwar zunächst die Anzahl der Buchstabenvergleiche von 7 auf 26, muss jedoch nur einmal durchgeführt werden, wodurch eine Neubewertung für jeden neuen Buchstabensatz vermieden wird. Antwortwörter werden durch Extrahieren der entsprechenden Spalten aus der anfänglichen Alphabetmatrix gefunden, was zu einer viel schnelleren Lösung führt. Mit 1146 Zeichen ist es auch das kürzeste Skript.
Hier ist die Bestenliste nach der ersten Herausforderung:
Seien Sie gespannt auf die Veröffentlichung von Challenge 2 am 1. Mai!
@MathStatChem Ich entferne die Kommentare und Leerzeichen, bevor ich die Zeichen zähle. Ihr neues Skript wird im aktuellen Zustand auf meinem Rechner in etwa 3,6 Sekunden ausgeführt. Langsamer als Bradys, aber schneller als Craiges. Ziemlich dramatischer Unterschied für ein paar kleine Änderungen! Einige Punkte werden jedoch nicht richtig beantwortet. Unten finden Sie die Buchstabensätze, die ich zusammen mit den Antworten verwendet habe.
//acehlot
1. {"acacatechol"}
2. {"scientificophilosophical"}
3. {"hypercivilization"}
4. {"macracanthrorhynchiasis", "pancreaticoduodenostomy", "pericardiomediastinitis"}
//ilosuvx
1. {"lixivious"}
2.{"subclavioaxillary"}
3.{"excitovascular"}
4. {"formaldehydesulphoxylate"}
//mnoruwy
1.{"unwormy"}
2.{"countrywoman", "journeywoman", "laundrywoman"}
3.{"jurywoman"}
4.{"formaldehydesulphoxylate"}
Die Länge Ihres neuen und Ihres alten Skripts betrug 2461 bzw. 2469.
Also habe ich im Grunde die gleiche Logik verwendet wie @brady_brady , aber mein ursprünglicher Code zur Buchstabenzählung war einfach sehr ineffizient, da er mehr Schleifen und Aufrufe von Listen verwendete.Ich ersetzte ihn durch seinen Ansatz und tatsächlich lief mein Skript in etwa 3 Sekunden.Sehr cool!
Die Funktion items() ist hierfür wirklich der Schlüssel.Ich wusste nicht, dass es das bewirken würde.Konvertiert eine Zeichenfolge in eine Liste ihrer einzelnen Zeichen (in der Reihenfolge, wobei wiederholte Buchstaben als separate Elemente in der Liste auftreten) mit just
Elemente(Zeichenfolge);
also gibt items("easypeasy","") {"e", "a", "s", "y", "p", "e", "a", "s", "y"} zurück.
Dann war es auch ein wirklich netter Trick, „contains“ zu verwenden, um auf den Index des Buchstabens des Alphabets zu verweisen.
enthält("abcedfghijklmnopqrstuvwxyz","a") gibt 1 zurück,
enthält("abcedfghijklmnopqrstuvwxyz","b") gibt 2 zurück, ...
Ich habe meinen Code und die Ausgabe im Protokoll etwas ausführlicher gestaltet und bin mir nicht sicher, ob Sie Kommentare entfernt haben, bevor Sie die Zeichen gezählt haben.
Hier ist mein Code (verbessert mit dem schnelleren Ansatz):
startTime = Time Of Day( Today() );
letterSetList = {"apouter", "abdcefl", "acouter", "rstlneo", "efghijk"};
alphabet = {"a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x",
"y", "z"};
abet="abcedfghijklmnopqrstuvwxyz";
_dt = Current Data Table();
numwords = N Rows( _dt );
_c = Column( _dt, "Words" );
wordlist = _c << get values;
// get lengths of each word in word list
// also create a matrix indicating how many times each letter in the alphabet is used in each word
wordlengths = J( numwords, 1, 0 );
alphacounts = J( numwords, 26, 0 );
For( ii = 1, ii <= numwords, ii++,
its=items(wordlist[ii],"");
wordlengths[ii] = Length( wordlist[ii] );
for(jj=1, jj<=nitems(its), jj++, alphacounts[ii,contains(abet,its[jj])]++);
);
// also create a matrix indicating if a letter in the alphabet is used in each word
alphaindex = alphacounts > 0;
For( ll = 1, ll <= N Items( letterSetList ), ll++,
str = letterSetList[ll];
// create an indicator vector for the letters in the string
str_alphaindex = J( 1, 26, 0 );
For( jj = 1, jj <= 26, jj++,
For( kk = 1, kk <= Length( str ), kk++,
str_alphaindex[1, jj] = str_alphaindex[1, jj] + (Substr( str, kk, 1 ) == alphabet[jj])
)
);
// 1 The longest word using all seven letters and only those seven letters. Letters may be used more than once.
// words that meet this criteria will have a "zero distance" from their letter indicator row and the string letter indicator vector
pickrow1 = Distance( alphaindex, str_alphaindex ) == 0;
// now find the word that has the longest length
pickrow1 = pickrow1 & (wordlengths == Max( wordlengths[Loc( pickrow1 )] ));
Print( "1. Find longest word(s) that uses only the letters <" || str || "> (item " || Char( ll ) || " from itemSetList)" );
If( Dim( Loc( pickrow1 ) )[1],
Print( wordlist[Loc( pickrow1 )] );
Print( "which is in the following row(s) from the Word List table " );
Print( Loc( pickrow1 & (wordlengths == Max( wordlengths[Loc( pickrow1 )] )) ) );
,
Print( "no word(s) found" )
);
Print( "-------------------" );
// 2 The longest word using all seven letters and any other letters.
// words that meet this condition, the sum of their letter indictor rows for the letters in the string should equal 7
pickrow2 = (V Sum( alphaindex[0, Loc( str_alphaindex )]` )` == 7);
// now find the word that has the longest length
pickrow2 = pickrow2 & (wordlengths == Max( wordlengths[Loc( pickrow2 )] ));
Print(
"2. Find longest word(s) that use all letters <" || str || "> (item " || Char( ll ) ||
" from itemSetList) and/or any other letters"
);
If( Dim( Loc( pickrow2 ) )[1],
Print( wordlist[Loc( pickrow2 )] );
Print( "which is in the following row(s) from the Word List table " );
Print( Loc( pickrow2 ) );
,
Print( "no word(s) found" )
);
Print( "-------------------" );
// 3 The longest word using all seven letters and any other letters where no letter
// from the set of seven is used more than once.
// words that meet this condition, meet the condition for the 2nd rule but also the sum of their letter counts for
// the letters in the string has to be equal to 7
pickrow3 = (V Sum( alphaindex[0, Loc( str_alphaindex )]` )` == 7) & (V Sum( alphacounts[0, Loc( str_alphaindex )]` )` == 7);
// now find the word that has the longest length
pickrow3 = pickrow3 & (wordlengths == Max( wordlengths[Loc( pickrow3 )] ));
Print(
"3. Find longest word(s) that use all letters <" || str || "> (item " || Char( ll ) ||
" from itemSetList) only once and/or any other letters "
);
If( Dim( Loc( pickrow3 ) )[1],
Print( wordlist[Loc( pickrow3 )] );
Print( "which is in the following row(s) from the Word List table " );
Print( Loc( pickrow3 ) );
,
Print( "no word(s) found" )
);
Print( "-------------------" );
// 4 The longest word in which 5 of the 7 letters appears.
// Any letter including those outside of the 7 may appear once or more
// except the two unused letters from the list of 7, which may not appear at all.
// words that meet this condition have the sum of their letter indicators (for the letters in the string) equal to 5
pickrow4 = (V Sum( alphaindex[0, Loc( str_alphaindex )]` )` == 5);
// now find the word that has the longest length
pickrow4 = pickrow4 & (wordlengths == Max( wordlengths[Loc( pickrow4 )] ));
Print(
"4. Find longest word(s) that uses only 5 of the 7 letters <" || str || "> (item " || Char( ll ) ||
" from itemSetList) and/or any other letters"
);
If( Dim( Loc( pickrow4 ) )[1],
Print( wordlist[Loc( pickrow4 )] );
Print( "which is in the following row(s) from the Word List table " );
Print( Loc( pickrow4 ) );
,
Print( "no word(s) found" )
);
Print( "-------------------" );
);
endTime = Time Of Day( Today() );
Print( endTime - startTime );
