I believe that if i get a 32bit integer which uniquely defines the string then the storage and comparison operations will be much faster.

That's exactly what a hash does; with the additional benefit that it deals with collisions, if they occur, automatically.

So store your strings in a hash; lookup is very fast and memory management is taken care of.

Hi rjohn1,

When you've got 200000 strings like "dir1/dir2/dir3/config1.config2/config/test1", they likely hold a whole lot more than 32 bits of information each, which means that when you reduce each string down to 32 bits you will lose information. Depending on the algorithm, that results in a chance of collisions - two different strings might produce the same 32 bit number, so they won't be unique. You've already said you want the numbers to be unique, so I'm assuming this is not acceptable, but just in case, there are lots of functions to do that (just one example of many: String::CRC32).

Since you said you want to uniquely identify each string, then you'll have to use something like Perl's hashes (probably best and easiest, as BrowserUk already noted) or maybe an indexed database column.

Note I've said nothing about speed gains or losses so far. When you're thinking about an optimization, the first step is to measure: How slow is your current implementation? How fast do you need it to be? Also it'd be helpful if you could tell us a bit about your current implementation. Maybe there's an easy fix that we haven't seen yet, like using a hash instead of grepping an array. Does your script run continually, or does it get called multiple times for each incoming string?

Regards,
-- Hauke D

Hi Hauke,

Thanks for the explanation. 32 bit has 2^32 combinations so theoritically speaking it can represent 200000 strings easily without repeating. But the algorithm should be tailored for it. I am not sure if you agree.. I was curious if such a unique number generating algo exits for Perl

Honestly speaking i did not think of keying my incoming strings in hashes as i was not sure of performance hit when doing an if(exists $storage{"String"})

I would like to be the most efficient as it is a Perl/Tk GUI showing real time functional tests which fail with a given signature.

So if it is not efficient the GUI faces some slowness even though i fork it off..

Hi rjohn1,

Are you really only expecting a total of 200000 unique strings across all runs of the program? Or is it 200000 different strings per run of the program? If it's the former, then sure, you could write a function that maps those 200000 strings to unique numbers. But if it's the latter, then remember that any algorithm you write has to handle all possible inputs across all runs of the program, and in that case 32 bits to represent them may no longer be enough, depending on your input.

Anyway, all of this is very theoretical, including worrying about efficiency - I'd recommend that, knowing that Perl's hashes are already pretty fast, try writing some code. Not only will you then be able to say definitely whether the code runs too slow for your purposes or not, you'll have a baseline that you can compare any optimizations you make against. Optimization is not a matter of feeling, it's more of a science - measure the performance of the code to find which parts are running slow, try an optimization on that part of the code, measure to see if it made a difference, and so on. Of course there is some basic knowledge necessary, like for example knowing that hash lookups will outperform grep {$_ eq $what} @array or knowing what the Schwartzian transform is, but too much worrying also costs precious time :-)

Regards,
-- Hauke D

Perl hashes are built in to Perl. They are implemented in carefully written and optimized C, so they run very fast. An algorithm you write in Perl will run on the Perl virtual machine, so will automatically run slower compared to the equivalent C code.

Of course, you could use Inline::C and code your algorithm in C with in your Perl program, but using Perl's hashes will be a lot easier.

Indeed, you can use hashing for your string, and then compare by hash-value. If the hash result does not match, that means that stings does not match too; but it hash matches, the full comparison for strings should be performed

You don't have to use cryptography hashes (i.e. MD, SHA), I can recommend you to use Digest::MurmurHash

If the hash table is like: $hash{"String"}=1;, then if there is a hash collision, Perl compares the strings. All you need to know is if the string's key exists or is defined. Leave the "1" value out of the test, just look at the key. Different strings can indeed hash to the same hash value (which means hash "bucket number"). So a bucket can have more than one string/value pair.

At one time, I knew the hash doubling algorithm, but I've forgotten and it also periodically changes. But when "too many" strings hash to the same bucket, Perl will increase the hash size to make more buckets and spread things out more. This all happens automatically and is fast.

You are completely right: all the hash complexities are handled by perl. I've mention that to let the author of the original question got an impression, how it works, and, implement his own logic, if the standard hashes aren't enough for him.

BTW, does perl caches the string hash value? I.e. is the following approach:

my $index = $hash->{$string};
...
my $value1 = $array1->[$index];
my $value2 = $array2->[$index];
...
my $valueN = $arrayN->[$index];
[download]

comparing to the following approach:

my $value1 = $hash1->{$string};
my $value2 = $hash2->{$string};
...
my $valueN = $hashN->{$string};
[download]

I.e. I know that number of keys is fixed and isn't changed at runtime, so, I sort them, and store their order in hash, and then in future I always use arrays to store/retrieve values associated with string.

Is the first approach faster than the second?

WBR, basiliscos.

Thanks Bascillios and Marshall. I will check the string as hash key approach

Honestly speaking i did not think of keying my incoming strings in hashes as i was not sure of performance hit when doing an if(exists $storage{"String"}), as if we can generate a unique number from String and then   if(exists $storage{uniq number}) should be obviously faster the searching a big string as hash key. But anyways i will try it out

In other words: you're looking for a way to enumerate a bag of strings.

As far as algorithms go, (Minimal) Perfect Hashing can do it. However. Those mappings typically involve lookups in two or three tables i.e. random memory accesses, whereas straightforward hashing needs just one. So going via enumeration will probably cost you 4x compared to simple hash lookup.

When it comes to hashing, there are various complicated monstrosities out there — such as dense maps — that serve a particular purpose (trading speed for compactness). Speed-wise, you can't beat the traditional hash.

Less than 200000 They grow in number form 0 to 200000 over a period of time