プログラミングの知恵によると、循環プログラミング タスクを線形タスク、つまりベクトル化に変えると、計算時間が改善されます。 しかし、これは本当ですか？ どんな条件で？ いくらで？ 課題 1 は、それを知る絶好の機会を提供してくれました。 4 つの課題の質問に答えるために、7 文字のセットごとに次のことを行うことにしました。
- 各文字が辞書の単語に出現する回数を数えます。 これにより、項目 2、3、および 4 に対する答えを見つけることができました。
- 単語に 7 文字セット以外の文字が含まれているかどうかを判断します。 これは項目 1 に必要でした。
チャレンジ 1 トライ 1.JSLに基づいて列の数式を使用してカウントを行います長さと正規表現機能。 コードを読みやすくするために、いくつかの追加の列式が使用されています。 唯一のループは、各文字セットの関数を再評価するために使用されます。 実行時間は 29 秒弱です (すべての時間は 10 回の実行の平均です)。 悪くはありませんが、素晴らしいものではありません。 数式の複雑さですか、それとも列ではなくループ (リストまたはマトリックス) を使用して数式の評価を行う必要があるためですか? 使ったシンプルなJSLをテストするとフルテスト.JSL調べる。 列とループを比較するだけでなく、テーブルから直接入力値を読み取るか、リストから入力値を読み取る方が速いかを調べました。 最初にテーブルからリストまたはマトリックスに値を読み取る時間が追加されますか?
以下の結果 (秒単位) は、数式が複雑になるにつれて、数式とループの違いがわかりにくくなっていることを示しています。 数式を作成するために使用された関数は、時間にはるかに大きな影響を与えました。 一般的な検索機能 (正規表現とロク) は、特定の検索機能 (含むとサブストリング）。
機能
|
方式
|
リスト + リスト アクセス
|
リスト + テーブル アクセス
|
長さ
|
0.0525
|
0.1398
|
0.1311
|
ロク+アイテム
|
0.4187
|
0.5462
|
0.5383
|
長さ+正規表現
|
9.3744
|
9.2745
|
9.3911
|
ループ +含む+サブストリング
|
3.3255
|
3.4139
|
3.5444
|
この知識を実践して、2 つの新しいスクリプトを作成しました。 チャレンジ 1 トライ 2.JSL文字を数えるために、1 つの数式内でループを含む数式を使用します。 チャレンジ 2 3.JSL を試す数式ではなくリストを使用します。 また、任意の単語が項目 1、2、および 3 を満たすためには、7 つの文字セットのすべての文字が少なくとも 1 回含まれている必要があるという条件も利用しています。 実行時間は、それぞれ 15.50 秒と 10.40 秒でした。 この場合、評価する関数が少なかったため、ループが高速になった可能性があります。 どちらの改善も私の最初の試みよりもはるかに優れていますが、それでも最速ではありません. 改善は、関数の高速化、ループ/関数評価の削減、またはチャレンジの質問に回答するための別の方法からもたらされる必要があります。 最初の 2 つのアプローチは実りある可能性をもたらす可能性が低いと思われたため、別の方法が模索されました。
の課題 1 パターン マッチング.JSLスクリプトは@Craige_Hales . Craige は最近 JMP Development を退職しましたが、コミュニティでは今も活発に活動しています。 彼は、パターン マッチングと正規表現機能を担当していました。 JMP . Craige のソリューションでは、最初に辞書リストを長い文字列に変換して問題をベクトル化し、次にパターン マッチングを適用して単語を解析し、ソリューション バケットに入れます。 実行時間は 3.71 秒で、パターン マッチングの幅広さと柔軟性を示す好例です。 最速の解は 2.76 秒でした。 @ブレイディ_ブレイディ. 各文字セットを辞書の単語に適用するのではなく、各辞書の単語のすべてのアルファベット文字の出現回数を数えることから始めます。 これにより、最初は文字比較の数が 7 から 26 に増えますが、1 回だけ実行する必要があるため、新しい文字セットごとに再評価する必要がありません。 最初のアルファベット行列から適切な列を抽出することで、答えの単語が見つかり、はるかに高速なソリューションにつながります。 また、1146 文字で最も短いスクリプトです。
最初のチャレンジ後のリーダーボードは次のとおりです。
5 月 1 日にリリースされるチャレンジ 2 にご期待ください。
@MathStatChem文字数を数える前に、コメントと空白を削除します。 新しいスクリプトは、現在の状態で私のマシンで約 3.6 秒で実行されます。 Brady よりは遅いが、Craige よりは速い。 いくつかの小さな変更のためのかなり劇的な違い! ただし、一部の項目は正しく回答されていません。 以下は、回答とともに使用した文字セットです。
//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 でした。
だから私は基本的に同じロジックを使用しました@ブレイディ_ブレイディ、しかし、私の最初の文字カウントコードは、より多くのループとリストへの呼び出しを使用して、非常に非効率的でした.私は彼のアプローチを代用し、確かに私のスクリプトは約 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 );
