in reply to Re^3: Date Array Convolution
in thread Date Array Convolution

BrowserUK, get ready for the longest post ever.

First of all, the explanation has allowed me to actually understand what's going on in the code, thank you.

I have a couple last little questions for you, but first off, here is my current-ish code:

use strict; use warnings; #convert DDHHMM into int of m sub d2i { my( $d, $h, $m ) = unpack '(A2)*', $_[0]; return ( ( $d - 1 ) * 24 + $h ) * 60 + $m; } #convert int of m into DDHHMM sub i2d { sprintf "%02d%02d%02d", int($_[0]/1440)+1, int($_[0]/60)%24, $_[0] +%60; } #find and open files ... only ever 1 of each file type my ($d,$t); foreach (<*>) { $d = $_ if (/\.dat$/); $t = $_ if (/\.mrg$/); } open(D, $d) or die "Unable to open DAT file. Exiting.\n"; my @dl = <D +>; close(D); open(T, $t) or die "Unable to open MRG file. Exiting.\n"; my @tl = <T +>; close(T); #create big array of data points with added d2i my @big; foreach (@dl,@tl) { chomp($_); if (/^\/\d\d\d\d\d\d\//) { my @n = split(/\//); push @big,[$n[1],$n[2],$n[5],d2i($n[1]),d2i$n[2]]; } } #break by day if needed my @ex = map { my $s = $_->[3]; my $e = $_->[4]; my @out; while (int($s/1440) != int($e/1440)) { my $newe = ( int($s/1440) + 1) * 1440 - 1; push @out, [i2d($s),i2d($newe),$_->[2],$s,$newe]; $s = $newe + 1; } (@out, [i2d($s),$_->[1],$_->[2],$s,$e]); } @big; #build parallel arrays of minute and values ... total minimized for ov +erlaps my (@tally, @id); for my $e (0 .. $#ex) { my $r = $ex[$e]; for my $i ($r->[3] .. $r->[4] ) { if( !defined($tally[$i]) or $tally[$i] > $r->[2] ) { $tally[$i] = $r->[2]; $id[$i] = $e; } } } #recreate [DDHHMM,DDHHMM,V] with overarching tally and ids my @res; my $i = 0; while ($i < $#id) { ++$i until defined $id[$i]; my $id = $id[$i]; my $start = $i; ++$i while defined ($id[$i]) and $id[$i] == $id; my $end = $i - 1; push @res, [i2d($start),i2d($end),$tally[$start]]; } #output organized final to file open (C,'>CDA.txt'); my @last = ("","",""); print C "To do later: ... this still needs specific formatting work(ea +sy)\n"; foreach (@res) { if (substr($last[0],0,2) ne substr(@$_[0],0,2)) { print C "\n"; } print C "@$_[0] @$_[1] @$_[2]\n"; $last[0] = @$_[0]; } close(C); #[temporary] report comparison for manual check @big = sort {$a->[0] <=> $b->[0]} (@big); foreach (@big) { print "@$_[0] @$_[1] @$_[2]\n"; } print "\n"; foreach (@res) { print "@$_[0] @$_[1] @$_[2]\n"; }
This all works EXACTLY as intended.

A couple easy questions:
1) Does the map function assume an output format of @array, [1,2,3,4,5]? Why isn't it push @array, [1,2,3,4,5] ?
2) Fundamentally what is the difference bewteen $_[0] and $_->[0]? When I start replacing $e and some $s in the map with the array counterpart (either $_[x] or $_->[x]) things break. I understand that $s may or may not be modified and needs to be variablarized (I bet that's not a word), but why does it break for just pointing to $e's array location($_->[4])?
3) The tally method was quite clever :)

So now that the easy questions are done, I have some new questions ... and a warning: you might throw your arms up in exasperation.

So I've just realized that in my effort to simplify the task enough to ask for help, I made a very unfortunate assumption that has bad consequences for the code. I think I've fixed most of it but I have a couple little problems.

Essentially, the two digit date value in DDHHMMV represents day of month and has the potential to roll over halfway through a file. Also, toward the top of each input file is a line that identifies the period of time applicable to that file, for instance '/XXX/XXX/110000ZNOV/140000ZNOV/XXX/XXX' where the value is 'DDHHHHZMON'. The input files will only ever cover a few days at a time (3-10ish), so there is never an issue of which month the data is applicable to, as the date tag in the beginning identifies that. The potential problem I see is when different months rollover (ie, /XXX/XXX/300000ZSEP/030000ZOCT/XXX/XXX'), the day breaking map effectively increments forever.

Here's an example of an input file (only a couple important lines, the rest is nonsense I filled in to test parsing):
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa f sd fa sdfasdf /XXX/XXX/300000ZSEP/020000ZOCT/XXX/XXX a sdfasdfasdf asdf df sa fas dfASDFASDF AS DF ASDF SDFASDF /// //sdfasdf/123 \\ /asdfasdf adsf sdf// /555/234/ /301222/301232/234/4234/011.0/ /fasdfasd /301240/301250/asdf/fdsa/011.3/ /302340/302355/9j9js9j9j9jf9sjfd/9j9sfj9df9323/010.0/ /302359/010002/kfjakdjfakdfasdf/salkdjfaklsdjflkasjd/008.1/ /011200/011400/kfjakdjfakdfasdf/salkdjfaklsdjflkasjd/008.1/ asd /1/2/3/4/5 // /
As you can also see, there is no 'year' date tag in input files, so there is still an assumption being made about DEC->JAN rollovers too.

Here's my new code that almost fixes the problem:
use strict; use warnings; use Time::Local; #convert MMddhhmm into minutes since epoch (w/ leap year accounted for +) sub d2i { my( $mo, $d, $h, $m ) = unpack '(A2)*', $_[0]; my @temp = localtime(time); return int(timelocal(0,$m,$h,$d,$mo,$temp[4]) / 60); } #convert minutes since epoch into MMddhhmm (w/ leap year accounted for +) sub i2d { my @times = localtime($_[0]*60); sprintf "%02d%02d%02d%02d", $times[4], $times[3], $times[2], $time +s[1]; } #return month sub fmon { if ($_[0] =~ /JAN$/) {return "00"; } if ($_[0] =~ /FEB$/) {return "01"; } if ($_[0] =~ /MAR$/) {return "02"; } if ($_[0] =~ /APR$/) {return "03"; } if ($_[0] =~ /MAY$/) {return "04"; } if ($_[0] =~ /JUN$/) {return "05"; } if ($_[0] =~ /JUL$/) {return "06"; } if ($_[0] =~ /AUG$/) {return "07"; } if ($_[0] =~ /SEP$/) {return "08"; } if ($_[0] =~ /OCT$/) {return "09"; } if ($_[0] =~ /NOV$/) {return "10"; } if ($_[0] =~ /DEC$/) {return "11"; } } #find and open files ... only ever 1 of each file type my ($d,$t); foreach (<*>) { $d = $_ if (/\.dat$/); $t = $_ if (/\.mrg$/); } open(D, $d) or die "Unable to open DAT file. Exiting.\n"; my @dl = <D +>; close(D); open(T, $t) or die "Unable to open MRG file. Exiting.\n"; my @tl = <T +>; close(T); #create big array of data points with added d2i my (@big, $startmon, $stopmon);#@big format: [MMddhhmm,MMddhhmm,V,I,I] + where I is minutes from epoch foreach (@dl,@tl) { chomp($_); if (/^\/\w{3}\/\w{3}\/\d{6}/) { #find month values my @n = split(/\//); $startmon = fmon($n[3]); #cheating because start/s +top always preceeds values $stopmon = fmon($n[4]); } if (/^\/\d{6}\//) { #read in actual data my @n = split(/\//); #if ($startmon ne $stopmon && substr($n_[0],0,2) < 15) { # push @big,[$startmon.$n[1],$stopmon.$n[2],$n[5],d2i($star +tmon.$n[1]),d2i($stopmon.$n[2])]; #} push @big,[$startmon.$n[1],$stopmon.$n[2],$n[5],d2i($startmon. +$n[1]),d2i($stopmon.$n[2])]; } } #break by day if needed my @ex = map { my $s = $_->[3]; my $e = $_->[4]; my @out; while (int($s/1440) != int($e/1440)) { my $newe = ( int($s/1440) + 1) * 1440 - 1; push @out, [i2d($s),i2d($newe),$_->[2],$s,$newe]; $s = $newe + 1; } (@out, [i2d($s),$_->[1],$_->[2],$s,$e]); } @big; #build parallel arrays of minute and values ... total minimized for ov +erlaps my (@tally, @id); for my $e (0 .. $#ex) { my $r = $ex[$e]; for my $i ($r->[3] .. $r->[4] ) { if( !defined($tally[$i]) or $tally[$i] > $r->[2] ) { $tally[$i] = $r->[2]; $id[$i] = $e; } } } #recreate [MMddhhmm,MMddhhmm,V] with overarching tally and ids my @res; my $i = 0; while ($i < $#id) { ++$i until defined $id[$i]; my $id = $id[$i]; my $start = $i; ++$i while defined ($id[$i]) and $id[$i] == $id; my $end = $i - 1; push @res, [i2d($start),i2d($end),$tally[$start]]; } #output organized final to file open (C,'>CDA.txt'); my @last = ("","",""); print C "To do later: ... a lot of specific formatting work(easy)\n"; foreach (@res) { if (substr($last[0],0,2) ne substr(@$_[0],0,2)) { print C "\n"; } print C substr(@$_[0],2,6), " ", substr(@$_[1],2,6), " ", @$_[2], + "\n"; $last[0] = @$_[0]; } close(C); #[temporary] report comparison for manual check @big = sort {$a->[0] <=> $b->[0]} (@big); foreach (@big) { print "@$_[0] @$_[1] @$_[2]\n"; } print "\n"; foreach (@res) { print "@$_[0] @$_[1] @$_[2]\n"; }
The problems I am having are:
1) Making the assumption of 'current year', as when this rolls over it would mess up.
2) Breaking days apart doesn't seem to be working and I don't see why ... I'm just using minutes since epoch instead of minutes since start of month.
3) Wastes a lot of resources (maybe in #recreate loops, start counting at 100000000 instead of 0 or something?
4) The way the input files are implemented real world is typically from today-ish to 3-10 days in the future, so the assumption of current year is valid except for the last couple days of the year when the file spans after the rollover.

Sorry to be such a pain in the butt, and thank you again for your help. On the bright side, I think I figured a lot of it out!

-Alan

Replies are listed 'Best First'.
Re^5: Date Array Convolution
by BrowserUk (Patriarch) on Nov 07, 2011 at 14:26 UTC

    The tally method lent itself to your application because you identified your dates as being DDHHMM.

    This meant that an entire month period can be covered, using a granularity of minutes, by an array of 60*24*31=44,640 elements.

    If you needed to deal with a year at a time, then using a tally stick of 16,338,240 is still feasible -- especially if you move to using vec to store an array 8 or 16-bit ints to store your values. But the problem is that then the role-over from one month to the next is complicated by the fact that months have differing numbers of days.

    But trying to use the epoch (by which I assume you mean the *nix epoch of 1/1/1970) mean that the tally would have to be 653,529,600 elements long which is just silly. And will be even sillier if you are using the Windows epoch of 1/1/1600!

    If you really cannot break your data sets up into 1 month subsets, then you are going to have to go back to using the O(N^2) process of comparing every range with every other range in order to detect your overlaps, rather than using the O(N) method of the tally stick. This because once the set of ranges can span month and year boundaries you will need to handle all the messy details of data arithmetic. Variable length months and leap years etc.

    Essentially, whether you should move forward with the tally method or go over to using proper date math should depend entirely upon the frequency (therefore performance constraint) of having to perform your processing versus the difficulty in having to pre-filter your ranges into by-month subsets.

    If performance is important and the subsetting easy, then stick with the tally method and start of month offsets. If the subseting is hard and the performance requirement is low, then encode your dates using a proper date package and use full date arithmetic to detect your overlaps.


    With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    "Science is about questioning the status quo. Questioning authority".
    In the absence of evidence, opinion is indistinguishable from prejudice.
      This meant that an entire month period can be covered, using a granularity of minutes, by an array of 60*24*31=44,640 elements.
      In my solution, I only need the array of the size of 2 × the number of input ranges, because there can be no change in value if there is no start/end of a range.

        Cool! But you're comparing apples with oranges.

        Besides which, your solution contains bugs.

        Update:Dataset removed as it seems that PM cannot handle it. Despite that it appeared fine in preview.

        If you want the data set which I observed produces this incorrect output (note the second last range is invalid) I can email it to you.:

        C:\test>junk88 935755.dat [ ["010005", "010022", 41], ["010023", "012359", 0], ["020000", "022359", 0], ["030000", "032359", 0], ["040000", "042359", 0], ["050000", "052359", 0], ["060000", "062359", 0], ["070000", "072359", 0], ["080000", "082359", 0], ["090000", "092359", 0], [100000, 102359, 0], [110000, 112359, 0], [120000, 122359, 0], [130000, 132359, 0], [140000, 142359, 0], [150000, 152359, 0], [160000, 162359, 0], [170000, 172359, 0], [180000, 182359, 0], [190000, 192359, 0], [200000, 202359, 0], [210000, 212359, 0], [220000, 222359, 0], [230000, 232359, 0], [240000, 242359, 0], [250000, 252359, 0], [260000, 262359, 0], [270000, 272359, 0], [280000, 282359, 0], [290000, 292359, 0], [300000, 302359, 0], [310000, 312356, 0], [312357, 312356, 52], [312357, 312359, 27], ]

        Instead of this outptu:

        C:\test>935755 935755.dat [ ["010005", "010022", 41], ["010023", "012359", 0], ["020000", "022359", 0], ["030000", "032359", 0], ["040000", "042359", 0], ["050000", "052359", 0], ["060000", "062359", 0], ["070000", "072359", 0], ["080000", "082359", 0], ["090000", "092359", 0], [100000, 102359, 0], [110000, 112359, 0], [120000, 121942, 0], [121943, 122359, 0], [130000, 132359, 0], [140000, 142359, 0], [150000, 152359, 0], [160000, 162359, 0], [170000, 172359, 0], [180000, 182359, 0], [190000, 192359, 0], [200000, 202359, 0], [210000, 211659, 0], [211700, 211741, 0], [211742, 212359, 0], [220000, 222359, 0], [230000, 232359, 0], [240000, 242359, 0], [250000, 252359, 0], [260000, 262359, 0], [270000, 272359, 0], [280000, 282355, 0], [282356, 282359, 0], [290000, 292359, 0], [300000, 300936, 0], [300937, 302359, 0], [310000, 311315, 0], [311316, 312042, 0], [312043, 312159, 0], [312200, 312356, 0], [312357, 312359, 27], ]