OSDN -- オープンソース・ソフトウェアの開発とダウンロード
日本語の翻訳状況 translation status for ja

チケット #45129
チケット一覧/検索 新規チケット登録 RSS

文字単位で比較 (PR#1405 関連)

登録: 2022-07-17 22:35 最終更新: 2022-07-20 01:16

報告者:
stonee-k
担当者:
(未割り当て)
チケットの種類:
パッチ
状況:
オープン
コンポーネント:
(未割り当て)
マイルストーン:
(未割り当て)
優先度:
5 - 中
重要度:
5 - 中
解決法:
なし
ファイル:
2

詳細

This PR also causes UnitTests to fail.

デバッグします.......orz

今回の修正は一旦却下して下さいませ。

However, the reason for the current implementation (word-by-word comparison followed by character-by-character range adjustment) is performance. (It may not be a problem in CPU speed today.)

パフォーマンスについては、ループの最内にあたる snake() 関数で M, N をいちいち計算しているのが気になるので、 呼び出し元で計算済みの値をそのまま引数で渡せばよいと思うのですが、PRを分けようと思って今回のPR#1405に含めていませんでした。

▼修正前 

  1.  // /Src/stringdiffs.cpp
  2.  
  3.  int
  4.  stringdiffs::snake(int k, int y, bool exchanged)
  5.  {
  6.          int M = static_cast<int>(exchanged ? m_words2.size() - 1 : m_words1.size() - 1);
  7.          int N = static_cast<int>(exchanged ? m_words1.size() - 1 : m_words2.size() - 1);
  8.          int x = y - k;
  9.          while (x < M && y < N && (exchanged ? AreWordsSame(m_words1[y + 1], m_words2[x + 1]) : AreWordsSame(m_words1[x + 1], m_words2[y + 1]))) {
  10.                  x = x + 1; y = y + 1;
  11.          }
  12.          return y;
  13.  }

▼修正案 

  1.  int
  2.  stringdiffs::snake(int k, int y, int M, int N, bool exchanged)
  3.  {
  4.          int x = y - k;
  5.  
  6.          if (exchanged)
  7.          {
  8.                  for (; x < M && y < N; x++, y++)
  9.                  {
  10.                          if (!AreWordsSame(m_words1[y + 1], m_words2[x + 1])) break;
  11.                  }
  12.          }
  13.          else
  14.          {
  15.                  for (; x < M && y < N; x++, y++)
  16.                  {
  17.                          if (!AreWordsSame(m_words1[x + 1], m_words2[y + 1])) break;
  18.                  }
  19.          }
  20.  
  21.          return y;
  22.  }

チケットの履歴 (7 件中 3 件表示)

2022-07-17 22:35 更新者: stonee-k
  • 新しいチケット "文字単位で比較 (PR#1405 関連)" が作成されました
2022-07-18 21:39 更新者: sdottaka
コメント

PRありがとうございます。

パフォーマンスの問題というのは、例えば１行あたり５０００文字の数百行の英文テキストファイルがある場合、 1文字単位で区切って比較するのと今の疑似一文字単位比較(まず単語単位で比較して、差異のある単語の範囲を文字単位で調整)で比較するのでは、おそらく4,5倍は比較速度が変わると思っています。 (1単語あたり平均文字数4,5文字と仮定した場合)

速いマシンだとあまり気にならないかもしれませんが、遅いマシンだと気になるかもしれないので できれば、デフォルトを真の1文字単位比較ではなく、今の疑似一文字単位比較にしたいと思っています。

2022-07-18 21:53 更新者: sdottaka
コメント

パフォーマンスの問題というのは、例えば１行あたり５０００文字の数百行の英文テキストファイルがある場合、 1文字単位で区切って比較するのと今の疑似一文字単位比較(まず単語単位で比較して、差異のある単語の範囲を文字単位で調整)で比較するのでは、おそらく4,5倍は比較速度が変わると思っています。

すみません。O(NP) のアルゴリズムを使用しているので 4,5倍ではなく最悪のケースだともっと遅くなる可能性があります。

2022-07-19 21:49 更新者: None
コメント

Reply To sdottaka

パフォーマンスの問題というのは、例えば１行あたり５０００文字の数百行の英文テキストファイルがある場合、 1文字単位で区切って比較するのと今の疑似一文字単位比較(まず単語単位で比較して、差異のある単語の範囲を文字単位で調整)で比較するのでは、おそらく4,5倍は比較速度が変わると思っています。

すみません。O(NP) のアルゴリズムを使用しているので 4,5倍ではなく最悪のケースだともっと遅くなる可能性があります。

ひとまず、書き直したPRでは現行の挙動のまま、snake関数の最適化だけにしました。

「一文字単位でごりごり比較」vs「現行の挙動」を切り替えるのは、仕様を練った方がよさそうなので、考慮後にします。

2022-07-20 01:16 更新者: sdottaka
コメント

ひとまず、snake関数の最適化までとしたいということでよろしいでしょうか? そうであれば、現状のPRのタイトルが実態と異なっていますので、タイトルを変えていただくか、別PRでお願いできますでしょうか? また、snake関数以外の変更も入っているように見えますので最適化に限定していただけると助かります。 また、https://github.com/WinMerge/winmerge/pull/1405/files 見ていただくと気づくかと思いますが、 以下のコードのコメントアウトは 

	//int M = static_cast<int>(exchanged ? m_words2.size() - 1 : m_words1.size() - 1);
	//int N = static_cast<int>(exchanged ? m_words1.size() - 1 : m_words2.size() - 1);
CodeQLで以下のようなアラートが発生してしまうので思い切って削除していただいた方がよいと思います。

Check notice on line 759

Code scanning / CodeQL

Commented-out code Note

This comment appears to contain commented-out code

なお、ご参考までに現状の行内差異の比較処理があまり最適化されていないせいで、 かなり表示速度が遅くなっていることがわかる例を以下のURLに置いています。 https://github.com/WinMerge/winmerge-testdata/tree/master/%231405%20Fix%20Character%20level%20option%20is%20always%20ignored

file1l.txt と file2l.txt を比較すると私の環境では表示完了まで10秒ほど時間がかかります。

VisualStudioのパフォーマンスプロファイラで計測してみると、snake関数の最適化により、おそらく200ミリ秒ほど早くなっています。 (snake関数最適化前.png, snake関数最適化後.png を添付しています。)

添付画像の lambda～(実際はaddEditScriptElem)が最適化されるともっと早くなるのではないかという気がしています

(編集済, 2022-07-20 01:17 更新者: sdottaka)

添付ファイルリスト

編集

ログインしていません。ログインしていない状態では、コメントに記載者の記録が残りません。 » ログインする