lambdaclass / lambdaclass/lambda_compiler_kit
perf: refactor rejectDuplicates in Parser.lean to avoid redundant sort and O(n²) insertion
Dieses Issue hat noch niemand übernommen.
- Vorherrschende Sprache
- Lean
- Sterne
- 2
- Forks
- 1
- PR-Merge-Kennzahlen
- Keine gemergten PRs in 30 T.
Beschreibung
Problem
SortedKVs.ofListWithPolicy .rejectDuplicates in Lck/Json/Parser.lean does two passes:
hasDuplicateKeysList: sorts the list (mergeSort, O(n log n)) then scans adjacent pairsSortedKVs.ofList: builds the sorted structure via repeatedinsert(O(n) each → O(n²) total)
Total cost is O(n log n) + O(n²) = O(n²) with a hidden constant from sorting twice.
Suggested Fix
Add a SortedKVs.fromSortedList helper that builds the sorted structure from a pre-sorted list in O(n), then combine the duplicate check and structure construction into a single pass over the mergeSort output. This would bring the rejectDuplicates path to O(n log n) overall.
The same refactor would help firstWins and lastWins paths in ofList/ofListLastWins.
Complexity
Moderate: requires a new Syntax.lean helper and corresponding proof in Proofs.lean.
Beitragsleitfaden
Für dieses Repository ist kein Beitragsleitfaden indexiert
Erste Schritte
- Lies das ganze Issue und danach den Beitragsleitfaden des Projekts.
- Schreib ins Issue, dass du es übernimmst — das erspart doppelte Arbeit.
- Forke das Repository und arbeite in einem Branch.
- Öffne einen Pull Request, der die Issue-Nummer nennt.
Rechercherichtung
Beginne in Lck/Json/Parser.lean, indem du SortedKVs.ofListWithPolicy, hasDuplicateKeysList, ofList und ofListLastWins liest. Untersuche anschließend die bestehende Struktur in Syntax.lean und die zugehörigen Beweise in Proofs.lean. Die Aufgabe ist abgeschlossen, wenn ein fromSortedList-Helfer einen einzigen mergeSort-Durchlauf für rejectDuplicates, firstWins und lastWins ermöglicht und dabei die entsprechenden Beweise sowie das O(n log n)-Verhalten erhalten bleiben.
Vom Indexierungsmodell aus dem Issue-Text verfasst.
Bewertung
- Bereich
- compilers, performance
- Issue-Typ
- Refactoring
- Schwierigkeit
- 4/5
- Geschätzter Aufwand
- 3-5 Tage
- Aktivitätsstatus
- Veraltet
- Klarheit
- Größtenteils klar
- Anfängerfreundlichkeit
- 45/100