Java: Splitting a Pipe-delimited String - Fast!

This post shows how you can efficiently split a pipe-delimited string e.g. "foo|bar|baz". There are many ways to do this - I could even write my own - but I will only use those that are available in the JDK (or commonly used libraries) and will measure the performance of each.

Remember that, since the pipe symbol (|) is a special character in regular expressions, it needs to be escaped if necessary.

1. String.split

The most obvious way to split a string on the pipe character is to use Java's String.split:

public static String[] split(String s) {
  return s.split("\\|");
}

2. String.split with Pattern.quote

Instead of escaping the pipe ourselves, we can use Pattern.quote to do it for us. (Note: Pattern.quote("|") returns "\Q|\E".)

public static String[] splitWithPatternQuote(String s) {
  return s.split(Pattern.quote("|"));
}

3. Pattern.split

Create a static Pattern and use it to split the string.

private static final Pattern SPLITTER = Pattern.compile("\\|");

public static String[] splitWithPattern(String s) {
  return SPLITTER.split(s);
}

4. StringUtils.split

Apache Commons provides StringUtils.split, which splits a string on a single character:

import org.apache.commons.lang3.StringUtils;

public static String[] splitWithStringUtils(String s) {
  return StringUtils.split(s, '|');
}

So, which one is fastest?

I ran each method on 1 million pipe-delimited strings of different lengths - RandomStringUtils.randomAlphabetic is great for generating random strings - and the table below shows how long each one took:

Method	Time (ms)
split	485
splitWithStringUtils	520
splitWithPattern	643
splitWithPatternQuote	936

An interesting observation is that splitWithPatternQuote is so much slower than split, even though they both call String.split internally! If we delve into the source code for String.split, we can see that there is an optimisation (a "fastpath") if the provided regex has two-chars and the first char is a backslash. This applies to "\\|" but, since Pattern.quote produces \Q|\E, it does not use the fastpath and instead creates a new Pattern object for every split. This also explains why it is slower than splitWithPattern, which re-uses the same Pattern object.

Stack Overflow - 150,000 rep reached!

I've been a bit quiet on Stack Overflow lately, but just managed to reach 150,000 reputation!

For me, Stack Overflow has not simply been a quest for reputation, but more about learning and helping fellow programmers in need.

Shell Scripting: <, << and <<<

This post shows the difference between the three standard input redirection operators: <, << and <<<.

1. <

< allows you to pass data contained in a file to the standard input of a command. The format is:

command < file

Examples:

# replace comma with new-lines:
tr ',' '\n' < file

# read a file line-by-line and do something with each line:
while IFS= read -r line; do
  # do something with each line
  ssh "$line" who -b
done < hosts.txt

2. <<

<< allows you to pass multi-line text (called a here-document) to a command until a specific "token" word is reached. The format is:

command << TOKEN
line 1
line 2
TOKEN

For example:

# query a database
sqsh -S server -D db << END
select * from table
where foo='bar'
go
END

3. <<<

<<< allows you to pass a string of text (called a here-string) to a command. If you find yourself echo-ing text and piping it to a command, you should use a here-string instead. (See my previous post on Useless Use of Echo.) The format is:

command <<< text

Examples:

tr ',' '\n' <<< "foo,bar,baz"

grep "foo" <<< "foo,bar,baz"

mailx -s subject $USER <<< "email body"

Java 8: Tree Traversal Using Streams

It's quite common to traverse a tree using recursion, but with Java 8 it is now possible to lazily traverse a tree using streams.

The class below represents a tree. The stream() method streams the nodes contained in the tree. You can then do all the cool things that you can do with other streams, such as filtering, mapping and collecting!

public class TreeNode<E> {

  private final E data;
  private final List<TreeNode<E>> children;

  /**
   * Creates the tree node with the specified data and no children.
   * @param data
   */
  public TreeNode(final E data) {
    this.data = data;
    this.children = new ArrayList<>();
  }

  /**
   * @return the data contained in this node
   */
  public E getData() {
    return data;
  }

  /**
   * Adds a child to this tree node.
   * @param data the data to add
   */
  public TreeNode<E> addChild(final E data) {
    final TreeNode<E> toAdd = new TreeNode<>(data);
    children.add(toAdd);
    return toAdd;
  }

  /**
   * @return a stream of nodes in this tree in depth first order
   */
  public Stream<TreeNode<E>> stream() {
    return Stream.concat(Stream.of(this), children.stream().flatMap(TreeNode::stream));
  }
}

Example usage:

TreeNode<String> root = new TreeNode<>("Root");
TreeNode<String> a = root.addChild("A");
a.addChild("A1");
a.addChild("A2");
root.addChild("B");
TreeNode<String> c = root.addChild("C");
c.addChild("C1");

int count = root.stream().count(); // 7

String tree = root.stream().map(TreeNode::getData).collect(Collectors.joining(","));
// Root,A,A1,A2,B,C,C1

Power Set Algorithm - Iterative

The power set of a set S is the set of all subsets of S including the empty set and S itself. For example, the power set of {1, 2, 3} is {{}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}.

Previously, I wrote about how you can generate the power set using a recursive algorithm. This time I'll show you how to use iteration.

Recall, that when we are generating a set for the power set, each element can either be in the set or out of the set. In other words, each set can be represented in binary form, where 1 means that the element is in the set and 0 means that it is not. For example, given a set {a, b, c}, the binary string 101 would represent {a, c}.

Generating the power set just comes down to generating all numbers from 0 to 2^n (since there are 2^n possible subsets) and converting the binary representation of the number into the set!

Here is the algorithm:

public static <E> List<List<E>> powerSet(final List<E> list) {
  final List<List<E>> result = new ArrayList<>();
  final int numSubSets = 1 << list.size(); // 2^n
  for (int i = 0; i < numSubSets; i++) {
    final List<E> subSet = new ArrayList<>();
    int index = 0;
    for (int j = i; j > 0; j >>= 1) { // keep shifting right
      if ((j & 1) == 1) { // check last bit
        subSet.add(list.get(index));
      }
      index++;
    }
    result.add(subSet);
  }
  return result;
}