StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>The best way is to switch to a different data structure. A <code>Map<Integer, User></code> will be best, because presumably users have uniquely identifying IDs. Your choice of <code>Map</code> implementation can be either a <code>HashMap</code> (expected <code>O(1)</code> for basic operations) or a <code>TreeMap</code> (<code>O(log N)</code>).</p> <p>IMPORTANT: You <code>@Override equals(Object)</code> without <code>@Override hashCode()</code>!!! This is <strong>dangerous</strong>! You should always get into the habit of overriding neither or both! (see: <a href="https://stackoverflow.com/questions/27581/overriding-equals-and-hashcode-in-java"> Overriding equals and hashCode in Java </a>)</p> <p>So, let's say you have <code>Map<Integer, User> remoteUsers</code> and <code>Map<Integer, User> localUsers</code>.</p> <blockquote> <p>1.) If a remote user already exists locally, update its fields.<br> <strike>4.) If a local user also appears in the remote list, update its fields.</strike> (same as 1)<br> 2.) If a remote user doesn't already exist locally, add the user. </p> </blockquote> <p>Finding if a <code>User</code> from <code>remoteUsers</code> is in <code>localUsers</code> can be answered in <code>O(1)</code> or <code>O(log N)</code> with a simple <code>containsKey</code> and <code>get</code>.</p> <pre><code>for (int id : remoteUsers.keys()) { User local; if (localUsers.containsKey(id)) { local = localUsers.get(id); else { localUsers.put(id, local = new User(id)); } local.updateFrom(remoteUsers.get(id)); } </code></pre> <blockquote> <p>3.) If a local user doesn't appear in the remote list, deactivate or delete.</p> </blockquote> <p>The following solution shows how powerful these more advanced data structures can be:</p> <pre><code>Set<Integer> toDeactivate = new TreeSet<Integer>(); toDeactivate.addAll(localUsers.keySet()); toDeactivate.removeAll(remoteUsers.keySet()); for (int id : toDeactivate) { User local = localUsers.get(id); local.deactivate(); localUsers.remove(id); } </code></pre> <hr> <p>Additionally, if you are stuck with <code>List<User></code>, you can still use <code>Map<Integer, User></code> as an intermediary data structure for this processing (basically transform <code>List<User></code> to <code>Map<Integer, User></code> and then back to <code>List<User></code>). It will still be faster, since it's <code>O(N log N)</code> or <code>O(N)</code>, compared to the <code>O(N^2)</code> that you have right now.</p> <p>If you insist on using only lists, then you might want to look at making it a <code>Collections.sort</code>-ed list, so you can do a <code>Collections.binarySearch</code> on it. You'd need to provide a <code>Comparator<User></code>, or make <code>User implements Comparable<User></code>, naturally ordering by <code>id</code>. This too will be <code>O(N log N)</code>.</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