Transform ArrayList to LinkedList for Performance Improvement
Nobody has claimed this yet.
Assessment
- Difficulty
- 3/5
- Estimated time
- 1-2 days
- Newbie friendliness
- 25/100
- Issue type
- Refactor
- Clarity
- Mostly clear
- Activity status
- Stale
- Tech stack
- java
- Domain
- performance
Research direction
Start by reviewing the patch referenced as #1444 and the affected ArrayList usages. Confirm that each is used only for traversal or first/last-element retrieval and that the proposed LinkedList conversion preserves behavior; completion is acceptance of that patch.
Written by the indexing model from the issue text.
Description
Hi,
We find that there are several ArrayList objects which are not manipulated by random access. Due to the memory reallocation triggered in the successive insertions, the time complexity of add method of ArrayList is amortized O(1). We notice that these objects are only used for traversal and the retrieval for the first or the last element.
This functionality can be implemented by LinkedList. Moreover, the insertion of LinkedList is strictly O(1) time complexity because no memory reallocation occurs.
We discovered this inefficient usage of containers by our tool Ditto. The patch is submitted in #1444. Could you please check and accept it? We have tested the patch on our PC. The patched program works well.
Bests
Ditto
- Dominant language
- Java
- Stars
- 1.4k
- Forks
- 476
- Avg merge
- 10h 47m
- Merged PRs (30d)
- 3
Getting set up
- No Dockerfile or Docker Compose file
- Has a pull request template
- Read the contributing guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
More from googleapis/google-http-java-client
-
Core: Validate header names and values to prevent CRLF injectionPossibly taken @insaf021 claimed this 106 days ago. Openpriority: p3
Difficulty 2/5 1-3 hours Newbie friendliness 78/100
-
Core: XmlPullParser processes external DTD entities (XXE) — disable FEATURE_PROCESS_DOCDECL in Xml#createParser()Possibly taken @insaf021 claimed this 106 days ago. Openpriority: p3
Difficulty 2/5 1-3 hours Newbie friendliness 84/100
-
Core: LowLevelHttpResponse not disconnected when HttpResponse construction throws RuntimeExceptionPossibly taken @insaf021 claimed this 106 days ago. Openpriority: p3
Difficulty 2/5 1-3 hours Newbie friendliness 84/100
-
type: cleanup
Difficulty 2/5 1-3 hours Newbie friendliness 68/100
-
org.apache.http.conn.ssl.SSLSocketFactory is deprecatedMay be free again A pull request for this issue was closed without being merged. Openpriority: p2 type: cleanup
Difficulty 2/5 1-3 hours Newbie friendliness 65/100
All issues in googleapis/google-http-java-client
Similar issues
-
Difficulty 1/5 Under an hour Newbie friendliness 88/100
-
Difficulty 2/5 Under an hour Newbie friendliness 84/100
cpp-best-practices/project_validator#251 ·
Maintainers usually reply within 1 day
-
backend enhancement
Difficulty 2/5 Half a day Newbie friendliness 70/100
damodharg6/payledger#16 ·
-
[Bug]: An initiative list with no current entry logs an error on every changePossibly taken @dwizard0 claimed this today. Open
Difficulty 2/5 1-3 hours Newbie friendliness 75/100
Maintainers usually reply within 1 day
-
Difficulty 1/5 Under an hour Newbie friendliness 85/100
Maintainers usually reply within 1 day