c_cpp/lib/klib/test/khash_keith2.c

   1 /*
   2  * This is an optimized version of the following C++ program:
   3  *
   4  *   http://keithlea.com/javabench/src/cpp/hash.cpp
   5  *
   6  * Keith in his benchmark (http://keithlea.com/javabench/data) showed that the
   7  * Java implementation is twice as fast as the C++ version. In fact, this is
   8  * only because the C++ implementation is substandard. Most importantly, Keith
   9  * is using "sprintf()" to convert an integer to a string, which is known to be
  10  * extremely inefficient.
  11  */
  12 #include <stdio.h>
  13 #include "khash.h"
  14 KHASH_MAP_INIT_STR(str, int)
  15
  16 inline void int2str(int c, int base, char *ret)
  17 {
  18         const char *tab = "0123456789abcdef";
  19         if (c == 0) ret[0] = '0', ret[1] = 0;
  20         else {
  21                 int l, x, y;
  22                 char buf[16];
  23                 for (l = 0, x = c < 0? -c : c; x > 0; x /= base) buf[l++] = tab[x%base];
  24                 if (c < 0) buf[l++] = '-';
  25                 for (x = l - 1, y = 0; x >= 0; --x) ret[y++] = buf[x];
  26                 ret[y] = 0;
  27         }
  28 }
  29
  30 int main(int argc, char *argv[])
  31 {
  32         int i, l, n = 1000, ret;
  33         khash_t(str) *h, *h2;
  34         khint_t k;
  35         h = kh_init(str);
  36         h2 = kh_init(str);
  37         if (argc > 1) n = atoi(argv[1]);
  38         for (i = 0; i < 10000; ++i) {
  39                 char buf[32];
  40                 strcpy(buf, "foo_");
  41                 int2str(i, 10, buf+4);
  42                 k = kh_put(str, h, strdup(buf), &ret);
  43                 kh_val(h, k) = i;
  44         }
  45         for (i = 0; i < n; ++i) {
  46                 for (k = kh_begin(h); k != kh_end(h); ++k) {
  47                         if (kh_exist(h, k)) {
  48                                 khint_t k2 = kh_put(str, h2, kh_key(h, k), &ret);
  49                                 if (ret) { // absent
  50                                         kh_key(h2, k2) = strdup(kh_key(h, k));
  51                                         kh_val(h2, k2) = kh_val(h, k);
  52                                 } else kh_val(h2, k2) += kh_val(h, k);
  53                         }
  54                 }
  55         }
  56         k = kh_get(str, h, "foo_1"); printf("%d", kh_val(h, k));
  57         k = kh_get(str, h, "foo_9999"); printf(" %d", kh_val(h, k));
  58         k = kh_get(str, h2, "foo_1"); printf(" %d", kh_val(h2, k));
  59         k = kh_get(str, h2, "foo_9999"); printf(" %d\n", kh_val(h2, k));
  60         for (k = kh_begin(h); k != kh_end(h); ++k)
  61                 if (kh_exist(h, k)) free((char*)kh_key(h, k));
  62         for (k = kh_begin(h2); k != kh_end(h2); ++k)
  63                 if (kh_exist(h2, k)) free((char*)kh_key(h2, k));
  64         kh_destroy(str, h);
  65         kh_destroy(str, h2);
  66         return 0;
  67 }