3 ms·

What is the word splitting task mentioned here?

• lurker14 15y ago
  Not sure, but for the article's sake, "word splitting" is only relevant as it involves (singly-linked) list concatenation as a performance bottleneck. List concatentation is efficient when the first list is short (ideally length=1), which is to say, a right fold that builds a list by a series of prepend operations. Of course, that analysis is a little weird, because if our goal is to accumulate a large sequence (O(1) to get head, O(n) full traversal) as fast as possible, you shouldn't use a linked list at all. You should use something like a Finger Tree, whose construction is parallelizable (that is merging two size-n sublists is O(log n), not linked list's O(n) ).