Mark Dilger said: >If you know the state space, such as [0..255], you can use an array instead >of a hash
After thinking about this some more, I realized that using an array assumes that you have integer data in a continuous range. In real-world data, this might not be the case. Even data from an A/D would probably be converted back to "real" values (instead of just 0..255) using a calibration curve or lookup table. So you might have 0=0, 1=3.14, 2=78.67, etc. Keeping everything in a hash means you don't need to know anything about the data except that there are a discrete number of values (but you don't care what those values are). Anyway, I'm doing h2xs, writing a test script, etc. to get this ready for CPAN. I'll use Statistics::Descriptive::Discrete unless I hear a better idea. Regards, --Rhet ----Original Message Follows---- From: "Rhet Turnbull" <[EMAIL PROTECTED]> To: [EMAIL PROTECTED] Subject: Re: Naming advice: Statistics::Descriptive::Discretized? Date: Wed, 27 Feb 2002 19:28:32 +0000 Yes, I think I like Statistics::Descriptive::Discrete as well. Thanks for the idea about using an array -- I implemented something similar in 'C' once and for that I did use an array. I don't necessarily know the state space ahead of time since I don't know what kind of data the user is feeding me so I think I'll stick with a hash. Of course, the state space could be a parameter to new which places the burden on the user. However, even if you had a state space of [0..2^20-1], your data set might only have 10 discrete values in it. In that case you'd be unnecessarily carrying around a large array whereas the hash would not be larger than necessary. I may do some benchmarks though just to test it out. --Rhet ----Original Message Follows---- From: Mark Dilger <[EMAIL PROTECTED]> To: Rhet Turnbull <[EMAIL PROTECTED]>, [EMAIL PROTECTED] CC: [EMAIL PROTECTED] Subject: Re: Naming advice: Statistics::Descriptive::Discretized? Date: Wed, 27 Feb 2002 10:37:28 -0800 (PST) The term "discrete" is used to differentiate discrete from continuous variables, which is the distinction you are making if I understand correctly. I like Statistics::Descriptive::Discrete, if Statistics::Descriptive is where you are going to place this. On the matter of using a hash... If you know the state space, such as [0..255], you can use an array instead of a hash, initializing each element to zero (or treating undef appropriately when encountered). Array references can be blessed just as hash references can, and array lookups are a bit faster. Mark Dilger --- Rhet Turnbull <[EMAIL PROTECTED]> wrote: > Background > I use the full version > (Statistics::Descriptive::Full) of the > Statistics::Descriptive module quite a bit and it > works great. However, > because it stores a copy of all the data in an array > (and also needs to sort > this array), the module is quite slow for large > datasets (> 1 million data > values). I frequently use data sets of this size or > larger so I devised a > faster solution. > > My solution: > Since most of the data I need to analyze is the > output of satellite > telemetry it has all been through an analog to > digital conversion so there > are a known, discrete number of "levels" or > different values present in the > data. For example, an 8 bit value would only have > 2^8 possible values even > though there might be 3 million such data points in > my data set. I don't > know the proper name for data that has been > converted in such a way > (discretized? quantized?) hence request for naming > help. > > Instead of storing every value in an array, I only > store the particular > values I've seen as hash keys then store the number > of times I've seen each > value as the hash value. This lets me reconstruct > the original data set > (but not the original order) with very little > overhead -- particularly when > the number of discrete levels is small compared to > the total number of data > points. > > Performance: > The results are VERY good. For a real-world data > set using 2.6 million > 8-bit values, Statistics::Descriptive::Full took 561 > seconds to produce > results (min, max, mean, mode, median, standard > deviation, and frequency > distribution) and my module took 40 seconds to > produce the same results. > Futhermore, Statistics::Descriptive::Full required > 400MB of RAM and my > module required 3MB. Statistics::Descriptive::Full > scales somewhat > exponentially with number of data points whereas my > new module scales > linearly. > > Testing: > I've tested this module using quite a few data sets > and performance is very > good as long as the number of discrete levels in the > data is a fraction of > the total number of data points. Even with 2^20 > possible levels, this beats > Statistics::Descriptive::Full as long as the number > of data points is high. > > Naming: > Please note that this new module is NOT a > replacement for > Statistics::Descriptive (which is a very good, well > tested module) but it > does perform much better for certain data sets. So, > I think I should stay > in the Statistics::Descriptive namespace which is > why I propose something > like Statistics::Descriptive::Discrete or > Statistics::Descriptive::Quantized. Any ideas? > Also note that I've kept > the interface identical to Statistics::Descriptive > as much as possible so > this should be a drop-in replacement for most > purposes. > > More info: > I've attached some sample code that demos the module > (which is in a very > rough state at the moment). You can also read my > write-up over at > perlmonks.org: > http://www.perlmonks.org/index.pl?lastnode_id=9066&node_id=146691 > > Regards, > --Rhet Turnbull, RhetTbull_at_hotmail.com > > Code: > ### cut here ### > #!/usr/bin/perl > > use strict; > use warnings; > > my $stats = > Statistics::Descriptive::Discretized->new(); > > while(<>) > { > chomp; > $stats->add_data($_); > } > > print "count = ",$stats->count(),"\n"; > print "uniq = ",$stats->uniq(),"\n"; > print "sum = ",$stats->sum(),"\n"; > print "min = ",$stats->min(),"\n"; > print "max = ",$stats->max(),"\n"; > print "mean = ",$stats->mean(),"\n"; > print "standard_deviation = > ",$stats->standard_deviation(),"\n"; > print "variance = ",$stats->variance(),"\n"; > print "sample_range = ",$stats->sample_range(),"\n"; > print "mode = ",$stats->mode(),"\n"; > print "median = ",$stats->median(),"\n"; > > #my @data = $stats->get_data(); > #print "data = @data\n"; > > print "-"x80,"\n"; > my %histogram = $stats->frequency_distribution(8); > print "$_\t\t$histogram{$_}\n" foreach (sort {$a <=> > $b} keys %histogram); > > BEGIN > { > package Statistics::Descriptive::Discretized; > > ### This module draws heavily from > Statistics::Descriptive > > use strict; > use warnings; > use Carp; > use vars qw($VERSION $REVISION $AUTOLOAD $DEBUG > %autosubs); > > $VERSION = '0.1'; > $REVISION = '$Revision: 1.20 $'; > $DEBUG = 0; > > #what subs can be autoloaded? > %autosubs = ( > count => undef, > mean => undef, > sum => undef, > uniq => undef, > mode => undef, > median => undef, > min => undef, > max => undef, > standard_deviation => undef, > sample_range => undef, > variance => undef, > ); > > > sub new > { > my $proto = shift; > my $class = ref($proto) || $proto; > my $self = {}; > $self->{permitted} = \%autosubs; > $self->{data} = (); > $self->{dirty} = 1; #is the data dirty? > > bless ($self,$class); > print __PACKAGE__,"->new(",join(',',@_),")\n" if > $DEBUG; > return $self; > } > > sub add_data > { > #add data but don't compute ANY statistics yet > my $self = shift; > print __PACKAGE__,"->add_data(",join(',',@_),")\n" > if $DEBUG; > > #get each element and add 0 to force it be a number > #that way, 0.000 and 0 are treated the same > my $val = shift; > while (defined $val) > { > $val += 0; > $self->{data}{$val}++; > #set dirty flag so we know cached stats are > invalid > $self->{dirty}++; > $val = shift; #get next element > } > } > === message truncated === __________________________________________________ Do You Yahoo!? Yahoo! Greetings - Send FREE e-cards for every occasion! http://greetings.yahoo.com _________________________________________________________________ Send and receive Hotmail on your mobile device: http://mobile.msn.com _________________________________________________________________ Get your FREE download of MSN Explorer at http://explorer.msn.com/intl.asp.
