文字列を先頭から見て同じところまで除去をlinq.jsとC#で解いてみた
- 2011-08-19
JavaScript で「文字列を先頭から見て同じところまで除去」をやってみました。という記事を見て、「linq.js を使いたかったのですが使いどころがパッと思い浮かびませんでした」とのことなので、linq.js - LINQ for JavaScriptで答えてみます。お題の元はお題:文字列を先頭から見て同じところまで除去からです。解き方も色々あると思いますが、最長の一致する文字を見つけて、それを元に文字列を削除していく、という方法を取ることにしました。
function dropStartsSame(array)
{
var seq = Enumerable.From(array);
return Enumerable.From(seq.First())
.Scan("$+$$")
.TakeWhile(function (x) { return seq.All(function (y) { return y.indexOf(x) == 0 }) })
.Insert(0, [""]) // 一つもマッチしなかった場合のため
.TakeFromLast(1)
.SelectMany(function (x) { return seq.Select(function (y) { return y.substring(x.length) }) });
}
dropStartsSame(["abcdef", "abc123"]).WriteLine();
dropStartsSame(["あいうえお", "あいさんさん", "あいどる"]).WriteLine();
dropStartsSame(["12345", "67890", "12abc"]).WriteLine();
はい、ワンライナーで書けました、って何だか意味不明ですね!まず、例えば"abcdef"から["a","ab","abc","abcd","abcde","abcdef"]を作ります。これはものすごく簡単で、Scanを使うだけです。
// ["a","ab","abc","abcd","abcde","abcdef"]
Enumerable.From("abcdef").Scan("$+$$")
素晴らしい!そうして比較のタネができたら、あとは全てのindexOfが0(先頭に一致する)の間だけ取得(TakeWhile)します。["abcdef","abc123"]だとシーケンスは["a","ab","abc"]に絞られます。必要なのは最長のもの一つだけなのでTakeFromLast(1)で最後のものだけを取得。もし一つもマッチしなかった場合は代わりに""が通るようにInsertで事前に先頭にさしてやってます。あとは、その"abc"を元にして文字列を置換したシーケンスを返してやるようにすればいい、というわけです、はい。
少し修正
SelectManyで繋げるのは悪趣味なので、ちょっと変えましょう。
function dropStartsSame(array)
{
var seq = Enumerable.From(array);
var pre = Enumerable.From(seq.First())
.Scan("$+$$")
.TakeWhile(function (x) { return seq.All(function (y) { return y.indexOf(x) == 0 }) })
.LastOrDefault("");
return seq.Select(function (x) { return x.substring(pre.length) });
}
変数を一つ置いてやるだけで随分とすっきり。無理に全部繋げるのはよくないね、という当たり前の話でした。
C# + Ix
C#とIxで書くとこうなるかな?基本的には同じです。(Ixって何?という人はneue cc - LINQ to Objects & Interactive Extensions & linq.js 全メソッド概説を参照ください)
static IEnumerable<string> DropStartsSame(params string[] args)
{
var pre = args.First()
.Scan("", (x, y) => x + y)
.TakeWhile(x => args.All(y => y.StartsWith(x)))
.LastOrDefault() ?? "";
return args.Select(x => x.Substring(pre.Length));
}
static void Main()
{
var x = DropStartsSame("abcdef", "abc123").SequenceEqual(new[] { "def", "123" });
var y = DropStartsSame("あいうえお", "あいさんさん", "あいどる").SequenceEqual(new[] { "うえお", "さんさん", "どる" });
var z = DropStartsSame("12345", "67890", "12abc").SequenceEqual(new[] { "12345", "67890", "12abc" });
Console.WriteLine(x == y == z == true);
}
Ixで使ってるのはScanだけですけれど。
Deferの使い道
ところで、上のコードは遅延評価なのか遅延評価でないのか、微妙な感じです。preの計算までは即時で、その後は遅延されています。まるごと遅延したい場合はIxのDeferというメソッドが使えます。
// Deferで生成を遅延する
static IEnumerable<string> DropStartsSame2(params string[] args)
{
return EnumerableEx.Defer(() =>
{
var pre = args.First()
.Scan("", (x, y) => x + y)
.TakeWhile(x => args.All(y => y.StartsWith(x)))
.LastOrDefault() ?? "";
return args.Select(x => x.Substring(pre.Length));
});
}
// もしくはyield returnを使ってしまうという手も私はよく使っていました
static IEnumerable<string> DropStartsSame3(params string[] args)
{
var pre = args.First()
.Scan("", (x, y) => x + y)
.TakeWhile(x => args.All(y => y.StartsWith(x)))
.LastOrDefault() ?? "";
var query = args.Select(x => x.Substring(pre.Length));
foreach (var item in query) yield return item;
}
// 勿論、全部LINQで組んでしまってもOK
static IEnumerable<string> DropStartsSame4(params string[] args)
{
return args.First()
.Scan("", (x, y) => x + y)
.TakeWhile(x => args.All(y => y.StartsWith(x)))
.StartWith("") // linq.jsではInsert(0, [])でした
.TakeLast(1) // linq.jsではTakeFromLastでした
.SelectMany(x => args.Select(y => y.Substring(x.Length)));
}
私はIx以前はyield returnを結構よく使ってました。今は、Deferのほうが、例えば if(args == null) throw new ArgumentNullException(); とかがそのまま書けるのでDeferを選びたいかも。この辺の評価タイミングの話は前回、詳説Ix Share/Memoize/Publish編(もしくはyield returnの注意点)で書きました。
まとめ
というわけで、Scanの使い方でした。Scan可愛いよScan。ようするにAggregateの計算途中も列挙する版なわけなので、これ、標準クエリ演算子にも入って欲しかったなあ。結構使えるシーン多いです。
ああ、あとJavaScriptでもforなんて使いません(キリッ。linq.jsは真面目に普通に多機能なので遅い、じゃなくて、いや、それはまあ事実なんですが、便利には違いないです。他の普通のコレクションライブラリじゃ出来ないことも平然と出来ます。でもかわりに(ry