[PHP] Array 2D doorzoeken

[Verwijderd]

Een leuke uitdaging, dacht ik zelf

Mijn huidige situatie:

PHP:

$dieren=array(  
            0=>array(   
                        "Hond"=>"Brokken",
                        "Kat"=>"Vis"
                    ),
            1=>array(   
                        "Olifant"=>"Water",
                        "Tijger"=>"Vlees"
                    ),
            2=>array(   
                        "Muis"=>"Muesli",
                        "Hamster"=>"Korrels"
                    ),
        );
        
$keuze = "Hamster";

foreach($dieren as $soort)
    foreach($soort as $dier=>$voedsel)
        if ($dier == $keuze)
            $voedselkeuze = $voedsel;

echo $voedselkeuze;

Een simpel script. Het begint met een array waar er verschillende dieren zijn, onderverdeeld in verschillende catogorieën. Elk dier is een key, met als value het voedsel dat hij normaal eet.

Ik wil snel kunnen zien wat een hond eet. Op het moment loop ik de complete array door, en zodra ik het resultaat vind gooi ik het voedsel dat hij eet in de variabele "voedselkeuze". Daarna break ik de loop (niet in het voorbeeld te zien), en heb ik wat ik wil.

In de huidige situatie is alles echter veel groter. Het kan een vertraging veroorzaken, en met name daarom wil ik het sneller kunnen doen. Ik heb al diverse array zoekfuncties die standaard in PHP zitten doorgenomen, maar ik heb er nog geen één gevonden die 2D op enkele levels deep in een array zoekt.

Zou dit beter kunnen?

[Glewellyn]

Je weet toch de naam dan de key al?
Waarom loop je dan over het hele array heen?

[Janoz]

Ja, maar daarvoor moet je je structuur wel omgooien. Met je huidige structuur zul je altijd je hele array door moeten lopen. Ook interne php functies doen exact hetzelfde. Je zou het iets kunnen versnellen door die binnenste foreach niet te doen en gewoon opvragen of $soort[$keuze] een waarde heeft.

Ik snap trouwens niet waarom iedereen altijd van die enorm gecompliseerde array structuren loopt te gebruiken om hun data in op te slaan.

[crisp]

Zie Janoz: in feite is dit natuurlijk een normalisatie-probleem (of beter: gebrek aan normalisatie )

Maar dit zou de boel wel moeten versnellen:

PHP:

foreach($dieren as $soort)
{
    if (isset($soort[$keuze]))
    {
        $voedselkeuze = $soort[$keuze];
        break;
    }
}

[Verwijderd]

De rede dat ik het op deze wijze opsla is vrij simpel. Het is een PHP-bestand dat ge-include wordt, en wat makkelijk door de gebruiker te bewerken moet zijn. Een database is geen optie.

In de echte situatie werk ik met

PHP:

$array[date("w",$timestamp)]

, waarna ik een array terugkrijg welke activiteiten er op die dag zijn. Mocht dat iets verklaren. Bedankt voor bovenstaande tips, die ga ik zeker verwerken :-)

[Janoz]

De rede dat ik het op deze wijze opsla is vrij simpel. Het is een PHP-bestand dat ge-include wordt, en wat makkelijk door de gebruiker te bewerken moet zijn. Een database is geen optie.

Er zijn zoveel meer mogelijkheden dan enkel een database. Ook als een eis "makkelijke aanpasbaarheid" is. Sowieso vind ik een door gebruikers aanpasbaar php bestand een groot risico. Vergeten ze een quote dan werkt je hele applicatie niet meer ipv dat er gewoon een foutmelding gegeven kan worden dat er een fout in de data zit.

[Verwijderd]

Janoz schreef op donderdag 15 maart 2007 @ 15:11:
[...]

Er zijn zoveel meer mogelijkheden dan enkel een database. Ook als een eis "makkelijke aanpasbaarheid" is. Sowieso vind ik een door gebruikers aanpasbaar php bestand een groot risico. Vergeten ze een quote dan werkt je hele applicatie niet meer ipv dat er gewoon een foutmelding gegeven kan worden dat er een fout in de data zit.

Goed, in mijn geval is het een applicatie die ik *ooit* nog eens uit wil gaan brengen, waarbij de data die aan te passen is in een los bestand staat, in een array. Enige PHP kennis is toch nodig, dus dat is geen enkel probleem. Zelf zie ik daarom geen probleem met mijn huidige array methode.

Maar mocht je een concreet voorbeeld hebben, dan moedig ik je aan het hier te posten

[mithras]

code:

[huisdieren]
Hond = Brokken
Kat = Vis

[exoten]
Olifant = Water
Tijger = Vlees

[irritante_beesten]
Muis - Muesli
Hamster = Korrels

En vervolgens de ini parsen kan toch ook: is vele malen gebruiksvriendelijker, je hebt met een fout niet direct een exploit in je code en je kan er wellicht nog wat extra checks op doen zodat je het bestand helemaal veilig uitleest

Er zijn trouwens nog wel meer manieren: xml en dergelijke, maar voor een leek is dat ook niet handig.

[ Voor 12% gewijzigd door mithras op 15-03-2007 15:33 ]

[Verwijderd]

Ach, hoe moeilijk is XML nou?

XML:

<dier>
    <naam>Hond</naam>
    <soort>Huisdieren</soort>
    <eten>Brokken</eten>
</dier>

[Daos]

In Php zijn er zelfs functies voor xml .

Als je echt geen xml wilt gebruiken, dan zou ik elk record (info per dier) op een regel in een tekstbestand stoppen met tussen de velden een komma. Oftewel in het "Comma Separated Value (CSV) File Format".


Als je alleen wilt zoeken op 1 veld (bv de naam van het dier), dan kan je bij het maken van je databestand al sorteren op dat veld (naam). Via een binary search kan je dan heel snel alle gegevens (van dat dier) opvragen. In C heb je daar de functie bsearch voor:

C:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    char *naam;
    char *voer;
    char *soort;
} dier;


#define AANTAL 4

/* dieren gesorteerd op naam */
dier dieren[AANTAL] = {{"Hond","Brokken","Huisdier"},
        {"Kat","Vis","Huisdier"},
        {"Olifant","Water","Exoot"},
        {"Tijger","Vlees","Exoot"}};


int vergelijk(const void *a, const void *b) {
    return strcmp(((dier *)a)->naam, ((dier *)b)->naam);
}

dier *zoekDier(const char *naam) {
    dier zoek;
    zoek.naam = naam;
    return (dier *)bsearch(&zoek, dieren, AANTAL, sizeof(dier), vergelijk);
}

int main() {
    dier *gevonden = zoekDier("Kat");

    if (gevonden)
        printf("De %s is een %s en heeft als voer %s.\n",
                gevonden->naam, gevonden->soort, gevonden->voer);
    else
        printf("Dat dier is onbekend.\n");
}

Misschien is er ook zoiets in Php...

offtopic:
Op een of andere manier lijken mijn kleine C voorbeeldjes altijd heel groot

[Verwijderd]

mithras schreef op donderdag 15 maart 2007 @ 15:26:

code:

[huisdieren]
Hond = Brokken
Kat = Vis

[exoten]
Olifant = Water
Tijger = Vlees

[irritante_beesten]
Muis - Muesli
Hamster = Korrels

En vervolgens de ini parsen kan toch ook: is vele malen gebruiksvriendelijker, je hebt met een fout niet direct een exploit in je code en je kan er wellicht nog wat extra checks op doen zodat je het bestand helemaal veilig uitleest

Er zijn trouwens nog wel meer manieren: xml en dergelijke, maar voor een leek is dat ook niet handig.

Kijk, dat is een leuke uitdaging om mijn source verder te perfectioneren. Mijn parser voor dit formaat:

PHP:

function parseDieren(){
    $dieren = parse_ini_file("settings/dieren.ini", TRUE);
    $result = array()

    $result[0] = $dieren['Huisdieren'];
    $result[1] = $dieren['Exoten'];
    $result[2] = $dieren['Irritante Beesten'];

    return $result;
}

Ik rebuild de complete array in plaats van een simpele string replace. De rede hiervoor? Zodat er niet geklooit kan worden

[Daos]

Je array in Php is nog steeds net zo vreemd als in je eerste post. Een ini is bovendien niet echt geschikt voor het opslaan van data. Het is alleen voor configuratie bedoeld.


Php-versie van mijn C-voorbeeldje:

PHP:

// BinarySearch gejat van wikipedia
function BinarySearchOpNaam( $A, $value ) {
    $low = 0;
    $high = count($A) - 1;
    $p = $low+(($high-$low)/2);
    while ( $low <= $high) {
        if ( $A[$p]["Naam"] > $value )
            $high = $p - 1;
        else if ( $A[$p]["Naam"] < $value )
            $low = $p + 1;
        else
            return $A[$p];
        $p = $low+(($high-$low)/2);
    }
    return NULL;
}


// array gesorteerd op naam
$dieren=array(
    array(
        "Naam"=>"Hond",
        "Voer"=>"Brokken",
        "Soort"=>"Huisdier"
    ),
    array(
        "Naam"=>"Kat",
        "Voer"=>"Vis",
        "Soort"=>"Huisdier"
    ), 
    array(
        "Naam"=>"Olifant",
        "Voer"=>"Water",
        "Soort"=>"Exoot"
    ),
    array(
        "Naam"=>"Tijger",
        "Voer"=>"Vlees",
        "Soort"=>"Exoot"
    )
);

$naam = "Kat";

$gevonden = BinarySearchOpNaam($dieren, $naam);

if (is_null($gevonden)) 
    printf("Dat dier is onbekend.\n");
else 
    printf("De %s is een %s en heeft als voer %s.\n", 
         $gevonden["Naam"], $gevonden["Soort"], $gevonden["Voer"]);

[Verwijderd]

Wordt het er al beter op als ik zeg dat mijn array de vorm heeft van:

code:

[Maandag]
Touwklimmen = "Drie kwartier , melden bij de grote gymzaal"
Ringhangen = "Half uur, melden bij de kleine gymzaal"

[Dinsdag]
Judo = "Twee uur, melden bij H. Bos"
.....

[Vrijdag]
Bokspring = "Half uur, melden bij de kleine gymzaal"

?

Mogelijk een slecht voorbeeld, ik hoop het hiermee duidelijker te hebben

[Daos]

Verwijderd schreef op donderdag 15 maart 2007 @ 19:26:
Wordt het er al beter op als ik zeg dat mijn array de vorm heeft van:

Nee. Een activiteit kan je zien als een object/record. De dag is alleen maar een eigenschap (veld) van een activiteit.

XML:

<kalender>
    <activiteit> 
        <dag>Maandag</dag> 
        <actie>Touwklimmen</actie> 
        <omschrijving>"Drie kwartier , melden bij de grote gymzaal"</omschrijving> 
    </activiteit> 
    <activiteit> 
        <dag>Maandag</dag> 
        <actie>Ringhangen</actie> 
        <omschrijving>"Half uur, melden bij de kleine gymzaal"</omschrijving> 
    </activiteit> 
    <activiteit> 
        <dag>Dinsdag</dag> 
        <actie>Judo</actie> 
        <omschrijving>"Twee uur, melden bij H. Bos"</omschrijving> 
    </activiteit> 
    <!-- ..... -->
    <activiteit> 
        <dag>Vrijdag</dag> 
        <actie>Bokspring</actie> 
        <omschrijving>"Half uur, melden bij de kleine gymzaal"</omschrijving> 
    </activiteit> 
</kalender>

Je array kan volgens mij het beste ook zo'n structuur hebben. Dus een array met activiteiten.

Misschien kan iemand anders het beter uitleggen...

[Verwijderd]

Goed, enige puntje is dat de use-ability hiermee diep zinkt. Dat is een punt dat ik ook niet moet vergeten. Het kan zelfs nog extremer dan het voorbeeld dat jij geeft

Imho vind ik de front-end vaak belangrijker dan de back-end.

[ Voor 15% gewijzigd door Verwijderd op 15-03-2007 20:04 ]

[Creepy]

Ik weet niet hoeveel data je precies gaat krijgen maar data opslaan gaat mijn inziens nog het beste in een (jawel) database. Kleine front-end erbij maken om het makkelijk bewerkbaar te maken en gaan. En met de juiste structuur en indexen nog snel ook. Waarom je pertinent geen DB wilt gebruiken is me dan ook een raadsel.

En haal gelijk de tijdsduur uit je omschrijving en benoem dat ook tijdsduur o.i.d., dan zie je gelijk zaken als een INI file ook afvallen.

[mithras]

Tja, je kan beweren dat een ini file niet geschikt is om data in op te slaan, als je laagdrempelig wil zijn én geen database wil gebruiken zit er niet veel anders op.

Met xml kan je in het voorbeeld van DOT al acht fouten maken in 5 regels code: de sluit tag van elke tag vergeten (of in ieder geval de sluitende /) en een spelfout maken in de begin tag en de sluit tag.
Met een ini kan je deze fouten al niet maken, en omvat je data niet al te veel informatie, kan je prima met een ini overweg. Het is er niet voor bedoeld, maar elke leek kan het gebruiken, in tegenstelling tot xml

[Creepy]

Maak dan een simpele front-end zodat de gebruiker met een editor alleen z'n waarden hoeft in te kloppen. Kan je nog extra checks op de invoer maken ook zodat de gebruiker bijna geen fouten meer kan maken. Dan maakt voor de gebruiker de manier van opsalg helemaal niet meer uit.

[ Voor 15% gewijzigd door Creepy op 16-03-2007 09:46 ]

[Verwijderd]

een ini is in die zin dan ook een soort voorloper van xml, daar xml ook niet bedoeld is om als database te gebruiken en als we dan toch bestands formatten aan het misbruiken zijn dan kan je net zogoed een comma-delimmted text-bestand gebruiken. kun je gewoon met file en explode inlezen.

een database is inderdaad de aangewezen structuur zeker omdat de TS al aangeeft dat het hier mogelijk om honderden, zoniet duizenden records gaat en dan wil je echt geen xml, ini, whatever gebruiken.

ik denk dat de reden waarom de ts geen database wil gebruiken is omdat deze geen aparte server er bij wil hebben. kan een geldige reden zijn i.c.m bijvoorbeeld php-gtk. dan wil je geen losse mysql install bij je stand-alone applicatie voegen.

mischien dat sqlite hier een oplossing kan bieden en anders zou de ts er goed aan doen om gewoon een I/O klasse te schrijven die het hele gebeuren van de xml/ini/whatever formaat afhandelt met wat caching algorithme's etc. een soort DB-engine dus.

daarnaast mag de TS ook wel eens gaan nadenken over de structuur van zijn array want in het voorbeeld van dieren en wat ze eten hoef je niet eens te zoeken. je kijk gewoon of de key bestaat.

PHP:

 $dieren = array();
 $dieren["hond"] = "brokken";
 $dieren["kat"] = "vis";
 $dieren["koe"] = "gras";

 $dier = "hond";
  if(isset($dieren[$dier])){
   print("een ".$dier." eet ".$dieren[$dier].".");
  }else{
   print("ik kon niet vinden wat een ".$dier." eet.");
  }

geeft zonder te zoeken: "een hond eet brokken".
zo kun je zonder de hele array te hoeven doorzoeken toch bijna instant het juiste record terug vinden door gewoon even slim na te denken over wat de records van elkaar ondersheidt.

[Daos]

Verwijderd schreef op vrijdag 16 maart 2007 @ 15:06:
een ini is in die zin dan ook een soort voorloper van xml, daar xml ook niet bedoeld is om als database te gebruiken en als we dan toch bestands formatten aan het misbruiken zijn dan kan je net zogoed een comma-delimmted text-bestand gebruiken. kun je gewoon met file en explode inlezen.

Ini is voor configuratie bedoeld en is gewoon niet geschikt voor data.
Xml is wel voor data bedoeld. Csv werd vroeger best veel gebruik voor data (het is dus geen misbruiken).

Csv kan best handig zijn. Excel kan een .csv gewoon openen. Excel gebruikt alleen de ; als scheidingsteken. Verder moet je er rekening meehouden dat de " opgeslagen wordt als "". Bovendien kunnen "-jes om het veld heen komen te staan. Dit gebeurt zowiezo als er een " of ; in het veld gebruikt wordt.

een database is inderdaad de aangewezen structuur zeker omdat de TS al aangeeft dat het hier mogelijk om honderden, zoniet duizenden records gaat en dan wil je echt geen xml, ini, whatever gebruiken.

Klopt in dit geval. Bij Php wordt alle code elke keer uitgevoerd als je de site bezoekt. Bij een normaal (geen Php, met gui) programma kan je gewoon bij het opstarten rustig de bestanden inlezen/parsen en de data in het geheugen laten staan.

Als je altijd alleen op 1 veld wilt zoeken zou je het wel snel uit een bestand kunnen doen. Bestand moet gesorteerd zijn op dat veld; Elk veld heeft een vaste breedte; Je leest niet het hele bestand in, maar gebruikt fseek in een BinarySearch.

geeft zonder te zoeken: "een hond eet brokken".

Dat de code kort is betekent niet dat het snel gaat.

"zonder te zoeken" slaat alleen op echte arrays. De geheugenlokatie van een element is dan de geheugenlocatie van het begin plus index maal de grootte van een element. Oftewel zonder te zoeken vindt je met een simpele berekening in 1 keer het juiste element.

In Php zijn het geen echte arrays, maar associatieve arrays. Als je een element wilt, dan moet dit dus altijd gezocht worden door het hele array af te lopen (gebeurt intern).

[Verwijderd]

klopt inderdaad dat php arrays associatieve zijn maar de snelheid liegt er niet om.

een foreach over enkele 10.000 keys laten gaan kan in de seconden lopen terwijl php er intern bijna naar toe springt. php houdt volgensmij intern een duidelijke lijst met de key's en de bijbehorende reference zodat dit vele malen sneller is dan een array_search omdat de waarde van de array niet wordt ge-evalueerd. enkel de key's.

xml is inderdaad iets meer richting cvs maar wordt steeds meer gebruikt als configuratie bestand. dan nog is xml nooit bedoeld om 10.000 rows te herbergen. alleen het parsen van de structuur is al performance-hit waar je u tegen zegt.

ik denk dat de TS zich eens zou moeten gaan verdiepen in sqlite wat zeer geschikt is om grote databases aan stand-alone applicaties te koppelen zonder externe servers te hoeven draaien.

[Woy]

Daos schreef op vrijdag 16 maart 2007 @ 21:15:
[...]
In Php zijn het geen echte arrays, maar associatieve arrays. Als je een element wilt, dan moet dit dus altijd gezocht worden door het hele array af te lopen (gebeurt intern).

Ik geloof er niks van dat PHP intern alle elementen afloopt. Waarschijnlijk is het als een soort Hashmap geimplementeerd waardoor een element opvragen ook in grote datasets zeer snel zal gaan ( O(1) ). Het is dus ook een "simpele" berekening waar het geheugen adres uit voort komt.

[ Voor 8% gewijzigd door Woy op 20-03-2007 15:55 ]

[ReverendBizarre]

Arrays in PHP zijn inderdaad als hashmap geimplementeerd en bovendien nog zwaar geoptimaliseerd. Dat hij intern alle items gaat aflopen is dus niet waar.