kmike/DAWG — pull request #4 by dan-blanchard (2012-09-25 19:36:00+00:00)
Title: Added iterkeys(), iteritems(), and iterprefixes()

I've added the iterator-based versions of keys(), items(), and prefixes(). I used def instead of cpdef because I couldn't figure out what the return type was supposed to be for something that uses a generator.

Here are the current benchmark results. I had to change the benchmark code a little bit to wrap the calls to the iterator based versions in list(), because otherwise it was only using each iterator one time. As you expected there was a drop in performance, but the memory usage improvements are worth it in my case.

====== Benchmarks (100k unique unicode words) =======

dict __getitem__ (hits): 5.820M ops/sec
DAWG __getitem__ (hits): not supported
BytesDAWG __getitem__ (hits): 2.047M ops/sec
RecordDAWG __getitem__ (hits): 1.457M ops/sec
IntDAWG __getitem__ (hits): 3.664M ops/sec
dict get() (hits): 4.014M ops/sec
DAWG get() (hits): not supported
BytesDAWG get() (hits): 1.720M ops/sec
RecordDAWG get() (hits): 1.235M ops/sec
IntDAWG get() (hits): 2.916M ops/sec
dict get() (misses): 5.404M ops/sec
DAWG get() (misses): not supported
BytesDAWG get() (misses): 3.570M ops/sec
RecordDAWG get() (misses): 3.118M ops/sec
IntDAWG get() (misses): 3.971M ops/sec
dict __contains__ (hits): 5.605M ops/sec
DAWG __contains__ (hits): 3.883M ops/sec
BytesDAWG __contains__ (hits): 3.515M ops/sec
RecordDAWG __contains__ (hits): 3.581M ops/sec
IntDAWG __contains__ (hits): 3.816M ops/sec
dict __contains__ (misses): 4.874M ops/sec
DAWG __contains__ (misses): 5.338M ops/sec
BytesDAWG __contains__ (misses): 5.097M ops/sec
RecordDAWG __contains__ (misses): 5.099M ops/sec
IntDAWG __contains__ (misses): 5.243M ops/sec
dict items(): 52.135 ops/sec
DAWG items(): not supported
BytesDAWG items(): 15.795 ops/sec
RecordDAWG items(): 11.405 ops/sec
IntDAWG items(): not supported
dict keys(): 116.619 ops/sec
DAWG keys(): not supported
BytesDAWG keys(): 21.188 ops/sec
RecordDAWG keys(): 20.985 ops/sec
IntDAWG keys(): not supported
DAWG.prefixes (hits): 0.533M ops/sec
DAWG.prefixes (mixed): 2.689M ops/sec
DAWG.prefixes (misses): 3.234M ops/sec
DAWG.iterprefixes (hits): 0.309M ops/sec
DAWG.iterprefixes (mixed): 0.734M ops/sec
DAWG.iterprefixes (misses): 0.851M ops/sec
DAWG.keys(prefix="xxx"), avg_len(res)==415: not supported
DAWG.items(prefix="xxx"), avg_len(res)==415: not supported
DAWG.iterkeys(prefix="xxx"), avg_len(res)==415: not supported
DAWG.iteritems(prefix="xxx"), avg_len(res)==415: not supported
DAWG.keys(prefix="xxxxx"), avg_len(res)==17: not supported
DAWG.items(prefix="xxxxx"), avg_len(res)==17: not supported
DAWG.iterkeys(prefix="xxxxx"), avg_len(res)==17: not supported
DAWG.iteritems(prefix="xxxxx"), avg_len(res)==17: not supported
DAWG.keys(prefix="xxxxxxxx"), avg_len(res)==3: not supported
DAWG.items(prefix="xxxxxxxx"), avg_len(res)==3: not supported
DAWG.iterkeys(prefix="xxxxxxxx"), avg_len(res)==3: not supported
DAWG.iteritems(prefix="xxxxxxxx"), avg_len(res)==3: not supported
DAWG.keys(prefix="xxxxx..xx"), avg_len(res)==1.4: not supported
DAWG.items(prefix="xxxxx..xx"), avg_len(res)==1.4: not supported
DAWG.iterkeys(prefix="xxxxx..xx"), avg_len(res)==1.4: not supported
DAWG.iteritems(prefix="xxxxx..xx"), avg_len(res)==1.4: not supported
DAWG.keys(prefix="xxx"), NON_EXISTING: not supported
DAWG.items(prefix="xxx"), NON_EXISTING: not supported
DAWG.iterkeys(prefix="xxx"), NON_EXISTING: not supported
DAWG.iteritems(prefix="xxx"), NON_EXISTING: not supported
BytesDAWG.prefixes (hits): 0.498M ops/sec
BytesDAWG.prefixes (mixed): 2.313M ops/sec
BytesDAWG.prefixes (misses): 2.774M ops/sec
BytesDAWG.iterprefixes (hits): 0.294M ops/sec
BytesDAWG.iterprefixes (mixed): 0.702M ops/sec
BytesDAWG.iterprefixes (misses): 0.806M ops/sec
BytesDAWG.keys(prefix="xxx"), avg_len(res)==415: 5.644K ops/sec
BytesDAWG.items(prefix="xxx"), avg_len(res)==415: 4.483K ops/sec
BytesDAWG.iterkeys(prefix="xxx"), avg_len(res)==415: 5.559K ops/sec
BytesDAWG.iteritems(prefix="xxx"), avg_len(res)==415: 4.389K ops/sec
BytesDAWG.keys(prefix="xxxxx"), avg_len(res)==17: 124.065K ops/sec
BytesDAWG.items(prefix="xxxxx"), avg_len(res)==17: 101.816K ops/sec
BytesDAWG.iterkeys(prefix="xxxxx"), avg_len(res)==17: 108.605K ops/sec
BytesDAWG.iteritems(prefix="xxxxx"), avg_len(res)==17: 79.601K ops/sec
BytesDAWG.keys(prefix="xxxxxxxx"), avg_len(res)==3: 490.352K ops/sec
BytesDAWG.items(prefix="xxxxxxxx"), avg_len(res)==3: 424.382K ops/sec
BytesDAWG.iterkeys(prefix="xxxxxxxx"), avg_len(res)==3: 321.238K ops/sec
BytesDAWG.iteritems(prefix="xxxxxxxx"), avg_len(res)==3: 200.748K ops/sec
BytesDAWG.keys(prefix="xxxxx..xx"), avg_len(res)==1.4: 731.310K ops/sec
BytesDAWG.items(prefix="xxxxx..xx"), avg_len(res)==1.4: 652.742K ops/sec
BytesDAWG.iterkeys(prefix="xxxxx..xx"), avg_len(res)==1.4: 407.056K ops/sec
BytesDAWG.iteritems(prefix="xxxxx..xx"), avg_len(res)==1.4: 238.548K ops/sec
BytesDAWG.keys(prefix="xxx"), NON_EXISTING: not supported
BytesDAWG.items(prefix="xxx"), NON_EXISTING: not supported
BytesDAWG.iterkeys(prefix="xxx"), NON_EXISTING: not supported
BytesDAWG.iteritems(prefix="xxx"), NON_EXISTING: not supported
RecordDAWG.prefixes (hits): 0.488M ops/sec
RecordDAWG.prefixes (mixed): 2.254M ops/sec
RecordDAWG.prefixes (misses): 2.671M ops/sec
RecordDAWG.iterprefixes (hits): 0.296M ops/sec
RecordDAWG.iterprefixes (mixed): 0.716M ops/sec
RecordDAWG.iterprefixes (misses): 0.836M ops/sec
RecordDAWG.keys(prefix="xxx"), avg_len(res)==415: 5.604K ops/sec
RecordDAWG.items(prefix="xxx"), avg_len(res)==415: 3.423K ops/sec
RecordDAWG.iterkeys(prefix="xxx"), avg_len(res)==415: 5.541K ops/sec
RecordDAWG.iteritems(prefix="xxx"), avg_len(res)==415: 3.358K ops/sec
RecordDAWG.keys(prefix="xxxxx"), avg_len(res)==17: 124.167K ops/sec
RecordDAWG.items(prefix="xxxxx"), avg_len(res)==17: 78.939K ops/sec
RecordDAWG.iterkeys(prefix="xxxxx"), avg_len(res)==17: 107.266K ops/sec
RecordDAWG.iteritems(prefix="xxxxx"), avg_len(res)==17: 62.268K ops/sec
RecordDAWG.keys(prefix="xxxxxxxx"), avg_len(res)==3: 476.951K ops/sec
RecordDAWG.items(prefix="xxxxxxxx"), avg_len(res)==3: 337.651K ops/sec
RecordDAWG.iterkeys(prefix="xxxxxxxx"), avg_len(res)==3: 317.702K ops/sec
RecordDAWG.iteritems(prefix="xxxxxxxx"), avg_len(res)==3: 162.293K ops/sec
RecordDAWG.keys(prefix="xxxxx..xx"), avg_len(res)==1.4: 718.572K ops/sec
RecordDAWG.items(prefix="xxxxx..xx"), avg_len(res)==1.4: 541.830K ops/sec
RecordDAWG.iterkeys(prefix="xxxxx..xx"), avg_len(res)==1.4: 406.727K ops/sec
RecordDAWG.iteritems(prefix="xxxxx..xx"), avg_len(res)==1.4: 198.766K ops/sec
RecordDAWG.keys(prefix="xxx"), NON_EXISTING: not supported
RecordDAWG.items(prefix="xxx"), NON_EXISTING: not supported
RecordDAWG.iterkeys(prefix="xxx"), NON_EXISTING: not supported
RecordDAWG.iteritems(prefix="xxx"), NON_EXISTING: not supported
IntDAWG.prefixes (hits): 0.614M ops/sec
IntDAWG.prefixes (mixed): 2.970M ops/sec
IntDAWG.prefixes (misses): 3.432M ops/sec
IntDAWG.iterprefixes (hits): 0.360M ops/sec
IntDAWG.iterprefixes (mixed): 0.857M ops/sec
IntDAWG.iterprefixes (misses): 0.977M ops/sec
IntDAWG.keys(prefix="xxx"), avg_len(res)==415: not supported
IntDAWG.items(prefix="xxx"), avg_len(res)==415: not supported
IntDAWG.iterkeys(prefix="xxx"), avg_len(res)==415: not supported
IntDAWG.iteritems(prefix="xxx"), avg_len(res)==415: not supported
IntDAWG.keys(prefix="xxxxx"), avg_len(res)==17: not supported
IntDAWG.items(prefix="xxxxx"), avg_len(res)==17: not supported
IntDAWG.iterkeys(prefix="xxxxx"), avg_len(res)==17: not supported
IntDAWG.iteritems(prefix="xxxxx"), avg_len(res)==17: not supported
IntDAWG.keys(prefix="xxxxxxxx"), avg_len(res)==3: not supported
IntDAWG.items(prefix="xxxxxxxx"), avg_len(res)==3: not supported
IntDAWG.iterkeys(prefix="xxxxxxxx"), avg_len(res)==3: not supported
IntDAWG.iteritems(prefix="xxxxxxxx"), avg_len(res)==3: not supported
IntDAWG.keys(prefix="xxxxx..xx"), avg_len(res)==1.4: not supported
IntDAWG.items(prefix="xxxxx..xx"), avg_len(res)==1.4: not supported
IntDAWG.iterkeys(prefix="xxxxx..xx"), avg_len(res)==1.4: not supported
IntDAWG.iteritems(prefix="xxxxx..xx"), avg_len(res)==1.4: not supported
IntDAWG.keys(prefix="xxx"), NON_EXISTING: not supported
IntDAWG.items(prefix="xxx"), NON_EXISTING: not supported
IntDAWG.iterkeys(prefix="xxx"), NON_EXISTING: not supported
IntDAWG.iteritems(prefix="xxx"), NON_EXISTING: not supported

~~~~~~~~~~~~~~