Ich baue grade einen pure Python parser für
OpenPGP Messages nach
RFC 4880. Dabei ist mir wieder mal was aufgefallen.
Wenn man einen Parser baut, der eine grosse Datenstruktur analysiert und in Pakete zerlegt, hat man in den meisten Sprachen folgendes Muster:
In C würde man es wohl so machen:
void parse_message(char * input) {
int len = find_packet_len(input);
handle_packet(make_packet(input, len));
input += len;
}
In Python ist der naive Ansatz:
def parse_message(input):
while input:
packet_len = find_length_of_packet(input)
packet = input[:packet_len]
handle_packet(input[:packet_len])
input = input[packet_len:]
In funktionalen Sprachen entsprechend.
Das Problem ist nun, das Python an dieser Stelle jeweils eine Kopie des Paketes und eine Kopie des restlichen Inputs anlegt. Letzteres ist leider eine O(n^2) Operation ....
Entweder baut man das parsing also um, indem man
input als Array behandelt nur nur über Indizes adressiert:
def parse_message(input):
start = 0
while len(input) > start:
pl = find_length_of_packet(input, start)
handle_packet(input[start:start + pl])
start += pl
Oder, man verfolgt weiter den Stil aus dem oberen Beispiel, legt aber einen Wrapper um den input, der das Kopieren verhindert:
class ROList(list):
def __init__(self, l, start = 0):
self.__l = tuple(l)
self.__start = start
self.__end = sys.maxint
def __getitem__(self, i):
return self.__l[self.__start + i]
def __getslice__(self, start, end):
#print self, start, end, sys.maxint - end
res = self.__class__("")
res.__l = self.__l
res.__start = self.__start + start
if end < sys.maxint:
res.__end = self.__start + end
return res
def __len__(self):
if self.__end == sys.maxint:
return len(self.__l) - self.__start
else:
return self.__end - self.__start
def __repr__(self):
return "%s : %d" % (self.__l, self.__start)
def test_performance(list_type):
l = list_type(range(1024*1024))
while l:
l = l[512:]
if __name__ == "__main__":
for t in list, ROList:
start_time = time.time()
test_performance(t)
print 'test of %s performance: %f seconds' % (t, time.time() - start_time)