PHP: Eintrag in Array einfügen! Meine Routine dazu:

[WarSlash]

Auftrag: Füge einen zusätzlichen Eintrag in das Array ein!

Kann man diesen Code noch vereinfachen? Mir fällt gerade nix ein. Ich habe das unterschwellige Gefühl, dass die Routine nicht optimal ist, aber vielleicht irre ich mich.

function array_additem($parray,$item,$id)
{
for ($i=0; $i < $id; $i++) {

$newarry[$i] = $parray[$i];

}

$newarry[$id] = $item;


$j = $id;

for ($i=$id+1; $i <=sizeOf($parray); $i++) {

$newarry[$i] = $parray[$j];
$j++;
}
return $newarry;

};

[Coda]

Es wäre nett eine Beschreibung davon zu haben was das Ding eigentlich machen soll.

[WarSlash]

Es wäre nett eine Beschreibung davon zu haben was das Ding eigentlich machen soll.

Haste meine Edit noch gelesen?
Die Routine soll einen neuen Eintrag {$item] in ein Array{$parray} hinter Stelle {$id} einfügen. Die alten Einträge vor der gewählten Stelle werden hinter das neues Element angefügt. Die Größe des Arrays wird dabei um 1 erhöht.

[darph]

Hier stand müll.

[Coda]

Haste meine Edit noch gelesen?
Einfach einfügen ist nunmal etwas anderes als an einer bestimmten Stelle.

Was du ändern könntest ist das du kein neues Array erstellst, sondern das bestehende änderst ab der Stelle wo du einfügst.

Ansonsten eignet sich als Datenstruktur mit denen du an beliebigen Stellen einfügen kannst eher z.B. eine Linked-List.

[darph]

function arr2($parray, $item, $id) {
$head = array_slice($parray, 0, $id);
$tail = array_slice($parray, $id, count($parray));

$head[$id] = $item;

return array_merge($head, $tail);
}

[WarSlash]

Einfach einfügen ist nunmal etwas anderes als an einer bestimmten Stelle.

Was du ändern könntest ist das du kein neues Array erstellst, sondern das bestehende änderst ab der Stelle wo du einfügst.

Ansonsten eignet sich als Datenstruktur mit denen du an beliebigen Stellen einfügen kannst eher z.B. eine Linked-List.

Danke! Man stimmt ja, sowas habe ich mal in Delphi geschrieben.

Und natürlich bestens Dank an darph!

[darph]

Na das ist interessant:

<?php
function array_additem($parray,$item,$id) {
for ($i = 0; $i < $id; $i++) {
$newarry[$i] = $parray[$i];
}

$newarry[$id] = $item;
$j = $id;
for ($i = $id + 1; $i <= sizeOf($parray); $i++) {
$newarry[$i] = $parray[$j];
$j++;
}
return $newarry;
}

function array_additem2($parray, $item, $id) {
$head = array_slice($parray, 0, $id);
$tail = array_slice($parray, $id, count($parray));

$head[$id] = $item;

return array_merge($head, $tail);
}

$parray = Array();
for ($i = 0; $i < 200000; $i++) {
$parray[] = $i;
}

$time_start = microtime(true);
$xa = array_additem($parray, 0, 1000);
$time_end = microtime(true);
$time = $time_end - $time_start;
echo("WarSlash: ".$time." seconds<br>");

$time_start2 = microtime(true);
$xb = array_additem2($parray, 0, 1000);
$time_end2 = microtime(true);
$time2 = $time_end2 - $time_start2;
echo("darph: ".$time2." seconds<br>");
?>

WarSlash: 0.148230075836 seconds
darph: 0.275879144669 seconds

array_slice() ist offenbar langsamer als das händische Rumkopieren jedes einzelnen Elements. :O Die ursprüngliche Lösung ist mal eben doppelt so schnell.

[Coda]

PHP is manchmal echt gnadenlos beschissen :biggrin:

[Sephiroth]

so muss nicht bei jedem neuen durchlauf der schleife am anfang bei der prüfung der schleifenbedingung die größe des arrays neu bestimmt werden.

function array_additem($parray,$item,$id)
{
for ($i=0; $i < $id; $i++)
{
$newarry[$i] = $parray[$i];
}

$newarry[$id] = $item;

for ($j=$id, $i=$id+1, $l=sizeOf($parray); $i <= $l; $i++, $j++)
{
$newarry[$i] = $parray[$j];
}

return $newarry;
}

das mit $j ist nur makulatur ;D

@darph: eventuell durch die zusätzlichen funktions-aufrufe.

[darph]

Ha! Die version ist dann doch noch etwas schneller:

function array_additem($parray, $item, $id) {
for ($i = count($parray) -1; $i >= $id; $i--) {
$parray[$i+1] = $parray[$i];
}
$parray[$id] = $item;
return $parray;
}

WarSlash: 0.149986028671 seconds
darph: 0.276751041412 seconds
darph2: 0.0920810699463 seconds
Sephi: 0.114814996719 seconds

Bei einem Array mit 200 000 Elementen.

[medi]

bringt es eigentlich was das count() noch mit aus der schleife rauszunehmen oder wird die startbedingung nur beim schleifeneinstieg betrachtet?

[Marscel]

bringt es eigentlich was das count() noch mit aus der schleife rauszunehmen oder wird die startbedingung nur beim schleifeneinstieg betrachtet?

Soweit ich weiß - ich machs zumindest nicht - wird count() bei jedem Durchgang aufgerufen, kostet also.

[Kinman]

Wen das count() beim Initialisieren der Schleife verwendet wird, dann nur einmal. Wenns jedoch in der Abbruchbedingung steht, natürlich jedesmal.

mfg Kinman

[Sephiroth-Gast]

Wen das count() beim Initialisieren der Schleife verwendet wird, dann nur einmal. Wenns jedoch in der Abbruchbedingung steht, natürlich jedesmal.

mfg Kinman
eben. das ist genau das was ich oben meinte.

So eine for-schleife sieht ja wie folgt aus:

startanweisungen
loop:
if (bedingung)
{
rumpf
endanweisungen
goto loop
}

code_nach_der_schleife

Daran wird deutlich, dass man a) mehr als nur eine Start- und Endanweisung machen kann (wenn es syntaktisch erlaubt ist) und b) das ein Funktionsaufruf bei der Bedingung auch jedesmal durchgeführt wird und daher zusätzliche Zeit kostet.
Bei JavaScript z.b. macht auch der Zugriff auf ein Attribut eines Objekts einen Unterschied aus. Der Zugriff auf eine Variable ist da schneller. Bei anderen Programmier- oder Skriptsprachen (;)) dürfte es nicht anders sein.

[WarSlash]

Jetzt stellt sich doch die Frage, wie sich eine Linked-List (2x verkettet) bei gleichen Bedingungen verhalten würde, also natürlich auch nur in PHP-Umgebung.

Hat jemand da eine passende gute Klasse zu und kann mal das mal prüfen?
Eigentlich müsste ja rein von der Theorie die Linked-List am schnellsten sein, da der Aufwand O(n) ist. n ist in diesem Fall $ID.

Die obigen Algorithmen, zumindest meiner, läuft ja linear entsprechend der Arrayfeldgröße.

Ein objektiver Test wäre dennoch interessant.

[Expandable]

Jetzt stellt sich doch die Frage, wie sich eine Linked-List (2x verkettet) bei gleichen Bedingungen verhalten würde, also natürlich auch nur in PHP-Umgebung.

Also theoretisch sind beide Versionen (array und linked list) im worst case gleich O(n) (n = Array/Listenlänge), da auch die Liste im worst-case bis zum Ende durchlaufen werden muss (sprich: Das Element soll hinter ID eingeordnet werden, ID ist das letzte Element, und wir fangen vorne an zu suchen). Man könnte wohl O(n/2) (aber das ist ja = O(n)) erhalten, wenn man die Liste gleichzeitig von vorne bis hinten und umgekehrt durchläuft.

Allerdings ist die Listen-Version im average case (O(n/2)) und best case O(1) schneller, Array hat hingegen immer O(n) in allen 3 Fällen.

[WarSlash]

<?php
function array_additem($parray,$item,$id) {
for ($i=$id; $i <=count($parray)-1;$i++){
$parray[$i] = $parray[$i+1];
}
$parray[$id] = $item;
return $parray;
}


Dieser Code ist symetrisch zu dem zweiten von darph. Komischerweise ist darphs Algorithmus schneller! Wie kann das sein? Best-Case ist gleich, aber Average und Worst nicht!

Settings: Array 20000
AverageCase (id = 10000)
WarSlash2: 0.00708889961243 seconds
darph2: 0.00460696220398 seconds

BestCase (id = 20000)
WarSlash2: 0.00254893302917 seconds
darph2: 0.00258183479309 seconds

WorstCase (id = 1)
WarSlash2: 0.0136950016022 seconds
darph2: 0.00672292709351 seconds

[ZapBee]

for ($i = count($parray) -1; $i >= $id; $i--) {
...;
}
...;


for ($i=$id; $i <=count($parray)-1;$i++){
...;
}
...;

Dieser Code ist symetrisch zu dem zweiten von darph.

Ist er nicht. Bei Dir steht das count() in der Abbruchbedingung. Da sieht man, welchen Effekt das hat :eek:

Zap

[Berni]

<?php
function array_additem($parray,$item,$id) {
for ($i = 0; $i < $id; $i++) {
$newarry[$i] = $parray[$i];
}

$newarry[$id] = $item;
$j = $id;
for ($i = $id + 1; $i <= sizeOf($parray); $i++) {
$newarry[$i] = $parray[$j];
$j++;
}
return $newarry;
}

function array_additem2($parray, $item, $id) {
$head = array_slice($parray, 0, $id);
$tail = array_slice($parray, $id, count($parray));

$head[$id] = $item;

return array_merge($head, $tail);
}

function array_additem3($parray, $item, $id) {
for ($i = count($parray) -1; $i >= $id; $i--) {
$parray[$i+1] = $parray[$i];
}
$parray[$id] = $item;
return $parray;
}

$parray = Array();
for ($i = 0; $i < 200000; $i++) {
$parray[] = $i;
}

$time_start = microtime(true);
$xa = array_additem($parray, 0, 1000);
$time_end = microtime(true);
$time = $time_end - $time_start;
echo("WarSlash: ".$time." seconds<br>");

$time_start2 = microtime(true);
$xb = array_additem2($parray, 0, 1000);
$time_end2 = microtime(true);
$time2 = $time_end2 - $time_start2;
echo("darph: ".$time2." seconds<br>");

$time_start3 = microtime(true);
$xb = array_additem3($parray, 0, 1000);
$time_end3 = microtime(true);
$time3 = $time_end3 - $time_start3;
echo("darph2: ".$time3." seconds<br>");

$time_start4 = microtime(true);
$xb = array_splice($parray, 1000, 0, array(0)); //Achtung: Gibt entfernte Elemente zurück, es wird das Originalarray verändert!
$time_end4 = microtime(true);
$time4 = $time_end4 - $time_start4;
echo("berni: ".$time4." seconds<br>");
?>


WarSlash: 0.154680967331 seconds
darph: 0.144827842712 seconds
darph2: 0.0804779529572 seconds
berni: 0.0533318519592 seconds

Also zunächst mal ists ja schon seltsam, dass darph bei mir schneller als WarSlash ist (systemabhängig oder PHP-Version?).
Des Weiteren macht eben jeder Funktionsaufruf was aus. Es gibt ne extra Funktion, die genau das macht (kann auch Elemente entfernen, siehe PHP-Handbuch!), was gewünscht ist und wenn man die ohne Umwege nutzt ists eben am Schnellsten...wenn ich diese allerdings nochmal in ne extra Funktion baue, ists langsamer als darph2.

http://de2.php.net/array_splice

Edit: Scheinbar hat die Anordnung der Funktionen auch Auswirkungen solange man es nur 1x ausführt. Daher sind die Werte wohl mit Vorsicht zu genießen.

[darph]

<?php
function array_additem($parray,$item,$id) {
for ($i=$id; $i <=count($parray)-1;$i++){
$parray[$i] = $parray[$i+1];
}
$parray[$id] = $item;
return $parray;
}


Dieser Code ist symetrisch zu dem zweiten von darph.
Sicher? Wenn $id =5, dann kopierst du in $parray[5] das rein, was in $parray[6] steht. Das heißt da würde zum Beispiel stehen nach der Bearbeitung in deinem aufsteigend befüllten Array stehen:
0 1 2 3 5 6 7 8 9 9. Außerdem bekommst du, wenn du auf $i = count()-1... +1 zugreifst eh einen Fehler, weil du dann in beispielsweise einem 10-Elementigen Array (also von 0-9) auf Element mit Index 10 - 1 + 1 = 10 zugreifst.

[WarSlash]

Sicher? Wenn $id =5, dann kopierst du in $parray[5] das rein, was in $parray[6] steht. Das heißt da würde zum Beispiel stehen nach der Bearbeitung in deinem aufsteigend befüllten Array stehen:
0 1 2 3 5 6 7 8 9 9. Außerdem bekommst du, wenn du auf $i = count()-1... +1 zugreifst eh einen Fehler, weil du dann in beispielsweise einem 10-Elementigen Array (also von 0-9) auf Element mit Index 10 - 1 + 1 = 10 zugreifst.

Na toll. Geiler Denkfehler, denn ich da verunstaltet habe. Wie wäre der Algo denn richtig?