CGI/Perl Guide | Learning Center | Forums | Advertise | Login
Site Search: in

  Main Index MAIN
INDEX
Search Posts SEARCH
POSTS
Who's Online WHO'S
ONLINE
Log in LOG
IN

Home: Perl Programming Help: Beginner:
check if two strings are permutations

 



orange
User

Mar 3, 2017, 12:38 AM

Post #1 of 4 (3550 views)
check if two strings are permutations Can't Post

I need to compare two strings, say:

$a="line1\nline2\nline3"
$b="line3\nline2\nline1"

so that order of lines is ignored.
what would be fast way to do it?
thank you.


Laurent_R
Veteran / Moderator

Mar 3, 2017, 4:36 AM

Post #2 of 4 (3538 views)
Re: [orange] check if two strings are permutations [In reply to] Can't Post

Usually, the easiest (and very often fastest) way to check whether two pieces of data are permutation of each other (of whether strings are palindromes), is to sort the individual data items of both data inputs and to check whether they compare equal.


BillKSmith
Veteran

Mar 3, 2017, 5:34 AM

Post #3 of 4 (3535 views)
Re: [orange] check if two strings are permutations [In reply to] Can't Post

It probably is not possible to recognize the fastest way to do anything. It of course is possible to compare alternate approaches. This is what benchmark does. Below, I propose two solutions to your problem and compare them. (Laurent outlined the first while I was preparing this post.)


Code
use strict; 
use warnings;
use Test::Simple tests => 2;
use List::MoreUtils qw(all);

sub compare_via_sort {
my ($string_a, $string_b) = @_;
my @arry_a = split /\n/, $string_a;
my @arry_b = split /\n/, $string_b;
$string_a = join "\n", sort @arry_a;
$string_b = join "\n", sort @arry_b;
return $string_a eq $string_b;
}

sub compare_via_hash {
my ($string_a, $string_b) = @_;
my %hash_a;
$hash_a{$_} = 1 foreach split( /\n/, $string_a);
return scalar all {defined $hash_a{$_}} split( /\n/, $string_b);
}


our $string_a="line1\nline2\nline3";
our $string_b="line3\nline2\nline1";
ok( compare_via_sort($string_a, $string_b), 'sort_compare');
ok( compare_via_hash($string_a, $string_b), 'hash_compare');

use Benchmark qw(cmpthese);

cmpthese 100000, {
sort => my $ans_sort = 'compare_via_sort($string_a, $string_b)',
hash => my $ans_hash = 'compare_via_hash($string_a, $string_b)',
}
OUTPUT:
1..2
ok 1 - sort_compare
ok 2 - hash_compare
Rate hash sort
hash 90171/s -- -56%
sort 206186/s 129% --


The results show that both approaches work correctly (at least for this test case). The sort approach is more than twice as fast as the hash approach. Results will be different with real data.
Good Luck,
Bill


orange
User

Mar 3, 2017, 5:44 AM

Post #4 of 4 (3534 views)
Re: [BillKSmith] check if two strings are permutations [In reply to] Can't Post

great, thank you all very much.

 
 


Search for (options) Powered by Gossamer Forum v.1.2.0

Web Applications & Managed Hosting Powered by Gossamer Threads
Visit our Mailing List Archives