PHP - Breitensuche

Michael E.

Shade Of Mine schrieb:

Du hast O(N) speicherkomplexitaet wenn ich das richtig sehe.

Eine Adjazenzmatrix hat die Größe n². Macht bei 300 Knoten 90000 Einträge. Viel billiger kommt man hier weg, wenn man eine Adjazenzliste benutzt, die nur ~~900~~ 1800 Einträge benutzt. Dann läuft der Algorithmus nebenbei auch noch deutlich schneller.

Shade Of Mine

triptop schrieb:

willst du mich ärgern? wenn eine php version 10 anfragen pro sek. schafft, aber eine c version 1000 pro sek., wie macht dann ein vor- oder nachgeschalteter loadbalancer php schneller

Und wenn PHP 1000 pro Sek schafft und C nur 10 dann ist PHP schneller.

Was ist der Sinn von so einem Schwachfug?

klar, sind 100 php instanzen dann gleich schnell wie eine c instanz aber doch nicht wie 100 c instanzen!

Du hast nur 1 PHP Instanz aber N C++ Instanzen. DAS ist der Punkt. C++ ist nicht trivial Skalierbar auf den Server zu bekommen. CGI, FastCGI, etc. ist alles Schrott. Du brauchst einen App Server. Da gibts nicht viele die was bringen. Und selbst dann gewinne ich idR durch andere Methoden mehr Performance.

Die Sprache ist idR komplett uninteressant.

@Michael E.:
Und das müsste sich eigentlich in einer Tabellenstruktur abspeichern lassen. Damit kann ich direkt über SQL darauf suchen.

Und alles was ich in der DB halten kann, ist halt enorm schnell und skaliert wie sau

Shade Of Mine schrieb:

Und alles was ich in der DB halten kann, ist halt enorm schnell und skaliert wie sau

okay, ich denke wir lassen das jetzt. ich geh jetzt bischen spazieren und dann gibts krieg in der champions league

314159265358979

Shade Of Mine schrieb:

Und wenn PHP 1000 pro Sek schafft und C nur 10 dann ist PHP schneller.

Was ist der Sinn von so einem Schwachfug?

http://i3.kym-cdn.com/photos/images/newsfeed/000/218/902/this%20is%20a%20viking%20biker%20arguement%20invalid.jpg
Ehrlich, so viel Mist hab ich schon ewig nicht mehr gelesen, musste fast lachen.

Aber extra für dich, ein kleines Benchmark, damit du einsiehst, was für fatalen Mist du von dir gibst. Gegeben seien die beiden folgenden Programme:

<?php
	function fib($n)
	{
		return $n > 1 ? fib($n - 1) + fib($n - 2) : 1;
	}

	$begin = microtime(true);
	echo fib(35);
	$end = microtime(true);

	echo "<br />".($end-$begin);
?>

#include <iostream>
#include <ctime>

unsigned fib(unsigned n)
{
	return n > 1 ? fib(n - 1) + fib(n - 2) : 1;
}

int main()
{
	auto begin = std::clock();
	std::cout << fib(35);
	auto end = std::clock();

	std::cout << "<br />" << (end - begin) / static_cast<double>(CLOCKS_PER_SEC);
}

Ausgabe PHP:

14930352
16.2973461151

Ausgabe C++:

14930352
0.0403

Ohne Worte...

Zeus

Mein Gott, bist du schlecht in deine Haut will ich nicht sein. Ich bin mit JavaScript viel schneller

function fib(n)
{
    return n > 1 ? fib(n-1) + fib(n-2) : 1;
}
var start = new Date();
console.log(fib(35));
var end = new Date();
console.log((end - start) / 1000);

14930352
0.288

pyhax

Berechne es doch mit Template Magie zur Compile Zeit, dann bist du schnell

314159265358979

@Zeus: Immerhin Faktor 3. Gar nicht mal so schlecht für eine Scriptsprache, hätte mit mehr gerechnet.

pyhax schrieb:

Berechne es doch mit Template Magie zur Compile Zeit, dann bist du schnell

Das wäre doch geschummelt.

Zeus

314159265358979 schrieb:

@Zeus: Immerhin Faktor 3. Gar nicht mal so schlecht für eine Scriptsprache, hätte mit mehr gerechnet.

Ist es auch Faktor ~7.

314159265358979 schrieb:

pyhax schrieb:

Berechne es doch mit Template Magie zur Compile Zeit, dann bist du schnell

Das wäre doch geschummelt.

Können wir die Compilezeit mitrechnen, dann würde C++ verlieren

314159265358979

Zeus schrieb:

Ist es auch Faktor ~7.

LOL, hab ich mich doch tatsächlich dabei verrechnet. Wie peinlich

zwutz

314159265358979 schrieb:

Aber extra für dich, ein kleines Benchmark, damit du einsiehst, was für fatalen Mist du von dir gibst. Gegeben seien die beiden folgenden Programme:

spielt das eine Rolle? Ernsthaft? Ergebnis wird gecached und der nächste hats in ner 100stel Sekunde, irrelevant also. Sowas wird im Webbereich niemals ständig neu berechnet. Wär ja unsinnig, wenn die Ergebnismenge endlich ist

PHP _ist_ langsamer, da sind wir uns einig. Eine Skriptsprache kann nunmal nicht gegen eine kompilierte Sprache bestehen. Wer sowas vergleicht hat aber mMn nicht wirklich die Stärken von Skriptsprachen verstanden. In der Praxis (also das Ding, was später auch Relevanz hat) ist die Laufzeit der PHP-Skripte irrelevant. Was wichtig ist, sind Filesystem- und Datenbank-Zugriffe. memcached oder ne Datenbank installieren und deine fibonacci-Seuche ist Geschichte. Was länger dauert, wird über nen jobworker oder cron im Hintergrund ausgeführt. Du bist hier nicht im Desktop-Bereich, wo man nach dem Mausklick ein Ergebnis haben will. Allein der Ping zum Webserver ist idR weit höher als die Skriptausführungszeit.

Wir setzen PHP als Skriptsprache ein und wenn wir mal Probleme wegen der Geschwindigkeit der Abfrage haben, dann ist nicht PHP der Grund (ok, außer wenn wir wegen eines Skriptfehlers mal wieder 10^9 verschiedene Varianten berechnen; da macht aber auch der Server schlapp)

Klar hat PHP Grenzen, aber die muss man erstmal erreichen. Und selbst dann gibt es Auswege (hiphop z.B.)

Im Übrigen berechnen nur Idioten den Fibonacci rekursiv, weil der, im Gegensatz zur iterativen Variante, exponentielle Laufzeit hat.

LOL Alter! Wenn ich was von diesem PI lese, roflt es mir regelrecht eine Glatze. Im wahrsten Sinne lolt es mich gerade quer durchs Treppenhaus, wenn ich seine dummen Kommentare über Skriptsprachen lese.

Achja, zum eigentlichen Problem:
Die Breitensuche dieser Größenordnung ist auch für PHP kein Problem. Nimm eine Adjazenzliste, um die Daten sinnvoll zu kodieren. Sei der Graph mit G = (V,E) gegeben, wobei V die Knotenmenge, E die Kantenmenge, so benötigt die Breitensuche O(|V| + |E|) = O(n).

314159265358979

Ihr seid halt einfach nur zu blöd, die Message in meinem Text zu verstehen. Ob der Algorithmus schlecht ist, spielt überhaupt keine Rolle. Ob man das mit Caching optimieren kann, ist ebenso scheißegal.

Der TE meinte, wenn der Algorithmus in PHP zu langsam ist, nimmt er einen anderen. Vielleicht eher die richtige Programmiersprache für rechenintensives Zeug aussuchen, anstatt zu behaupten, der Algorithmus wäre ungeeignet. DAS ist die Message.

Learn to read. Learn to understand.
fcktards

zwutz

314159265358979 schrieb:

fcktards

Und du erwartest dann ernsthaft, dass man mit dir diskutieren will?

314159265358979

Die Diskussion ist für mich gelaufen, ihr habt euch disqualifiziert.

314159265358979 schrieb:

Der TE meinte, wenn der Algorithmus in PHP zu langsam ist, nimmt er einen anderen. Vielleicht eher die richtige Programmiersprache für rechenintensives Zeug aussuchen, anstatt zu behaupten, der Algorithmus wäre ungeeignet.

lol, PIs gesicht möcht ich sehen wenn er in 5 Jahren zum ersten Mal in einem Hörsal sitzt und der Dozent versucht ihm das auszutrichtern

> Wenn der Algorithmus zu langsam ist einfach mal eine andere Sprache benutzen, und dann am besten das assembler optimieren

weißt du wie oft ich schon in js/php implementierten algorithmen gelesen hab, dass sie von c portiert wurden?

es gibt ein level an abstraktion, ab dem man einfach langsamer wird, weil man sich ständig für überdimensionierte algorithmen und datenstrukturen entscheidet. automatische typumwandlungen und immutable strings erledigen dann meist den rest.

jeder der hier behauptet, dass es nur auf den algo ankommt hat einfach keinen plan vom business... denn meist haben besser bezahlte programmierer auch mehr ahnung von algorithmen und der hardware und php ist neben js eine der schlecht bezahltesten sprachen der welt!

Bashar

triptop schrieb:

denn meist haben besser bezahlte programmierer auch mehr ahnung von algorithmen und der hardware und php ist neben js eine der schlecht bezahltesten sprachen der welt!

Die bestbezahlten Programmierer sind laut c't für COBOL, ABAP und ähnliche Grausamkeiten unterwegs (ich hab die Ausgabe nicht mehr vorliegen, vielleicht mag das nochmal jemand verifizieren), das sind mit Sicherheit keine Algorithmen- oder Hardware-Experten. Am Gehalt würde ich es also nicht festmachen.

triptop schrieb:

jeder der hier behauptet, dass es nur auf den algo ankommt hat einfach keinen plan vom business... denn meist haben besser bezahlte programmierer auch mehr ahnung von algorithmen und der hardware und php ist neben js eine der schlecht bezahltesten sprachen der welt!

Ahja, es kommt nicht nur auf den Algorithmus an, denn besser bezahlte Programmierer haben mehr Ahnung von Algorithmen. LOL Alter! Wenn ich sowas lese, roflt es bei mir das Frühstück wieder hoch.

Die untere Schranke wurde mit O(n) schon genannt, die algorithmische Analyse ist damit abgeschlossen, die optimale Suche ist trivial. Dass PHP langsamer als eine C-Implementierung ist, hat hier niemand behauptet. Und generell kommt es natürlich nicht nur auf den Algorithmus an. Aussage hier war: in den meisten Fällen spielen bei Webanwendungen andere Kriterien eine Rolle.

Hast du das jetzt geschnallt? Wenn ja, erklär es noch PI.

Äh PHP "schneller" hat niemand behauptet!
LOL Alter! Wenn ich sehe, was ich schreibe, roflt es mir die Zehnägel quer.