[Israel.pm] sliding window on streaming lines

Shlomo Yona shlomo at cs.haifa.ac.il
Sat Jun 5 21:12:42 PDT 2004

On Sun, 6 Jun 2004, Gaal Yahas wrote:

> Emphasizing the input suggested that's where you were looking for help.
> I didn't say so in my reply so far, but I don't think you can do much
> better than holding $N clusters in memory at any given moment. (My
> implementation actually holds at most $N+1, but at some expense of
> clarity that is fixable.) (Well, you could play seek games on the file
> if you were desperate, but that sucks.[1])

Yes. Keeping the clusters in a window in memory is probably
inevitable, still as long as $N is a lot smaller than the
number of clusters in the input, this is not so bad.



Getting all the necessary data of a window in memory is done
pretty much as you described it last night. However, the
real challange, I think, is attending "all possible *paths*
of strings in a given window". 

My current strategy is going over all possible paths using
a DFS or BFS style algorithm. I'll post the code on the
mailing list as soon as I'm convinced it's correct. I was
hoping to see other approaches/implementations in order to
get inspired to further increase the clarity of my own code.

Shlomo Yona
shlomo at cs.haifa.ac.il

More information about the Perl mailing list