OSDN -- 오픈 소스 소프트웨어 개발 및 다운로드
Translation Status of 한국말 translation status for ko

Ticket #45129
Ticket List Submit New Ticket RSS

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

오픈 날짜: 2022-07-17 22:35 마지막 업데이트: 2022-07-20 01:16

Reporter:
stonee-k
소유자:
(None)
Type:
Patches
Status:
Open
Component:
(None)
MileStone:
(None)
Priority:
5 - Medium
Severity:
5 - Medium
Resolution:
None
File:
2

Details

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.  }

Ticket History (3/7 Histories)

2022-07-17 22:35 Updated by: stonee-k
  • New Ticket "文字単位で比較 (PR#1405 関連)" created
2022-07-18 21:39 Updated by: sdottaka
댓글 올리기

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

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

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

2022-07-18 21:53 Updated by: sdottaka
댓글 올리기

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

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

2022-07-19 21:49 Updated by: None
댓글 올리기

Reply To sdottaka

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

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

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

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

2022-07-20 01:16 Updated by: 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)が最適化されるともっと早くなるのではないかという気がしています

(Edited, 2022-07-20 01:17 Updated by: sdottaka)

Attachment File List

Edit

You are not logged in. I you are not logged in, your comment will be treated as an anonymous post. » Login