revised 0217/Driver.java (cuckoo versus chaining)

From: Michelangelo Grigni (mic@mathcs.emory.edu)
Date: Thu Feb 23 2012 - 13:22:53 EST

• Next message: Michelangelo Grigni: "hw3"
• Previous message: Michelangelo Grigni: "late penalties"
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]

I revised 0217/Driver.java, which we used to compare Cuckoo hashing
and Chaining.  The old driver created a set of random int keys, but
from a small range (N distinct keys in the range 0 to 2*N).  Later I
realized this would make our max bucket-size artificially small, which
ruins the motivation for Cuckoo hashing.

The revised Driver.java uses unbounded random int keys, and now
Chaining has a higher "max" probes stat (the maximum number of key
comparisons required to find any one key, we expect this to grow
slowly with N).  That motivates Cuckoo hashing, and other "perfect"
schemes, which bound their max probes by a constant.

Summary (N=500000 distinct int keys, max load 2 in chaining):
   cuckoo, either driver: max=2
   chaining, new driver:  max=12
   chaining, old driver:  max=4

For more detailed output, see 0217/Addendum.txt
 ( http://mathcs.emory.edu/~cs323000/share/0217/Addendum.txt )

• Next message: Michelangelo Grigni: "hw3"
• Previous message: Michelangelo Grigni: "late penalties"
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]

This archive was generated by hypermail 2.1.4 : Wed Apr 04 2012 - 17:34:17 EDT