Login
Newsletter
Werbung

Thema: Google Programming Contest

38 Kommentar(e) || Alle anzeigen ||  RSS
Kommentare von Lesern spiegeln nicht unbedingt die Meinung der Redaktion wider.
0
Von TBO am Mi, 6. Februar 2002 um 20:32 #
Da will google wohl billig an schnellere Software kommen ;-)

Mich würde sowieso mal interessieren,
welche Rechenleistung und welche Algorithmen bei Google bzw. bei Suchmaschinen im Einsatz sind.
Wie kann man solche riesigen Datenmengen in so kurzer Zeit durchsuchen?
Den Quellcode werd ich mir mal ziehen, vielleicht komm ich ja irgendwann dazu, da mal reinzuschauen...

[
| Versenden | Drucken ]
  • 0
    Von panthera am Mi, 6. Februar 2002 um 20:35 #
    ich hab mal irgendwo gelesen, dass es linux-cluster sind, 8000 an der zahl.
    [
    | Versenden | Drucken ]
    0
    Von LiNFaN am Mi, 6. Februar 2002 um 22:00 #
    Da gibts ganz tolle mathematische Tricks so riesige Datenmengen zu durchsurchen ;)

    Wenn du dich dafür interessierst, solltest du entweder Informatik studieren oder ein gutes Algorithmenbuch über Suchalgorithmen kaufen ;)

    Was recht interessant ist z.B. Fourier-Transformation, Binärbäume verknüpft mit den bekannten Suchalgorithmen wie Heapsort, Quick-, Mergesort.

    [
    | Versenden | Drucken ]
    0
    Von Martin Röhricht am Mi, 6. Februar 2002 um 22:10 #
    Wird da nicht einfach eine Hash-Tabelle aufgebaut, die in O(n log n) den Baum durchsucht?
    Da hast Du ja dann bei so riesen Datenmengen gewonnen.
    [
    | Versenden | Drucken ]
    0
    Von TBO am Mi, 6. Februar 2002 um 22:14 #
    @LinFan: Ich studiere Informatik :-))

    Die Algos sind mir ja auch alle bekannt (auch wenns keine Such- sondern Sortieralgorithmen sind),
    aber wenn Google da noch
    Verbesserungspotential sieht, geht
    das wohl über die Standardalgorithmen
    hinaus. Bzw. sie werden irgendwie besonders trickreich angewandt.
    Sonst hätten sie das wohl auch schon selbst hinbekommen.

    Achja: Ich kenne
    Fouriertransformation bisher nur
    aus der E-Technik, kannst Du mich da
    über den Zusammenhang zu Suchen/sortieren aufklären?

    [
    | Versenden | Drucken ]
    0
    Von Anonymous am Mi, 6. Februar 2002 um 22:27 #
    Ich denke, hier geht es sich nicht um neue Suchalgorithmen, sondern darum, wie man Bestehende am effektivsten parallelisiert, das ist nämlich ne Kunst für sich, eine Aufgabe sinnvoll auf viele Rechner zu verteilen.
    [
    | Versenden | Drucken ]
    0
    Von Martin Röhricht am Mi, 6. Februar 2002 um 22:30 #
    Ich sehe auch keine Anwendung von Fourier, da damit ja nur eine schnellere Polynommultiplikation erzielt werden kann (FFT).
    Aber wie mein Vorredner schon ansprach: Parallele Algorithmen geben da vielleicht den Ausschlag.
    [
    | Versenden | Drucken ]
    0
    Von TBO am Mi, 6. Februar 2002 um 22:31 #
    Hmm,
    Suchraum in kleinen Häppchen auf die Cluster verteilen? Sollte eigentlich
    recht gut parallelisierbar sein. Sag ich mal so in meiner jugendlichen
    Naivität ;-)
    Aber stimmt schon, es gibt da bestimmt noch viele Möglichkeiten
    zu tricksen.
    [
    | Versenden | Drucken ]
    0
    Von Anonymous am Do, 7. Februar 2002 um 17:00 #
    @Martin Röhricht: Viel Spass mit Hashen! Die Hastables sind immer grösser als die eigentlichen Datentabellen, das mag recht lange gut gehen, aber bei Googles Datenbeständen bestimmt nicht mehr.
    Sicher Hashing ist schnell, aber nicht unbedingt speicher freundlich (sonst ist es nicht mehr schnell ;) da alle Hash-Codes wenn möglich eindeutig sein sollten.
    Also mit Hashing alleine kommt man nicht weit bei ner Suchmaschine.
    [
    | Versenden | Drucken ]
    0
    Von Anonymous am Do, 7. Februar 2002 um 20:23 #
    Wie überall machts die Kombination. Ein Hashtable zum Beispiel mit der IP als Key und von dortaus Trees. Natürlich bräuchte man einen zweiten Key weil Unterseiten ja über die gleiche IP-angesprochen werden (könnte man über den pfadnamen hinbekommen). Die Performance ist mathematisch gut zu belegen (findet man auch alles sehr gut beim Sedgewick beschrieben)
    [
    | Versenden | Drucken ]
    0
    Von Prefect am Fr, 8. Februar 2002 um 08:54 #
    Hallo

    Ich denke hier geht es wohl eher um die Qualität der Ergebnisse. Also dass beim Suchbegriff "Samba" nicht Dieter V's "Meine besten Tanzfotos" ganz oben steht, sondern eher www.samba.org oder so.

    Performanceverbesserungen durch Parallelisierung können die meisten wohl schlecht zu Hause entwickeln. (es sei denn, man kann die Rechner der ganzen WG mißbrauchen)

    Schöne Grüsse, Prefect


    [
    | Versenden | Drucken ]
0
Von jensemann am Mi, 6. Februar 2002 um 20:39 #
57MB!!!
Ist das etwa alles Quellcode? Ich hätte nicht gedacht das da so viel drin ist, aber gut man lernt ja niemals aus. Bitte nicht falsch verstehen, das das mehr als 2000 Zeilen sind, war mir auch vorher klar.
Mfg jensemann
[
| Versenden | Drucken ]
0
Von Anonymous am Mi, 6. Februar 2002 um 21:02 #
>If you prefer, we will mail you the code and data on a set of five CDs

oder saugen:
>http://research.google.com/contest/prog-contest-sample.tar - 57M

Irgendwas passt da nicht, oder?

[
| Versenden | Drucken ]
0
Von Anonymous am Mi, 6. Februar 2002 um 21:19 #
ich hab immer gedacht hinter google steckt ein einfacher such algorithmus. naja, jetzt wurde ich ja überzeugt ;-)

das es ein cluster sein soll aus mehreren rechnern (!) hat mich auch überrascht!!

hehe, google ist halt DIE linux suchmaschine!!

[
| Versenden | Drucken ]
0
Von arni am Mi, 6. Februar 2002 um 21:23 #
Gibt es eigentlich noch andere Suchmaschinen als Google? Kann mich garnicht mehr so recht erinnern :))
[
| Versenden | Drucken ]
0
Von Stefan Antoni am Mi, 6. Februar 2002 um 22:12 #
mhh. C++ und Java, war google nicht mal in python geschrieben?
oder ist es in jython implementiert?
oder war das mit python eine fehlinfo?
[
| Versenden | Drucken ]
  • 0
    Von Anonymous am Mi, 6. Februar 2002 um 22:23 #
    Letzteres ist richtig.
    [
    | Versenden | Drucken ]
    0
    Von Martin Röhricht am Mi, 6. Februar 2002 um 22:32 #
    Also ich kenne Python nicht selbst, aber an C geht hier doch eigentlich kein Weg vorbei, oder?
    Und ich glaube auch nicht, dass hier ein Hauptbetätigungsfeld der Objektorientiertheit liegt ...
    [
    | Versenden | Drucken ]
    0
    Von Anonymous am Do, 7. Februar 2002 um 09:12 #
    olala, also zu einer Suchmaschine gehört bekanntlich mehr, als nur der Suchalgorithmus, den der Nutzer sieht (und schätzt). Zunächst muß man crowlen, also im Web nach Webseiten suchen und die analysieren. Und das entsprechend aufbereiten, damit man dann darauf suchen kann. Dazu wird bei Google z.T. auch python verwendet. Das alles ist ziemlich komplex, um es stabil und ausreichend schnell zu machen. Das ist im wesentlichen keine Frage der Programmiersprache, sondern der Technik. Es geht hier ja nicht um den Inhalt von ein paar Festplatten ... aber dazu gibt es ziemlich viele Infos von google selbst, also wer sich dafür interessiert, der schaue doch mal bei google nach ...
    [
    | Versenden | Drucken ]
    0
    Von Anonymous am Do, 7. Februar 2002 um 09:31 #
    Die von Goggle gelieferte Sourcen sind übrigens in C++ geschrieben. Eine gute objektorientierte Programmierung hat nur wenig mit dem Verwendungszwecks des zu erstellenden Programms zu tun.

    dil

    [
    | Versenden | Drucken ]
    0
    Von Martin Röhricht am Do, 7. Februar 2002 um 14:52 #
    Also Objektorientierung hat ja sehr wohl etwas mit der Verwendung zu tun.
    Und im allgemeinen erlebst Du Geschwindigkeitseinbussen durch OO. Du erreichst natürlich eine viel bessere Modularität und Übersicht, aber es hat schon seinen Grund, warum bspw. Treiber unter Windows in C und nicht C++ geschrieben werden.
    [
    | Versenden | Drucken ]
0
Von Anonymous am Do, 7. Februar 2002 um 00:32 #
andere suchmaschinen?

www.alltheweb.com sind schnell und gute advanced funktionen, aber die ergebnisse sind doch leider n bischen schlechter als google :)is nur noch suchmaschine 2. wahl

[
| Versenden | Drucken ]
0
Von RPR am Do, 7. Februar 2002 um 02:02 #
Google ist zwar anscheinend echt gut und so weiter, aber es würde mich schon mal interessieren, warum deren Spider nicht über dynamische Webseiten geht.
Vielleicht sollte "man" das mal implementieren, sonst geht in naher Zukunft ein grosser Teil der Informationen an Google vorbei...

Greets :-)

[
| Versenden | Drucken ]
  • 0
    Von Andreas am Do, 7. Februar 2002 um 09:40 #
    Überleg mal, wieso. Was macht es für einen Sinn, heute eine Seite zu indizieren, die morgen oder eine Stunde später schon einen anderen Inhalt haben kann? Da kommt es eher auf gute Archivierung an.
    [
    | Versenden | Drucken ]
    0
    Von Heiko am Do, 7. Februar 2002 um 10:21 #
    machen Sie.

    Es ist mittlerweile (google) egal, ob eine Datei mit *.html, *.php oder was weiß ich endet. Auch werden Parameter beachtet (index.php?page=2 etc.) und bei der Indizierung berücksichtigt.

    [
    | Versenden | Drucken ]
    0
    Von RPR am Do, 7. Februar 2002 um 14:42 #
    @ Andreas:
    Ds kann mit HTML-Seiten auch passieren, oder?
    Der einzige Unterschied ist, dneke ich, dass HTML-Seiten per FTP und dynamische Seiten per HTTP, ODBC oder sonst wie aktualisiert werden.

    @ Heiko:
    Echt?
    Gute Neuigkeiten. Muss ich gleich mal ansehen... :-)

    [
    | Versenden | Drucken ]
0
Von Kay am Do, 7. Februar 2002 um 13:19 #
Also, ich bezweifle, dass jemand einen noch schnelleren Algo hinkriegt, als die von Google. Hinter Google stecken viele Software-Ingenieure, die lange gearbeitet haben, und die sind auch nicht blöd. Jetzt soll einer einfach kommen und in dieser kurzen Zeit so aus dem Ärmel einen besseren Algo, der alle anderen Suchmaschinen in fast allen Punkten schlägt, schütteln?
[
| Versenden | Drucken ]
  • 0
    Von Florian am Do, 7. Februar 2002 um 14:41 #
    Also wenn ich den englischen Text richtig gelsen habe soll der eingesendete Code etwas ineterressantes mit den Daten machen. Also denke ich mal, dass die eher auf der Suche nach neuen Funktionen sind...
    [
    | Versenden | Drucken ]
0
Von Anonymous am Do, 7. Februar 2002 um 16:19 #
Glaubt ihr wirklich, dass in dem downloadbaren Archiv die "original" Google Suchmaschine steckt, denn wenn das wirklich so wäre, hätte sie ja ihren technologischen Vorsprung gegenüber anderen Suchmaschinen in programmtechnischer Hinsicht verloren ?!
[
| Versenden | Drucken ]
  • 0
    Von grovel am Do, 7. Februar 2002 um 20:55 #
    Nach deiner Meinung hat also Linux seinen technologischen Vorsprung gegenüber Microsoft in programmtechnischer Hinsicht verloren?
    [
    | Versenden | Drucken ]
    0
    Von Anonyümous am Mo, 11. Februar 2002 um 23:27 #
    He, He! Dann brauchst du ja mindestens so grosses Entwicklerteam, wie es google hat um die Sourcen anzupassen und zu sichten. Wenn alle Informationen immer und ewig geheimgehalten wordne wären, hätte sich die Menschheit nie entwickelt. ;) It's for the future, not for now!
    [
    | Versenden | Drucken ]
Pro-Linux
Pro-Linux @Facebook
Neue Nachrichten
Werbung