Opened by flowdy at 2012-08-03 22:56
User since
2012-08-03
45 Artikel
BenutzerIn
2012-08-03
45 Artikel
BenutzerIn
Hallo ihr,
ich habe eine potenziell große bis sehr große Anzahl von booleschen Werten aus einer Liste von vielleicht noch mehr Werten auf ihren Wahrheitswert zu prüfen und abhängig davon eine Zahl um $x zu erhöhen bzw. zu verringern. Leider kann ich dazu meines Wissens nur seriell vorgehen, da jedes Bit mit dem davor geXORt und dementsprechend weiterverarbeitet werden muss, nämlich so:
Zwei Varianten sehe ich, die leider ausgerechnet bei meiner Suche nach einem guten Kompromiss zwischen Speicher- und Recheneffizienz die beiden Extreme bilden:
Das Array ist also zwei bis drei mal schneller als der Bitvektor, theoretisch fünfmal, wenn man die Slice in ein eigenes Array kopiert, was aber wieder, eben durch das Kopieren, konterkariert wird.
Ich tendiere zum Bitvektor, obwohl der langsamer ist. Die Ergebnisse werden ja in einem Integerarray aggregiert und gecacht (s. XOR-Weiche oben). Dieses Array wird neuberechnet nur nach Änderungen am / Neuerstellungen des Bitvektors, oder nach Änderungen an $start und $end. Da beide vom Nutzer mittels der Modul-API angestoßen wird, münden meine Optimierungsgedanken an dieser Stelle in bloße Spekulation.
Mehr spaßeshalber fällt mir ein, dass die Menschheit eines Tages mehr Zeit als Rohstoffe für Rechnerboliden bzw. die sie herstellenden Maschinen haben wird ... :D Die Frage ist jedoch eher, ob es dann noch Perl(5) gibt.
Sind meine Gedanken zur Optimierung meines Algorithmus soweit korrekt oder irre ich mich irgendwo? Fällt euch etwas ein, was ungefähr in der Mitte zwischen Array und Bitvektor rangiert und evtl. sogar die XOR-Weiche mit einschließt?
Viele Grüße,
Flowdy
Last edited: 2012-08-03 23:00:16 +0200 (CEST)
ich habe eine potenziell große bis sehr große Anzahl von booleschen Werten aus einer Liste von vielleicht noch mehr Werten auf ihren Wahrheitswert zu prüfen und abhängig davon eine Zahl um $x zu erhöhen bzw. zu verringern. Leider kann ich dazu meines Wissens nur seriell vorgehen, da jedes Bit mit dem davor geXORt und dementsprechend weiterverarbeitet werden muss, nämlich so:
Code: (dl
)
1
2
3
$x = $bit ? $val : -$val;
if ($bit xor $last_bit) { push @returned, $x }
else { $returned[-1] += $x }
Zwei Varianten sehe ich, die leider ausgerechnet bei meiner Suche nach einem guten Kompromiss zwischen Speicher- und Recheneffizienz die beiden Extreme bilden:
- Die Iteration über ein einfaches Perl-Array. Ein Skalar belegt meines Wissens 12 Byte. Macht bei einer Array-Länge von sagen wir 1_000_000 Elementen, also 12 MB +/-, die bei Arrayexpansionen im Speicher ggf. umzukopieren sind. 1 bedeutungstragenden Bit stehen also 95 sinnlos reservierten Bits gegenüber. Dafür ist ein Array schnell beim Indexzugriff.
- Bit::Vector. Komprimiert das ganze bis an die maschinentechnische Grenze in Maschinenworte, d.h. das ganze belegt dann nur 122 KB, also das Hundertstel. Und wär auch rasend schnell, wenn nur nicht die Bits einzeln getestet werden müssten, jeweils mit einem Subroutinenaufruf, der an CPU-Zyklen wieder recht teuer ist.:
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
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% --
Das Array ist also zwei bis drei mal schneller als der Bitvektor, theoretisch fünfmal, wenn man die Slice in ein eigenes Array kopiert, was aber wieder, eben durch das Kopieren, konterkariert wird.
Ich tendiere zum Bitvektor, obwohl der langsamer ist. Die Ergebnisse werden ja in einem Integerarray aggregiert und gecacht (s. XOR-Weiche oben). Dieses Array wird neuberechnet nur nach Änderungen am / Neuerstellungen des Bitvektors, oder nach Änderungen an $start und $end. Da beide vom Nutzer mittels der Modul-API angestoßen wird, münden meine Optimierungsgedanken an dieser Stelle in bloße Spekulation.
Mehr spaßeshalber fällt mir ein, dass die Menschheit eines Tages mehr Zeit als Rohstoffe für Rechnerboliden bzw. die sie herstellenden Maschinen haben wird ... :D Die Frage ist jedoch eher, ob es dann noch Perl(5) gibt.
Sind meine Gedanken zur Optimierung meines Algorithmus soweit korrekt oder irre ich mich irgendwo? Fällt euch etwas ein, was ungefähr in der Mitte zwischen Array und Bitvektor rangiert und evtl. sogar die XOR-Weiche mit einschließt?
Viele Grüße,
Flowdy
Last edited: 2012-08-03 23:00:16 +0200 (CEST)
package MyClass; sub new {\b\b\b\b\b\b\b\b\buse Moose;