Die Programmierweisheit legt nahe, dass die Umwandlung einer zyklischen Programmieraufgabe in eine lineare, 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, entschied ich mich für jeden Satz von sieben Buchstaben:
- Zählen Sie, wie oft jeder Buchstabe in einem Wörterbuchwort vorkommt. Dadurch konnte ich Antworten auf die Punkte 2, 3 und 4 finden.
- Bestimmen Sie, ob ein Wort Buchstaben hatte, die nicht im Sieben-Buchstaben-Satz enthalten waren. Dies wurde für Punkt 1 benötigt.
Herausforderung 1 versuchen Sie 1.JSL führt die Zählung mithilfe von Spaltenformeln aus, die auf dem basieren Länge Und Regex Funktionen. Einige zusätzliche Spaltenformeln werden verwendet, um den Code leichter lesbar zu machen. 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 über 10 Durchläufe gemittelt). Nicht schlecht, aber nicht großartig. Liegt es an der Komplexität der Formeln oder daran, dass die Formelauswertung über eine Schleife (über eine Liste oder Matrix) statt über eine Spalte hätte erfolgen sollen? ich benutzte teste simple.JSL Und teste full.JSL zu untersuchen. Neben dem Vergleich von Spalte und Schleife habe ich geschaut, ob es schneller geht, die Eingabewerte direkt aus der Tabelle oder aus einer Liste zu lesen. Erhöht es die Zeit, die Werte aus der Tabelle zuerst in eine Liste oder Matrix einzulesen?
Die folgenden Ergebnisse (in Sekunden) zeigen, dass der Unterschied zwischen Formel und Schleife weniger offensichtlich ist, je komplexer die Formeln wurden. Die zum Erstellen der Formeln verwendeten Funktionen hatten einen viel größeren Einfluss auf die Zeit. Die allgemeinen Suchfunktionen ( Regex Und Lok ) waren viel langsamer als bestimmte Suchfunktionen ( Enthält Und Substr ).
Funktionen
|
Formel
|
Liste + Listenzugriff
|
Listen- und Tabellenzugriff
|
Länge
|
0,0525
|
0,1398
|
0,1311
|
Lok + Artikel
|
0,4187
|
0,5462
|
0,5383
|
Länge + 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 nutzt auch die Bedingung aus, dass jedes Wort, das die Punkte 1, 2 und 3 erfüllt, alle sieben Buchstaben des Buchstabensatzes mindestens einmal enthalten muss. Die Laufzeiten betrugen 15,50 bzw. 10,40 Sekunden. In diesem Fall war die Schleife wahrscheinlich schneller, da weniger Funktionen auszuwerten waren. Jede Verbesserung ist viel besser als mein erster Versuch, aber immer noch nicht die schnellste. Verbesserungen müssten aus schnelleren Funktionen, weniger Schleifen/Funktionsauswertungen oder einer anderen Methode zur Beantwortung der Herausforderungsfragen kommen. Da die ersten beiden Ansätze weniger fruchtbare Möglichkeiten zu ergeben schienen, wurde nach einer anderen Methode gesucht.
Der Herausforderung 1 Musterabgleich.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 verantwortlich für den Musterabgleich und die Funktionalität für reguläre Ausdrücke in JMP . Die Lösung von Craige vektorisiert das Problem, indem sie zuerst die Wörterbuchliste in eine lange Zeichenfolge umwandelt und dann einen Musterabgleich anwendet, um die Wörter in Lösungs-Buckets zu parsen. Es läuft in 3,71 Sekunden und bietet ein großartiges Beispiel für die Breite und Flexibilität des Musterabgleichs. Die schnellste Lösung, die 2,76 Sekunden dauerte, war von @brady_brady . Anstatt jeden Buchstabensatz auf die Wörterbuchwörter anzuwenden, beginnt er damit, die Anzahl der Vorkommen für jeden Buchstaben des Alphabets in jedem Wörterbuchwort zu zählen. Während dies anfänglich die Anzahl der Buchstabenvergleiche von 7 auf 26 erhöht, muss es nur einmal durchgeführt werden, wodurch eine Neubewertung für jeden neuen Buchstabensatz vermieden wird. Antwortwörter werden gefunden, indem die entsprechenden Spalten aus der anfänglichen Alphabetmatrix extrahiert werden, was zu einer viel schnelleren Lösung führt. Es ist auch das kürzeste Skript mit 1146 Zeichen.
Hier ist die Rangliste nach der ersten Herausforderung:
Bleib dran für Herausforderung 2, die am 1. Mai erscheint!
@MathStatChem Ich entferne die Kommentare und Leerzeichen, bevor ich die Zeichen zähle. Ihr neues Skript läuft in etwa 3,6 Sekunden auf meinem Computer in seinem aktuellen Zustand. Langsamer als Bradys, aber schneller als Craiges. Ziemlich dramatischer Unterschied für ein paar kleine Änderungen! Einige der Items werden jedoch nicht richtig beantwortet. Unten sind 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ängen Ihrer neuen und alten Skripte waren 2461 bzw. 2469.
Also habe ich im Grunde die gleiche Logik wie verwendet @brady_brady , aber mein ursprünglicher Code zum Zählen von Buchstaben war einfach sehr ineffizient und verwendete mehr Schleifen und Aufrufe von Listen.Ich ersetzte seinen Ansatz und tatsächlich lief mein Skript in etwa 3 Sekunden.Sehr cool!
Die Funktion items() ist wirklich der Schlüssel dazu.Ich wusste nicht, dass es das tun würde.Konvertiert einen String mit just in eine Liste seiner einzelnen Zeichen (in der Reihenfolge, mit wiederholten Buchstaben als separate Elemente in der Liste).
Artikel (Zeichenfolge);
also items("easypeasy","") gibt {"e", "a", "s", "y", "p", "e", "a", "s", "y"} zurück.
Dann war die Verwendung von contains, um auf den Index des Buchstabens des Alphabets zu verweisen, auch ein wirklich netter Trick.
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, 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 );
