[26152] in Perl-Users-Digest
Perl-Users Digest, Issue: 8343 Volume: 10
daemon@ATHENA.MIT.EDU (Perl-Users Digest)
Sun Aug 21 06:05:35 2005
Date: Sun, 21 Aug 2005 03:05:04 -0700 (PDT)
From: Perl-Users Digest <Perl-Users-Request@ruby.OCE.ORST.EDU>
To: Perl-Users@ruby.OCE.ORST.EDU (Perl-Users Digest)
Perl-Users Digest Sun, 21 Aug 2005 Volume: 10 Number: 8343
Today's topics:
Re: how to read file from sub-directories and do an ave <a@cuhk.edu.hk>
Re: how to read file from sub-directories and do an ave <a@cuhk.edu.hk>
Re: Organizing data for readability and efficiency xhoster@gmail.com
Re: Semi OT: Correction about Perl Funcs: ment index no <vtatila@mail.student.oulu.fi>
Semi OT: Uniquely Identifying Substrings for an Elem in <vtatila@mail.student.oulu.fi>
Re: Semi OT: Uniquely Identifying Substrings for an Ele xhoster@gmail.com
Re: Semi OT: Uniquely Identifying Substrings for an Ele <tassilo.von.parseval@rwth-aachen.de>
Digest Administrivia (Last modified: 6 Apr 01) (Perl-Users-Digest Admin)
----------------------------------------------------------------------
Date: Sun, 21 Aug 2005 11:40:16 +0800
From: "Ross" <a@cuhk.edu.hk>
Subject: Re: how to read file from sub-directories and do an average?
Message-Id: <de8t1f$318u$1@justice.itsc.cuhk.edu.hk>
"Tad McClellan" <tadmc@augustmail.com> wrote in message
news:slrndgeb7l.39j.tadmc@magna.augustmail.com...
> Ross <a@cuhk.edu.hk> wrote:
>
>> $curdir = `pwd`;
>> chop $curdir;
>
>
> You should not use chop() to remove newlines.
>
> You should use chomp() to remove newlines.
>
Thanks for letting me know there is a better (in a sense that's what i want)
function.
------------------------------
Date: Sun, 21 Aug 2005 12:34:12 +0800
From: "Ross" <a@cuhk.edu.hk>
Subject: Re: how to read file from sub-directories and do an average?
Message-Id: <de906k$6g$1@justice.itsc.cuhk.edu.hk>
Is there any built-in function/parameters in Perl not to take . and .. into
account when opening all the subdirectories?
When i run the code:
the error appears:
unable to open dir named /home/sunlab/AAA/Reb/rawdat/4601-4.SMP No such file
or directory at <the absolute path for this perl>/SMP2XLSAVG2.pl line 42
<the absolute path for this perl> is replaced by me.
indeed when ls -al rawdat
drwxr-xr-x 2 sunlab 4096 Aug 21 12:25 4601-4.SMP/
I've tried both the with and without slash at the end versions.
------------------------------
Date: 21 Aug 2005 05:10:34 GMT
From: xhoster@gmail.com
Subject: Re: Organizing data for readability and efficiency
Message-Id: <20050821011034.232$Hb@newsreader.com>
Mark Seger <Mark.Seger@hp.com> wrote:
> Anno Siegel wrote:
> > Mark Seger <Mark.Seger@hp.com> wrote in comp.lang.perl.misc:
> >
> > You appear to be obsessed with efficiency. You even wrote me in
> > private about it, but I want to keep it on Usenet, I won't reply.
> >
> > At this stage of programming, efficiency is no concern of yours. The
> > point to begin worrying about efficiency is when you have a correct and
> > working program and it turns out to be slow, not before.
>
> I'm afraid I have to strongly disagree with.
I'm afraid I have to agree with you. The problem is that bad programmers
take this type of advice as an excuse to implement the first dumb thing
that pops into their head, like using an quadratic (or even exponential)
algorithm for a problem which obiously has the potential to get large, when
there is an obvious linear algorithm which just as simple or even simpler.
Good programmers intuitively wouldn't consider doing something like that in
the first place, so don't consider it to fall under the label of
"optimization". That's why I try to distinguish between micro-optimization
and macro-optimization.
> I've known far to many
> programmers who simply 'get it running' and then try to make it
> efficient. Sometimes this cannot be done without an entire
> redesign/rewrite,
If that is the case, then I doubt obsessing over performance of isolated
components from the start would have helped. If you write large brittle
programs that can't be changed without being entirely rewritten, speed is
probably the least of your concerns.
> perhaps one of the best examples of this is database
> design in which your table organization is plan ineficient.
I've seen plenty of schema designs that could not be made efficient, but
I've never seen one whose *only* problem was that it could not be made
efficient. The ones that couldn't be made to work were just bad in
general, not only for speed reasons.
>
> > Also I fully agree with Xho's take that the organization of your data
> > is unlikely to have a noticeable effect on the runtime.
>
> again I have to disagree. perhaps I could have stated my question about
> how the internals of arrays vs hashes are organized but I really didn't
> want to go there. When I think of an array I think of adding and index
> to a pointer to get the the cell you desire.
Perl is not C.
> When I think of a hash I
> think of having to do some sort of lookup which seems like more overhead
> to me.
Yes, there is. If there is absolutely no non-performance reason to prefer
one over the other (which is pretty hard to believe) then go with the
array. The chances of this materially affecting anything are small.
Given your emphasis on the size of this dataset, I'd be far more worried
about memory efficiency than staight CPU efficiency. Once you start heavy
swapping, you can kiss your speed good-bye.
Xho
--
-------------------- http://NewsReader.Com/ --------------------
Usenet Newsgroup Service $9.95/Month 30GB
------------------------------
Date: Sun, 21 Aug 2005 02:26:34 +0300
From: "Veli-Pekka Tätilä" <vtatila@mail.student.oulu.fi>
Subject: Re: Semi OT: Correction about Perl Funcs: ment index not substr
Message-Id: <de8e7d$l7k$1@news.oulu.fi>
Hi again,
First mistake spotted. When talking about the perl functions I naturally
ment index rather than substr. I think this does come down to my English
skills and the semantics. Sub string means any part of a larger original
string. yet the substr function won't tell if a given substring is found but
rather extracts a substring based on character indeces. Maybe the names
cutString, piece or contains would be more descriptive. Well, my bad as
usual.
PS: Please reply to my original message in most cases. If someone wants to
discuss Perl's naming further, do at least change the subject.
With kind regards Veli-Pekka Tätilä (vtatila@mail.student.oulu.fi)
Accessibility, game music, synthesizers and programming:
http://www.student.oulu.fi/~vtatila/
------------------------------
Date: Sun, 21 Aug 2005 02:05:36 +0300
From: "Veli-Pekka Tätilä" <vtatila@mail.student.oulu.fi>
Subject: Semi OT: Uniquely Identifying Substrings for an Elem in a Set: substr, Sets and Complexity
Message-Id: <de8d02$l0b$1@news.oulu.fi>
Hi,
Here's a text processing problem that came to mind based on finding a
certain set of sub strings. As I came up with this one on my own
incidentally, I don't know any real good words for Googling useful
information or solutions to the problem and thought I'd ask here then,
having seen a number of basic string processing threads during my short-time
presence.
The Problem:
Suppose we have a set S of character strings. Each string in the set is
unique (well sets are), may be of arbitrary length and is composed of some
known alphabet (e.g. a to z). The task is to write a function that takes an
element E in S and returns all sub strings of E that uniquely identify E in
S. Put another way, all the returned strings are sub strings of E but they
may *not* be sub strings of any other element in S.
Some Thoughts:
Upon closer inspection, I also found out that the set of sub strings may
contain an element that is equal to E if E differs from some other string in
S by only one character. In that case, E as a whole is the only substring
identifying E.
Now, I must confess the problem is not inherently related to Perl in any way
thus the Semi OT tag in the subject-line. Perl would be the language of
choice for implementation personally, however, and thus some questions about
that, too.
There are bound to be better methods than the obvious brute-force tac of
trying everything. Howabout the string matching, is substr the way to go or
am I better off trying to hack regular expressions to do the job? If I'm
aiming at low temporal complexity, what would be the worst case complexity
for this problem? Surely not O(n). Performance is not an issue but I'm just
curious and not guru enough in math or computer science to figure it out
myself.
I'm certain the solution is relatively simple. I didn't find anything that
useful in the Perl Cookbook. The problem is not exactly a straight
intersection, difference etc... of two arrays but rather the set will
include elements that are not directly in the array being processed, though
they are based on an element of the array.
Motivation:
By the way, the thing that got me into pondering this problem in the first
place is somewhat related. I was writing a real crude mini-shell for a
textmode app of mine and in one command the user had to choose a very long
element (voice name) from a long list. To make the process easier, I allowed
selection based on a partial match provided that only one element contained
the sub string in question. Otherwise the matching elements would be listed.
Then I started to think if I could generate all the strings that select a
given element programatically, read lazily, and here's this post you're
reading.
PS: I had a hard time titling this post appropriately. Feel free to change
the subject to something more descriptive.
--
With kind regards Veli-Pekka Tätilä (vtatila@mail.student.oulu.fi)
Accessibility, game music, synthesizers and programming:
http://www.student.oulu.fi/~vtatila/
------------------------------
Date: 20 Aug 2005 23:42:24 GMT
From: xhoster@gmail.com
Subject: Re: Semi OT: Uniquely Identifying Substrings for an Elem in a Set: substr, Sets and Complexity
Message-Id: <20050820194224.342$ZT@newsreader.com>
"Veli-Pekka Tätilä" <vtatila@mail.student.oulu.fi> wrote:
> Hi,
> Here's a text processing problem that came to mind based on finding a
> certain set of sub strings. As I came up with this one on my own
> incidentally, I don't know any real good words for Googling useful
> information or solutions to the problem and thought I'd ask here then,
> having seen a number of basic string processing threads during my
> short-time presence.
>
> The Problem:
>
> Suppose we have a set S of character strings. Each string in the set is
> unique (well sets are), may be of arbitrary length and is composed of
> some known alphabet (e.g. a to z). The task is to write a function that
> takes an element E in S and returns all sub strings of E that uniquely
> identify E in S. Put another way, all the returned strings are sub
> strings of E but they may *not* be sub strings of any other element in S.
This was discussed here two months ago, and someone claimed Text::Ngrams
was the/a solution. I don't whether it actually is or not, but you may
want to look up the original thread.
> Upon closer inspection, I also found out that the set of sub strings may
> contain an element that is equal to E if E differs from some other string
> in S by only one character. In that case, E as a whole is the only
> substring identifying E.
What if E itself is a substring of some other element of S? Then not even
E as a whole identifies E!
Xho
--
-------------------- http://NewsReader.Com/ --------------------
Usenet Newsgroup Service $9.95/Month 30GB
------------------------------
Date: Sun, 21 Aug 2005 08:38:33 +0200
From: "Tassilo v. Parseval" <tassilo.von.parseval@rwth-aachen.de>
Subject: Re: Semi OT: Uniquely Identifying Substrings for an Elem in a Set: substr, Sets and Complexity
Message-Id: <slrndgg8b9.qn.tassilo.von.parseval@localhost.localdomain>
Also sprach Veli-Pekka Tätilä:
> Hi,
> Here's a text processing problem that came to mind based on finding a
> certain set of sub strings. As I came up with this one on my own
> incidentally, I don't know any real good words for Googling useful
> information or solutions to the problem and thought I'd ask here then,
> having seen a number of basic string processing threads during my short-time
> presence.
>
> The Problem:
>
> Suppose we have a set S of character strings. Each string in the set is
> unique (well sets are), may be of arbitrary length and is composed of some
> known alphabet (e.g. a to z). The task is to write a function that takes an
> element E in S and returns all sub strings of E that uniquely identify E in
> S. Put another way, all the returned strings are sub strings of E but they
> may *not* be sub strings of any other element in S.
>
> Some Thoughts:
>
> Upon closer inspection, I also found out that the set of sub strings may
> contain an element that is equal to E if E differs from some other string in
> S by only one character. In that case, E as a whole is the only substring
> identifying E.
>
> Now, I must confess the problem is not inherently related to Perl in any way
> thus the Semi OT tag in the subject-line. Perl would be the language of
> choice for implementation personally, however, and thus some questions about
> that, too.
>
> There are bound to be better methods than the obvious brute-force tac of
> trying everything. Howabout the string matching, is substr the way to go or
> am I better off trying to hack regular expressions to do the job? If I'm
> aiming at low temporal complexity, what would be the worst case complexity
> for this problem? Surely not O(n). Performance is not an issue but I'm just
> curious and not guru enough in math or computer science to figure it out
> myself.
With a set of $n words, I would assume the complexity of a brute-force
approach to be
O( $n * ($n-1) * ($avg * ($avg-1) / 2) )
where $avg is the average word length, the term ($avg * ($avg-1) / 2)
being the number of substrings for an average word and ($n-1) the number
of words to test each substring against. As the average number of
substrings doesn't depend on the size of the set, it can be assumed to
be some constant in which case the algorithm is in O($n**2) for all
words and subsequently O($n) for retrieving the unique substrings for
one word.
Note that the question whether to use a pattern match or index() or
whatever doesn't really change the algorithm. In the one below I used
index() but could have done it just as easily using a pattern match.
Here's an implementation of such a brute-force algorithm which gave me
the opportunity to make use of Eric J. Roode's Iterator module recently
uploaded to the CPAN:
#!/usr/bin/perl -w
use strict;
use Iterator;
use List::MoreUtils qw/all/;
chomp( my @words = <DATA> );
for (@words) {
print "Unique ids for $_:\n ";
print join ", ", uniq_id($_, \@words);
print "\n";
}
sub uniq_id {
my ($word, $set) = @_;
my $iter = do {
my ($len, $off) = (1, 0);
my $i = Iterator->new(
sub {
Iterator::is_done() if $len > length $word;
my $sub = substr $word, $off++, $len;
($len, $off) = ($len + 1, 0)
if $off + $len > length $word;
return $sub;
}
);
$i;
};
my @ids;
while ($iter->isnt_exhausted) {
my $pat = $iter->value;
push @ids, $pat
if all { index($_, $pat) == -1 } grep { $_ ne $word } @$set;
}
return @ids;
}
__DATA__
abc
bcd
foobar
foo
bar
pearl
perl
modperl
One optimization immediately springs to my mind (unfortunately after
I've written the above):
The iterator returns the substrings in ascending order length-wise.
However, it's always so that if there is no unique substring of length
$m, there cannot possibly be one of $m-1. Therefore, have the iterator
return the substrings in descending order and rewrite the 'all { } grep
{ } @$set' condition into a real loop that exits early as soon as none
of the substrings of a given length are unique.
This does not really change the complexity of the algorithm as it only
makes the constant ($avg * ($avg-1) / 2) smaller. For small sets though
this constant is the dominant parameter.
> Motivation:
>
> By the way, the thing that got me into pondering this problem in the first
> place is somewhat related. I was writing a real crude mini-shell for a
> textmode app of mine and in one command the user had to choose a very long
> element (voice name) from a long list. To make the process easier, I allowed
> selection based on a partial match provided that only one element contained
> the sub string in question. Otherwise the matching elements would be listed.
> Then I started to think if I could generate all the strings that select a
> given element programatically, read lazily, and here's this post you're
> reading.
Something like TAB-completion offered by many shells? That would
decrease the complexity somewhat as you'd only have to test substrings
with offset zero (that is, at the beginning of the word).
> PS: I had a hard time titling this post appropriately. Feel free to change
> the subject to something more descriptive.
Your Subject was fine. You can't normally squeeze the whole content of a
posting into the Subject. If that was possible, postings wouldn't need a
body and we'd all communicate here by exchanging Subjects. :-)
Tassilo
--
use bigint;
$n=71423350343770280161397026330337371139054411854220053437565440;
$m=-8,;;$_=$n&(0xff)<<$m,,$_>>=$m,,print+chr,,while(($m+=8)<=200);
------------------------------
Date: 6 Apr 2001 21:33:47 GMT (Last modified)
From: Perl-Users-Request@ruby.oce.orst.edu (Perl-Users-Digest Admin)
Subject: Digest Administrivia (Last modified: 6 Apr 01)
Message-Id: <null>
Administrivia:
#The Perl-Users Digest is a retransmission of the USENET newsgroup
#comp.lang.perl.misc. For subscription or unsubscription requests, send
#the single line:
#
# subscribe perl-users
#or:
# unsubscribe perl-users
#
#to almanac@ruby.oce.orst.edu.
NOTE: due to the current flood of worm email banging on ruby, the smtp
server on ruby has been shut off until further notice.
To submit articles to comp.lang.perl.announce, send your article to
clpa@perl.com.
#To request back copies (available for a week or so), send your request
#to almanac@ruby.oce.orst.edu with the command "send perl-users x.y",
#where x is the volume number and y is the issue number.
#For other requests pertaining to the digest, send mail to
#perl-users-request@ruby.oce.orst.edu. Do not waste your time or mine
#sending perl questions to the -request address, I don't have time to
#answer them even if I did know the answer.
------------------------------
End of Perl-Users Digest V10 Issue 8343
***************************************
