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

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