重複行の削除マクロ（RemoveDuplicates.js）の処理速度

  1. Ver3.6.1に同梱されている重複行の削除マクロ（RemoveDuplicates.js）について、行数が多いと処理が終わらない問題が発生しました。
    1行の長さや重複具合にもよりますが、下記のような重複無しのデータだと30万行程度から怪しくなってきます。

    1
2
3
（中略）
300000

    こちらでしたら重複無し1000万行でも耐えれましたので、実装方法を変更したほうが良いかもしれません。
    https://www.haijin-boys.com/wiki/重複行を削除

     |  Noah  |  返信

  2. ご報告ありがとうございます。

    確かに…、サンプルの [重複行の削除] マクロは、データを総当たりで検索しているため、動作速度が非常に遅いですね。

    実は、ChatGPT に書いてもらったマクロなんです。

    Mery に同梱するサンプル マクロということでお願いしたので、プログラミング入門者にも分かりやすく、総当たり方式にしてくれたのだと思います。

    > こちらでしたら重複無し1000万行でも耐えれましたので、実装方法を変更したほうが良いかもしれません。
    > https://www.haijin-boys.com/wiki/重複行を削除

    おお、速っ！これは素晴らしいですね。

    差し支えなければ、そのハッシュマップ方式？を採用させていただけるとありがたいのですが、ライセンスや著作権の表示などが必要でしたら、ご返信いただけますでしょうか。

     |  Kuro  |  返信
  3. Kuro さんの投稿 (2023年10月21日) への返信

    > 実は、ChatGPT に書いてもらったマクロなんです。
    えっ、すごい。ChatGPTがそこまでできるとは…。
    もう人間がロジックを考えなくてもよい時代が来ているのかもしれませんね。

    > 差し支えなければ、そのハッシュマップ方式？を採用させていただけるとありがたいのですが、ライセンスや著作権の表示などが必要でしたら、ご返信いただけますでしょうか。
    NYSL 0.9981に従いますので、著作権表示などは不要です。
    ご自分の作ったものと同じように扱っていただいて大丈夫です。

     |  Noah  |  返信
  4. Noah さんの投稿 (2023年10月21日) への返信

    ご返信ありがとうございます。

    > もう人間がロジックを考えなくてもよい時代が来ているのかもしれませんね。

    それはありえますね。試しに、ChatGPT に重複行を削除するマクロの最適化をお願いしてみたら…

    #language = "V8"
if (document.selection.Text == "") {
	document.selection.SelectAll();
}
var lines = document.selection.Text.split("\n");
var uniqueLines = Array.from(new Set(lines));
document.selection.Text = uniqueLines.join("\n");

    …と、ロジックの部分、1 行でした。(Windows 10 未満だと使えないので没ですが)

    > NYSL 0.9981に従いますので、著作権表示などは不要です。
    > ご自分の作ったものと同じように扱っていただいて大丈夫です。

    ありがとうございます！早速、次のバージョンで採用させていただきたいと思います。

     |  Kuro  |  返信
  5. Kuro さんの投稿 (2023年10月21日) への返信

    > それはありえますね。試しに、ChatGPT に重複行を削除するマクロの最適化をお願いしてみたら…
    >
    > …と、ロジックの部分、1 行でした。(Windows 10 未満だと使えないので没ですが)
    あー、なるほど。Setを使うという手がありましたか。
    Setの方が速そうですし、バグも発生しにくいですし、もうChatGPTに聞いてプログラミングした方がよさそうですねぇ。

     |  Noah  |  返信
  6. Kuro さんの投稿 (2023年10月21日) への返信

    Version 3.6.3 に同梱されている重複行の削除マクロの in 演算子を使っているところは別の方法を使ったほうがいいかもしれません。

    in 演算子はプロトタイプチェーンをたどってチェックするので、例えば下記のようなテキストに対してマクロを実行すると全て消えてしまいます。

    hasOwnProperty
hasOwnProperty
isPrototypeOf
isPrototypeOf
propertyIsEnumerable
propertyIsEnumerable
toLocaleString
toLocaleString
toString
toString
valueOf
valueOf

    当該箇所を下記のように継承されたプロパティの値と被らないような文字列で比較する方法に変更すると回避できると思います。

    if (map[line] !== 'Mery重複行の削除') {
			result.push(line);
			map[line] = 'Mery重複行の削除';
		}

    in 演算子を使う方法と似たアプローチだと下記のように hasOwnProperty を使う方法でも回避できますが、これは少し遅くなるみたいです。

    if (!Object.prototype.hasOwnProperty.call(map, line)) {
			result.push(line);
			map[line] = true;
		}
     |  ucky  |  返信
  7. ucky さんの投稿 (2023年12月15日) への返信

    ご報告ありがとうございます。

    > in 演算子はプロトタイプチェーンをたどってチェックするので、例えば下記のようなテキストに対してマクロを実行すると全て消えてしまいます。

    はじめに教えていただいたマクロを、勝手に in を使った方法に変更してしまったのですが、そんな落とし穴があったとは…。

    余計なことをしてしまったかと思いまして、はじめに教えていただいたマクロのほうも確認してみましたが、こちらの場合も null かどうかのチェックだと、プロトタイプが含まれるので同様の問題が発生するようですね。

    if (lineMap[line] == null) {
		newLines.push(line);
		lineMap[line] = line;
	}

    プロトタイプを持たないオブジェクトを作る方法も考えてみましたが、たとえば、以下のようなコードは Windows XP あたりのスクリプトエンジンでは動作しそうにないですね。

    var map = Object.create(null);

    教えていただいたとおり、ユニークな文字列を入れておいてそれをチェックする方法がシンプルで良さそうです。

    勉強になりました。次のバージョンでは修正版を含めるようにいたします。

     |  Kuro  |  返信
  8. Kuro さんの投稿 (2023年12月15日) への返信

    > in 演算子はプロトタイプチェーンをたどってチェックするので、例えば下記のようなテキストに対してマクロを実行すると全て消えてしまいます。

    おお…これは思わず感嘆のため息が漏れました。私も勉強になりました。

    > 教えていただいたとおり、ユニークな文字列を入れておいてそれをチェックする方法がシンプルで良さそうです。

    普通のテキストと全く一致しなさそうな文字列を詰めるのもアリですが、オブジェクト参照の比較を用いれば絶対に被らない比較もできそうです。

    // ... 上部省略
var map = {};
var emptyObject = {};  // オブジェクト比較用に空オブジェクトを用意
doMultiEdit(function() {
	var lines = sel.Text.replace(/\n?$/, '').split('\n');
	var result	= [];
	for (var i = 0; i < lines.length; i++) {
		var line = lines[i];
		if (map[line] !== emptyObject) {  // オブジェクト比較
			result.push(line);
			map[line] = emptyObject;  // 空オブジェクトの参照を詰める
		}
	}
	sel.Text = result.join('\n') + RegExp.lastMatch;
}, !isEmpty);
     |  yuko  |  返信
  9. yuko さんの投稿 (2023年12月16日) への返信

    > おお…これは思わず感嘆のため息が漏れました。私も勉強になりました。

    普段、そこまで気にかけていなかったので、他のプロジェクトでも同じことをやってしまっている可能性がありそうで、ちょっとドキッとしています😱

    > 普通のテキストと全く一致しなさそうな文字列を詰めるのもアリですが、オブジェクト参照の比較を用いれば絶対に被らない比較もできそうです。

    プロパティの名前と一致しない文字列なので、適当に 'あ' でも十分かもしれませんが、なるほど、オブジェクト参照の比較なら文字列の比較よりも動作が速そうですね。

    あと、ユニークな文字列を考えるのって案外難しく、何にしようか迷っていたので、参考になります。

     |  Kuro  |  返信
  10. Kuro さんの投稿 (2023年12月16日) への返信

    > プロパティの名前と一致しない文字列なので、適当に 'あ' でも十分かもしれませんが、

    あ、そうか、対象行の文字列と被っちゃいけない…と勝手に思い込んでいましたが、 true の代わりに詰めるだけのものなのでなんでよかったわけですね😅

    勘違いから思いついたアイデアでしたが、何らかの参考になったのなら幸いです。

     |  yuko  |  返信
  11. yuko さんの投稿 (2023年12月16日) への返信

    yuko さんの案はユニークな文字列を考える必要がなくてスマートですね。

    yuko さんが投稿されたコードを見て気づいたのですが、「result」と「=」の間がスペースじゃなくてタブになってますね。（Filter.js、FilterOut.js、RemoveEmptyLines.js も同様）

    動作には全く影響しない些細なことですが意図してのことではないと思ったので一応報告します。

     |  ucky  |  返信
  12. ucky さんの投稿 (2023年12月16日) への返信

    ご報告ありがとうございます。

    > yuko さんの案はユニークな文字列を考える必要がなくてスマートですね。

    良いですよね。動作速度も実際に計測してみましたが、文字列比較よりもオブジェクト参照の比較のほうがちょっと速いようです。

    > yuko さんが投稿されたコードを見て気づいたのですが、「result」と「=」の間がスペースじゃなくてタブになってますね。（Filter.js、FilterOut.js、RemoveEmptyLines.js も同様）

    本当ですね、気づきませんでした。これは修正しておきますね。

     |  Kuro  |  返信
  13. Kuro さんの投稿 (2023年12月16日) への返信

    Version 3.6.4 のリリースお疲れ様です。

    同梱されているマクロの修正確認しました。

    ご対応ありがとうございました。

     |  ucky  |  返信
  14. ucky さんの投稿 (2023年12月25日) への返信

    ご確認いただき、ありがとうございます。

    おかげさまで、Ver 3.6.4 をなんとか年内にリリースすることができました。

    本件では、みなさんのおかげで大変助かりました。ご協力いただき、ありがとうございました。

    どうぞ素敵なお年をお迎えくださいね！

     |  Kuro  |  返信
スポンサーリンク