[PHP] Hoogste row van grid

[Hellion]

Beste Tweakers,

Voor een hobby project ( EVE Online! ) ben ik een weergave grid aan het maken hoe systemen met elkaar verbonden zijn. Misschien het beste uit te leggen met mijn perfecte paintskills;


Stel vanuit X wil ik een systeem toevoegen, dan wil ik de hoogst aangesloten row, in dit voorbeeld Y (row 5). Nu is dit een klein voorbeeld maar ik moest dus op de één of andere manier door alle aangesloten systemen heen om te zien welke de hoogste row heeft.

Wat ik al heb geprobeerd/ideeën
- (binary/recursive) tree search, hiervoor moet ik eigenlijk al het eindpunt weten wat ik nog niet heb
- A* search algorithm, idee was om alle connecties met het systeem in array op te slaan en dan de hoogste row uit het array te selecteren, maar hier heb je ook eigenlijk al een eindpunt voor nodig (wat ik ervan begreep)
- foreach loop vanuit de database, alleen hoe laat ik deze dan loopen door alle systemen en weer terug gaan als er geen hogere row is gevonden.

Hopelijk is het een (klein) beetje duidelijk en kan iemand mij hierbij helpen of in de juiste richting sturen. Breek mijn hoofd hier al dagen op

[Ventieldopje]

Over hoeveel aangesloten systemen hebben we het dan (in één kolom dus?), als het er niet veel zijn zie ik niet in waarom een simpele foreach niet voldoet

(bedoel je met systemen trouwens ook echt de constellations? Dat zijn er nooit zo veel, hooguit een stuk of 10 bij grote voor zover ik weet). Iets meer EVE related info zou makkelijk zijn

[ Voor 7% gewijzigd door Ventieldopje op 22-09-2016 13:46 ]

[Hellion]

In theorie oneindig, in praktijk zal er waarschijnlijk nooit een groter grid zijn dan 25 (column) bij 25 (rows).

foreach was mijn eerst oplossing maar hoe laat ik die dan alleen door de systems heen gaan die verbonden zijn (en dan weer daaraan verbonden etc etc.)?

[Der Rudi]

Lijken me hierarchische lijsten welke je wilt gebruiken.

Als dat idd zo is, is er http://stackoverflow.com/...-in-a-relational-database en https://www.sitepoint.com/hierarchical-data-database/ meer info over te vinden. Een google actie op een of meer in de links aangegeven key words geeft meer info.

[Hellion]

@Der Rudi dat zou me inderdaad welleens kunnen helpen, snel even overheen gelezen maar vooral de link van sitepoint zit op de goede weg, vanavond eens op men gemak kijken

@Ventieldopje het gaat om een Wormhole mapper, die aangesloten wormholes in kaart brengt (met extra intel natuurlijk). Een leuk project met SSO en CREST en zoveel mogelijk intel integratie.

[Bloemkoolsaus]

Je gaat een recursieve functie nodig hebben. Voor elk volgend systeem bereken je de volgende verbinding(en) totdat je niet verder kunt.

Maar, waarom teken je je map niet met een canvas? Dat is technisch een stuk makkelijker uit te voeren. Bovendien kan ik uit ervaring vertellen dat een mapper die weergeeft zoals je voorstelt erg snel onduidelijk wordt (en dus geen voordeel bied).

Vergelijk deze 2 voorbeelden eens:
Wat jij wilt maken (of althans, zoals ik het begrijp uit je post): http://i.imgur.com/V9FXY6r.png
Of eentje getekend op een canvas: http://i.imgur.com/PEoDfuI.png

[ Voor 2% gewijzigd door Bloemkoolsaus op 22-09-2016 15:07 . Reden: tiepvaut ]

[DJMaze]

Je probleem is simpel en kan prima met een flat list zolang er een parent is.

SQL:

CREATE TABLE tree (
    tree_item_id SERIAL,
    parent_tree_item_id INT NOT NULL DEFAULT 0,
    tree_item_name VARCHAR(64) NOT NULL
);

PHP:

$list = array();
$result = mysqli_query("SELECT * FROM tree");
foreach ($result as $item) {
    if (!isset($list[$item['parent_tree_item_id']])) {
        $list[$item['parent_tree_item_id']] = array(
            'id' => $item['parent_tree_item_id'],
            'parent' => null,
            'name' => null,
            'children' => array(),
        );
    }
    if (isset($list[$item['tree_item_id']])) {
        $list[$item['tree_item_id']]['parent'] = &$list[$item['parent_tree_item_id']];
        $list[$item['tree_item_id']]['name'] = $item['tree_item_name'];
    } else {
        $list[$item['tree_item_id']] = array(
            'id' => $item['tree_item_id'],
            'parent' => &$list[$item['parent_tree_item_id']],
            'name' => $item['tree_item_name'],
            'children' => array(),
        );
    }
    $list[$item['parent_tree_item_id']]['children'][] = &$list[$item['tree_item_id']];
}

print_r($list[0]);

// Krijg parents van item 5
$parent = $list[5]['parent'];
while ($parent) {
    var_dump($parent['id']);
    $parent = $parent['parent'];
}

Je kan dan met die $list dus alles doen wat je maar wilt.

[ Voor 5% gewijzigd door DJMaze op 22-09-2016 16:34 ]

[Hellion]

Wat kan het leven toch simpel zijn soms, frisse kijk erop helpt. Het stukje code uit de link van sitepoint hergebruikt en het werkt nu;

PHP:

private function calculateRow($solarSystemID, $level) {
       
        $ste = DB::prepare("SELECT `solarSystemName`, `solarSystemID`, `row` FROM `mapCurrent` WHERE `linkedTo`=:solarSystemID ");
        $ste->bindParam(':solarSystemID', $solarSystemID);
        $ste->execute();
        
        while($row = $ste->fetch()) {
            
            if($row['row'] > $this->_newRow) {
                
                $this->_newRow = $row['row'];
                
                
            }
            
            $this->calculateRow($row['solarSystemID'], $level+1); 
         
        }
    }

Nu is dit natuurlijk beetje SQL heavy omdat voor elke iteratie een SQL query uitgevoerd dus ik zal zeker nog kijken of de methode van DJMaze me ook zover kan krijgen.

Bedankt iedereen voor het meedenken!

@bloemkoolsaus; behalve dat ik geen ervaring heb met het generen van zulke canvassen, ik en de corp waar ik zit zijn er niet zo fan van. Je blijft dingen naderhand wijzigen, en iedereen heeft zijn eigen manier van het vormen van zo'n chain.

[DJMaze]

Hellion schreef op donderdag 22 september 2016 @ 20:53:
Nu is dit natuurlijk beetje SQL heavy omdat voor elke iteratie een SQL query uitgevoerd dus ik zal zeker nog kijken of de methode van DJMaze me ook zover kan krijgen.

Beide zijn een oplossing. De vraag is of je 100 records hebt of 100.000.001, en of de nesting 4 levels is of 101, en of de juiste indices bestaan.
In geval van 4 levels is 4 queries helemaal zo gek nog niet en volstaat jouw code prima.
Het grootste nadeel van je code is de query statement. Run je code maar eens gewoon als

PHP:

DB::query("SELECT solarSystemName, solarSystemID, row FROM mapCurrent WHERE linkedTo=" . intval($solarSystemID))

En je zal zien dat dat veel sneller is.

P.S. ja ik gebruik geen `backtiks` in de code, het is zo niet de ANSI standaard.
En je programmeert blijkbaar op Windows OS, anders weet je de consequenties van je hoofdletter gebruik

[ Voor 11% gewijzigd door DJMaze op 22-09-2016 21:45 ]

[Hmail]

Het is zeker geen slechte zaak om jezelf aan te leren altijd met prepared statements te werken. Je elimineert daarmee direct het risico op SQL injecties en je code wordt er een stuk leesbaarder van. De performance winst die je zou behalen door concatenation weegt m.i. niet op tegen de voordelen.

Daarnaast zou ik ook kiezen voor de recursieve variant, het is gewoon een stuk dynamischer. Je zult net zien dat je hierna een actie wilt doen als een parent geen childs heeft en daarvoor moet je in DJMaze's code de hele array nog een keer doorlopen.

Dus ik zou de code aanhouden die je nu hebt. Ziet er een stuk cleaner uit.

[DJMaze]

Hmail schreef op vrijdag 23 september 2016 @ 08:38:
Je zult net zien dat je hierna een actie wilt doen als een parent geen childs heeft en daarvoor moet je in DJMaze's code de hele array nog een keer doorlopen.

Die snap ik niet. Leg eens uit?

Hmail schreef op vrijdag 23 september 2016 @ 08:38:
Het is zeker geen slechte zaak om jezelf aan te leren altijd met prepared statements te werken. Je elimineert daarmee direct het risico op SQL injecties en je code wordt er een stuk leesbaarder van. De performance winst die je zou behalen door concatenation weegt m.i. niet op tegen de voordelen.

Dat je SQL injectie wil elimineren begrijp ik, maar daar zijn statements eigenlijk niet voor gemaakt.
Ik vond dit ooit een interessant artikel: http://edorian.github.io/...sqli-prepared-statements/
Maar we weten natuurlijk niet wat die "static class DB" is en doet (sowieso is static een slechte manier hier).

[ Voor 55% gewijzigd door DJMaze op 23-09-2016 12:09 ]

[Hellion]

Jullie gaan al een stukje verder dan mijn kennis (doe dit alleen voor hobby, en alles zelf geleerd).

Ja, ik programmeer op windows en hosting is linux, hoofdletter gebruik komt voornamelijk door de DB die aangeleverd is vanuit EVE Online en wil daarom de consistentie houden.

Ooit toen ik PDO aan het uitvinden was heb ik (meerdere malen) gelezen dat eigenlijk elke query waar een gebruiksinput bij zit een prepared statement zou moeten zijn, ook al heb je de variable server-side gecontroleerd. Dat de prepared statements hier in origine niet voor bedoeld waren wist ik niet.

De "Static class DB" is iets wat ik redelijk lang geleden ooit heb gekopieerd van een guide, het werkt maar geen flauw idee of het goed of slecht is.

PHP:

class DB { 
    
    private static $objInstance; 
   
    private function __construct() {}    
    private function __clone() {} 
    
    public static function getInstance(  ) { 
            
        if(!self::$objInstance){ 
            self::$objInstance = new PDO('mysql:host='.db_host.';dbname='.db_database.';charset=utf8', db_username, db_password, array(PDO::ATTR_PERSISTENT => true)); 
            self::$objInstance->setAttribute(PDO::ATTR_ERRMODE, PDO::ERRMODE_EXCEPTION); 
        } 
        
        return self::$objInstance; 
    
    } 
    
    final public static function __callStatic( $chrMethod, $arrArguments ) { 
            
        $objInstance = self::getInstance();         
        return call_user_func_array(array($objInstance, $chrMethod), $arrArguments); 
        
    }
}

[Bloemkoolsaus]

Hellion schreef op vrijdag 23 september 2016 @ 12:31:
Ja, ik programmeer op windows en hosting is linux, hoofdletter gebruik komt voornamelijk door de DB die aangeleverd is vanuit EVE Online en wil daarom de consistentie houden.

Dat probleem herken ik

Let wel op dat MySQL op windows is niet hoofdletter gevoelig is voor zijn tabelnamen, maar op Linux wel!! Een foutje is zo gemaakt en ik heb ook wel eens uren zitten zoeken naar zo'n foutje omdat je ontwikkel en productie omgeving verschillen (windows/linux).

Ik gooi de data export altijd nog even door een scriptje wat alles renamed naar lowercase tabel/kolom namen.

[Hmail]

DJMaze schreef op vrijdag 23 september 2016 @ 11:54:
[...]
Die snap ik niet. Leg eens uit?

Wat me zo even te binnen schiet...

PHP:

$childs = [];
foreach($rows as $child) 
{
  if($currentUser->hasAccessTo($child)) 
    $childs[] = $child;
}
if(count($childs) <= 0)
   $parent->visible = false;

Ofzo.. In jouw geval betekent dat dat je alsnog de volledige array structuur recursief door moet werken. In dit geval heb je direct alle childs van dezelfde parent tot je beschikking.

DJMaze schreef op vrijdag 23 september 2016 @ 11:54:
Dat je SQL injectie wil elimineren begrijp ik, maar daar zijn statements eigenlijk niet voor gemaakt.
Ik vond dit ooit een interessant artikel: http://edorian.github.io/...sqli-prepared-statements/
Maar we weten natuurlijk niet wat die "static class DB" is en doet (sowieso is static een slechte manier hier).

Een willekeurige website linken kan natuurlijk iedereen https://www.reddit.com/r/...ements_be_used_for_every/
Anyway, geheugenoptimalisatie is voor hobbyprojectjes min of meer zinloos, je hebt het hoogstens over milliseconden. En als je met mega datasets zit te werken hoor je ook een bijbehorend systeem te hebben dat op performance gebaseerd is. Het lijkt cool voor beginnende programmeurs, maar de realiteit is dat je onleesbare code aan het schrijven bent omdat je daarmee een paar honderd milliseconden tijdswinst krijgt. Die krijg je niet terug als je een jaar later een paar uur aan het uitzoeken bent waarom in sommige gevallen je query mislukt. En je opvolger zal je niet echt dankbaar zijn.

De regel dat je prepared statements moet gebruiken bij user input onderschrijf ik dus volledig, heck, doe het gewoon altijd, je hoeft je gelijk niet meer druk te maken over escaping en string concatenation, je query werkt gewoon.

[DJMaze]

De regel dat je prepared statements moet gebruiken is een keuze die je moet voorleggen.
Ik kom situaties tegen waarbij een statement gewoon een slechte keuze is.
Een VIEW, PROCEDURE, FUNCTION of gewoon een query blijken dan beter.
Natuurlijk moet je dan wel die kennis in huis hebben, anders zijn Statements inderdaad een defacto.

Wat meer impact is, is de DB class die hij gebruikt. Die zorgt voor veel meer overhead/vertraging door call_user_func_array().
En de vraag of die statement elke keer opnieuw wordt aangemaakt, of slechts 1x en dan alleen de bindParam steeds wordt aangepast:

PHP:

private function calculateRow($solarSystemID, $level) {
    static $ste;
    if (!$ste) {
        $ste = DB::prepare("SELECT `solarSystemName`, `solarSystemID`, `row` FROM `mapCurrent` WHERE `linkedTo`=:solarSystemID ");
    }
}

[ Voor 16% gewijzigd door DJMaze op 23-09-2016 17:42 ]