[cups.development] why not hash?

Hidetomo Katsura Hidetomo.Katsura at efi.com
Mon Apr 23 14:14:41 PDT 2007


thanks for the quick response, Michael.

i guess i wasn't clear what i meant by "hash". i meant to use the hash table
lookup which is O(1) assuming the collision is minimum, not the binary search
or linear search of hash values.

http://en.wikipedia.org/wiki/Hash_table

anyways, i'll post the changes when i have something.

thanks again!

katsura

-----Original Message-----
From: cups-dev-bounces at easysw.com on behalf of Michael Sweet
Sent: Mon 4/23/2007 1:59 PM
To: cups-dev at easysw.com
Subject: Re: [cups.development] why not hash?
 
Hidetomo Katsura wrote:
> hi there,
> 
> i'm new on this list.
> 
> i noticed that cups 1.2+ uses a binary search O(log n) to lookup the
> option keyword which is a major improvement from a linear search O(n)
> on cups 1.1.
 >
> can it use a hash table lookup O(1) instead? would cups.org take it
> if i write the hash table lookup? what's the process? obviously, i'm
> not familiar with open source processes.

First, hashes do not make a search O(1).  All they do is
potentially reduce the size of the set you are searching, possibly
improving the time needed to do the search.  Thus, a hashed binary
search is still O(log n) and a hashed linear search is still O(n).
("n" may just be smaller, but it is still "n").

Second, we've had a couple folks propose hashed lookups of the
options, some with very large patches that break binary
compatibility and in the end do not offer that much of a
speedup for the normal case, especially over the current O(log n)
implementation.

That said, you can probably experiment with the CUPS 1.2+
implementation that is based on the cups_array_t API.  As a starting
point, add a cupsArrayNew2() function that has hash size and hash
callback parameters, and add an (allocated) hash array to the private
cups_array_t structure to track the indices of the first element
added to the array with that hash value.  Make sure you update the
hash array indices whenever you add or remove an element (see the
code that maintains the current element index for inspiration), or
just update the hash after each cupsArrayFind() call (so the hash
array would be more of a cache array for previous lookups).

If you come up with a good performance improvement, post the changes
along with a sample PPD that demonstrates the improvement to the
Bugs & Features page:

     http://www.cups.org/str.php

-- 
______________________________________________________________________
Michael Sweet, Easy Software Products           mike at easysw dot com
Internet Printing and Document Software          http://www.easysw.com
_______________________________________________
cups-dev mailing list
cups-dev at easysw.com
http://lists.easysw.com/mailman/listinfo/cups-dev





More information about the cups-devel mailing list