最後の投稿の直後から、準備を含めてたくさんのことが起こっていますJMP 16 、ほんの数日前に出てきたもので、読者が遭遇した列式の課題を尋ねる私の最後の投稿への返信がなかったので、読む価値のあるものを投稿する時間や資料がないと思いました。
私は最近もう少し時間がありました、そしてそれは新しい挑戦の時間です。 別の機会に列式の課題を表にして、新しい課題と新しいアプローチから始めます。 この投稿のために、そしておそらくその後数回、私はについて話しますコミュニティの投稿に対するCraigeHalesの回答に基づく一般的な質問。 クレイジ（ @Craige_Hales ）は、JMP開発を退職したにもかかわらず、コミュニティで非常に活発に活動し続け、ユーザーの質問に答え、彼の未知のブログ、そしてこのブログに貢献しています。 問題は、ループを使用せずに（多次元）リストを転置する効率についてでした。 私はよく疑問に思うより一般的な質問を提起したいと思います。「反復のより良い代替案はありますか？もしそうなら、それらは何ですか？」ほとんどの場合、より良いということはより速いことを意味しますが、速度をあまり妥協しないのであれば、コードのコンパクトさも考慮します。 また、反復へのさまざまなアプローチを見て、そこにも違いがあるかどうかを確認します。 テキストの検索から始めましょう。
文字列
バイオインフォマティクスの一般的なタスクは、特定の部分文字列パターンを見つけるために遺伝情報を含む文字列を検索することです。 DNAの場合、文字列文字はA、T、C、およびGの4文字のみで構成されます。 ファイルCovid19.TXT （この投稿に添付されている）には、約30,000文字の長さのCovid19ゲノムの遺伝子配列が含まれています（対照的に、最長のヒト1番染色体は約2億9千万文字の長さです）。 2〜10文字の長さの特定の部分文字列が出現するすべての場所を見つけるために、どれだけ迅速に検索できますか？
4つのアプローチを見てみましょう。そのうちの3つは反復的です。 手法に関係なく、部分文字列の一致は重複する可能性があることに注意してください。 例えば、 BABに2回含まれていますババブ、位置1から3まで、また3から5まで。 これらの両方の出来事を捉える何かが必要です。 から始めましょうSubstr以下のコードを使用します。 inString検索する文字列であり、 inSeq検索する部分文字列です。
findSequence = Function({inString,inSeq},{i,seqLen,checkTo,outVec},
seqLen = Length(inSeq);
checkTo = Length(covid19)-seqLen+1; //Only need to go until the substring includes the last character
outVec = J(checkTo,1,0);
For(i=1,i<=checkTo,i++,
outVec[i] = Substr(inString,i,seqLen) == inSeq;
);
Loc(outVec);
);
これは、サブストリングの長さに関係なく、平均1.2秒かかるアプローチの中で最も印象的ではありませんでした。 結果を以下に示します（マイクロ秒単位）。 テストでは、サブストリングの長さごとに10個のランダムなサブストリングが生成され、検索が20回繰り返されました。 値は、指定された長さのすべてのサブストリングにわたって要約されました。 個々の部分文字列の完全な詳細は次のとおりです。 Covid19結果Full.JMPこの投稿に添付されています。 テストの生成に使用されるコードは、TestCovid19Search.JSLにあります。
| サブストリングの長さ |
Substr |
索引 |
含まれています |
PatMatch |
| 2 |
1,227,342 |
60,312 |
79,640 |
4,046 |
| 3 |
1,245,909 |
62,650 |
22,143 |
3,103 |
| 4 |
1,215,641 |
66,045 |
4,938 |
2,881 |
| 5 |
1,218,983 |
72,337 |
1,293 |
2,880 |
| 6 |
1,220,846 |
76,705 |
357 |
2,956 |
| 7 |
1,249,843 |
77,127 |
234 |
3,010 |
| 8 |
1,212,982 |
84,413 |
132 |
3,078 |
| 9 |
1,227,892 |
87,479 |
113 |
3,331 |
| 10 |
1,208,948 |
89,732 |
106 |
3,742 |
以前の課題で、 Substr遅い。 文字列を「アトマイズ」し、個々の文字に分割して文字範囲を確認するとしたらどうでしょうか。 この動機は、Cのような言語でできるように、インデックスを介して文字列値に直接アクセスするという順序にあります。 文字列に直接インデックスを付けることはできないため、JSLではアトマイズ部分が必要です。 私が使用したコードはここにあります：
findSequence = Function({inString,inSeq},{i,seqLen,checkTo,outVec,inList,seqList},
seqLen = Length(inSeq);
checkTo = Length(inString)-Length(inSeq)+1; //Only need to go until the substring includes the last character
outVec = J(checkTo,1,0);
inList = Items(inString,"");
seqList = Items(inSeq,"");
For(i=1,i<=checkTo,i++,
outVec[i] = inList[i::(i+seqLen-1)] == seqList;
);
Loc(outVec);
);
このアプローチは、検索に加えて検索された文字列を分割する初期オーバーヘッドがあるため、より時間がかかるように聞こえますが、結果表に示されているように、約13〜19倍高速です。 ようではないSubstrただし、検索時間は部分文字列の長さの関数として増加します。
最後の反復アプローチでは、含まれています。 アイデアは、指定された部分文字列を見つけ、検索された文字列内のその場所をマークし、部分文字列が見つからなくなるまで、場所の1文字先から開始するプロセスを繰り返すことです。 この方法の魅力は、検索された文字列に部分文字列がほとんど出現しない場合に、検索が非常に高速になることです。 以下のコードはBradyBrady（ @brady_brady 
findSequence = Function({inString,inSeq},{pos=0,ans={}},
while(1,
pos = contains(inString, inSeq, pos);
if(pos, insertinto(ans, pos++), break())
);
ans;
);
ご覧のとおり、このアプローチは2文字の部分文字列のインデックス作成方法よりもわずかに遅くなりますが、部分文字列が長くなると、つまり検索する部分文字列が少なくなると、急速に速くなります。
最後のアプローチでは、私のお気に入りのJSLツールの1つであるパターンマッチングを使用します。 コードが速いだけでなく、短いです。
findSequence = Function({inString,inSeq},{i=1,locs={}},
Pat Match(inString,Pat Pos()>>r + inSeq + Pat Test(Insert Into(locs,r+1);0));
locs;
);
2文字の部分文字列の場合は少し遅くなりますが、3文字以上の場合は部分文字列の長さの影響を受けないようです。
明らかに、を使用した反復アプローチ含まれていますおよびパターンマッチングアプローチは、長い文字列を検索するための優れた方法です。 しかし、どの方法で、いつですか？ テストはさまざまなサブストリングを使用して行われたため、サブストリングの頻度（＃発生数* 1000 / 29,903）が検索時間にどのように影響するかを示しています。 以下のプロットは、1,000文字あたり2つのサブストリングの頻度のあたりのクロスオーバーポイントを示しています。 ただし、すべてのテストは同じcovid19ゲノム文字列で行われたため、検索された文字列の長さが検索時間にどのように影響するかは不明です。
これらの質問に対する答えを見つけ、要因間の可能な相互作用を調査するために、スペースを埋めるデザインを使用して実験を実行し、検索された文字列の長さ（10,000〜500,000文字）、部分文字列の長さ（2〜21文字）、および頻度（ 0.75 – 1,000文字あたり3つのサブストリング）。 125回の実行は、端数の文字列長の値が丸められたFastFlexible設計を使用して生成されました。 実行ごとに、アルファベット文字のランダムな文字列が生成されました。 その文字列内で、ランダムに生成された数字で構成されるサブ文字列がランダムな場所に挿入されました。 頻度の値は整数以外の挿入数につながる可能性があるため、挿入数は、頻度の上限に検索された文字列の長さを掛けて1,000で割ったものと見なされました。 検索された同じ文字列/サブ文字列の組み合わせで、各実行が10回繰り返されました。 実行の生成に使用されるコードは次のとおりです。 DesignScript.JSLを実行します結果はスペース充填結果1.JMPこの投稿に添付されています。
結果を簡単に調べると、13の観測値しか示されていません。含まれていますメソッドはパターンマッチングよりも優れています。 これらのうち、最大の違いは約4,000マイクロ秒高速です（パターンマッチングは0.72秒も高速でした）含まれています）。 ガウス過程モデルをデータに適合させることは、検索された文字列の長さが、検索された文字列の長さの相互作用によって強い頻度で最大の効果をもたらしたことを示唆しています。 サブストリングの長さはほとんど効果がありませんでした。 線形モデルは最初にデータに適合しましたが、残差分析は適合が疑わしい可能性があることを示唆しました。 投稿しましたこのモデルとフォローアップモデルのプロファイラーのインタラクティブバージョンJMPパブリックに。
2番目の空間充填設計は、次のような場合をより適切に表現するために作成されました。含まれていますパターンマッチングを上回りました。 この実験では、両方の弦の長さの範囲は以前と同じままで、周波数は0から1の間で変化しました。 結果はスペース充填結果2.JMP 。 結果の方向は以前と同様で、検索された文字列の長さが長く、頻度が高いため、パターンマッチングが優先されます。
両方の結果セットを組み合わせてガウス過程モデルをフィッティングすると、50,000文字の文字列に対して次のようになります。含まれています周波数が2未満の場合は優れています。 100,000文字の場合、頻度は1に低下し、200,000文字の場合は0.5未満になります。 これからの結論は、よりまばらな短い文字列には、含まれています文字列の長さと密度が高くなると、パターンマッチングが優れたものになります。
今月のチャレンジ
Covid19ゲノムを使用して、2回以上出現する最長の部分文字列を見つけます。
次の投稿までこれを未回答のままにするのではなく、話し合い、共有しましょう。 これは非常に難しい問題だと思います。私たちはオープンな議論から利益を得るでしょう。
状況によっては改善される場合と改善されない場合がある別のアプローチを見つけてください（確認する時間がありませんでした）。
NamesDefaultToHere(1);
str = LoadTextFile("$DOWNLOADS/covid-19.txt");
txt = "AACA";
bStr = CharToBlob(str);
bTxt = CharToBlob(txt);
pos = {};
for(i=1, i<=(Length(str) - Length(txt)), i++,
if(BlobPeek(bStr, i, Length(txt)) == bTxt, InsertInto(pos, i+1));
);
Print(NItems(pos));オーバーラップを含みますか？ それはそれを簡単にします。 オーバーラップを除いてどうやってやるのかわからないけど。 このソリューションは、提供されたデータに対する5〜10秒の回答です。 そして、はるかに長い部分文字列を持つはるかに長いデータでは苦痛になります。
アイデアは、テキストの長さ1 ...のすべての位置で、さまざまな部分文字列の長さに対して発生する各部分文字列の数を数えることです。 次に、「1を超えるカウントはありますか？」と尋ねます。 部分文字列の長さを二分探索して、重複を生成する最大の部分文字列の長さを見つけます。 同じ長さの別のより興味深い部分文字列があるかどうかを確認するために、最後にもう少し作業を行う必要があります。
txt = Load Text File( "z:/covid-19.txt" );
// finding the longest duplicated substring, including overlaps.
// if there is one, then there will be shorter ones of every possible
// shorter length. So, as the possible length of the substring grows,
// there is a boundary at some length where all shorter lengths have
// duplicates and no longer lengths have duplicates. find the boundary.
// do a binary search for the longest string that occurs 2 or more times
// testlength is the length during a pass
// see https://en.wikipedia.org/wiki/Binary_search_algorithm#Procedure
// for a *real* binary search. this code is potentially wrong and very
// poorly tested!
// Changing the maxlength guess below from 1...1000 will produce different times.
// 20 is a good starting point, bigger than 200 or so is very slow because
// length(txt) * maxlength strings are being manipulated, a lot.
start = Tick Seconds();
minlength = 1;
maxlength = 27; // initial guess, will (slowly) auto-adjust bigger as needed
firstpass = 1; // needed to detect guess too small
minkey = .;
minval = .;
while( 1,
testlength = if( firstpass == 1,
Min( Length( txt ), maxlength )// this binary search starts at the big end, then splits on subsequent passes. This lets code
, // else
Floor( (minlength + maxlength) / 2 )// below test that the big end is big enough on the first pass.
);
Write( "testing strings of length ", testlength, "\!n" );
Wait( 0 );
aa = [=> 0];
patmatch( txt,
Pat Len( testlength ) >> sequence + //
pattest( // build the associative array of key=sequence, val=count
aa[sequence]++;
// usually I use 1; on the next line. that always succeeds.
// here, I want pattest to make the matcher back up and retry...
0; // fail! try again at next position
),
NULL, // unused positional replacement
FULLSCAN // needed to bypass a heuristic and get the last little bit
);
keys = aa << getkeys;
vals = aa << getvalues;
idx = Loc Max( Matrix( vals ) );
bigN = vals[idx];
//
// the binary search is for the biggest testlength that has bigN > 1.
// bigN is the maximum repeats of a string of testlength characters.
//
if( bigN == 1,
maxlength = testlength;// maxlength promises to be 1-too-big at the end
, //else
minlength = testlength;
Write( " found some, minlength=", minlength, " maxlength=", maxlength, "\!n" );
minkey = keys[idx];
minval = vals[idx];
if( firstpass == 1, // looking for a big-enough high end, still
maxlength = Min( 2 * maxlength, Length( txt ) );
Write( "Increasing max, minlength=", minlength, " maxlength=", maxlength, "\!n" );
Continue();
);
);
firstpass = 0;
if( minlength >= maxlength - 1,
if( Is Missing( minkey ),
Continue();// needs one more pass
, // else
Break();// got it
)
);
);
Write( "\!n", minkey, " occurs ", minval, " times at " );
patmatch(
txt,
Pat Pos() >> location + //
minkey + //
pattest(
Write( location + 1, " " );
1;
) + //
Pat Fail() // this will also retry the match, 1 character further along
);
Write( "\!n" );
stop = Tick Seconds();
Show( stop - start );
含むアプローチは、以下のように簡潔に書くことができます。 比較が削除されると、これには少し速く実行されるという利点もあります。最も顕著なのは、サブストリングがメインストリング内に存在しない場合です。
findSequence = Function({txt, sub},{pos=0,ans={}},
while(pos = contains(txt, sub, pos), insertinto(ans, pos++));
ans;
);
