From: Patrik Hagglund <patha@ida.liu.se>
To: davem@dm.cobaltmicro.com
Cc: linux-kernel@vger.rutgers.edu
Subject: "fuzzy hashing" = skiplists in a different shape
Date: Fri, 28 Aug 1998 11:06:33 +0200 [thread overview]
Message-ID: <199808280906.LAA13808@portofix.ida.liu.se> (raw)
I saw your "fuzzy hashing" implementation on Linux Weekly News
yesterday, and to me it looks much like randomized skip list. The
neigbour_next list is the first level pointer chain and hash_next is
the second level. But, there is a notable exception. Your code
contians 16 second-level lists, that is, 15 redundant ones.
> it will be as fast or cheaper _even_ in the common case than what we
> have now
? What is this common case. I can't see how your implementation would
be faster than a good implementation of a balanced search tree.
Regards,
Patrik Hägglund,
intrested in data structures and algorithms,
but not a kernel hacker (yet)
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu
Please read the FAQ at http://www.altern.org/andrebalsa/doc/lkml-faq.html
next reply other threads:[~1998-08-28 9:54 UTC|newest]
Thread overview: 2+ messages / expand[flat|nested] mbox.gz Atom feed top
1998-08-28 9:06 Patrik Hagglund [this message]
1998-08-28 21:06 ` David S. Miller
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=199808280906.LAA13808@portofix.ida.liu.se \
--to=patha@ida.liu.se \
--cc=davem@dm.cobaltmicro.com \
--cc=linux-kernel@vger.rutgers.edu \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox
all inboxes | Powered by JetHome®