Comparison of a Weighted Quick Find with Path Compression Union Find algorithm in Java and Swift

README.md

Intro

All the Java code here comes from Algorithms, 4th Edition, by Robert Sedgewick and Kevin Wayne.

The Swift code was written by myself. Although it is mainly a direct port of the Java code :)

The goal was to see how fast Swift would compare to a language such as Java in a somewhat non-trivial case.

The input used was largeUF.txt, also provided by the Algorithms book. It is about 27mb, so I left it out of the gist :)

Results

Java

○ javac -version                                                                                                                                                                                     
javac 1.8.0_11

○ java -version                                                                                                                                                                                      
java version "1.8.0_11"
Java(TM) SE Runtime Environment (build 1.8.0_11-b12)
Java HotSpot(TM) 64-Bit Server VM (build 25.11-b03, mixed mode)

○ javac *.java
○ time java WeightedQuickUnionPathCompressionUF < largeUF.txt
... output omitted ...
java WeightedQuickUnionPathCompressionUF < largeUF.txt  6.71s user 1.43s system 90% cpu 8.946 total

Swift

○ xcrun swiftc --version
Swift version 1.1 (swift-600.0.54.20)
Target: x86_64-apple-darwin13.4.0

○ xcrun -sdk macosx swiftc -O *.swift
○ time ./WeightedQuickUnionPathCompressionUF < largeUTF.txt
Time taken: 42.8143479824066
./WeightedQuickUnionPathCompressionUF < largeUF.txt  36.84s user 2.79s system 90% cpu 43.889 total

Notes

In Swift, running the tests with a class as opposed to a struct took 7 minutes 21 seconds beore I decided to scrap it. Turning into a struct brought it all the way down to less than 45 seconds!

StdIn.java

// This code is originally from Algorithms, 4th Edition: http://algs4.cs.princeton.edu/home/
// Source: http://introcs.cs.princeton.edu/java/stdlib/StdIn.java.html

/*************************************************************************
 *  Compilation:  javac StdIn.java
 *  Execution:    java StdIn   (interactive test of basic functionality)
 *
 *  Reads in data of various types from standard input.
 *
 *************************************************************************/

import java.util.ArrayList;
import java.util.InputMismatchException;
import java.util.Locale;
import java.util.Scanner;
import java.util.regex.Pattern;

/**
 *  The <tt>StdIn</tt> class provides static methods for reading strings
 *  and numbers from standard input. See 
 *  <a href="http://introcs.cs.princeton.edu/15inout">Section 1.5</a> of
 *  <i>Introduction to Programming in Java: An Interdisciplinary Approach</i>
 *  by Robert Sedgewick and Kevin Wayne.
 *  <p>
 *  For uniformity across platforms, this class uses <tt>Locale.US</tt>
 *  for the locale and <tt>"UTF-8"</tt> for the character-set encoding.
 *  The English language locale is consistent with the formatting conventions
 *  for Java floating-point literals, command-line arguments
 *  (via {@link Double#parseDouble(String)}) and standard output.
 *  <p>
 *  Like {@link Scanner}, reading a <em>token</em> also consumes preceding Java
 *  whitespace; reading a line consumes the following end-of-line
 *  delimeter; reading a character consumes nothing extra. 
 *  <p>
 *  Whitespace is defined in {@link Character#isWhitespace(char)}. Newlines
 *  consist of \n, \r, \r\n, and Unicode hex code points 0x2028, 0x2029, 0x0085;
 *  see <tt><a href="http://www.docjar.com/html/api/java/util/Scanner.java.html">
 *  Scanner.java</a></tt> (NB: Java 6u23 and earlier uses only \r, \r, \r\n).
 *  <p>
 *  See {@link In} for a version that handles input from files, URLs,
 *  and sockets.
 *  <p>
 *  Note that Java's UTF-8 encoding does not recognize the optional byte-order
 *  mask. If the input begins with the optional byte-order mask, <tt>StdIn</tt>
 *  will have an extra character <tt>uFEFF</tt> at the beginning.
 *  For details, see http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4508058.
 *
 *  @author David Pritchard
 *  @author Robert Sedgewick
 *  @author Kevin Wayne
 */
public final class StdIn {

    // it doesn't make sense to instantiate this class
    private StdIn() { }

    private static Scanner scanner;
 
    /*** begin: section (1 of 2) of code duplicated from In to StdIn */
    
    // assume Unicode UTF-8 encoding
    private static final String CHARSET_NAME = "UTF-8";

    // assume language = English, country = US for consistency with System.out.
    private static final Locale LOCALE = Locale.US;

    // the default token separator; we maintain the invariant that this value
    // is held by the scanner's delimiter between calls
    private static final Pattern WHITESPACE_PATTERN = Pattern.compile("\\p{javaWhitespace}+");

    // makes whitespace characters significant
    private static final Pattern EMPTY_PATTERN = Pattern.compile("");

    // used to read the entire input
    private static final Pattern EVERYTHING_PATTERN = Pattern.compile("\\A");

    /*** end: section (1 of 2) of code duplicated from In to StdIn */

    /*** begin: section (2 of 2) of code duplicated from In to StdIn,
      *  with all methods changed from "public" to "public static" ***/

   /**
     * Is the input empty (except possibly for whitespace)? Use this
     * to know whether the next call to {@link #readString()}, 
     * {@link #readDouble()}, etc will succeed.
     * @return true if standard input is empty (except possibly
     *     for whitespae), and false otherwise
     */
    public static boolean isEmpty() {
        return !scanner.hasNext();
    }

   /**
     * Does the input have a next line? Use this to know whether the
     * next call to {@link #readLine()} will succeed. <p> Functionally
     * equivalent to {@link #hasNextChar()}.
     * @return true if standard input is empty, and false otherwise
     */
    public static boolean hasNextLine() {
        return scanner.hasNextLine();
    }

    /**
     * Is the input empty (including whitespace)? Use this to know 
     * whether the next call to {@link #readChar()} will succeed.
     * <p>Functionally equivalent to {@link #hasNextLine()}.
     * @return true if standard input is empty, and false otherwise
     */
    public static boolean hasNextChar() {
        scanner.useDelimiter(EMPTY_PATTERN);
        boolean result = scanner.hasNext();
        scanner.useDelimiter(WHITESPACE_PATTERN);
        return result;
    }


   /**
     * Reads and returns the next line, excluding the line separator if present.
     * @return the next line, excluding the line separator if present
     */
    public static String readLine() {
        String line;
        try                 { line = scanner.nextLine(); }
        catch (Exception e) { line = null;               }
        return line;
    }

    /**
     * Reads and returns the next character.
     * @return the next character
     */
    public static char readChar() {
        scanner.useDelimiter(EMPTY_PATTERN);
        String ch = scanner.next();
        assert (ch.length() == 1) : "Internal (Std)In.readChar() error!"
            + " Please contact the authors.";
        scanner.useDelimiter(WHITESPACE_PATTERN);
        return ch.charAt(0);
    }  


   /**
     * Reads and returns the remainder of the input, as a string.
     * @return the remainder of the input, as a string
     */
    public static String readAll() {
        if (!scanner.hasNextLine())
            return "";

        String result = scanner.useDelimiter(EVERYTHING_PATTERN).next();
        // not that important to reset delimeter, since now scanner is empty
        scanner.useDelimiter(WHITESPACE_PATTERN); // but let's do it anyway
        return result;
    }


   /**
     * Reads the next token  and returns the <tt>String</tt>.
     * @return the next <tt>String</tt>
     */
    public static String readString() {
        return scanner.next();
    }

   /**
     * Reads the next token from standard input, parses it as an integer, and returns the integer.
     * @return the next integer on standard input
     * @throws InputMismatchException if the next token cannot be parsed as an <tt>int</tt>
     */
    public static int readInt() {
        return scanner.nextInt();
    }

   /**
     * Reads the next token from standard input, parses it as a double, and returns the double.
     * @return the next double on standard input
     * @throws InputMismatchException if the next token cannot be parsed as a <tt>double</tt>
     */
    public static double readDouble() {
        return scanner.nextDouble();
    }

   /**
     * Reads the next token from standard input, parses it as a float, and returns the float.
     * @return the next float on standard input
     * @throws InputMismatchException if the next token cannot be parsed as a <tt>float</tt>
     */
    public static float readFloat() {
        return scanner.nextFloat();
    }

   /**
     * Reads the next token from standard input, parses it as a long integer, and returns the long integer.
     * @return the next long integer on standard input
     * @throws InputMismatchException if the next token cannot be parsed as a <tt>long</tt>
     */
    public static long readLong() {
        return scanner.nextLong();
    }

   /**
     * Reads the next token from standard input, parses it as a short integer, and returns the short integer.
     * @return the next short integer on standard input
     * @throws InputMismatchException if the next token cannot be parsed as a <tt>short</tt>
     */
    public static short readShort() {
        return scanner.nextShort();
    }

   /**
     * Reads the next token from standard input, parses it as a byte, and returns the byte.
     * @return the next byte on standard input
     * @throws InputMismatchException if the next token cannot be parsed as a <tt>byte</tt>
     */
    public static byte readByte() {
        return scanner.nextByte();
    }

    /**
     * Reads the next token from standard input, parses it as a boolean,
     * and returns the boolean.
     * @return the next boolean on standard input
     * @throws InputMismatchException if the next token cannot be parsed as a <tt>boolean</tt>:
     *    <tt>true</tt> or <tt>1</tt> for true, and <tt>false</tt> or <tt>0</tt> for false,
     *    ignoring case
     */
    public static boolean readBoolean() {
        String s = readString();
        if (s.equalsIgnoreCase("true"))  return true;
        if (s.equalsIgnoreCase("false")) return false;
        if (s.equals("1"))               return true;
        if (s.equals("0"))               return false;
        throw new InputMismatchException();
    }

    /**
     * Reads all remaining tokens from standard input and returns them as an array of strings.
     * @return all remaining tokens on standard input, as an array of strings
     */
    public static String[] readAllStrings() {
        // we could use readAll.trim().split(), but that's not consistent
        // because trim() uses characters 0x00..0x20 as whitespace
        String[] tokens = WHITESPACE_PATTERN.split(readAll());
        if (tokens.length == 0 || tokens[0].length() > 0)
            return tokens;

        // don't include first token if it is leading whitespace
        String[] decapitokens = new String[tokens.length-1];
        for (int i = 0; i < tokens.length - 1; i++)
            decapitokens[i] = tokens[i+1];
        return decapitokens;
    }

    /**
     * Reads all remaining lines from standard input and returns them as an array of strings.
     * @return all remaining lines on standard input, as an array of strings
     */
    public static String[] readAllLines() {
        ArrayList<String> lines = new ArrayList<String>();
        while (hasNextLine()) {
            lines.add(readLine());
        }
        return lines.toArray(new String[0]);
    }

    /**
     * Reads all remaining tokens from standard input, parses them as integers, and returns
     * them as an array of integers.
     * @return all remaining integers on standard input, as an array
     * @throws InputMismatchException if any token cannot be parsed as an <tt>int</tt>
     */
    public static int[] readAllInts() {
        String[] fields = readAllStrings();
        int[] vals = new int[fields.length];
        for (int i = 0; i < fields.length; i++)
            vals[i] = Integer.parseInt(fields[i]);
        return vals;
    }

    /**
     * Reads all remaining tokens from standard input, parses them as doubles, and returns
     * them as an array of doubles.
     * @return all remaining doubles on standard input, as an array
     * @throws InputMismatchException if any token cannot be parsed as a <tt>double</tt>
     */
    public static double[] readAllDoubles() {
        String[] fields = readAllStrings();
        double[] vals = new double[fields.length];
        for (int i = 0; i < fields.length; i++)
            vals[i] = Double.parseDouble(fields[i]);
        return vals;
    }
    
    /*** end: section (2 of 2) of code duplicated from In to StdIn */
    
    
    // do this once when StdIn is initialized
    static {
        resync();
    }

    /**
     * If StdIn changes, use this to reinitialize the scanner.
     */
    private static void resync() {
        setScanner(new Scanner(new java.io.BufferedInputStream(System.in), CHARSET_NAME));
    }
    
    private static void setScanner(Scanner scanner) {
        StdIn.scanner = scanner;
        StdIn.scanner.useLocale(LOCALE);
    }

   /**
     * Reads all remaining tokens, parses them as integers, and returns
     * them as an array of integers.
     * @return all remaining integers, as an array
     * @throws InputMismatchException if any token cannot be parsed as an <tt>int</tt>
     * @deprecated For more consistency, use {@link #readAllInts()}
     */
    public static int[] readInts() {
        return readAllInts();
    }

   /**
     * Reads all remaining tokens, parses them as doubles, and returns
     * them as an array of doubles.
     * @return all remaining doubles, as an array
     * @throws InputMismatchException if any token cannot be parsed as a <tt>double</tt>
     * @deprecated For more consistency, use {@link #readAllDoubles()}
     */
    public static double[] readDoubles() {
        return readAllDoubles();
    }

   /**
     * Reads all remaining tokens and returns them as an array of strings.
     * @return all remaining tokens, as an array of strings
     * @deprecated For more consistency, use {@link #readAllStrings()}
     */
    public static String[] readStrings() {
        return readAllStrings();
    }


    /**
     * Interactive test of basic functionality.
     */
    public static void main(String[] args) {

        System.out.println("Type a string: ");
        String s = StdIn.readString();
        System.out.println("Your string was: " + s);
        System.out.println();

        System.out.println("Type an int: ");
        int a = StdIn.readInt();
        System.out.println("Your int was: " + a);
        System.out.println();

        System.out.println("Type a boolean: ");
        boolean b = StdIn.readBoolean();
        System.out.println("Your boolean was: " + b);
        System.out.println();

        System.out.println("Type a double: ");
        double c = StdIn.readDouble();
        System.out.println("Your double was: " + c);
        System.out.println();

    }

}

StdOut.java

// This code is originally from Algorithms, 4th Edition: http://algs4.cs.princeton.edu/home/
// Source: http://introcs.cs.princeton.edu/java/stdlib/StdOut.java.html

/*************************************************************************
 *  Compilation:  javac StdOut.java
 *  Execution:    java StdOut
 *
 *  Writes data of various types to standard output.
 *
 *************************************************************************/

import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.UnsupportedEncodingException;
import java.util.Locale;

/**
 *  <i>Standard output</i>. This class provides methods for writing strings
 *  and numbers to standard output.
 *  <p>
 *  For additional documentation, see <a href="http://introcs.cs.princeton.edu/15inout">Section 1.5</a> of
 *  <i>Introduction to Programming in Java: An Interdisciplinary Approach</i> by Robert Sedgewick and Kevin Wayne.
 *
 *  @author Robert Sedgewick
 *  @author Kevin Wayne
 */
public final class StdOut {

    // force Unicode UTF-8 encoding; otherwise it's system dependent
    private static final String CHARSET_NAME = "UTF-8";

    // assume language = English, country = US for consistency with StdIn
    private static final Locale LOCALE = Locale.US;

    // send output here
    private static PrintWriter out;

    // this is called before invoking any methods
    static {
        try {
            out = new PrintWriter(new OutputStreamWriter(System.out, CHARSET_NAME), true);
        }
        catch (UnsupportedEncodingException e) { System.out.println(e); }
    }

    // don't instantiate
    private StdOut() { }

    // close the output stream (not required)
   /**
     * Close standard output.
     */
    public static void close() {
        out.close();
    }

   /**
     * Terminate the current line by printing the line separator string.
     */
    public static void println() {
        out.println();
    }

   /**
     * Print an object to standard output and then terminate the line.
     */
    public static void println(Object x) {
        out.println(x);
    }

   /**
     * Print a boolean to standard output and then terminate the line.
     */
    public static void println(boolean x) {
        out.println(x);
    }

   /**
     * Print a char to standard output and then terminate the line.
     */
    public static void println(char x) {
        out.println(x);
    }

   /**
     * Print a double to standard output and then terminate the line.
     */
    public static void println(double x) {
        out.println(x);
    }

   /**
     * Print a float to standard output and then terminate the line.
     */
    public static void println(float x) {
        out.println(x);
    }

   /**
     * Print an int to standard output and then terminate the line.
     */
    public static void println(int x) {
        out.println(x);
    }

   /**
     * Print a long to standard output and then terminate the line.
     */
    public static void println(long x) {
        out.println(x);
    }

   /**
     * Print a short to standard output and then terminate the line.
     */
    public static void println(short x) {
        out.println(x);
    }

   /**
     * Print a byte to standard output and then terminate the line.
     */
    public static void println(byte x) {
        out.println(x);
    }

   /**
     * Flush standard output.
     */
    public static void print() {
        out.flush();
    }

   /**
     * Print an Object to standard output and flush standard output.
     */
    public static void print(Object x) {
        out.print(x);
        out.flush();
    }

   /**
     * Print a boolean to standard output and flush standard output.
     */
    public static void print(boolean x) {
        out.print(x);
        out.flush();
    }

   /**
     * Print a char to standard output and flush standard output.
     */
    public static void print(char x) {
        out.print(x);
        out.flush();
    }

   /**
     * Print a double to standard output and flush standard output.
     */
    public static void print(double x) {
        out.print(x);
        out.flush();
    }

   /**
     * Print a float to standard output and flush standard output.
     */
    public static void print(float x) {
        out.print(x);
        out.flush();
    }

   /**
     * Print an int to standard output and flush standard output.
     */
    public static void print(int x) {
        out.print(x);
        out.flush();
    }

   /**
     * Print a long to standard output and flush standard output.
     */
    public static void print(long x) {
        out.print(x);
        out.flush();
    }

   /**
     * Print a short to standard output and flush standard output.
     */
    public static void print(short x) {
        out.print(x);
        out.flush();
    }

   /**
     * Print a byte to standard output and flush standard output.
     */
    public static void print(byte x) {
        out.print(x);
        out.flush();
    }

   /**
     * Print a formatted string to standard output using the specified
     * format string and arguments, and flush standard output.
     */
    public static void printf(String format, Object... args) {
        out.printf(LOCALE, format, args);
        out.flush();
    }

   /**
     * Print a formatted string to standard output using the specified
     * locale, format string, and arguments, and flush standard output.
     */
    public static void printf(Locale locale, String format, Object... args) {
        out.printf(locale, format, args);
        out.flush();
    }

    // This method is just here to test the class
    public static void main(String[] args) {

        // write to stdout
        StdOut.println("Test");
        StdOut.println(17);
        StdOut.println(true);
        StdOut.printf("%.6f\n", 1.0/7.0);
    }

}

WeightedQuickUnionPathCompressionUF.java

// This code is originally from Algorithms, 4th Edition: http://algs4.cs.princeton.edu/home/
// Source: http://algs4.cs.princeton.edu/15uf/WeightedQuickUnionPathCompressionUF.java.html

/****************************************************************************
 *  Compilation:  javac WeightedQuickUnionPathCompressionUF.java
 *  Execution:  java WeightedQuickUnionPathCompressionUF < input.txt
 *  Dependencies: StdIn.java StdOut.java
 *
 *  Weighted quick-union with path compression.
 *
 ****************************************************************************/

/**
 *  The <tt>WeightedQuickUnionPathCompressionUF</tt> class represents a
 *  union-find data structure.
 *  It supports the <em>union</em> and <em>find</em> operations, along with
 *  methods for determinig whether two objects are in the same component
 *  and the total number of components.
 *  <p>
 *  This implementation uses weighted quick union (by size) with full path compression.
 *  Initializing a data structure with <em>N</em> objects takes linear time.
 *  Afterwards, <em>union</em>, <em>find</em>, and <em>connected</em> take
 *  logarithmic time (in the worst case) and <em>count</em> takes constant
 *  time. Moreover, the amortized time per <em>union</em>, <em>find</em>,
 *  and <em>connected</em> operation has inverse Ackermann complexity.
 *  <p>
 *  For additional documentation, see <a href="http://algs4.cs.princeton.edu/15uf">Section 1.5</a> of
 *  <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne.
 *
 *  @author Robert Sedgewick
 *  @author Kevin Wayne
 */
public class WeightedQuickUnionPathCompressionUF {
    private int[] id;    // id[i] = parent of i
    private int[] sz;    // sz[i] = number of objects in subtree rooted at i
    private int count;   // number of components

    /**
     * Initializes an empty union-find data structure with N isolated components 0 through N-1.
     * @throws java.lang.IllegalArgumentException if N < 0
     * @param N the number of objects
     */
    public WeightedQuickUnionPathCompressionUF(int N) {
        count = N;
        id = new int[N];
        sz = new int[N];
        for (int i = 0; i < N; i++) {
            id[i] = i;
            sz[i] = 1;
        }
    }

    /**
     * Returns the number of components.
     * @return the number of components (between 1 and N)
     */
    public int count() {
        return count;
    }


    /**
     * Are the two sites <tt>p</tt> and <tt>q</tt> in the same component?
     * @param p the integer representing one site
     * @param q the integer representing the other site
     * @return <tt>true</tt> if the two sites <tt>p</tt> and <tt>q</tt>
     *    are in the same component, and <tt>false</tt> otherwise
     * @throws java.lang.IndexOutOfBoundsException unless both 0 <= p < N and 0 <= q < N
     */
    public boolean connected(int p, int q) {
        return find(p) == find(q);
    }


    /**
     * Returns the component identifier for the component containing site <tt>p</tt>.
     * @param p the integer representing one site
     * @return the component identifier for the component containing site <tt>p</tt>
     * @throws java.lang.IndexOutOfBoundsException unless 0 <= p < N
     */
    public int find(int p) {
        int root = p;
        while (root != id[root])
            root = id[root];
        while (p != root) {
            int newp = id[p];
            id[p] = root;
            p = newp;
        }
        return root;
    }


    /**
     * Merges the component containing site<tt>p</tt> with the component
     * containing site <tt>q</tt>.
     * @param p the integer representing one site
     * @param q the integer representing the other site
     * @throws java.lang.IndexOutOfBoundsException unless both 0 <= p < N and 0 <= q < N
     */
    public void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP == rootQ) return;

        // make smaller root point to larger one
        if   (sz[rootP] < sz[rootQ]) { id[rootP] = rootQ; sz[rootQ] += sz[rootP]; }
        else                         { id[rootQ] = rootP; sz[rootP] += sz[rootQ]; }
        count--;
    }


    /**
     * Reads in a sequence of pairs of integers (between 0 and N-1) from standard input,
     * where each integer represents some object;
     * if the objects are in different components, merge the two components
     * and print the pair to standard output.
     */
    public static void main(String[] args) {
        StdOut.println("Starting...");
        int N = StdIn.readInt();
        WeightedQuickUnionPathCompressionUF uf = new WeightedQuickUnionPathCompressionUF(N);
        while (!StdIn.isEmpty()) {
            int p = StdIn.readInt();
            int q = StdIn.readInt();
            if (uf.connected(p, q)) continue;
            uf.union(p, q);
            StdOut.println(p + " " + q);
        }
        StdOut.println(uf.count() + " components");
    }

}

WeightedQuickUnionPathCompressionUF.m

#import <Foundation/Foundation.h>

@interface WeightedQuickUnionPathCompressionUF : NSObject
@property (nonatomic, strong) NSMutableArray *nodeIDs;
@property (nonatomic, strong) NSMutableArray *sizes;
@property (nonatomic, assign, readonly) NSInteger count;

- (NSInteger)findP:(NSInteger)p;
- (void)unionBetweenP:(NSInteger)p andQ:(NSInteger)q;
- (BOOL)isConnectedP:(NSInteger)p andQ:(NSInteger)q;
- (instancetype)initWithN:(NSInteger)n;
@end

@implementation WeightedQuickUnionPathCompressionUF

- (instancetype)initWithN:(NSInteger)n {
    self = [super init];
    if (self) {
        _nodeIDs = [NSMutableArray arrayWithCapacity:n];
        _sizes = [NSMutableArray arrayWithCapacity:n];
        _count = n;

        for (NSInteger i = 0; i < n; i++) {
            [_nodeIDs addObject:@(i)];
            [_sizes addObject:@(1)];
        }
    }
    return self;
}

- (NSInteger)nodeAtIndex:(NSInteger)index {
    NSNumber *node = _nodeIDs[index];
    return node.integerValue;
}

- (NSInteger)sizeAtIndex:(NSInteger)index {
    NSNumber *size = _sizes[index];
    return size.integerValue;
}

- (NSInteger)findP:(NSInteger)p {
    NSInteger root = p;
    NSInteger myP = p;
    while (root != [self nodeAtIndex:root]) {
        root = [self nodeAtIndex:root];
    }
    NSNumber *rootNumber = @(root);
    while (myP != root) {
        NSInteger newP = [self nodeAtIndex:myP];
        _nodeIDs[myP] = rootNumber;
        myP = newP;
    }
    return root;
}

- (void)unionBetweenP:(NSInteger)p andQ:(NSInteger)q {
    NSInteger rootP = [self findP:p];
    NSInteger rootQ = [self findP:q];
    if (rootP == rootQ) {
        return;
    }

    NSInteger sizeP = [self sizeAtIndex:rootP];
    NSInteger sizeQ = [self sizeAtIndex:rootQ];
    if (sizeP < sizeQ) {
        _nodeIDs[rootP] = @(rootQ);
        _sizes[rootQ] = @([self sizeAtIndex:rootQ] + [self sizeAtIndex:rootP]);
    } else {
        _nodeIDs[rootQ] = @(rootP);
        _sizes[rootP] = @([self sizeAtIndex:rootQ] + [self sizeAtIndex:rootP]);
    }
    _count--;
}

- (BOOL)isConnectedP:(NSInteger)p andQ:(NSInteger)q {
    return [self findP:p] == [self findP:q];
}

@end

WeightedQuickUnionPathCompressionUF.swift

// Playground - noun: a place where people can play

import Foundation

class WeightedQuickUnionPathCompressionUF {
    var id = [Int]()
    var sz = [Int]()
    var count = 0

    init(_ n: Int) {
        count = n
        id.reserveCapacity(n)
        sz.reserveCapacity(n)
        for i in 0 ..< n {
            id.append(i)
            sz.append(1)
        }
    }

    func connected(p: Int, _ q: Int) -> Bool {
        return find(p) == find(q)
    }

    func find(p: Int) -> Int {
        var root = p
        var myP = p
        while root != id[root] {
            root = id[root]
        }
        while myP != root {
            var newp = id[myP]
            id[p] = root
            myP = newp
        }
        return root
    }

    func union(p: Int, _ q: Int) {
        let rootP = find(p)
        let rootQ = find(q)

        if sz[rootP] < sz[rootQ] {
            id[rootP] = rootQ
            sz[rootQ] += sz[rootP]
        } else {
            id[rootQ] = rootP
            sz[rootP] += sz[rootQ]
        }
        count--
    }
}


func parseInput(inputString: String) -> (count: Int, pairs: [(Int, Int)]) {
    let nl = NSCharacterSet.newlineCharacterSet()
    let ws = NSCharacterSet.whitespaceAndNewlineCharacterSet()
    let lines = inputString
        .stringByTrimmingCharactersInSet(ws)
        .componentsSeparatedByCharactersInSet(nl)
    let count = (lines[0] as NSString).integerValue
    let pairs =
        map(lines[1..<lines.count]) { (line: String) -> (Int, Int) in
            let components = line.stringByTrimmingCharactersInSet(ws)
                                 .componentsSeparatedByCharactersInSet(ws)
            return ((components[0] as NSString).integerValue,
                    (components[1] as NSString).integerValue)
        }
    return (count: count, pairs: pairs)
}


func profileAs<T>(label: String, block: () -> T) -> T {
    println("\(label)...")
    let start = NSDate()
    let result = block()
    let end = NSDate()
    println("\(label) took \(end.timeIntervalSinceDate(start)) seconds.")
    return result
}


func buildUnionFind(count: Int, pairs: [(Int, Int)]) -> WeightedQuickUnionPathCompressionUF {
    var uf = WeightedQuickUnionPathCompressionUF(count)
    for (p, q) in pairs {
        if !uf.connected(p, q) {
            uf.union(p, q)
        }
    }
    return uf
}

// MARK: main program
func fastMain() {
    let handle = NSFileHandle.fileHandleWithStandardInput()

    let inputString = profileAs("Reading file") {
        NSString(data: handle.availableData, encoding: NSUTF8StringEncoding)!
    }

    let (count, pairs) = profileAs("Parse input") {
        parseInput(inputString)
    }

    println("count: \(count), #pairs: \(pairs.count)")

    let uf = profileAs("Building the Union-Find structure") {
        buildUnionFind(count, pairs)
    }

    println("There are \(uf.count) components.")
}

func slowMain() {
    println("Reading in file")
    var handle = NSFileHandle.fileHandleWithStandardInput()
    var inputData = handle.availableData
    var inputString = NSString(data: inputData, encoding: NSUTF8StringEncoding)!
    inputString = inputString.stringByTrimmingCharactersInSet(NSCharacterSet.newlineCharacterSet())
    var lines = inputString.componentsSeparatedByCharactersInSet(NSCharacterSet.newlineCharacterSet())
    var firstLine = lines[0] as NSString

    println("Creating UF")
    var uf = WeightedQuickUnionPathCompressionUF(firstLine.integerValue)

    println("Populating UF")
    let start = NSDate()
    for i in 1 ..< lines.count - 1 {
        let line = lines[i] as NSString
        var parts = line.componentsSeparatedByString(" ")
        let pString = parts[0] as NSString
        let qString = parts[1] as NSString
        let p = pString.integerValue
        let q = qString.integerValue
        if uf.connected(p, q) {
            continue
        }
        uf.union(p, q)
    }
    println("\(uf.count) components")
    let end = NSDate()
    println("Time taken: \(end.timeIntervalSinceDate(start))")
}

//slowMain()
fastMain()

Seems like the benchmark is dominated by IO. See the results from my edit in https://gist.github.com/pyrtsa/486bd679b326b01b6b85#file-test-run-txt