On Mon, Dec 16, 2002 at 08:54:38AM +0700, Komtanoo Pinpimai wrote:
> Hello,
>
> If I want to know that an element is exist in a datastructure, I can use hash
>to achieve with O(1):
>
> $x{a}=1;
> $x{b}=1;
>
> do something .. if exists $x{a};
I don't know Python's or PHP's implementation, but for Perl (at least
some versions) you can reduce the hash memory by 5% or so by storing
undef instead of 1. Of course, you must stick to using "exists" in
that case and not "defined" or simply "if".
I have mixed feelings about your binary tree idea. Do you propose to
implement it with Perl arrays and access them with Perl code? Oof!
On the other hand, I don't really agree with the wisdom that says hash
access is O(1). Apart from the "amortized" qualifier and warnings
about bad hashing functions, hash table access inherently involves
looking at a whole key, and the average key length must grow at least
O(log N). Perhaps this does not matter much in practice. Suffice it
to say, I would generally prefer to use a good b-tree implementation
than a hashtable for most (all?) purposes.
-John
> However, regarding of large memory size that a hash requires, I'm hastitate to
>use "perl hash" to tell whether some elements exist or not. (I don't want to know
>their corresponding values, I'm just want to know if it exists)
>
> The fisrt datastructure that come into my head is binary search tree. Even
>though its searching speed is not as fast as of hash (O(log N)), the data structure
>requires less memory..
>
> Yesterday, my friend told me that python and php have a built-in function to
>search their array. For python he said that python implements array with something
>like heap and it benefits for searching in array !?
>
> I wonder if "perl list" provides function for searching elements !? I think it
>is not good to do a bruteforce search in an unsorted array. If Perl list is built
>basing on data structures that enhance searching, it is possible to provide built-in
>fuction for searching !?
>
>
> Regards,
>
>
> _______________________________________________
> Boston-pm mailing list
> [EMAIL PROTECTED]
> http://mail.pm.org/mailman/listinfo/boston-pm
--
John Tobey <[EMAIL PROTECTED]>
\____^-^
_______________________________________________
Boston-pm mailing list
[EMAIL PROTECTED]
http://mail.pm.org/mailman/listinfo/boston-pm
