Category Archives: Uncategorized

Binary tree post order iterative traversal

I’m feeling bothered with the current tree search implementations I’ve found online. I think they are confusing and more difficult than they should be. People state that iterative post order is the “hardest of the three iterative DFS”, while the three implementation are supposed to be at least somewhat orthogonal.

So, here is my implementation of a post order iterative traversal. The idea is that we use a stack to store a program. The program has 3 parts, processing the left and right nodes and processing the current node, just like the contents of the recursive function. We also store context information to know what to do in each part of the program, again, like the recursive function: for children, we do the recursion (add a new program in the stack), for the current node, we process it.

#!/usr/bin/env python

class Tree:
        def __init__(self, val, left=None, right=None):
                self.left = left
                self.val = val
                self.right = right

        def postorder(self):
                stack = [(self.val, False), (self.right, True), (self.left, True)]

                while len(stack) != 0:
                        data, is_tree = stack.pop()
                        if not is_tree:
                                print(data)
                                continue
                        if data is None:
                                continue
                        stack += [(data.val, False), (data.right, True), (data.left, True)]

if __name__ == '__main__':
        t = Tree(1, Tree(2, Tree(3), Tree(4)), Tree(5, None, Tree(6)))
        t.postorder()

To implement the inorder and preorder versions, just change the relative position of self.val when inserting a new program in the stack.

                        stack += [(data.right, True), (data.val, False), (data.left, True)]
                        stack += [(data.right, True), (data.left, True), (data.val, False)]
Advertisements

Can compression slow down network transfers ?

Note: this post is mostly relevant to local links or very fast internet links. The task was to transfer a backup from my notebook to my desktop machine using an ethernet connection. After googling a little about rsync I ended up with the following discussion.

An interesting finding: using modern compression tools degrades transfer performance, because their compression speeds are lower than the disk speeds (and don’t compensate with data compression). For example, gzip compression is about 11MiB/s, while lzmash is 0,5MiB/s, or 22 times slower (2005 data). Expected compression is 2,7 times for gzip and 3,7 times for lzmash (when compressing openoffice):

​http://tukaani.org/lzma/benchmarks.html

This also means that gzip efficiency is limited to a network of 11MiB/s (92,3 Mbps). If a faster network is available, removing gzip will increase transfer rate. Ex: 100 Mbps.

  • File: 1GiB
  • raw transfer time: 85,9s
  • gzip time: 93,1s

Best cases described for gzip varied (in 2005) from 18MiB/s to 24MiB/s in fast mode. A more recent benchmark describes gzip at 54,8MiB/s at its best configuration, compressing source code:

http://pokecraft.first-world.info/wiki/Quick_Benchmark:_Gzip_vs_Bzip2_vs_LZMA_vs_XZ_vs_LZ4_vs_LZO

This raises network break even speed to 460 Mbps.

This updated benchmark describes 2 compressors much faster than gzip: lz4 and lzop. lz4 achieved 341,9MiB/s and lzop 277,8MiB/s. Network break-even jumps to 2.868,2 Mbps, but in this case, transfer would be limited by disk speed (or network). Expected compression is 2,8 times (for source code), versus 3,7 for gzip. Reviewing the transfer example:

  • File: 1GiB
  • raw transfer time: 85,9s
  • gzip time: 18,7s
  • lz4 time: 3,0s
  • gzip transfer time: 276,8MiB @ 23,2s
  • lz4 transfer time: 365,7MiB @ 30,7s
  • gzip decompression: 3,5s
  • lz4 decompression: 0,4s
  • gzip total time: ~26,7s (+latency)
  • lz4 total time: ~31,1s (+latency)

In this case gzip won, since the transfer is limited by the 100 Mbps link, so the best compression won. The improved gzip compression speed to more than 50MiB/s also made a lot of difference (however I’m currently unable to explain this speedup, since a quick and dirty gzip execution in my machine resulted in 17MiB/s).

Selecting the proper compressor, then is a matter of considering the transfer speed of the disk, the compressor and the network together, since each of them may impose a specific upper limit on each step of the transfer.