Jemand zu Hause?![[twitter]](/battie/theme/default/icons/twitter.gif){kind=icon}
![[gelöst]](/battie/theme/default/icons/tick.png "gelöst"){kind=icon}
Leser: 19
+15 replies
1
2
3
$x = $bit ? $val : -$val;
if ($bit xor $last_bit) { push @returned, $x }
else { $returned[-1] += $x }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
use strict;
use Benchmark 'cmpthese';
use Bit::Vector;
my @array = (!1) x 1_000_000;
my $vec = Bit::Vector->new(1_000_000);
# Perl optimiert nicht für Methodenaufrufe (s. Benchmark unten)
# Daher müssen wir das machen:
*test = $vec->can('bit_test');
# Die XOR-Weiche bleibe hier unberuecksichtigt
# Der gesuchte Kompromiss kann sie gerne beinhalten
my ($start,$end) = (0,999_999);
cmpthese(100, {
# über Array-Slice iterieren:
slice => sub { my $sum; $sum += $_ ? 1 : -1 for @array[$start..$end]; },
# vorher in ein eigenes Array kopieren, denn darüber wird schneller iteriert
array => sub {
my @array = @array[$start .. $end];
my $sum; $sum += $_ ? 1 : -1 for @array;
},
# Müssten wir stets über das ganze @array laufen, gäbs also weder @start noch @end:
theor => sub { my $sum; $sum += $_ ? 1 : -1 for @array; },
# Subroutinenaufruf an Bit::Vector, d.h. gecachter Methodenaufruf
bitvr => sub {
my $sum;
for ( my $i = $start; $i <= $end; $i++ ) {
$sum += test($vec,$i) ? 1 : -1;
}
},
# ungecacht:
bitvm => sub {
my $sum;
for ( my $i = $start; $i <= $end; $i++ ) {
$sum += $vec->bit_test($i) ? 1 : -1;
}
},
}
)
# Dies ist die Ausgabe:
#==============================
Rate bitvm bitvr array slice theor
bitvm 3.01/s -- -14% -43% -73% -84%
bitvr 3.51/s 17% -- -34% -68% -81%
array 5.29/s 76% 51% -- -52% -72%
slice 11.1/s 269% 217% 110% -- -41%
theor 18.8/s 524% 435% 255% 69% --
+7 replies![[default_avatar]](/battie/theme/default/default_avatar.gif){kind=avatar}
1
2
3
Schrift
use strict; use warnings;
Blog
Einstellungen![[feed]](/battie/theme/default/icons/feed.png){kind=icon}
mit_index => sub {
my $sum; for my $i ($start..$end) { $sum += $array[$i] ? 1 : -1 };
},
+6 replies
1
2
3
4
5
6
7
8
9
Rate bitvx strng bitvm bitvr array index slice theor
bitvx 1.37/s -- -6% -17% -20% -26% -43% -66% -72%
strng 1.45/s 6% -- -12% -15% -22% -40% -64% -71%
bitvm 1.65/s 21% 14% -- -3% -11% -31% -59% -67%
bitvr 1.70/s 24% 17% 3% -- -8% -29% -57% -66%
array 1.85/s 36% 28% 12% 9% -- -23% -53% -63%
index 2.40/s 76% 66% 46% 42% 30% -- -40% -52%
slice 3.97/s 191% 174% 141% 134% 115% 65% -- -20%
theor 4.96/s 263% 242% 201% 192% 168% 107% 25% --
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
use strict;
use Benchmark 'cmpthese';
use Bit::Vector;
# Länge % 8 == 0 trifft nicht immer zu, hier aber der Einfachkeit halber ang.
my $length = 1_000_000;
# Das Bitmuster hat direkt Einfluss darauf, wie oft ein neuer Wert an @cache
# angehängt und wie oft $cache[-1] erhöht bzw. verringert wird.
# Wir kennen es nicht, da es durch den Nutzer (mittelbar) festgelegt wird.
# Die von rand erzeugte 0<>1-Wechselfrequenz ist eigentlich viel zu groß,
# aber wollen wir uns mal nicht verkünsteln ...
my @array = map { split '', unpack 'B*', pack('C', int rand(256)) }
1 .. $length/8;
# Vorschlag von topeg++. Der Umweg über $bin_data ist mE unnötig.
# Zwar bräuchte das ähnlich wenig Speicher wie ein Bitvektor, aber da er bei
# jedem Funktionsaufruf neu aufgeblasen werden muss, nützt uns das nicht viel.
# So sparen wir uns wenigstens die Verwaltungsinformationen des Arrays und
# von 999.999 Skalaren
my $str_data = join '', @array;
my $vec = Bit::Vector->new_Bin(1_000_000, $str_data);
# Vorschlag von raubtier++: GeXOR'ter Kovektor
my $vex = $vec->Clone;
$vex->shift_left(!$vec->lsb);
$vex->ExclusiveOr($vex,$vec);
# Perl optimiert nicht für Methodenaufrufe (s. Benchmark unten)
# Daher müssen wir das machen:
*test = $vec->can('bit_test');
my ($start,$end) = (0,999_999);
cmpthese(100, {
# über Array-Slice iterieren:
slice => sub {
my (@cache, $last);
for (@array[$start..$end]) {
if ($_ xor $last // !$_) { push @cache, $_ ? 1 : -1 }
else { $cache[-1] += $_ }
$last = $_;
}
},
index => sub {
my (@cache,$last);
for ( my $i = $start; $i <= $end; $i++ ) {
my $v = $array[$i];
if ($v xor $last // !$v) { push @cache, $v ? 1 : -1 }
else { $cache[-1] += $v }
$last = $v;
}
},
# vorher in ein eigenes Array kopieren, denn darüber wird schneller iteriert:
array => sub {
my @array = @array[$start .. $end];
my (@cache,$last);
for ( @array ) {
if ($_ xor $last // !$_) { push @cache, $_ ? 1 : -1 }
else { $cache[-1] += $_ }
$last = $_;
}
},
# Müssten wir stets über das ganze @array laufen, gäbs also weder @start noch @end:
theor => sub {
# my @array = @array[$start .. $end];
my (@cache, $last);
for (@array) {
if ($_ xor $last // !$_) { push @cache, $_ ? 1 : -1 }
else { $cache[-1] += $_ }
$last = $_;
}
},
# Subroutinenaufruf an Bit::Vector, d.h. gecachter Methodenaufruf:
bitvr => sub {
my (@cache, $last);
for ( my $i = $start; $i <= $end; $i++ ) {
my $v = test($vec,$i);
if ($v xor $last // !$v) { push @cache, $v ? 1 : -1 }
else { $cache[-1] += $v }
$last = $v;
}
},
# ungecacht:
bitvm => sub {
my (@cache, $last);
for ( my $i = $start; $i <= $end; $i++ ) {
my $v = $vec->bit_test($i);
if ($v xor $last // !$v) { push @cache, $v ? 1 : -1 }
else { $cache[-1] += $v }
$last = $v;
}
},
# Test gegen XOR'd Covektor, Vorschlag von raubtier++ ($vex-Init. oben):
bitvx => sub {
my (@cache, $last);
for ( my $i = $start; $i <= $end; $i++ ) {
my $v = test($vec,$i);
if (test($vex,$i)) { push @cache, $v ? 1 : -1 }
else { $cache[-1] += $v }
# $last = $v; -- EDIT
}
},
# Sparen wir uns die Strukturdaten des Arrays und von 999.999 Skalaren
# Vorschlag von topeg++, angeglichen. $bit_data-Initialisierung oben.
strng => sub {
my (@cache, $last);
for ( my $i = $start; $i <= $end; $i++ ) {
my $v = substr($str_data,$_,1);
if (test($vex,$i)) { push @cache, $v ? 1 : -1 }
else { $cache[-1] += $v }
$last = $v;
}
},
}
);
+5 replies
1 2 3 4 5 6 7 8 9 10 11
# Sparen wir uns die Strukturdaten des Arrays und von 999.999 Skalaren # Vorschlag von topeg++, angeglichen. $bit_data-Initialisierung oben. strng => sub { my ($last,@cache)=(0); for ( my $i = $start; $i <= $end; $i++ ) { my $v = substr($str_data,$i,1); if ($v xor $last // !$v) { push @cache, $v ? 1 : -1 } else { $cache[-1] += $v } $last = $v; } },
+4 replies
+3 replies
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
my $data=''; $data.=pack('C', int rand(256)) for(0..$length/8); #... vectr => sub { my ($last,@cache)=(0); for ( my $i = $start; $i <= $end; $i++ ) { my $v = vec($data,$i,1); if ($v xor $last // !$v) { push @cache, $v ? 1 : -1 } else { $cache[-1] += $v } $last = $v; } },
1
2
3
4
5
6
7
8
9
10
s/iter bitvx bitvm array bitvr strng index vectr slice theor
bitvx 1.98 -- -22% -23% -25% -36% -47% -53% -62% -69%
bitvm 1.55 27% -- -2% -5% -18% -32% -41% -51% -60%
array 1.53 29% 2% -- -3% -17% -31% -40% -51% -59%
bitvr 1.48 34% 5% 3% -- -14% -28% -38% -49% -58%
strng 1.27 55% 22% 20% 16% -- -17% -28% -41% -51%
index 1.06 87% 47% 44% 40% 20% -- -13% -29% -41%
vectr 0.922 115% 69% 66% 60% 38% 15% -- -18% -33%
slice 0.757 162% 105% 102% 95% 68% 40% 22% -- -18%
theor 0.620 219% 150% 147% 138% 105% 71% 49% 22% --
+7 replies
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
#!/usr/bin/perl use strict; use warnings; my $bits=1_000_000; my $val=42; my $bin_data=''; for(my $i=0; $i<$bits; $i+=8) { $bin_data.=pack('C',int(rand(256))); } my @returned; my $str_data=unpack('B*',$bin_data); my ($x,$bit,$last_bit,$val_neg)=(0,0,0,-$val); for(0..length($str_data)-1) { $bit=substr($str_data,$_,1); $x = $bit ? $val : $val_neg; if($bit xor $last_bit) { push @returned, $x } elsif(@returned==0) { push @returned, $x } else { $returned[-1] += $x } $last_bit=$bit; } print @returned+0,"\n";
+6 replies
+5 replies
+4 replies
2012-08-04T13:40:46 topeg"substr" ist nur ein klein wenig langsamer als ein Array für Bitwerte kann es durchaus etwas bringen.
2012-08-04T13:40:46 topegWeiterhin alles was du außerhalb der Schleife initalisieren kannst "my", kostet keine Zeit in der Schleife. das betrifft auch das "$v". In der schleife definiert wird die varable am ende der Schleife zerstört und dann am Anfang neu eingerichtet (speicherallokation etc.)
1
2
3
4
5
6
7
8
9
Rate bitvx bitvm bitvr array strng index slice theor
bitvx 1.43/s -- -16% -20% -23% -38% -46% -65% -72%
bitvm 1.71/s 20% -- -4% -8% -26% -36% -58% -66%
bitvr 1.79/s 25% 5% -- -4% -22% -33% -56% -65%
array 1.86/s 30% 8% 4% -- -20% -30% -54% -63%
strng 2.31/s 61% 35% 29% 24% -- -13% -43% -54%
index 2.67/s 86% 56% 49% 44% 16% -- -34% -47%
slice 4.07/s 184% 138% 127% 119% 76% 53% -- -20%
theor 5.06/s 253% 195% 182% 172% 119% 90% 24% --
+3 replies
1 2
if ($v ne $last || $v eq '0') { push @cache, $v eq '1' ? 1 : -1 } elsif($v eq '1') { $cache[-1] ++ }
+2 replies
1
2
3
4
5
6
7
8
9
Rate bitvx bitvm bitvr array strng index slice theor
bitvx 1.45/s -- -15% -20% -22% -37% -43% -64% -71%
bitvm 1.70/s 18% -- -5% -8% -26% -33% -58% -66%
bitvr 1.80/s 25% 6% -- -3% -21% -29% -55% -64%
array 1.85/s 28% 9% 3% -- -19% -27% -54% -63%
strng 2.30/s 59% 35% 27% 24% -- -10% -43% -55%
index 2.55/s 76% 49% 41% 38% 11% -- -37% -50%
slice 4.03/s 178% 136% 124% 118% 76% 58% -- -20%
theor 5.06/s 250% 197% 181% 173% 121% 99% 26% --
1 2 3 4 5 6 7 8 9 10 11 12 13
# Sparen wir uns die Strukturdaten des Arrays und von 999.999 Skalaren # Vorschlag von topeg++, angeglichen. $bit_data-Initialisierung oben. strng => sub { my (@cache, $last, $v); for ( my $i = $start; $i <= $end; $i++ ) { $v = substr($str_data,$_,1); if ($v ne $last || $v eq '0') { push @cache, $v eq '1' ? 1 : -1 } else { $cache[-1] += $v } $last = $v; } },
![[Powered by Battie]](/battie/img/powered.png)
