From: Robert Klemme <shortcutter@...>
Date: 2008-01-03T01:24:59+09:00
Subject: Re: using reg expr with array.index

On 02.01.2008 13:45, Esmail wrote:
> Good morning!
> 
> Robert Klemme wrote:
>>
>>> I could scan the file once to determine which sequences are duplicates
>>> and then process the file a 2nd time eliminating those. In fact that was
>>> my first approach, but then Jordan's suggestions were so much cleaner
>>> and simpler that I went with them. My file aren't very large but it's
>>> good to have some other approaches in mind.
>>
>> If the volume of data is always so that it will fit into memory (and 
>> if you think about it, it *has* to be in memory for the duplicate 
>> detection).  
> 
> Actually, while it is easier this way, I don't think it has to be
> all in memory at once. The two step procedure above would work too
> I believe.
> 
> I.e., first do the equivalent of a grep for > and identify and
> store the duplicate headers this way.

I thought you needed the whole sequence to detect duplicates.  If you 
can do it on headers only then that's probably also good.

> Then re-read the file, line by line and stop copying input to
> output file when one of the duplicate headers is read, until
> the next legitimate header is found.

You could even store file offsets along with headers from the first 
reading pass.  That way you can faster skip duplicates during the second 
pass.

> Not perhaps the most efficient method, but it would work with
> any size file regardless of RAM since it essentially works on
> a line-by-line basis.

Well, it would work with significantly larger files.  "Any size" is a 
dangerous term - what do you do if there are 2^40 headers in there? :-) 
  But I guess in those cases you would rather resort to using some kind 
of hashing anyway.

>> Then I'd probably write a class (or find a class somewhere, probably 
>> in RAA) 
> 
> Ah .. thanks for the pointer to RAA, I just googled it and
> hadn't come across it before. It looks like a useful resource.

Definitively is.

>> that will represent a sequence and have proper comparison methods 
>> (#==, #eql?, #hash etc.).  
> 
> The equivalent of compareTo in Java right, yes, that would make
> a lot of sense, though again, for this simple script a simple
> string comparison of the header is all that's needed.

No, #== and #eql? are like Java's equals(), #hash is like Java's 
hashCode().  Java's compareTo() is in Ruby called #<=>.  Please also 
look at module Comparable which will give you all the other comparison 
operators for free.

>> That way you can even use a Hash for fast duplicate checks.  And you 
>> might even be able to internally represent those sequences with less 
>> memory (compressed, encoded or whatever suits you best).  For example, 
>> since you just need two bits to represent one element of the sequence 
>> you can achieve compression of factor 4 easily by not using a char per 
>> entry but just two bits.
> 
> Neat, you are right, there are lots of ways to work this.

Yep, and I'd add that this is what makes SE so interesting.  There are 
often so many solutions and a slight variation of the requirements and 
preconditions can make another solution much better than the one you 
had.  As we say so often "it all depends"... :-)

Kind regards

	robert