[PHP5] meest efficente manier om een element uit een array

[Verwijderd]

Binnen een project moet ik werken met een relatief grote array. Uit deze array moeten items deleted worden, op 'onlogische' posities, dus niet aan het eind of aan het begin.

Ik ben op zoek naar de meest efficiente methode om dit te doen.

Tot nu toe heb ik de volgende methodes gevonden:

1) gebruik maken van array_splice
2) een item uit de array naar null toe zetten, en dan een array_merge uitvoeren met alleen die array
3) via shift en unshift, waarbij je het te deleten element niet meer toevoegt aan de array

Alle drie de functies doen wat ze moeten doen, echter de performance is eigenlijk van alle drie belabberd. De snelste is de methode met array_merge, hoewel ik dat zelf een ietwat smerige methode vind.

Mijn vraag is dus, of iemand nog een andere methode weet om 1 element uit een array te verwijderen, welke mogelijk sneller zou zijn dan de genoemde methodes.

[whoami]

Kan je een element uit zo'n array uniek identificieren ?

[.oisyn]

Nou werk je helaas in PHP, maar is een array wel de juiste datastructuur? Zeker als je veel inserts of deletes wil doen is iets als een linked list of een set (hangt een beetje van je gebruik af) veel handiger.

Wat ik in C++ doe met plain old arrays en de volgorde maakt niet uit, is het te verwijderen element verwisselen met het element dat achteraan staat, zodat je de array alleen nog maar 1 element korter hoeft te maken.

[Verwijderd]

Helaas maakt de volgorde wel uit, dus mag ik niet zomaar elementen verwisselen van plek.

Een linked list zou in dit geval zonder meer een betere keuze zijn, maar je krijgt niet altijd de tijd om de juiste keuze te implementeren. Momenteel wordt het met een array gedaan en om dat te veranderen zou ik wel eens meer tijd kwijt kunnen zijn dan begroot, plus het feit dat ik dan een substantieel deel van al in productie staande code (dus getest en ook de GAT gepasseerd) moet gaan wijzigen, iets wat zal gebeuren als dat moet, maar wat ik liever zou voorkomen.

Vandaar mijn vraag.

@whoami: wat bedoel je met uniek identificeren? Het is een array met een uniek indexnummer per item. Ik neem aan dat het antwoord op je vraag dus 'ja' is

vb. zo'n soort array bedoel ik:

PHP:

$item[1]="iets"
$item[2]="iets anders"

alleen dan iets groter, en uiteraard inhoudelijk ook anders . Om een item te verwijderen krijg ik bv. een opdracht als 'verwijder het item met index 10 uit de array, met behoud van de volgorde van de items in de array'.

Gaten in de index hoeven niet opgevuld te worden, dit mag dus:

PHP:

$item[1]="iets"
$item[2]="iets anders"
$item[3]="nog iets anders"
<hier de verwijderingsactie, van item 2, resultaat:>
$item[1]="iets"
$item[3]="nog iets anders"

[ Voor 6% gewijzigd door Verwijderd op 10-10-2005 15:27 ]

[whoami]

Verwijderd schreef op maandag 10 oktober 2005 @ 15:26:

@whoami: wat bedoel je met uniek identificeren? Het is een array met een uniek indexnummer per item. Ik neem aan dat het antwoord op je vraag dus 'ja' is

vb. zo'n soort array bedoel ik:

PHP:

$item[1]="iets"
$item[2]="iets anders"

Het antwoord is dus nee; mijn bedoeling was om te weten of je in die array bv object zitten had die een soort van uniek veld hadden. Als dat het geval was, dan kon je beter een hashtable oid gebruiken ipv een array.

code:

alleen dan iets groter, en uiteraard inhoudelijk ook anders :). Om een item te verwijderen krijg ik bv. een opdracht als 'verwijder het item met index 10 uit de array, met behoud van de volgorde van de items in de array'.

Dus, op de plaats van het te verwijderen item, mag je gewoon 'null' inserten ?
Als je 't zo doet, zou het toch relatief snel moeten kunnen gaan ?

[Verwijderd]

whoami schreef op maandag 10 oktober 2005 @ 15:29:
Dus, op de plaats van het te verwijderen item, mag je gewoon 'null' inserten ?
Als je 't zo doet, zou het toch relatief snel moeten kunnen gaan ?

De count van de array moet wel kloppen. In feite doe ik bovenstaande nu al, maar trek er dan nog een array_merge overheen om de count weer goed te krijgen.

[tech-no-logical]

code:

<?php

$a = array('a','b','c');

print_r($a);

unset($a[1]);

print_r($a);

?>

uitvoer:

code:

Array
(
    [0] => a
    [1] => b
    [2] => c
)
Array
(
    [0] => a
    [2] => c
)

[Arjen Tempel]

Met unset kun je een item uit een array wissen:

PHP:

<?
$item[1]="iets";
$item[2]="iets anders";
$item[3]="nog iets anders";

print_r ($item);

unset($item[2]);

print_r ($item);
?>

Geeft keurig als uitvoer:

code:

Array
(
    [1] => iets
    [2] => iets anders
    [3] => nog iets anders
)
Array
(
    [1] => iets
    [3] => nog iets anders
)

En ook count($item) geeft keurig de goede waarde (2) terug.

-edit-
tech-no-logical was me net voor.

[ Voor 13% gewijzigd door Arjen Tempel op 10-10-2005 15:40 ]

[Verwijderd]

VIEZE FLIKKERS BOVEN MIJ!!!

code:

<pre>
<?php

$a[0] = 4;
$a[1] = 8;
$a[2] = 6;

unset($a[1]);
while (list($key, $val) = each($a)) {
    echo $key . ", " . $val . "\n";
}
echo "count: " . count($a);

?>
</pre>

Snel met verwijderen, vast belabbert met doorlopen..

[ Voor 18% gewijzigd door Verwijderd op 10-10-2005 15:42 ]

[Verwijderd]

Arjen Tempel schreef op maandag 10 oktober 2005 @ 15:39:
unset($item[2]);

Ah kijk, het bewijs dat aannames de moeder zijn van alle fuckups. Alhoewel het in dit geval niet helemaal een aanname was van mij.

In de 'PHP bible' die ik hier voor me heb liggen, stond het voorbeeld met unset en array_merge, waarbij vermeld werd dat de laatste nodig was om de count goed te krijgen.

Ik heb het dus, in alle eerlijkheid, niet getest zonder de array_merge. Dit blijkt inderdaad gewoon te werken, en het wordt er wel iets sneller van, maar blijft nog steeds vrij langzaam.

Als dat de snelste methode is om het in PHP te doen, so be it. Zo niet, dan hoor ik het graag

[Verwijderd]

In die drie kwartier had je al lang een linked list kunnen implementeren Is dat niet alsnog een goede oplossing?

[PrisonerOfPain]

.oisyn schreef op maandag 10 oktober 2005 @ 15:18:
Nou werk je helaas in PHP, maar is een array wel de juiste datastructuur? Zeker als je veel inserts of deletes wil doen is iets als een linked list of een set (hangt een beetje van je gebruik af) veel handiger.

Overigens kun je PHP arrays ook benaderen als een linked list, geen idee of het een merkbare performance winst oplevert om het zelf te implementeren.
Overigens, wat je ook doet loop niet door je array met een foreach loop! Die maakt immers een volledige kopie van je array, by reference doorgeven heeft ook weinig zin omdat het opstellen van een lijst met refs langer duurt.

[Verwijderd]

PrisonerOfPain schreef op maandag 10 oktober 2005 @ 20:18:
Overigens kun je PHP arrays ook benaderen als een linked list, geen idee of het een merkbare performance winst oplevert om het zelf te implementeren.

Bij mijn weten (en op PHP gebied is dat nog niet zo heel gruwelijk ver ) is een php array gewoon een linked list (elke array, for that matter). Ik zie alleen niet in hoe je hem ook als zodanig kunt benaderen, kun je daar over uitwijden? Hoe vertel ik bv. het 5e element dat niet het 6e, maar het 7e element de volgende in de lijst is?

Overigens, wat je ook doet loop niet door je array met een foreach loop! Die maakt immers een volledige kopie van je array, by reference doorgeven heeft ook weinig zin omdat het opstellen van een lijst met refs langer duurt.

In dit geval was ik dat ook niet van plan.. ik gebruik wel foreach loops, maar alleen als ik de gehele array moet doorlopen. Begrijp ik dat ik, ook in die situatie, beter een for .. next construtie kan gebruiken?

[ Voor 8% gewijzigd door Verwijderd op 10-10-2005 20:24 ]

[PrisonerOfPain]

Verwijderd schreef op maandag 10 oktober 2005 @ 20:23:
Bij mijn weten (en op PHP gebied is dat nog niet zo heel gruwelijk ver ) is een php array gewoon een linked list (elke array, for that matter).

PHP arrays proberen een soort uberdatatype te zijn, wat over het algemeen niet een al te groot probleem is. En is dus niet enkel een linked list, maar ook een hashtable en een gewone array, wat de duidelijkheid niet ten goede komt af en toe.

Ik zie alleen niet in hoe je hem ook als zodanig kunt benaderen, kun je daar over uitwijden? Hoe vertel ik bv. het 5e element dat niet het 6e, maar het 7e element de volgende in de lijst is?

Over het algemeen benader je een PHP array met next, prev, current en reset. Als je 't wilt benaderen als een linked list. Overigens heeft een PHP array ook een vreemde volgorde, zo kun je 'm op volgorde van keys benaderen, maar ook op de interne volgorde (welke verschillend zijn, zie asort voor een voor een voorbeeld.) asort Is dan ook meteen een van de weinige functies waarmee je die interne volgorde (die next ook aanhoud) mee kunt veranderen.

In dit geval was ik dat ook niet van plan.. ik gebruik wel foreach loops, maar alleen als ik de gehele array moet doorlopen. Begrijp ik dat ik, ook in die situatie, beter een for .. next construtie kan gebruiken?

Een for loop is inderdaad de oplossing, of een list() = each() oplossing als je een assoctieve array hebt.

[Verwijderd]

PrisonerOfPain schreef op maandag 10 oktober 2005 @ 21:13:
Over het algemeen benader je een PHP array met next, prev, current en reset. Als je 't wilt benaderen als een linked list.

Dus ik zou bv. kunnen doen:

code:

$my_array[0] = "iets";
$my_array[1] = "iets";
$my_array[2] = "iets";
[..]
$my_array[0]->next = $my_array[2];

?

[PrisonerOfPain]

Verwijderd schreef op maandag 10 oktober 2005 @ 21:40:
[...]


Dus ik zou bv. kunnen doen:

Sorry hoor, maar kijk eens in de manual.

[Verwijderd]

Yep.. een terechte opmerking, guilty as charged

Hoe dan ook, ik heb het gelezen maar zie daar voor het unsetten van een element geen oplossing, wel een andere manier om te navigeren. Dat of ik zit met m'n achterwerk te kijken, wat niet de eerste keer zou zijn.

Ik heb het geprobeerd met een omgekeerde for (van count naar 0), en door bladeren met next en previous. Het eerste lijkt sneller, maar veel scheelt het niet.

[tech-no-logical]

PrisonerOfPain schreef op maandag 10 oktober 2005 @ 20:18:
[...]
Overigens, wat je ook doet loop niet door je array met een foreach loop! Die maakt immers een volledige kopie van je array, by reference doorgeven heeft ook weinig zin omdat het opstellen van een lijst met refs langer duurt.

uit de manual :

As of PHP 5, you can easily modify array's elements by preceding $value with &. This will assign reference instead of copying the value.

code:

<?php
$arr = array(1, 2, 3, 4);
foreach ($arr as &$value) {
   $value = $value * 2;
}
// $arr is now array(2, 4, 6, 8)
?>

This is possible only if iterated array can be referenced (i.e. is variable).

dat argument is dus achterhaald...

[Gwaihir]

Achterhaald? Dat maak ik uit die regel niet op. Het kan net zo goed nog steeds een nieuw array zijn(met nieuwe keys en alles) waarbij "slechts" elke waarde een referentie naar het originele array is. Dan kan sneller zijn dan een kopie, als er veel in iedere enkele waarde staat, maar klinkt nog altijd niet optimaal. Meer input, of liever nog: tests, iemand?

[tech-no-logical]

een vlugge test waarbij een array van 1000 elementen 1000 keer wordt gelooped, en in de loop er ook nog assignment plaatvindt (om iets nuttigs te doen). ik ben niet onder de indruk van de verschillen, maar de testmethode rammelt misschien ook nog her-en-der....

PHP:

<?php

function timer($start) {
  print "\n".(microtime(true)-$start)." \n";
}

$b = array();
for($t=0;$t<1000;$t++) $b[]=$t;

$start = microtime(true);

// normal foreach
$a = $b;
for($t=0;$t<1000;$t++) {
  foreach($a as $key=>$val) {
    $tmp = $val;
    $a[$key] = ++$tmp;
  }
}
timer($start);

$start = microtime(true);

// referenced foreach
$a = $b;
for($t=0;$t<1000;$t++) {
  foreach($a as &$val) {
    $tmp = $val;
    $val = ++$tmp;
  }
}

timer($start);

$start = microtime(true);

// normal loop
$a = $b;
for($t=0;$t<1000;$t++) {
  for($s=0;$s<count($a);$s++) {
    $tmp = $a[$s];
    $a[$s] = ++$tmp;
  }
}

timer($start);
$start = microtime(true);

// each loop
$a = $b;
for($t=0;$t<1000;$t++) {
  while (list($key, $val) = each($a)) {
    $tmp = $val;
    $a[$key] = ++$tmp;
  }
  reset($a);
}

timer($start);

$start = microtime(true);

// iterator
$arrayobject = new ArrayObject($b);

for($t=0;$t<1000;$t++) {
  $iterator = $arrayobject->getIterator();

  while($iterator->valid()) {
    $tmp = $iterator->current();
    $arrayobject[$iterator->key()] = ++$tmp;
    $iterator->next();
  }
}

timer($start);

?>

uitvoer:

code:

peter@fire:~$ php test.php

1.61924314499

0.978187799454

1.11695194244

2.22381496429

2.5633790493

conclusies ? volgens mij maakt 't allemaal niet dramatisch veel uit. php versie is overigens 5.0.3

[T-MOB]

tech-no-logical schreef op dinsdag 11 oktober 2005 @ 12:32:
uitvoer:

code:

peter@fire:~$ php test.php

1.61924314499

0.978187799454

1.11695194244

2.22381496429

2.5633790493

conclusies ? volgens mij maakt 't allemaal niet dramatisch veel uit. php versie is overigens 5.0.3

Hoe bedoel je, het maakt niet zoveel uit? Dat een verschil van 0.7s voor duizend herhalingen voor het menselijk verstand verwaarloosbaar is wil niet zeggen dat het niet relevant is. Het performance verschil tussen de (normale) foreach en een referenced foreach bedraagt 65%! Voor een script dat een enkele keer wordt uitgevoerd allicht niet relevant, op een druk bezochte website kunnen dit soort optimalisaties echter wél 65% van de hardwarekosten schelen.

[tech-no-logical]

T-MOB schreef op dinsdag 11 oktober 2005 @ 12:46:
[...]Hoe bedoel je, het maakt niet zoveel uit?

het is een artificial benchmark. maar goed, ik kijk stiekum ook wel naar mijn eigen situatie : ik heb geen code waarbij de impact van deze verschillen veel zal uitmaken. voor anderen zou 't idd nog wel 's boeiend kunnen zijn.

overigens vind ik het opvallendste dat de list() ... each() loop relatief langzaam is...

[Verwijderd]

Voor mij maakt het in elk geval wel uit, en wat testmethode betreft.. ik zie in de praktijk in mijn script dezelfde resultaten, de for loop is het snelst.

[tech-no-logical]

Verwijderd schreef op dinsdag 11 oktober 2005 @ 13:08:
Voor mij maakt het in elk geval wel uit, en wat testmethode betreft.. ik zie in de praktijk in mijn script dezelfde resultaten, de for loop is het snelst.

bij mij dus niet... de referenced foreach is sneller. of heb jij die niet getest ?

[Verwijderd]

tech-no-logical schreef op dinsdag 11 oktober 2005 @ 13:11:
bij mij dus niet... de referenced foreach is sneller. of heb jij die niet getest ?

Ik had 'm nog niet getest, ook vanwege de opmerkingen t.o.v. de foreach in dit topic.. maar dat ga ik nu zeker nog testen

[T-MOB]

De for loop valt overigens nog te optimaliseren door de uitkomst van de count() in een variabele te dumpen. Dan hoeft niet elke iteratie opnieuw de grootte van het array bepaald te worden.

[tech-no-logical]

da's een goeie... overigens is daarmee de for-loop weer sneller dan de referenced foreach (en ruim ook).

nadeel : werkt natuurlijk alleen als je array een constante lengte heeft...

[Michali]

Als je geen nummerieke index hebt, dan kun je opzich wel op deze manier een for loop gebruiken:

PHP:

$keys = array_keys($a);
$keyCount = count($keys);
for($t=0;$t<1000;$t++) {
    for ( $s = 0; $s < $keyCount; $s++ ) {
        $tmp = $a[$keys[$s]];
        $a[$keys[$s]] = ++$tmp;
    }
}

Ik ben wel benieuwd of dat ook sneller is dan een foreach loop.

Ik heb het zelf even getest en ik krijg dit als resultaten:

code:

normal foreach
2.3186581134796 

referenced foreach
1.2393798828125 

normal for loop
1.5349621772766 

normal for loop with optimized count
1.2438051700592 

for loop with each
2.7187628746033 

for loop with keys
1.8634049892426 

iterator
13.395064115524

[ Voor 35% gewijzigd door Michali op 11-10-2005 17:15 ]