Opened by flowdy at 2012-08-03 22:56
User since
2012-08-03
45 Artikel
BenutzerIn
2012-08-03
45 Artikel
BenutzerIn
Hi,
habe deine Vorschläge in die Benchmarks index und bitvx einfließen lassen, topegs Vorschlag von weiter unten in strng verwurstet. Die Ergebnisse lassen mir eigentlich nur die Wahl zwischen bitvr und slice, je nachdem, ob ich stärkeres Gewicht auf Speicher- oder Recheneffizienz lege, oder?
Generiert mit folgendem
Last edited: 2012-08-04 15:46:29 +0200 (CEST)
habe deine Vorschläge in die Benchmarks index und bitvx einfließen lassen, topegs Vorschlag von weiter unten in strng verwurstet. Die Ergebnisse lassen mir eigentlich nur die Wahl zwischen bitvr und slice, je nachdem, ob ich stärkeres Gewicht auf Speicher- oder Recheneffizienz lege, oder?
Code: (dl
)
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% --
Generiert mit folgendem
Code: (dl
)
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;
}
},
}
);
Last edited: 2012-08-04 15:46:29 +0200 (CEST)
package MyClass; sub new {\b\b\b\b\b\b\b\b\buse Moose;