Array ist nicht Array?!?: Was ist eigentlich ein Array in Perl? (Seite 2) (Allgemeines zu Perl)

[thread]7866[/thread]

Array ist nicht Array?!?: Was ist eigentlich ein Array in Perl? (Seite 2)

Leser: 1

ptk

2006-04-07 23:08

User since
2003-11-28
3645 Artikel
ModeratorIn
[default_avatar]

[quote=highlander,07.04.2006, 17:05]

Quote

Wenn du auf Element 500 zugreifen willst, kannst du das einfach mit $array[499] tun, da musst du nichts durchlaufen.

Es gibt kein Unterschied zwieschen Arrays und Listen in Perl
Wenn du @array[499] schreibst dann durchlauft er (PERL) von 0->1->2->......->499

Obwohl ich kann mich irren. Ich bin doch nur ein neuling in Perl[/quote]
Du irrst dich. Intern werden bei Perl ganz normale Arrays verwendet. Funktionen wie push oder splice lassen es vielleicht aussehen lassen, als ob es sich um Listen handelt. Aber intern muss, falls kein Platz mehr vorhanden ist, das gesamte Array umkopiert werden (bei einer echten Liste ist das nie notwendig).

lichtkind

2006-04-08 00:39

User since
2004-03-22
5701 Artikel
ModeratorIn + EditorIn

ptk hat recht auch wenn in perl arrays einiges mehr an speicher nehmen als in c sind es keine verketteten listen sondern der zugriff auf eine zelle ist direkt\n\n

Tutorien in der Wiki, mein zeug:
kephra, baumhaus, garten, gezwitscher

Es beginnt immer mit einer Entscheidung.

highlander

2006-04-08 01:46

User since
2006-04-07
5 Artikel
BenutzerIn
[default_avatar]

Dumme Frage, was meinst du mit "pack" (nicht vergessen ich bin neu in Perl)

Quote
............dolle verschlüsselung sein wird schau dir wirklich pack an es ist wirklich geschwindigkeitsoptimiert oder du nimmst xor mit einem grösseren schlüssel.

lichtkind

2006-04-08 02:42

User since
2004-03-22
5701 Artikel
ModeratorIn + EditorIn

schon aber ich sagte dir perdoc -f pack und dort wird dir erklärt wie man da viele bytes auf einmal umformen kann wie gesagt xor ist die andere möglichkeit( einfache $ergebnis = $sring xor $schlüssel, aufpassen mit den längen.). ausserdem würde ich ganz zu begin $datei = shift; schreiben, so brauchst du nicht die ganze zeit $_[0] schreiben und der code wird einiges lesbarer. oder my ($input_file, $output_file) = @ARGV; dann fürde ich benchmark nehmen und das script von dir wird dann so klein das du keine extra subroutinen für jeden schritt brauchst auch die riesen kommentarkästen sind doch etwas überdimensioniert. es macht viel aus so viel wie möglich code überblicken zu können.\n\n

Tutorien in der Wiki, mein zeug:
kephra, baumhaus, garten, gezwitscher

Es beginnt immer mit einer Entscheidung.

murphy

2006-04-08 04:21

User since
2004-07-19
1776 Artikel
HausmeisterIn

[quote=ptk,07.04.2006, 20:08][...] Aber intern muss, falls kein Platz mehr vorhanden ist, das gesamte Array umkopiert werden (bei einer echten Liste ist das nie notwendig).[/quote]
Ja, das kann passieren. Kommt es sehr auf die Performance an, kann man die aber die Größe des Arrays, bevor man zum Beispiel viele einzelne Elemente einfügt, festlegen indem man $#array eine Zahl zuweist.

When C++ is your hammer, every problem looks like your thumb.

sid burn

2006-04-09 17:58

User since
2006-03-29
1520 Artikel
BenutzerIn

user image

[quote=murphy,08.April.2006, 02:21][quote=ptk,07.04.2006, 20:08][...] Aber intern muss, falls kein Platz mehr vorhanden ist, das gesamte Array umkopiert werden (bei einer echten Liste ist das nie notwendig).[/quote]
Ja, das kann passieren. Kommt es sehr auf die Performance an, kann man die aber die Größe des Arrays, bevor man zum Beispiel viele einzelne Elemente einfügt, festlegen indem man $#array eine Zahl zuweist.[/quote]
Dazu hätte ich dann mal eine Frage.

Wenn ich also die Größe mit "$#array = xxx" nicht festlege, und ich ein push ausführe, dann müsste doch rein theoretisch für jedes weitere push das array umkopiert werden, und die größe um eins erhöht werden? Wenn ich das mit 3Mio. Elementen mache dann sollte man doch einen deutlichen Performance unterschied Merken.

Hierzu habe ich dann also paar Tests gemacht. Mein Skript sah erstmal folgendermaßen aus.

Code: (dl )

#!/usr/bin/perl -w

use Time::HiRes 'time';

$string = "x" x 3_000_000;
my @array;
#$#array = 3_000_010;

$start = time();
@array = split( //, $string );
$end = time();

printf "Die Zeit Betrug %lf Sekunden\n", $end - $start;
printf "Das Array hat %d Eintraege\n", scalar @array;

Ich initialisiere einen String der 3 Mio. 'x'e enthält, und schiebe danach jedes x in einem array hinein.

Als ich das so ausführte gab das bei mir ca. 3,3 Sekunden laufzeit. Und das Array ist 3 Mio. Eintraege groß.

Danach habe ich die Grenze mit "$#array" auskommentiert. Das Ergebnis ist wieder 3.3 Sekunden. Und 3 Mio. Eintraege. Aber eigentlich müssten doch 3Mio+10 Eintraege vorhanden sein? So dachte ich mir das jedenfalls. Anscheind wird bei einer direkt zuweisung die maximal Größe des Arrays wieder gelöscht, und dann neu zugewiesen. Eigentlich ja logisch, wäre ja blöd wenn ich bei einer direkten zuweisung noch Werte aus der vorherigen zuweisung noch im array hätte. Hier bringt also eine Zuweisung mittels "$#..." nichts.

Danach habe ich dann anstatt einer direkten Zuweisung ein push genommen. Jedoch habe ich erstmal die zuweisung der maximalen größe "$#..." weg gelassen.

Dafür habe ich dann anstatt er Zuweisung folgende Zeile geschrieben.

Code: (dl )

push @array, split( //, $string );

Anscheind ist ein push schneller. Hier bekomme ich 2.7 Sekunden laufzeit heraus.

Danach habe ich die Maximale größe mittels "$#..." gesetzt. Das Ergebnis ist das es wieder 2.7 Sekunden sind. Allerdings ist das Array jetzt 6Mio.+11 Eintraege groß.

Mit "$#..." setzte ich anscheind die Größe. Allerdings zeigt ein Pointer wohl auf diese Stelle. Und ein Push benutzt anscheind diesen Pointer und hängt dann an dieser Position etwas an. Allerdings weiß ich nicht wie ich bei Perl den Pointer wieder auf der ersten Stelle setze? Vielleicht kann mir das einer sagen?

Allerdings wäre die Verwendung von "push" ja dann unsinnig. Es würde ja nichts mehr am Array anhängen.

Also ein normales setzen von "$#..." bringt eigentlich nichts. Den mit einer Zuweisung wird das Array komplett neu erstellt. Die maximale größe wird also überschrieben. Und mit einem Push hängt man ja wie gesagt nur etwas an. Man vergößert dann das array nochmals. Also müsste hier eigentlich auch wieder das gesamte Array umkopiert werden.

Da ich dann aber schon 6Mio. Eintrage habe die umkopiert werden. Müsste doch eigentlich eine Zuweisung schneller sein. Denn bei einer Zuweisung muss ich ja immer nur 3 Mio. Eintrage umkopieren. Bei einen Push muss ich dann immer 3Mio. Eintrage plus jeden Schleifendurchlauf einen Wert mehr umkopieren, bis zum Ende 6 Mio. Werte. Die zeit bleibt aber trotzdem auf 2.7 Sekunden. Von daher sieht es nicht so aus, dass etwas umkopiert werden muss.

Das einzige was etwas bringen könnte wäre wenn man die Größe festlegt und dann in einer Schleife jedes element neu setzt.

Also habe ich folgendes geschrieben

Code: (dl )

use Time::HiRes 'time';

my @array;
#$#array = 3_000_010;

$start = time();
for( 1 .. 3_000_000 )
{
    $array[$_] = 'x';
}
$end = time();

printf "Die Zeit Betrug %lf Sekunden\n", $end - $start;
printf "Das Array hat %d Eintraege\n", scalar @array;

Die Laufzeit beträgt hier 1.8 Sekunden bei mir. Allerdings macht es bei mir keinen Unterschied ob ich nun vorher die maximale Größe mittels "$#..." gesetzt habe, oder nicht.

Für mich sieht das jedenfalls aus, als wenn das Arrays doch nicht jedesmal neu umkopiert werden muss? Und es sieht eher wie ein Listenverhalten aus.

Klärt mich auf! ^^
Oder habe ich gerade einen Denkfehler?\n\n

Nicht mehr aktiv. Bei Kontakt: ICQ: 404181669 E-Mail: perl@david-raab.de

murphy

2006-04-09 19:40

User since
2004-07-19
1776 Artikel
HausmeisterIn

- Selbst wenn das Array zunächst leer ist und du eine Menge Elemente mit push anfügst muss das Array nicht jedesmal kopiert werden, denn zum einen wird das Array vermutlich sinnvollerweise exponentiell vergrößert (also jedesmal, wenn das Ding voll ist, multipliziert man den reservierten Platz mit einem konstanten Faktor) und zum anderen ist der Speicherallokator des Systemes oder von Perl gewiss so ausgelegt, dass er Speicherblöcke bis zu einem gewissen Grad vergrößern kann, ohne zu kopieren.

- es gibt in Perl keinen "Pointer", der angibt, an welcher Stelle im Array etwas eingefügt werden soll, wenn man push benutzt. push hängt immer hinten an und unshift immer vorne.

- Eine Zuweisung zu $#array macht in der Tat zusammen mit push oder unshift wenig Sinn. Zusammen mit einer Zuweisung im Listenkontext noch weniger.

Ich habe bei mir mal folgendes Benchmark laufen lassen:

Code: (dl )

use strict;
use warnings;

use Benchmark qw/cmpthese/;

my $runs = 1024;
my $elts = 1024;

sub getsome {
    return 0 .. $elts-1;
}

cmpthese(
    $runs,
    {
        'push $' => sub {
            my @ray = ();
            push @ray, $_ for (0 .. $elts-1);
        },
        'push @' => sub {
            my @ray = ();
            push @ray, getsome();
        },
        'assign $' => sub {
            my @ray = ();
            $ray[$_] = $_ for (0 .. $elts-1);
        },
        'assign @' => sub {
            my @ray = getsome();
        },
        'p assign $' => sub {
            my @ray = ();
            $#ray = $elts + $[ - 1;
            $ray[$_] = $_ for (0 .. $elts-1);
        }
    });

Und das Resultat sieht so aus:
Rate p assign $ assign $ push $ push @ assign @ p assign $ 1014/s -- -4% -12% -29% -30% assign $ 1056/s 4% -- -8% -26% -27% push $ 1151/s 13% 9% -- -19% -20% push @ 1422/s 40% 35% 24% -- -1% assign @ 1442/s 42% 37% 25% 1% --

Das entspricht nicht so recht deinen Ergebnissen aber eher meinen Erwartungen (deine Messungen sind vielleicht nicht so gut vergleichbar, weil du immer noch die Zeit misst, die Split benötigt um den String auseinanderzunehmen).

Ich hätte allerdings gedacht, dass die Präallokation das ganze nicht noch verlangsamen sollte -- vielleicht spielt da noch Overhead von der Referenzzählung hinein, wenn man die Arrayelemente neu beschreibt.

When C++ is your hammer, every problem looks like your thumb.

sid burn

2006-04-09 21:26

User since
2006-03-29
1520 Artikel
BenutzerIn

user image

Hmm,
entweder verstehen wir uns Falsch, oder ich verstehe dich nicht richtig. Ich glaube eher letzteres ^^

Ich selber wollte nicht Testen welche Methode schneller ist um ein Array zu füllen, sondern ob es wirklich stimmt das es sich hier um ein Array und nicht um eine Liste handelt.

Es wurde ja gesagt das bei verwendung bei einem Array das ganze Array hin und her kopiert werden muss. Es kostet also letztendlich Performance. Das es jetzt nicht bei jedem push passiert, und das die größe Exponentiel steigt ist Interessant, sollte aber nichts an der Tatsache ändern, das dass Kopieren trotzdem passiert und es Zeit kostet.

Daher habe ich deine Aussage genommen, dass man mit "$#var = xxx" Die größe schon vorher festlegen kann, und danach ein umkopieren nicht mehr nötigt ist.

Von daher muss es ja so sein, dass wenn ich diese Methode anwende, es aufjedenfall schneller ist, als wenn ich das nicht Benutze. Den wenn ich diese Zeile nicht Benutze, muss das Array beim hinzufügen öfters mal vergrößert werden, was letztendlich Zeit kostet.

Am anfang habe ich eine Zuweisung und ein push genommen. Da hat sich aber schnell herausgetsellt das "$#..." logischerweise darauf keine Auswirkung hat.

Nur ein Direkter Zugriff über den index Wert dürfte letztendlich schneller sein, vor allem sollte es dann schneller sein, wenn ich die maximale größe des Arrays vorher festgelegt habe, und das array an sich schon im Speicher liegt, nur noch mit inhalten gefüllt werden muss. Damit ich auch wirklich sicher gehen kann das das Arrays öfters mal hin und her kopiert wird, und nicht zufällig so viel Speicher an einem Stück im RAM frei ist, habe ich das Arrays etwas größer gewählt.

Das Array ist nun 20Mio Eintraege groß, und im jeden wird ein 50Byte String gespeichert. Dadadurch kommt man nur durch die Strings auf einem Speicherverbrauch von ~953MB.

Ich besitze 1GB Ram und meine Swap Partition ist ebenfalls 1GB groß. Für den Speicher das mein System verbraucht + Zusätzlichen Verwaltungsaufwand den perl benötigt sollte allerdings mehr als 953MB Speicher verbraucht werden. Vor allem wird es mit dem Umkopieren zu ende hin schwer, da unter umständen gar nicht mehr so viel Speicher zur verfügung steht.

Wenn ich also vorher die Größe mit "$#..." festlege, dann sollte das wohl letztendlich deutlich schneller sein. Allerdings sollte das erzeugen des Arrays etwas dauern. Diese Zeit wird aber nicht mit eingerechnet.

Insgesamt bringt das Ergebnis aber einem zum Grübeln. Wenn ich vorher "$#..." benutze, dauert das auffüllen des Arrays ca. 45sek. beim Auffüllen sollte er kein einziges mal das Array umkopieren, da das Array ja immer groß genug ist.

Lasse ich "$#..." weg, dann sollte es ja eigentlich langsamer sein, da er ja letztendlich öfters mal umkopieren muss. Allerdings wenn ich es weg lasse, dann ist das letztere Schneller. Im Schnitt brauche ich nur 38sek.

Hier mein Code:

Code: (dl )

#!/usr/bin/perl -w
use Time::HiRes 'time';

my @array;
#$#array = 20_000_010;


$start = time();
  for( 1 .. 20_000_000 )
  {
      $array[$_] = 'x' x 50;
  }
$end = time();

printf "Die Zeit Betrug %lf Sekunden\n", $end - $start;
printf "Das Array hat %d Eintraege\n", scalar @array;

Von daher stellt sich nicht die Frage ob nicht doch Listen benutzt werden? Vielleicht ja auch ein Misch aus Liste & Array.

ich weiß es nicht.\n\n

Nicht mehr aktiv. Bei Kontakt: ICQ: 404181669 E-Mail: perl@david-raab.de

lichtkind

2006-04-09 21:42

User since
2004-03-22
5701 Artikel
ModeratorIn + EditorIn

die autorität heisst nicholas clark aber soweit ich mal die perl5 internals überflogen hab sind das alles seltsame structs mit vielen queverweisen. ich nehme an ein perl array ist ein echter erray aus diesen structs und wenn man neue brauch werden ein paar neue gemacht (nicht jedesmal). umkopiert wird das ganze nur wenn der speicherbereich generell zu klein für erweiterungen wird. wobei ich das selber nicht verstehe fa neue elemente je irgendwo im speicher gebildet werden können und man ja dann zeiger drauf legen kann.

Tutorien in der Wiki, mein zeug:
kephra, baumhaus, garten, gezwitscher

Es beginnt immer mit einer Entscheidung.

sid burn

2006-04-09 22:07

User since
2006-03-29
1520 Artikel
BenutzerIn

user image

[quote=lichtkind,09.April.2006, 19:42]die autorität heisst nicholas clark aber soweit ich mal die perl5 internals überflogen hab sind das alles seltsame structs mit vielen queverweisen. ich nehme an ein perl array ist ein echter erray aus diesen structs und wenn man neue brauch werden ein paar neue gemacht (nicht jedesmal). umkopiert wird das ganze nur wenn der speicherbereich generell zu klein für erweiterungen wird. wobei ich das selber nicht verstehe fa neue elemente je irgendwo im speicher gebildet werden können und man ja dann zeiger drauf legen kann.[/quote]
Genau so hatte ich mir das gedacht.
Anscheind ist ein Perl Array keine richtige Liste. Es muss also nicht jedes Element durchlaufen werden, um zu Element 500 zu kommen.

Allerdings ist es anscheind auch kein richtiges Array. Also das, dass Array an einer Speicherstelle beginnt, und man dann die Speicherstellen dazu addieren kann, um Element 1, Element 2 etc. zu bekommen.

Anscheind hat man ein Array, dass die unterschiedlichen Speicherstellen der unterschiedlichen Elemente enthält. Greift man auf Element 500 wird auf eine Speicherstelle verwiesen die auf einer Struktur zeigt, wo sich der Inhalt befindet.

Letztendlich wird beim vergößern des Arrays dann nur die tabelle mit den Speicherorten neu angelegt, und umkopiert. Aber nicht die Inhalte des Arrays.

Rein theoretisch ist es auch unmöglich das ein Perl Array ein echtes Array ist. Den bei einem echten Array muss jedes Element gleich groß sein, wenn das nicht der Fall ist könnte ich ja nie von der Ursprungsadresse ausgehen, und dann bestimmte Bytes hochzählen um zum nächsten Element zu kommen. Ich weiß ja nie wie groß das nächste Element ist.

Aber bei Perl ist es ja gerade nicht der Fall das jedes Element gleich groß ist. Ich kann ja ein String beliebiger größe mit Zahlen mischen wie ich Lustig bin.

Vielleicht sollte man auch einfach Perl vertrauen das alles gut und schnell geht, und sich keine größere Gedanken darüber machen. Immerhin Programmieren wir mit Perl und nicht mit C, damit wir uns nicht mit solchen Sachen befassen müssen. *g*\n\n

Nicht mehr aktiv. Bei Kontakt: ICQ: 404181669 E-Mail: perl@david-raab.de

View all threads created 2006-04-07 17:02.