Add to_list Implementation

[xingyaoww]

For Issue #13, add to_list method to SortedDict and some test cases for it. It takes one optional argument n_levels as an input parameter.

The method will return a list of (key, value) tuples with the length specified in the input argument. If no argument is passed or the argument is larger than the length of self->data, return items with a length of self->data.

Performance Result I also updated perf/performance_test.py to benchmark read performance (get depth of 10 for different dict types). to_list gives about 2x~2.5x improvement over .index of the current implementation, and large improvement over to_dict (when data length is large).

Here are some benchmark log:

===== Read Performance =====
C lib with 10 entries (access)
- index impl Time: 0.003099 ms
- todict impl Time: 0.005007 ms
- iter impl (incorrect when called multiple times) Time: 0.001431 ms
- tolist impl Time: 0.001907 ms
Orderbook SortedDict Python lib with 10 entries (access)
Time: 0.001431 ms
Python dict (non sorted) with 10 entries (access)
Time: 0.001192 ms
===== Read Performance =====
C lib with 100 entries (access)
- index impl Time: 0.002146 ms
- todict impl Time: 0.010729 ms
- iter impl (incorrect when called multiple times) Time: 0.001192 ms
- tolist impl Time: 0.001192 ms
Orderbook SortedDict Python lib with 100 entries (access)
Time: 0.001192 ms
Python dict (non sorted) with 100 entries (access)
Time: 0.001192 ms
===== Read Performance =====
C lib with 200 entries (access)
- index impl Time: 0.001907 ms
- todict impl Time: 0.018835 ms
- iter impl (incorrect when called multiple times) Time: 0.001192 ms
- tolist impl Time: 0.000954 ms
Orderbook SortedDict Python lib with 200 entries (access)
Time: 0.001431 ms
Python dict (non sorted) with 200 entries (access)
Time: 0.001192 ms
===== Read Performance =====
C lib with 400 entries (access)
- index impl Time: 0.001907 ms
- todict impl Time: 0.033617 ms
- iter impl (incorrect when called multiple times) Time: 0.001431 ms
- tolist impl Time: 0.001431 ms
Orderbook SortedDict Python lib with 400 entries (access)
Time: 0.001669 ms
Python dict (non sorted) with 400 entries (access)
Time: 0.001192 ms
===== Read Performance =====
C lib with 500 entries (access)
- index impl Time: 0.002384 ms
- todict impl Time: 0.040770 ms
- iter impl (incorrect when called multiple times) Time: 0.001669 ms
- tolist impl Time: 0.001192 ms
Orderbook SortedDict Python lib with 500 entries (access)
Time: 0.001431 ms
Python dict (non sorted) with 500 entries (access)
Time: 0.001192 ms
===== Read Performance =====
C lib with 1000 entries (access)
- index impl Time: 0.004053 ms
- todict impl Time: 0.085115 ms
- iter impl (incorrect when called multiple times) Time: 0.001431 ms
- tolist impl Time: 0.002146 ms
Orderbook SortedDict Python lib with 1000 entries (access)
Time: 0.001669 ms
Python dict (non sorted) with 1000 entries (access)
Time: 0.001431 ms
===== Read Performance =====
C lib with 2000 entries (access)
- index impl Time: 0.007629 ms
- todict impl Time: 0.265598 ms
- iter impl (incorrect when called multiple times) Time: 0.002146 ms
- tolist impl Time: 0.002384 ms
Orderbook SortedDict Python lib with 2000 entries (access)
Time: 0.004292 ms
Python dict (non sorted) with 2000 entries (access)
Time: 0.001192 ms
===== Read Performance =====
C lib with 10000 entries (access)
- index impl Time: 0.012159 ms
- todict impl Time: 1.729488 ms
- iter impl (incorrect when called multiple times) Time: 0.003099 ms
- tolist impl Time: 0.004530 ms
Orderbook SortedDict Python lib with 10000 entries (access)
Time: 0.008345 ms
Python dict (non sorted) with 10000 entries (access)
Time: 0.001669 ms
===== Read Performance =====
C lib with 100000 entries (access)
- index impl Time: 0.010014 ms
- todict impl Time: 27.706623 ms
- iter impl (incorrect when called multiple times) Time: 0.006676 ms
- tolist impl Time: 0.004530 ms
Orderbook SortedDict Python lib with 100000 entries (access)
Time: 0.009060 ms
Python dict (non sorted) with 100000 entries (access)
Time: 0.004053 ms
===== Read Performance =====
C lib with 200000 entries (access)
- index impl Time: 0.010967 ms
- todict impl Time: 71.116686 ms
- iter impl (incorrect when called multiple times) Time: 0.009060 ms
- tolist impl Time: 0.006437 ms
Orderbook SortedDict Python lib with 200000 entries (access)
Time: 0.010014 ms
Python dict (non sorted) with 200000 entries (access)
Time: 0.003576 ms
===== Read Performance =====
C lib with 500000 entries (access)
- index impl Time: 0.014305 ms
- todict impl Time: 220.933676 ms
- iter impl (incorrect when called multiple times) Time: 0.013828 ms
- tolist impl Time: 0.005722 ms
Orderbook SortedDict Python lib with 500000 entries (access)
Time: 0.011206 ms
Python dict (non sorted) with 500000 entries (access)
Time: 0.004530 ms

[bmoscon]

@xingyaoww - thanks for the PR - I'll review it in the next few days!

[lijiachang]

thanks