Title: difflib.GestaltSequenceMatcher implementation · Issue #144132 · python/cpython · GitHub
Open Graph Title: difflib.GestaltSequenceMatcher implementation · Issue #144132 · python/cpython
X Title: difflib.GestaltSequenceMatcher implementation · Issue #144132 · python/cpython
Description: Feature or enhancement Proposal: Increase quality of results by being able to run Longest Common Subsequence with autojunk=False with little to no degradation in performance. Implemented GestaltSequenceMatcher by default gives equivalent...
Open Graph Description: Feature or enhancement Proposal: Increase quality of results by being able to run Longest Common Subsequence with autojunk=False with little to no degradation in performance. Implemented GestaltSeq...
X Description: Feature or enhancement Proposal: Increase quality of results by being able to run Longest Common Subsequence with autojunk=False with little to no degradation in performance. Implemented GestaltSeq...
Opengraph URL: https://github.com/python/cpython/issues/144132
X: @github
Domain: github.com
{"@context":"https://schema.org","@type":"DiscussionForumPosting","headline":"difflib.GestaltSequenceMatcher implementation","articleBody":"# Feature or enhancement\n\n### Proposal:\n\nIncrease quality of results by being able to run Longest Common Subsequence with `autojunk=False` with little to no degradation in performance.\n\nImplemented `GestaltSequenceMatcher` by default gives equivalent results to `SequenceMatcher(autojunk=False)`.\n\n\n| case | Myers | difflib(aj=1) | difflib(aj=0) | New(aj=0) | New+balancing=2/3 |\n| -------------------------------- | -------: | -------------: | -------------: | -------------: | -------------: |\n| [L] diff_key ( 15, 15) | 8 | 5 -3 | 5 -3 | 5 -3 | 8 0 |\n| [L] diff_mid1 ( 28, 27) | 11 | 11 0 | 11 0 | 11 0 | 11 0 |\n| [L] diff_mid2 ( 128, 128) | 73 | 72 -1 | 72 -1 | 72 -1 | 72 -1 |\n| [L] diff_mid3 ( 131, 131) | 63 | 50 -13 | 50 -13 | 50 -13 | 57 -6 |\n| [L] difflib.py ( 2041, 2334) | 1883 | 1878 -5 | 1879 -4 | 1879 -4 | 1879 -4 |\n| [L] linux_sched.c (11373, 11832) | 10844 | 10793 -51 | 10837 -7 | 10837 -7 | 10844 0 |\n| [L] react.js ( 3555, 3337) | 2631 | 2568 -63 | 2581 -50 | 2581 -50 | 2581 -50 |\n| [L] three.js (36282, 36793) | 30688 | 25877 -4811 | 30588 -100 | 30588 -100 | 30656 -32 |\n| [L] webpack.js ( 2327, 3429) | 929 | 772 -157 | 899 -30 | 899 -30 | 916 -13 |\n| ----- | | | | | | |\n| Total: | 47130 | 42026 -5104 | 46922 -208 | 46922 -208 | 47024 -106 |\n| Avg % diff: | 0% | 10.58% | 7.25% | 7.25% | 1.61% |\n| Total % diff: | 0% | 10.83% | 0.44% | 0.44% | 0.22% |\n| Runtime (s): | 32.451 | 0.694 | 41.517 | 0.292 | 0.362 |\n\nTable above shows the number of individual match points.\nWhich is not a definitive metric.\nMore definitive metric could be a number of alignment points sacrificed for the sake of quality.\n\nHowever, it can be safely assumed that `autojunk=False` / new matcher produces higher quality diffs by not resorting to approximations. Luckily, it also increases number of match points.\n\nNew optional `balancing` argument can be turned on to reduce the chance of greedily committing to unbalanced matches. It produces more concise diffs with more lines matched, while retaining block-oriented nature.\n\nFor visual inspection, can see outputs of different algorithms for tailored case [HERE!]( https://htmlpreview.github.io/?https://gist.githubusercontent.com/dg-pb/89c2ed7cc3ebad06d9cd87fe91361292/raw/d6220ec7c71d40112a01b2257e3b2f0f28bbe354/diff_comparison.html)\n\n\u003cdetails>\u003csummary>Legacy\u003c/summary>\n\u003cp>\n\n\nO(n) solution is not that complex - 100 of Python lines.\n\nI hacked in initial implementation and ran `context_diff` on the `difflib.py` - the change itself.\n\n```python\nimport difflib, time\n\nwith open('/Users/Edu/lib/src/cx_amb/src/cx/cli/snd/diff/difflib.py') as f:\n s1 = f.read().splitlines(keepends=True)\n\nwith open('/Users/Edu/lib/src/cx_amb/src/cx/cli/snd/diff/difflib_new.py') as f:\n s2 = f.read().splitlines(keepends=True)\n\nlist(difflib.context_diff(s1, s2, fromfile='before.py', tofile='after.py'))\n# 2.4 ms (Current)\n# 2.9 ms (New)\n```\n\n~~So 30% faster.~~\nSo 20% slower.\nAlso, this is a fairly rough plug-in - there is a chance that the gap can be bridged.\n\n`O(n)` solution should avoid some of the user dissatisfaction:\n\u003c/p>\n\u003c/details> \n\n\n### Has this already been discussed elsewhere?\n\nNo response given\n\n### Links to previous discussion of this feature:\n\nMade a couple of posts in unrelated thread.\nPerformance tables are there showing that this is faster even for sizes of 10.\nhttps://discuss.python.org/t/include-time-and-space-complexity-in-documentation/105683/32\n\n\u003c!-- gh-linked-prs -->\n### Linked PRs\n* gh-144164\n\u003c!-- /gh-linked-prs -->\n","author":{"url":"https://github.com/dg-pb","@type":"Person","name":"dg-pb"},"datePublished":"2026-01-22T00:57:39Z","url":"https://github.com/python/cpython/issues/144132"}
| react-profiling | 0 |
| react-import-map | react,react-dom,react-dom/client,react-dom/profiling,react-is,react/compiler-runtime,react/jsx-dev-runtime,react/jsx-runtime,scheduler@b8488ee2c322 |
| route-pattern | /_view_fragments/issues/show/:user_id/:repository/:id/issue_layout(.:format) |
| route-controller | voltron_issues_fragments |
| route-action | issue_layout |
| fetch-nonce | v2:c68f410a-9054-9fa0-5b14-2e3cdc631a1c |
| current-catalog-service-hash | 81bb79d38c15960b92d99bca9288a9108c7a47b18f2423d0f6438c5b7bcd2114 |
| request-id | ED90:4BB79:4246CBB:547FFEA:6B023684 |
| html-safe-nonce | edec6b3ff1c23516e28fd11c19fef6e9b5a26935cb3bcb8ed046b904c969afe7 |
| visitor-payload | eyJyZWZlcnJlciI6IiIsInJlcXVlc3RfaWQiOiJFRDkwOjRCQjc5OjQyNDZDQkI6NTQ3RkZFQTo2QjAyMzY4NCIsInZpc2l0b3JfaWQiOiIxODk3MTk0OTMzMTMyMDgwNzcyIiwicmVnaW9uX2VkZ2UiOiJpYWQiLCJyZWdpb25fcmVuZGVyIjoiaWFkIn0= |
| visitor-hmac | e2e78c79e055a7fce015acd8bd4f9320bb0b5478e5706c3399c7dd433de41dbd |
| hovercard-subject-tag | issue:3840701656 |
| github-keyboard-shortcuts | repository,issues,copilot |
| google-site-verification | Apib7-x98H0j5cPqHWwSMm6dNU4GmODRoqxLiDzdx9I |
| octolytics-url | https://collector.github.com/github/collect |
| analytics-location | / |
| fb:app_id | 1401488693436528 |
| apple-itunes-app | app-id=1477376905, app-argument=https://github.com/_view_fragments/issues/show/python/cpython/144132/issue_layout |
| twitter:image | https://opengraph.githubassets.com/7a7578383b57d2a4662424a7767c47a2f8a18882884c009b08a87457c14d781d/python/cpython/issues/144132 |
| twitter:card | summary_large_image |
| og:image | https://opengraph.githubassets.com/7a7578383b57d2a4662424a7767c47a2f8a18882884c009b08a87457c14d781d/python/cpython/issues/144132 |
| og:image:alt | Feature or enhancement Proposal: Increase quality of results by being able to run Longest Common Subsequence with autojunk=False with little to no degradation in performance. Implemented GestaltSeq... |
| og:image:width | 1200 |
| og:image:height | 600 |
| og:site_name | GitHub |
| og:type | object |
| og:author:username | dg-pb |
| hostname | github.com |
| expected-hostname | github.com |
| None | 87e774ee7c6b3bee0490394e4d3e57ec9dbc956f74b87ea685dc8996c1676456 |
| turbo-cache-control | no-preview |
| go-import | github.com/python/cpython git https://github.com/python/cpython.git |
| octolytics-dimension-user_id | 1525981 |
| octolytics-dimension-user_login | python |
| octolytics-dimension-repository_id | 81598961 |
| octolytics-dimension-repository_nwo | python/cpython |
| octolytics-dimension-repository_public | true |
| octolytics-dimension-repository_is_fork | false |
| octolytics-dimension-repository_network_root_id | 81598961 |
| octolytics-dimension-repository_network_root_nwo | python/cpython |
| turbo-body-classes | logged-out env-production page-responsive |
| disable-turbo | false |
| browser-stats-url | https://api.github.com/_private/browser/stats |
| browser-errors-url | https://api.github.com/_private/browser/errors |
| release | 423dbb54c5e7bfecc838eb387c1435eb3d0e760d |
| ui-target | full |
| theme-color | #1e2327 |
| color-scheme | light dark |
| react-app-name | issues |
Links:
Viewport: width=device-width