Movatterモバイル変換


[0]ホーム

URL:


Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

Sign up
Appearance settings

gh-119105: Differ.compare is too slow [for degenerate cases]#119492

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to ourterms of service andprivacy statement. We’ll occasionally send you account related emails.

Already on GitHub?Sign in to your account

Merged
tim-one merged 13 commits intopython:mainfromtim-one:differ
May 25, 2024

Conversation

tim-one
Copy link
Member

@tim-onetim-one commentedMay 24, 2024
edited
Loading

Make it impossible forDiffer.compare() to degenerate to cubic-time. This may change results in some cases, but no natural ones come to mind, and I don't care about contrived cases.

…window of 10 lines, and picks "the first" pair within the current window with a ratio > cutoff to synch on. This should make cubic-time cases impossible. It may change results in some cases, but I don't think I care - difflib is fundamentally opposed to synching on lines "far apart", and using a window enforces a notion of locality.
@tim-onetim-one linked an issueMay 24, 2024 that may beclosed by this pull request
@tim-onetim-one merged commitde19694 intopython:mainMay 25, 2024
33 checks passed
@tim-onetim-one deleted the differ branchMay 25, 2024 03:08
estyxx pushed a commit to estyxx/cpython that referenced this pull requestJul 17, 2024
…ython#119492)``_fancy_replace()`` is no longer recursive. and a single call does a worst-case linear number of ratio() computations instead of quadratic. This renders toothless a universe of pathological cases. Some inputs may produce different output, but that's rare, and I didn't find a case where the final diff appeared to be of materially worse quality. To the contrary, by refusing to even consider synching on lines "far apart", there was more easy-to-digest locality in the output.
Sign up for freeto join this conversation on GitHub. Already have an account?Sign in to comment
Reviewers
No reviews
Assignees

@tim-onetim-one

Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.

difflib.py Differ.compare is too slow [for degenerate cases]
1 participant
@tim-one

[8]ページ先頭

©2009-2025 Movatter.jp