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:
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)