RE-Modul, die Entdeckung der Langsamkeit?

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Antworten
snakeseven
User
Beiträge: 405
Registriert: Freitag 7. Oktober 2005, 14:37
Wohnort: Berlin
Kontaktdaten:

Montag 20. Oktober 2008, 16:58

Moin,
will hier nicht provozieren, denn das RE-Modul ist eine wirklich tolle Sache, aber im 1:1 Vergleich mit der Zufuss-Methode mit der Stringfunktion "find", scheint es nicht gerade das Schnellste zu sein.
Ich denke mal, dass ich da was falsch gemacht habe, denn bei 50000 Durchläufen ist es bereits halb so schnell wie die Zufussmethode und bei 100000 Durchläufen sogar nur noch 1/3 so schnell. Hier mein Testscript:

Code: Alles auswählen

#!/usr/bin/env python
# -*- coding: UTF-8 -*-

import re, urllib2
from httplib import BadStatusLine
from time import localtime



def scansource1():        
    # duchsucht mit Hilfe des RE-Moduls eine Website nach Informationen
    expression1 = re.compile("www.myspace.com/([a-z]*)\s*</title>")
    expression2 = re.compile('width="175".*break-word">(.*)</td></tr>\s*</table>')
    expression3 = re.compile('<span class="nametext">(.*)</span><br>')
    expression4 = re.compile("</strong></font>\s*<br>\s*<br>\s*.*\s*<br>\s*(.*)")
    expression5 = re.compile('SWFObject\(\"http://musicservices.myspace.com/Modules/MusicServices/Services/Embed.ashx/ptype=4(.*)", "shell')
    
    url="http://profile.myspace.com/index.cfm?fuseaction=user.viewprofile&friendID=40254287"
    
    online = False
    try:
        u = urllib2.urlopen(url)
    except (urllib2.URLError, BadStatusLine): 
        pass        
    else:       
        online = True
        buffer = u.read() 
        try:
            source = unicode(buffer, 'iso-8859-15','replace')
        except:
            source = buffer
            
            
    if online:
        src1 = source[:60000]
        src2 = source[180000:190000]
        print localtime()[4:8]
            
        for i in range(50000):
            # Adresse
            address = str(re.findall(expression1, src1))[3:-2] 
            if address == '': address = 'invalid address'
            
             # Label
            label = str(re.findall(expression2, src1))[3:-2]  
            if label == '': label = 'no label found'
                    
            # Name
            name = str(re.findall(expression3, src1))[3:-2]                     
            if name == '': name = 'no name found'

            # Land
            country = str(re.findall(expression4, src1))[3:-3]     
            if country == []: country = 'no country found'
            
            # Playerurl
            playerurl = str(re.findall(expression5 , src2))[9:-2]  # without ap=1,
            if playerurl == '': playerurl = 'no player'

        print localtime()[4:8]
        print
        
        
        
        
def scansource2():        
    # hangelt sich von Keyword zu Keyword durch den Seitencode und sammelt Informationen
    url="http://profile.myspace.com/index.cfm?fuseaction=user.viewprofile&friendID=40254287"

    online = False
    try:
        u = urllib2.urlopen(url)
    except (urllib2.URLError, BadStatusLine): 
        pass        
    else:       
        online = True
        buffer = u.read() 
        try:
            source = unicode(buffer, 'iso-8859-15','replace')
        except:
            source = buffer


    if online:
        print localtime()[4:8]
            
        for i in range(50000):
            # Adresse
            pos1 = source.find('www.myspace.com',0)             
            pos2 = source.find('</title>',pos1)
            address= source[pos1+16:pos2-2]
            tst =  re.findall("[A-Z!$%&/()=?\{}*+#',.;:_<>|^-]",address)
            if len(tst) != 0: address = 'invalid address'
                
            # Name
            pos1 = source.find('"nametext"',0)
            if pos1 > 0: 
                pos2 = source.find('</span><br>',pos1)
                name = source[pos1+11:pos2].strip()
            else: 
                name = 'no name found'

            # Land
            pos1=source.find('user.viewAlbums&friendID=',pos2)
            if pos1 > 0: 
                pos2 = source.find('</strong></font>',pos1)
                if pos2 > 0: 
                    pos3 = source.find('<br>',pos2)
                    if pos3 > 0: 
                        pos4 = source.find('<br>',pos3+1)
                        if pos4 > 0: 
                            pos5 = source.find('<br>',pos4+1)
                            if pos5 > 0: 
                                pos6 = source.find('<br>',pos5+1)
                                if pos6 > 0: 
                                    country = source[pos5+5 : pos6].strip()
            
            # Label
            label = 'no label found'
            pos0 = 0                                                  
            pos1 = source.find('"lightbluetext8"',pos0)    
            if pos1 > 0: 
                pos2 = source.find('</table>',pos1)
                if pos2 > 0: 
                    pos3 = source.find('</td></tr>',pos2-40)
                    if pos3 > 0: 
                        pos4 = source.find('break-word">',pos3-20)
                        if pos4 > 0: 
                            label = source[pos4+12:pos3]
                                
            # Playerurl
            pos1 = source.find('SWFObject("')                 
            if pos1 > 0: 
                pos2 = source.find('", "',pos1)
                if pos2 > 0:
                    playerurl = source[pos1+11:pos2]    
                    playerurl = playerurl.replace('http://musicservices.myspace.com/Modules/MusicServices/Services/Embed.ashx/ptype=4,ap=1,','')
                    playerurl = playerurl.replace('http://musicservices.myspace.com/Modules/MusicServices/Services/Embed.ashx/ptype=4,ap=0,','')
                    
        print localtime()[4:8]
        print '------------'

                
scansource1()
scansource2()
Gruß, Seven
Leonidas
Administrator
Beiträge: 16024
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Montag 20. Oktober 2008, 17:12

snakeseven hat geschrieben:will hier nicht provozieren, denn das RE-Modul ist eine wirklich tolle Sache, aber im 1:1 Vergleich mit der Zufuss-Methode mit der Stringfunktion "find", scheint es nicht gerade das Schnellste zu sein.
Natürlich ist es recht langsam, da Reguläre Expressions über einen Zustandsautomaten ablaufen und nicht einfach über eine lineare Suche.

Siehe auch Regular Expression Matching Can Be Simple And Fast.

PS: Zum parsen von HTML mit regulären Ausdrücken kann man eigentlich nur sagen... ähm, umständlich, um's mal freundlich auszudrücken.
My god, it's full of CARs! | Leonidasvoice vs Modvoice
lunar

Montag 20. Oktober 2008, 18:13

snakeseven hat geschrieben:will hier nicht provozieren, denn das RE-Modul ist eine wirklich tolle Sache
Man munkelt ja, echte HTML-Parser seinen noch toller zum Parsen von HTML ...
snakeseven
User
Beiträge: 405
Registriert: Freitag 7. Oktober 2005, 14:37
Wohnort: Berlin
Kontaktdaten:

Montag 20. Oktober 2008, 18:49

lunar hat geschrieben:Man munkelt ja, echte HTML-Parser seinen noch toller zum Parsen von HTML ...
Ja, ich hab mir auch mal die Dokumentation zu einem angesehen (wxHtmlParser), war aber nicht so begeistert, da es nicht darum geht, Standardkonstrukte wie URLs, Tabellen oder Formulare auszulesen, sondern Informationen, welche in immer wieder neuer textlicher Umgebung eingebunden sind.

Die Seiten, um die es geht, sind von Land zu Land unterschiedlich aufgebaut, haben abweichende Keywords und die Art, wie die Informationen angezeigt werden (Tabelle, Liste, etc.) ist auch nicht immer gleich. Da dürfte auch ein HTML-Parser einiges zu tun haben.

Aber ich werde den Performancetest gerne auch mit einem HTML-Parser durchführen. Vieleicht bringt mich dieser Test dann der Wahrheit näher.
(Empfehlung für einen Pareser?)

Dass man das RE-Modul besser nicht auf HTML-Seiten anwendet wundert mich in sofern, als dass eine HTML-Seite auch nichts anderes ist als Text. Und für Texte ist das RE-Modul doch eigentlich gemacht?

Gruß, Seven
lunar

Montag 20. Oktober 2008, 19:06

snakeseven hat geschrieben:Die Seiten, um die es geht, sind von Land zu Land unterschiedlich aufgebaut, haben abweichende Keywords und die Art, wie die Informationen angezeigt werden (Tabelle, Liste, etc.) ist auch nicht immer gleich. Da dürfte auch ein HTML-Parser einiges zu tun haben.
Und du glaubst, mit regulären Ausdrücken ging das einfacher?
Aber ich werde den Performancetest gerne auch mit einem HTML-Parser durchführen. Vieleicht bringt mich dieser Test dann der Wahrheit näher.
(Empfehlung für einen Pareser?)
lxml.html oder html5lib. Vielleicht sind die langsamer als deine lineare Suche, aber der resultierende Code ist unter Garantie kürzer und besser lesbar. Du willst deinen Code doch in sechs Monaten noch lesen können, oder?
Dass man das RE-Modul besser nicht auf HTML-Seiten anwendet wundert mich in sofern, als dass eine HTML-Seite auch nichts anderes ist als Text. Und für Texte ist das RE-Modul doch eigentlich gemacht?
Reguläre Ausdrücke sind einfache Zustandsautomaten, die keine Zustände verwalten und somit nur kontextfreie Grammatiken gut parsen können. HTML dagegen ist kontextsensitiv. Folglich muss man reguläre Ausdrücke innerhalb einer Zustandsmaschine ablaufen lassen, um HTML korrekt zu parsen.

Praktische Schwierigkeiten gesellen sich auch noch dazu: Ein regulärer Ausdruck ist normalerweise zeilenbasiert, HTML dagegen erlaubt Knoten auch über mehrere Zeilen. re.DOTALL ist also Pflicht. Desweiteren muss man darauf achten, greedy und non-greedy korrekt zu verwenden. Ein ".*" an der falschen Stelle führt zu völlig falschen Ergebnissen.

All das erschwert das Parsen mit regulären Ausdrücken. Letztendlich endet man bei der Verwendung von regulären Ausdrücken bei einem selbst implementierten Parser, man erfindet das Rad also erneut. Folglich kann man auch einen fertigen HTML-Parser nehmen. Das hat auch den Vorteil, dass man sich auf dessen Funktionalität in der Regel verlassen kann, während man selbstentwickelte Parser erst testen muss.
BlackJack

Montag 20. Oktober 2008, 20:25

@snakeseven: REs sind nicht per se langsam, aber man kann welche Schreiben die verdammt langsam werden. Und Du hast da welche mit quadratischer Laufzeit dabei. Such Dir mal eine Beschreibung wie REs abgearbeitet werden, zum Beispiel die Seite, die Leonidas verlinkt hat. Da wird sehr viel unnötige CPU-Zeit verbraten.

Und HTML ist zwar grundätzlich auch Text, aber mit einer verschachtelten Struktur und sehr vielen Variationsmöglichkeiten. Ein HTML-Parser eröffnet die Möglichkeit über die Sruktur des HTML-Dokuments zu navigieren, also auf einer höheren Ebene als einzelne Zeichen.
Leonidas
Administrator
Beiträge: 16024
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Montag 20. Oktober 2008, 20:28

snakeseven hat geschrieben:Ja, ich hab mir auch mal die Dokumentation zu einem angesehen (wxHtmlParser)
Naja, wer nutzt sowas schon in Python, wenn es bessere gibt? Python hat zumindest in der Hinsicht auf HTML die so ziemlich besten Parser überhaupt, wie Lunar bereits sagte, html5lib und lxml.html. Ersteren kann man auch instruieren unter anderem das Dokument als lxml-ElementTree zurückzugeben, wo man auch alle Vorteile von lxml verwenden kann.
My god, it's full of CARs! | Leonidasvoice vs Modvoice
snakeseven
User
Beiträge: 405
Registriert: Freitag 7. Oktober 2005, 14:37
Wohnort: Berlin
Kontaktdaten:

Dienstag 21. Oktober 2008, 13:29

Hi,
Ich werde es jetzt mal mit dem HTML-Parser von Python probieren.
Denn schön sehen diesen string.find() Kaskaden nicht aus und gut leserlich sind sie auch nicht.
Die RE-Expressions find ich da schon leserlicher und alles schön kurz, aber quadratischer Rechenaufwand? Das geht gar nicht.

Thanx allen!
Seven
Leonidas
Administrator
Beiträge: 16024
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Dienstag 21. Oktober 2008, 14:51

Also, dir wurden zwei gute parser empfohlen, und du waehlst einen aus der dir nicht empfohlen wurde? Hast du bedacht, dass es moeglicherweise einen Grund gibt, warum den hier niemand empfohlen hat?
My god, it's full of CARs! | Leonidasvoice vs Modvoice
snakeseven
User
Beiträge: 405
Registriert: Freitag 7. Oktober 2005, 14:37
Wohnort: Berlin
Kontaktdaten:

Dienstag 21. Oktober 2008, 19:21

Sorry, Verwechselung. Heißen beide HTMLParser. Werde den von der html5lib nehmen stat von htmllib. Traue den selbstgebastelten Seiten der MySpace User nicht.
Gruß, Seven
Leonidas
Administrator
Beiträge: 16024
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Dienstag 21. Oktober 2008, 19:32

snakeseven hat geschrieben:Traue den selbstgebastelten Seiten der MySpace User nicht.
Gute Entscheidung :D
My god, it's full of CARs! | Leonidasvoice vs Modvoice
Benutzeravatar
mkesper
User
Beiträge: 919
Registriert: Montag 20. November 2006, 15:48
Wohnort: formerly known as mkallas
Kontaktdaten:

Mittwoch 22. Oktober 2008, 08:14

Leonidas hat geschrieben:Gute Entscheidung :D
OMG, lol!
Samy is my hero!
sma
User
Beiträge: 3018
Registriert: Montag 19. November 2007, 19:57
Wohnort: Kiel

Mittwoch 22. Oktober 2008, 08:20

Snakeseven, deine REs sind "greedy", deine selbstgebauten finds nicht. Das könnte den Geschwindigkeitsunterschied erklären. Mache sie "nongreedy". Das ist wahrscheinlich auch das, was du eigentlich erreichen willst.

Stefan
snakeseven
User
Beiträge: 405
Registriert: Freitag 7. Oktober 2005, 14:37
Wohnort: Berlin
Kontaktdaten:

Sonntag 26. Oktober 2008, 23:09

Hm,

viel gegoogelt, viel ausprobiert, aber html5lib will sich mir mangels griffiger Dokumentation einfach nicht erschließen :roll: .
Der Parser von htmllib ist zwar einfacher zu verstehen, enttäuscht mich aber durch seine Langsamkeit beim Trennen von Tags und Textpassagen

Code: Alles auswählen

def handle_data(self, data).
Ich bin mir auch nicht mehr sicher, ob ein HTML-Parser das Richtige für mein Anliegen ist, da ich die geparsten Daten am Ende doch weiter mit RE zerlegen muß.

Ich verfolge daher die Strategie, die HTML-Seiten in kleinere Einheiten zu zerlegen und diese Einheiten dann mit den bestmöglichen Tools (RE, string.find, HTMLParse) weiter zu zerlegen. Performance wird aufgrund der zu erwartenden Gesamtdatenmenge die höchste Option haben.

Wenn ich die beste Lösung für mich gefunden habe, werde ich die hier zur kritischen Beurteilung posten.

Grüße, Seven
Antworten