StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<blockquote> <p>Now, the problem that I have been observing is that this part of the code, is slowing down considerably as soon as the list has objects more than 10000.I understand arraylist is doing a o(N) search.</p> </blockquote> <p>The algorithm you posted is actually worse than O(N)</p> <ul> <li>Iterating through the input list <code>lstEntities</code> - O(N)</li> <li>within this loop, you are calling <code>ArrayList.indexOf(T)</code> which has to scan the list - O(N) again</li> </ul> <p>You algorithm is actually O(N^2) since you are potentially scanning the list twice within a loop.</p> <p>It sounds like you what you want to do is actually two operations:</p> <ol> <li>From the input <code>List</code>, remove any duplicates</li> <li>When you find duplicates, "merge" the entities.</li> </ol> <p>You can do this by scanning the list just once, rather than in nested loops. I would recommend breaking up your <code>Entity</code> to move the fields that "identify" an Entity into another type, such as <code>ID</code>, or at the very least add a <code>getID()</code> method which can return these fields grouped into a single type. This way you can easily build a Map between the two types to be able to merge entities with "duplicate" identities. This might look something like this:</p> <pre><code>Map<ID, Entity> map = new HashMap<ID, Entity>(inputList.size()); for (Entity e : inputList) { Entity existing = map.get(e.getID()); if (existing == null) { //not in map, add it map.put(e.getID(), e); } else { existing.merge(e); } } </code></pre> <p>Iterating through the list is O(n) while <code>HashMap.get(K)</code> is a constant-time operation.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload