プログラミングの知恵は、周期的なプログラミング タスクを線形プログラミング タスクに変換する (ベクトル化) ことで計算時間が短縮されることを示唆しています。しかし、これは本当でしょうか？どのような条件下で?いくらくらいでしょうか？課題 1 は、それを知る素晴らしい機会となりました。 4 つの難問に答えるために、7 つの文字のセットごとに次のことを行うことにしました。
- 各文字が辞書の単語に出現する回数を数えます。これにより、項目 2、3、4 に対する答えを見つけることができました。
- 単語に 7 文字セットにない文字が含まれているかどうかを判断します。これは項目 1 で必要でした。
課題 1 try 1.JSL は、 Length関数とRegex関数に基づく列式を使用してカウントを行います。コードを読みやすくするために、いくつかの追加の列式が使用されています。唯一のループは、各文字セットの関数を再評価するために使用されます。実行時間は 29 秒弱です (すべての時間は 10 回の実行の平均です)。悪くはありませんが、素晴らしくはありません。式の複雑さが原因でしょうか、それとも列ではなくループ (リストまたは行列に対する) を使用して式の評価を行う必要があったためでしょうか? test simple.JSLとtest full.JSLを使用して調査しました。列とループの比較に加えて、テーブルから直接入力値を読み取るのとリストから入力値を読み取る方が速いかどうかを確認しました。最初にテーブルの値をリストまたは行列に読み取るのに時間がかかりますか?
以下の結果 (秒単位) は、数式が複雑になるにつれて、数式とループの違いが目立たなくなることを示しています。数式の構築に使用される関数は、時間にはるかに大きな影響を与えました。一般的な検索関数 ( RegexおよびLoc ) は、特定の検索関数 ( ContainsおよびSubstr ) よりもはるかに遅かった。
|
機能
|
式
|
リスト + リストアクセス
|
リスト + テーブルへのアクセス
|
|
長さ
|
0.0525
|
0.1398
|
0.1311
|
|
場所 + アイテム
|
0.4187
|
0.5462
|
0.5383
|
|
Length + 正規表現
|
9.3744
|
9.2745
|
9.3911
|
|
ループ +含む+部分文字列
|
3.3255
|
3.4139
|
3.5444
|
この知識を実践して、2 つの新しいスクリプトを作成しました。チャレンジ 1 試してみる 2.JSL は、 1 つの式内にループを含む式を使用して文字を数えます。課題 2 試してみましょう。JSL は数式ではなくリストを使用します。また、項目 1、2、および 3 を満たす単語には、7 つのレターセット文字すべてが少なくとも 1 回含まれている必要があるという条件も利用します。実行時間はそれぞれ 15.50 秒と 10.40 秒でした。この場合、評価する関数が少なかったため、ループが速くなったと考えられます。どちらの改善も最初の試みよりもはるかに優れていますが、それでも最速ではありません。改善するには、関数の高速化、ループ/関数評価の削減、または課題の質問に答えるための別の方法から行う必要があります。最初の 2 つのアプローチでは実りある可能性が低そうなため、別の方法が模索されました。
チャレンジ 1 の Pattern Matching.JSLスクリプトは@Craige_Halesからのものです。 Craige は最近 JMP 開発を退職しましたが、依然としてコミュニティで非常に活発に活動しています。彼は、 JMPのパターン マッチングと正規表現機能を担当していました。 Craige のソリューションでは、最初に辞書リストを長い文字列に変換することで問題をベクトル化し、次にパターン マッチングを適用して単語を解析してソリューション バケットに入れます。 3.71 秒で実行され、パターン マッチングの幅広さと柔軟性を示す良い例となります。最速の解決策は@brady_bradyによるもので、2.76 秒かかりました。各文字セットを辞書の単語に適用するのではなく、辞書の各単語に含まれるすべてのアルファベット文字の出現数を数えることから始めます。これにより、最初は文字比較の数が 7 から 26 に増加しますが、実行する必要があるのは 1 回だけであり、新しい文字セットごとに再評価する必要がなくなります。回答単語は、最初のアルファベット マトリックスから適切な列を抽出することによって検出され、はるかに高速な解決策が得られます。これは 1146 文字という最も短いスクリプトでもあります。
最初のチャレンジ後のリーダーボードは次のとおりです。
5 月 1 日にリリースされる Challenge 2 をお楽しみに!
@MathStatChem文字数を数える前にコメントと空白を削除します。 新しいスクリプトは、現在の状態では私のマシンで約 3.6 秒で実行されます。 ブレイディよりは遅いですが、クレイジよりは速いです。 いくつかの小さな変更でかなり劇的な違いが得られます。 ただし、一部の項目は正しく回答されていません。 以下は私が使用したレターセットと回答です。
//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"}
新しいスクリプトと古いスクリプトの長さは、それぞれ 2461 と 2469 でした。
したがって、私は基本的に次と同じロジックを使用しました@brady_brady 、しかし、私の最初の文字カウントコードは、より多くのループとリストの呼び出しを使用する非常に非効率なものでした。私は彼のアプローチを置き換えたところ、確かに私のスクリプトは約 3 秒で実行されました。とてもかっこいい！
関数 items() がこれにとって本当に重要です。こんなことになるとは知りませんでした。文字列を個々の文字のリスト (リスト内の個別の項目として繰り返される文字を順番に) に変換します。
アイテム(文字列);
したがって items("easypeasy","") は {"e", "a", "s", "y", "p", "e", "a", "s", "y"} を返します。
次に、contains を使用してアルファベット文字のインデックスを参照することも、非常に優れたトリックでした。
contains("abcedfghijklmnopqrstuvwxyz","a") は 1 を返します。
contains("abcedfghijklmnopqrstuvwxyz","b") は 2 を返します...
コードとログへの出力をもう少し冗長にしましたが、文字を数える前にコメントを削除したかどうかはわかりません。
これが私のコードです（より高速なアプローチで改善されました）。
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 );
