[PHP] Array filteren....hoe??? *

[Verwijderd]

Ik ben vandaag al een paar uur bezig geweest om een manier te vinden om een array te filteren op bepaalde waardes.

v.b:

$vb=array (''1","2","2","3","4","4","4");

Ik wil nu op een snelle en effeciente manier de elementen uit deze array verwijderen die de waarde "2" hebben. Dus niet de array doorlopen en dan elementen unsetten.

Ik heb getest met de array_diff functie van php. Deze lijkt goed te werken tot op zekere hoogte. Ten eerste creert deze functie legen velden in de array die voor een volgende bewerking weer verwijderd moeten worden. Tevens geeft deze functie bij mij het probleem dat hij niet altijd de correcte waardes terug geeft.
(vooral bij grootte arrays werkt deze functie bij mij niet optimaal)

Hoe kan dit nu? Ik heb op menige sites gezocht naar manieren om elementen uit arrays te verwijderen maar kan helemaal niets vinden behalve unset. Ook via de search of php.net kwam ik er niet uit. Wie weet een goede functie die dit probleem kan oplossen. (bovenstaand voorbeeld kan worden opgelost met array_diff maar mijn werkelijke array niet, daar worden ook waardes verwijderd die niet verwijderd moeten worden).

Alvast bedankt!

[Janoz]

Nou, de manier die jij voorstelt is gewoon de snelste manier waneer je verder niks van de array weet. Je kunt wel wat gaan lopen kloten met functies, maar over het algemeen zullen die intern exact hetzelfde of zelfs meer gaan doen.

[Soultaker]

Je zult de array echt moeten doorlopen, maar je kunt natuurlijk array_filter gebruiken om het vuile werk voor je te doen. Je hoeft dan alleen nog maar een functie te definiëren die aangeeft welke elementen verwijderd moeten worden.

[Verwijderd]

nee klopt, ik weet verder niets van de array. Het verbaast me een beetje dat een dergelijke functie nog niet geïmplementeerd is in php. Wel b.v een mogelijkheid om alle waardes in de array uniek te maken maar niet om bepaalde elementenreeksen in één keer te verwijderen, is toch raar nietwaar?

Misschien iemand anders nog?

Ik heb dus in mijn geval: 10 id's in een mysql database staan.
Ik wil elk van die 10 id's een bepaald gewicht geven in een array
om zodoende een random item te kiezen. (dus waarde x staat dan
tweemaal in de array en waarde y b.v 1 keer) Dus waarde x heeft
meer kans gekozen te worden. Wanneer ik deze waardes eruit filter
om per stuk in een string te zetten, wil ik per volgende randomkeuze
dat de eerdere randomkeuze is verwijderd uit de array.

Vorige keuze is X dan volgende keuze random array-X

X kan dus 10 of 1000 keer voorkomen, maar moet wel
worden verwijderd. Wat anders kan ik doen behalve
stuk voor stuk doorlopen. Misschien is mijn gewicht-random
bepaling handiger te vast te stellen?

Thanks a lot

[MikeN]

Waarom doorloop je de array niet gewoon?
Zoals gezegd zullen zo ongeveer alle array functies binnen PHP dit ook doen. Waarom? Een array is gewoon een stuk geheugen en wil je daar iets uit verwijderen zul je gewoon vooraan moeten beginnen en bij iedere waarde moeten kijken of je het wilt verwijderen.

[eborn]

Verwijderd schreef op 24 June 2003 @ 01:04:
nee klopt, ik weet verder niets van de array. Het verbaast me een beetje dat een dergelijke functie nog niet geïmplementeerd is in php. Wel b.v een mogelijkheid om alle waardes in de array uniek te maken maar niet om bepaalde elementenreeksen in één keer te verwijderen, is toch raar nietwaar?

In principe is daar toch de array_diff functie voor. Als je zelf merkt dat die niet goed werkt dan zou ik een bug-report indienen. array_diff hoort namelijk netjes alle waardes terug te geven die wel in het eerste maar niet in het als tweede opgegeven array staan.

[Verwijderd]

Als je array toch alleen maar getalletjes bevat: gebruik de index als nummer, en de value als aantal.

In jouw geval zou dit geven:

PHP:

$array[1] = 1;
$array[2] = 2;
$array[3] = 1;
$array[4] = 3;

Dit doe je terwijl je je gegevens uit de dbase haalt.

En volgens mij kan je dan gewoon unset($array[2]); (of iets gelijkaardigs, zoek maar eens op php.net) doen, zonder dat je moet loopen doorheen je array.

Als dat niet lijkt te werken/geen goede oplossing is, zorg dan, voordat je gaat loopen, dat je array gesorteerd is (quicksort, heapsort, je zoekt maar op), dan kan je dus stoppen met loopen als je al voorbij het getal bent dat al gewist moet worden.

Good luck.

edit: deze manier van omgaan met je array geeft ook een meer efficiënte implementatie voor het bepalen van max. en min. waarden:

- ofwel heeft php een max/min-functie, die niet alleen de waarde teruggeeft, maar ook de key(s) (want dat is jouw waarde, dus daar ben je in geïnteresseerd!) waarop die waarde (jou aantal, dus waarop die functie het hoogste getal vindt) zit. Hoe php juist het minimum/maximum zoekt, weet ik niet, maar hij moet allezins minder elementen (je array is veel kleiner!) beschouwen.

- ofwel moet je dat zelf maken, maar nu moet je wel minder elementen doorlopen

[ Voor 35% gewijzigd door Verwijderd op 24-06-2003 08:25 ]

[eborn]

Verwijderd schreef op 24 juni 2003 @ 08:11:
Als dat niet lijkt te werken/geen goede oplossing is, zorg dan, voordat je gaat loopen, dat je array gesorteerd is (quicksort, heapsort, je zoekt maar op), dan kan je dus stoppen met loopen als je al voorbij het getal bent dat al gewist moet worden.

De vraag is natuurlijk of dat vooraf sorteren niet meer tijd in beslag neemt dan bij gewoon alles doorlopen. Maar goed, dat zou de TS even kunnen testen.

[Verwijderd]

Ik denk dat je op een grote array echt wel wilt sorteren hoor.

[eborn]

Verwijderd schreef op 24 June 2003 @ 11:19:
Ik denk dat je op een grote array echt wel wilt sorteren hoor.

Ik weet het niet. Sorteren kost namelijk ook tijd. Een groter array zorgt dus ook voor een langere sorteertijd. Ik denk dat je dit alleen door te testen kunt vaststellen.

[Kaastosti]

Je kunt ook gewoon de key en de inhoud omwisselen met array_flip()... alleen weet ik dan niet wattie doet met dubbele data. Je krijgt dan bijvoorbeeld dit:

Origineel:
$array[1] = 'Blaat';
$array[2] = 'Woei';
$array[3] = 'Gnuk';
$array[4] = 'Loerp';

Als je nu de boel omdraaid:

$array['Blaat'] = 1;
$array['Woei'] = 2;
$array['Gnuk'] = 3;
$array['Loerp'] = 4;

Op die manier kun je makkelijk alle elementen $array['Blaat'] weghalen zonder de array zelf te moeten doorlopen. Ik weet echt niet wat ie doet als je er dus een dubbele waarde in krijgt.

---
Even getest met die dubbele data:
Als je bijvoorbeeld 2 keer 'Woei' hebt, wordt alleen de laatste onthouden. Je krijgt dan dus in de omgedraaide case:

$array['Blaat'] = 1;
$array['Woei'] = 4;
$array['Loerp'] = 3;

Ik had dus in dit geval in $array[2] ook 'Woei' ingevuld. In jouw geval is dat niet ernstig, aangezien je 'm toch weg wilt halen. Dan krijg je nu dus gewoon alsnog:
unset($array['Woei']); en klaar

[ Voor 45% gewijzigd door Kaastosti op 24-06-2003 16:38 ]

[eborn]

Als ik het volgende stukje stuk code uitvoer (wat ik net even quick and dirty gemaakt heb):

PHP:

function getmicrotime()
{ 
    list($usec,$sec) = explode(" ",microtime()); 
    return ((float)$usec + (float)$sec); 
} 

// Definieer een array met random waardes tussen 1 en 20
$arr_orig = array();
for( $i=0; $i<100000; $i++ )
    $arr_orig[] = round(rand(1,20));

// Filter de waardes d.m.v. array_diff
$starttime = getmicrotime();
$filtered = array_diff( $arr_orig, array( 2 ) );
$endtime = getmicrotime();
print "Duration1: ".number_format($endtime-$starttime,10)." (".
     (count($arr_orig)-count($filtered)).")\n";

// Kopieer het basis-array voor de eerste doorloop methode
$arr = array();
foreach( $arr_orig as $k=>$v )
    $arr[$k] = $v;
$found = 0;

// Loop het array door en haal alle verwijzigen naar 2 eruit
$starttime = getmicrotime();
foreach( $arr as $k=>$v )
    if( $v == 2 ) { $found++; unset($arr[$k]); }
$endtime = getmicrotime();
print "Duration2: ".number_format($endtime-$starttime,10)." ($found)\n";

// Kopieer het basis-array voor de tweede doorloop methode
$arr = array();
foreach( $arr_orig as $k=>$v )
    $arr[$k] = $v;
$found = 0;

// Loop het array door en haal alle verwijzigen naar 2 eruit
$starttime = getmicrotime();
asort($arr);
foreach( $arr as $k=>$v )
{
    if( $v == 2 ) { $found++; unset($arr[$k]); }
    if( $v > 2 ) break;
}
$endtime = getmicrotime();
print "Duration3: ".number_format($endtime-$starttime,10)." ($found)\n";

?>

Krijg ik de volgende output:

Duration1: 0.0690050125 (39)
Duration2: 0.0032820702 (39)
Duration3: 0.0032240152 (39)

De array_diff is dus het allerlangzaamste. De twee andere methodes verschillen niet veel. Als het aantal verhoogd wordt naar 10.000 dan wordt methode 3 (het eerst sorteren) iets sneller dan methode 2. Methode 1 blijft het meeste tijd innemen. Zodra we naar de 100.000 waardes gaan wordt array_diff nog trager. Alleen wordt dan methode twee een stukje sneller dan methode 3:

Duration2: 0.6074219942 (4989)
Duration3: 1.0053410530 (4989)

Het ligt er dus maar sterk aan hoeveel waardes je wilt gebruiken.

[ Voor 51% gewijzigd door eborn op 24-06-2003 16:47 . Reden: Nieuwe test ]

[bigtree]

Volgens mij is er een veel simpeler oplossing. Maak een tweede array 'used_ids' (als je die al niet had). Nadat je een ID gekozen hebt, haal het uit je eerste tabel en zet je het in de tabel used_ids. Vervolgens pak je een tweede random ID, kijk of het in de used_ids staat en als dat zo is, verwijderen uit de tabel en de volgende random ID pakken.

[Kaastosti]

Volgens mij is iedereen nog steeds vrolijk arrays aan het doorlopen, wat nu juist niet de bedoeling was

[eborn]

Kaastosti schreef op 24 June 2003 @ 16:47:
Volgens mij is iedereen nog steeds vrolijk arrays aan het doorlopen, wat nu juist niet de bedoeling was

Maar ik dacht dat we het er ook over eens waren dat het niet anders kan? Je zult namelijk toch altijd alle waardes moeten weten. Daarvoor zul je toch een bepaald gedeelte moeten doorlopen. Dat staat los van de vraag of het misschien heel anders opgezet kan worden (qua structuur) waardoor de TS helemaal geen waardes meer hoeft te unsetten. Maar het vraagstuk

[ Voor 26% gewijzigd door eborn op 24-06-2003 16:49 ]

[bigtree]

eborn schreef op 24 June 2003 @ 16:48:
[...]
Maar ik dacht dat we het er ook over eens waren dat het niet anders kan?

Lees mijn post even.

[eborn]

Kaastosti schreef op 24 June 2003 @ 16:29:
Ik had dus in dit geval in $array[2] ook 'Woei' ingevuld. In jouw geval is dat niet ernstig, aangezien je 'm toch weg wilt halen. Dan krijg je nu dus gewoon alsnog:
unset($array['Woei']); en klaar

Maar ik neem aan dat je ook een array wilt overhouden waar je oorspronkelijke gegevens nog uit te halen zijn? Nu raak je dus ook eventuele meerdere verwijzingen naar 1 of 3 kwijt. Die worden namelijk ook op een hoopje geraapt.

[Kaastosti]

Hmmm tjah als er van alle andere waarden ook dubbelen in zitten, gaat mijn methode ook niet werken helaas. Wat ik dan zou doen is gewoon array_diff draaien en daarna een korte functie toepassen die alleen gevulde elementen overzet naar een nieuwe array.

Volgens mij is er weinig anders mee te doen. Wat is anders de hele functie van een array? Het blijft een datastructuur.. als je daar niet doorheen mag loopen is het eind zoek dacht ik zo

--
bigtree volgens mij loop jij er toch ook gewoon doorheen? of pak je een willekeurig element en vergelijk je dat.. da's namelijk ook nie handig

[ Voor 15% gewijzigd door Kaastosti op 24-06-2003 16:53 ]

[eborn]

bigtree schreef op 24 juni 2003 @ 16:51:
Lees mijn post even.

Ik moet mijn uitspraak even rectificeren Ik bedoelde daarmee: er is geen andere methode om sneller uit een bestaand array bepaalde waardes te filteren Ik heb voor de rest niet echt gelezen wat de TS met deze informatie wil doen. Ik baseer me dus vooral op de vraag wat de snelste manier is om zo'n array te filteren (zoals in de openingspost vermeld staat)

[ Voor 28% gewijzigd door eborn op 24-06-2003 16:55 ]

[bigtree]

De TS liet de deur open voor andere methoden:

Misschien is mijn gewicht-random bepaling handiger te vast te stellen?

Dan heb ik er nog wel eentje: sorteer de id alvast in MySQL, die kan dat namelijk veel sneller. Zet ze met zijn allen in een array. Pik er random ééntje uit, wis die, kijk of degene er voor en er na hetzelfde zijn, wis die ook. Dan hoef je niet de hele array door te lopen.

[Verwijderd]

Random een getal kiezen is volgens mij een 'erg zware' operatie.

eborn schreef op 24 June 2003 @ 16:39:Krijg ik de volgende output:

Duration1: 0.0690050125 (39)
Duration2: 0.0032820702 (39)
Duration3: 0.0032240152 (39)

...

Duration2: 0.6074219942 (4989)
Duration3: 1.0053410530 (4989)

Het ligt er dus maar sterk aan hoeveel waardes je wilt gebruiken.

Interessante test! Op grote arrays blijkt sorteren dus aangewezen.

edit: niet dus

[ Voor 9% gewijzigd door Verwijderd op 24-06-2003 18:13 ]

[bigtree]

eborn: als je nu het sorteren uit de microteller weghaalt? (bijvoorbeeld doordat MySQL dat al gedaan zou hebben), is methode 2 of 3 dan sneller?

[Verwijderd]

Volgens mij is de beste oplossing, als die getalletjes in de dbase zitten, nog altijd die waarbij je array gaat beschouwen als key=waarde en value=aantal.

Zie eerste reply van mij: dus bij het neerhalen maak je gewoon die array (moet je zoiezo), je zoekt het maximum (maar hij moet nu minder elementen doorlopen), en dat unset je.

Je moet dus helemaal niet doorlopen

[eborn]

bigtree schreef op 24 June 2003 @ 18:56:
eborn: als je nu het sorteren uit de microteller weghaalt? (bijvoorbeeld doordat MySQL dat al gedaan zou hebben), is methode 2 of 3 dan sneller?

Op dit moment worden de waardes gegenereerd, dus dan moet ik even een tabelletje in MySQL aanmaken met die random waardes.

Aan de andere kant. Op het moment dat ik we MySQL gaan gebruiken zou ik persoonlijk gebruik maken van een WHILE constructie. Dan ben je de hele controle in PHP kwijt. Het gaat me iets te ver om dit er ook nog bij op te nemen Maar als iemand zich geroepen voelt om deze tests toe te voegen

[ Voor 29% gewijzigd door eborn op 24-06-2003 19:20 ]

[bigtree]

Ik bedoelde dat je dezelfde test zou uitvoeren zonder het sorteren mee te tellen. De data mag je gewoon op dezelfde manier genereren.

[Verwijderd]

bigtree schreef op 24 June 2003 @ 22:43:
Ik bedoelde dat je dezelfde test zou uitvoeren zonder het sorteren mee te tellen. De data mag je gewoon op dezelfde manier genereren.

Gaat niet, want dan ben je ofwel fout bezig omv. de 'if( $v > 2 ) break;', ofwel laat je die break weg, en zit je terug in het vorige geval

[bigtree]

Verwijderd schreef op 24 June 2003 @ 19:05:Zie eerste reply van mij: dus bij het neerhalen maak je gewoon die array (moet je zoiezo), je zoekt het maximum (maar hij moet nu minder elementen doorlopen), en dat unset je.

Je moet dus helemaal niet doorlopen

Hij moet nu dus nog wel je (stuk kleinere) array doorlopen, maar zou het niet handig zijn een array bij te houden met de min/max per id? Alleen moet ik nog even bedenken wat je met die array doet als je een element verwijdert. (We doen nu dus ALLES om te voorkomen dat je door welke array ook heen moet lopen )

[bigtree]

Verwijderd schreef op 24 June 2003 @ 22:55:
[...]


Gaat niet, want dan ben je ofwel fout bezig omv. de 'if( $v > 2 ) break;', ofwel laat je die break weg, en zit je terug in het vorige geval

Anders gezegd bedoelde ik: draai regel 39 en 40 om.

[eborn]

bigtree schreef op 24 June 2003 @ 22:43:
Ik bedoelde dat je dezelfde test zou uitvoeren zonder het sorteren mee te tellen. De data mag je gewoon op dezelfde manier genereren.

Met asort() buiten de tijdsmeting krijgen we:

Voor 50.000 nummers:

Duration1: 22.7620669603 (2451)
Duration2: 1.0405709743 (2451)
Duration3: 0.4373509884 (2451)

Voor 10.000 nummers:

Duration1: 4.0572520494 (474)
Duration2: 0.2066440582 (474)
Duration3: 0.0929698944 (474)

Voor 1.000 nummers:

Duration1: 0.3071799278 (58)
Duration2: 0.0184880495 (58)
Duration3: 0.0067919493 (58)

Ter herinnering:

Duration1 = array_diff
Duration2 = hele array doorlopen (van 0 .. n)
Duration3 = gesorteerd array doorlopen tot $value > $filterVal

(let op, deze resultaten zijn niet te vergelijken met de vorige lijst. Ze zijn namelijk op een oudere machine uitgevoerd)

De derde manier is nu uiteraard overal sneller, omdat er nu niet meer gesorteerd wordt. Eventueel kan MySQL dit natuurlijk doen, maar dan moet je bij de andere verzoeken ook een 'normale' (niet gesorteerd) database request meenemen om het eerlijk te testen.

[ Voor 9% gewijzigd door eborn op 24-06-2003 23:17 ]

[bigtree]

Om het proces helemaal te optimaliseren wil ik de verhouding weten tussen het unieke aantal id's in de database en het aantal id's dat random uitgespuugd moet worden. Als ik de TS mag geloven zitten er maar 10 unieke id's in de database. In dat geval zou ik zeker een GROUP BY doen en de boel in een array zetten. Dan maakt het verder volgens mij geen fluit uit op welke manier je die array doorloopt. Het zijn immers maar een paar iteraties, dus zal in absolute miliseconden niet veel uitmaken.