On Sat, Aug 22, 2009 at 5:07 PM, Forrest Sheng Bao<forrest....@gmail.com> wrote: > Oh, I mean both Perl 5 and Perl 6. I couldn't find proper list to ask this > question. So I asked in this list.
I'm not sure perl6-language is the proper place to be asking about the time-complexity of hashes in Perl6, or at least, not the way that you asked. Here's another way to ask, which might yield a more useful reply.. In C++, the STL guarantees that lookup operations in a "map" data structure are guaranteed to have a time complexity that is at most logarithmic in the number of key-value pairs in the map. Does the Perl-6 specification make any similar guarantees regarding hash lookups? If not, does anyone know, offhand, what the time complexity is for current implementations if hash lookup? > > Cheers, > Forrest > > Forrest Sheng Bao, BSEE, Graduate Student > Dept. of Computer Science/Electrical Engineering, Texas Tech University > http://narnia.cs.ttu.edu > Sent from Lubbock, TX, United States > > On Sat, Aug 22, 2009 at 4:04 PM, Nicholas Clark <n...@ccl4.org> wrote: > >> On Sat, Aug 22, 2009 at 04:01:13PM -0500, Forrest Sheng Bao wrote: >> > Does anyone know the time complexity of searching elements in hash tables >> in >> > Perl? Suppose the number of elements is n. >> > >> > I have no idea on how Perl automatically builds the hash function and the >> > table. If you can tell me how it works, that is also helpful. I can >> analyze >> > the algorithm myself. >> >> You're asking the question on the Perl 6 language list, but it's unclear >> whether you're asking about hashes in Perl 6, or in Perl 5. It's not >> possible to answer until you clarify that. >> >> Nicholas Clark >> >
