Databases
StackOverflow2013
Postsdbo
POWhat is the Time Complexity of size() for Sets in Java?
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POWhat is the Time Complexity of size() for Sets in Java?
    primarykey
    data
    text
    <p>I know, it seems like a stupid question, you would expect that the time complexity of size() on any collection would be O(1) - but I'm finding that an "optimization" in my code which requires a call to size() is actually slowing things down.</p> <p>So, what is the time complexity of size() for Sets in Java?</p> <p>My code is an implementation of a recursive algorithm to find the maximal cliques in a graph (not important). Basically, the optimization just checks whether two Sets have equal size (these Sets are being constructed either way), and allows for only one more recursive call (stopping the recursion after that) if they are equal in size.</p> <p>Here is a (simplified) version of my code:</p> <pre><code> private static void recursivelyFindMaximalCliques(Set&lt;Integer&gt; subGraph, Set&lt;Integer&gt; candidates, Set&lt;Integer&gt; notCandidates) { boolean noFurtherCliques = false; Iterator&lt;Integer&gt; candidateIterator = candidates.iterator(); while (candidateIterator.hasNext()) { int nextCandidate = candidateIterator.next(); candidateIterator.remove(); subGraph.add(nextCandidate); Set&lt;Integer&gt; neighbors = getNeighbors(nextCandidate); Set&lt;Integer&gt; newCandidates = calculateIntersection(candidates, neighbors); Set&lt;Integer&gt; newNotCandidates = calculateIntersection(notCandidates, neighbors); //if (newCandidates.size() == candidates.size()) // noFurtherCliques = true; recursivelyFindMaximalCliques(subGraph, newCandidates, newNotCandidates); //if (noFurtherCliques) // return; subGraph.set.remove(nextCandidate); notCandidates.set.add(nextCandidate); } } </code></pre> <p>The lines I have commented out are the ones in question - you can see that they check if the sets newCandidates and candidates are the same size, and if they are, the recursion is only allowed to go one level deeper.</p> <p>When the lines are uncommented, the code runs about 10% slower - this is true whether the sets used are HashSets, TreeSets, or LinkedHashSets. This makes no sense, since those lines ensure that there will be FEWER recursive calls.</p> <p>The only thing I can assume is that the call to size() on the sets is taking a long time. Does calling size() on Sets in Java take longer than O(1)?</p> <p><strong>EDIT</strong></p> <p>Since some people have asked, here is calculateIntersection():</p> <pre><code>private static IntegerSet calculateIntersection(Set&lt;Integer&gt; setA, Set&lt;Integer&gt; setB) { if (setA.size() == 0 || setB.size() == 0) return new Set&lt;Integer&gt;(); Set&lt;Integer&gt; intersection = new Set&lt;Integer&gt;(); //Replace this with TreeSet, HashSet, or LinkedHashSet, whichever is being used intersection.addAll(setA); intersection.retainAll(setB); return intersection; } </code></pre> <p><strong>SECOND EDIT</strong> Here is the full code, if you like. I hesitated to post it, since it's long and nasty, but people asked, so here it is:</p> <pre><code>public class CliqueFindingAlgorithm { private static class IntegerSet { public Set&lt;Integer&gt; set = new TreeSet&lt;Integer&gt;(); //Or whatever Set is being used } private static ArrayList&lt;IntegerSet&gt; findMaximalCliques(UndirectedGraph graph) { ArrayList&lt;IntegerSet&gt; cliques = new ArrayList&lt;IntegerSet&gt;(); IntegerSet subGraph = new IntegerSet(); IntegerSet candidates = new IntegerSet(); IntegerSet notCandidates = new IntegerSet(); for (int vertex = 0; vertex &lt; graph.getNumVertices(); vertex++) { candidates.set.add(vertex); } recursivelyFindMaximalCliques(cliques, graph, subGraph, candidates, notCandidates); return cliques; } private static void recursivelyFindMaximalCliques(ArrayList&lt;IntegerSet&gt; cliques, UndirectedGraph graph, IntegerSet subGraph, IntegerSet candidates, IntegerSet notCandidates) { boolean noFurtherCliques = false; Iterator&lt;Integer&gt; candidateIterator = candidates.set.iterator(); while (candidateIterator.hasNext()) { int nextCandidate = candidateIterator.next(); candidateIterator.remove(); subGraph.set.add(nextCandidate); IntegerSet neighbors = new IntegerSet(); neighbors.set = graph.getNeighbors(nextCandidate); IntegerSet newCandidates = calculateIntersection(candidates, neighbors); IntegerSet newNotCandidates = calculateIntersection(notCandidates, neighbors); if (newCandidates.set.size() == candidates.set.size()) noFurtherCliques = true; recursivelyFindMaximalCliques(cliques, graph, subGraph, newCandidates, newNotCandidates); if (noFurtherCliques) return; subGraph.set.remove(nextCandidate); notCandidates.set.add(nextCandidate); } if (notCandidates.set.isEmpty()) { IntegerSet clique = new IntegerSet(); clique.set.addAll(subGraph.set); cliques.add(clique); } } private static IntegerSet calculateIntersection(IntegerSet setA, IntegerSet setB) { if (setA.set.size() == 0 || setB.set.size() == 0) return new IntegerSet(); IntegerSet intersection = new IntegerSet(); intersection.set.addAll(setA.set); intersection.set.retainAll(setB.set); return intersection; } </code></pre> <p>}</p> <pre><code>public class UndirectedGraph { // ------------------------------ PRIVATE VARIABLES ------------------------------ private ArrayList&lt;TreeMap&lt;Integer, Double&gt;&gt; neighborLists; private int numEdges; // ------------------------------ CONSTANTS ------------------------------ // ------------------------------ CONSTRUCTORS ------------------------------ public UndirectedGraph(int numVertices) { this.neighborLists = new ArrayList&lt;TreeMap&lt;Integer, Double&gt;&gt;(numVertices); this.numEdges = 0; for (int i = 0; i &lt; numVertices; i++) { this.neighborLists.add(new TreeMap&lt;Integer, Double&gt;()); } } // ------------------------------ PUBLIC METHODS ------------------------------ public void addEdge(int vertexA, int vertexB, double edgeWeight) { TreeMap&lt;Integer, Double&gt; vertexANeighbors = this.neighborLists.get(vertexA); TreeMap&lt;Integer, Double&gt; vertexBNeighbors = this.neighborLists.get(vertexB); vertexANeighbors.put(vertexB, edgeWeight); vertexBNeighbors.put(vertexA, edgeWeight); this.numEdges++; } public List&lt;Integer&gt; computeCommonNeighbors(int vertexA, int vertexB) { List&lt;Integer&gt; commonNeighbors = new ArrayList&lt;Integer&gt;(); Iterator&lt;Integer&gt; iteratorA = this.getNeighbors(vertexA).iterator(); Iterator&lt;Integer&gt; iteratorB = this.getNeighbors(vertexB).iterator(); if (iteratorA.hasNext() &amp;&amp; iteratorB.hasNext()) { int nextNeighborA = iteratorA.next(); int nextNeighborB = iteratorB.next(); while(true) { if (nextNeighborA == nextNeighborB) { commonNeighbors.add(nextNeighborA); if (iteratorA.hasNext() &amp;&amp; iteratorB.hasNext()) { nextNeighborA = iteratorA.next(); nextNeighborB = iteratorB.next(); } else break; } else if (nextNeighborA &lt; nextNeighborB) { if (iteratorA.hasNext()) nextNeighborA = iteratorA.next(); else break; } else if (nextNeighborB &lt; nextNeighborA) { if (iteratorB.hasNext()) nextNeighborB = iteratorB.next(); else break; } } } return commonNeighbors; } // ------------------------------ PRIVATE METHODS ------------------------------ private class EdgeIterator implements Iterator&lt;int[]&gt; { private int vertex; private int[] nextPair; private Iterator&lt;Integer&gt; neighborIterator; public EdgeIterator() { this.vertex = 0; this.neighborIterator = neighborLists.get(0).keySet().iterator(); this.getNextPair(); } public boolean hasNext() { return this.nextPair != null; } public int[] next() { if (this.nextPair == null) throw new NoSuchElementException(); int[] temp = this.nextPair; this.getNextPair(); return temp; } public void remove() { throw new UnsupportedOperationException(); } private void getNextPair() { this.nextPair = null; while (this.nextPair == null &amp;&amp; this.neighborIterator != null) { while (this.neighborIterator.hasNext()) { int neighbor = this.neighborIterator.next(); if (this.vertex &lt;= neighbor) { this.nextPair = new int[] {vertex, neighbor}; return; } } this.vertex++; if (this.vertex &lt; getNumVertices()) this.neighborIterator = neighborLists.get(this.vertex).keySet().iterator(); else this.neighborIterator = null; } } } // ------------------------------ GETTERS &amp; SETTERS ------------------------------ public int getNumEdges() { return this.numEdges; } public int getNumVertices() { return this.neighborLists.size(); } public Double getEdgeWeight(int vertexA, int vertexB) { return this.neighborLists.get(vertexA).get(vertexB); } public Set&lt;Integer&gt; getNeighbors(int vertex) { return Collections.unmodifiableSet(this.neighborLists.get(vertex).keySet()); } public Iterator&lt;int[]&gt; getEdgeIterator() { return new EdgeIterator(); } </code></pre> <p>}</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USZarjio
    1. USZarjio
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POWhat is the Time Complexity of size() for Sets in Java?
      1. This table or related slice is empty.
      1. VTUpMod
    1. COHashSets just return a variable. so its O(1)
      singulars
      1. POWhat is the Time Complexity of size() for Sets in Java?
      1. USFDinoff
    2. COSomething is fishy. The code above, as is, will not run 10% slower with 2 size() calls regardless of the Set implementation you use in `calculateIntersection()`. There must be something else you aren't showing.
      singulars
      1. POWhat is the Time Complexity of size() for Sets in Java?
      1. USSotirios Delimanolis
    3. COI've posted all the (relevant) code. It's long and nasty, and I don't think it will clarify anything.
      singulars
      1. POWhat is the Time Complexity of size() for Sets in Java?
      1. USZarjio
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

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