ich habe meinen eigenen Heap geschrieben und musste feststellen, dass er um einiges langsamer ist als heapq. Da es mir nicht nur darum geht, etwas schnelles zu haben, sondern auch zu verstehen warum mein Heap langsamer ist, dachte ich mir post einfach mal.
Ich habe den Heap auf einer 2 fach verketteten Liste aufgebaut, sodass jeder Knoten neben seinen Kindern (leftChild, rightChild) und dem Elternteil (parent) auch seine Nachbarn (previousNode, nextNode) kennt. Ausserdem beinhaltet jeder Knoten einen Vergleichswert (compareValue) und hat ggf. ein Datenobjekt (data).
Der Heap selber hat natürlich eine Wurzel (root), welches auch das erste Element der Liste ist, und kennt ausserdem den letzten Knoten (lastNode) und das letzte Elternteil (lastParent). Dadurch wird das Einfügen und Entfernen sehr einfach.
Ich habe bei Wikipedia gelesen, dass man Heaps gerne auf Arrays aufbaut, aber dachte mir eine dynamische Datenstruktur müsste sich für sowas ja eigentlich besser eignen, deswegen die 2 fach verkettete Liste.
Nun haben meine bisherigen Tests mit profile ergeben, dass mein Heap gerne mal 3-15 mal langsamer ist als heapq.
So, nun die Frage:
Liegt es am Konzept, dass ich das ganze auf einer 2 fach verketteten Liste aufbaue, und durch die ganzen Kennt-Beziehungen viel Speicher fresse oder sich irgendwie ein Array besser eignet wegen dem Cache oder so (kenn mich damit noch nich aus (keine c++ kenntnisse, nur java und python, daher nie um die speicherverwaltung gekümmert..)
oder
liegt es an meiner Implementation (irgendwelche langsamen Operatoren benutzt oder so)?
Im 1. Fall: Warum war die Entscheidung das so zu implementieren generell falsch? Warum wäre eine Implementation aufbauend auf einem Array oder sonstwie besser?
Im 2. Fall: Welche Sachen muss ich ändern um das ganze zu beschleunigen? Warum sind die benutzten Funktionen/Operatoren/.. langsam (-er als eure Vorschläge)?
Wie sieht die Implementation von heapq aus, was macht diese anders? Was macht sie schneller?
Es ist also nur eine zum Teil Python betreffende Frage, der andere Teil betrifft Programmierung im Allgemeinen.
Ich würde mich über Antworten riesig freuen. =)
Hier der Code:
Code: Alles auswählen
class Heapl():
def __init__(self):
self.root = None
self.lastParent = None
self.lastNode = None
def insert(self, compareValue, data = None):
newNode = BLNode(compareValue, data)
# if heaplist is empty
if self.root == None:
self.root = newNode
self.lastParent = newNode
self.lastNode = newNode
else:
# add to list
self.lastNode.nextNode = newNode
newNode.previousNode = self.lastNode
self.lastNode = newNode
# add parent
newNode.parent = self.lastParent
# add as Child
if self.lastParent.leftChild == None:
self.lastParent.leftChild = newNode
else:
self.lastParent.rightChild = newNode
self.lastParent = self.lastParent.nextNode
self.heapify(newNode)
return newNode # unnecessary, good for testing though
def remove(self, node):
data = node.data
# if this is the only node in heap
if self.root is self.lastNode:
self.root = None
self.lastParent = None
self.lastNode = None
else:
# replace node with last node
node.data = self.lastNode.data
node.compareValue = self.lastNode.compareValue
# remove lastNode from parent
if self.lastNode is self.lastNode.parent.leftChild:
self.lastNode.parent.leftChild = None
else:
self.lastNode.parent.rightChild = None
self.lastParent = self.lastParent.previousNode
# remove last node from list
self.lastNode.previousNode.nextNode = None
self.lastNode = self.lastNode.previousNode
self.heapify(node)
return data
def heapify(self, node):
# this is where I decide that it's a min heap, so to change it to a max heap inverse the greater/smaller operator
# sift up
while node.parent != None and node.compareValue < node.parent.compareValue:
node.data, node.parent.data = node.parent.data, node.data
node.compareValue, node.parent.compareValue = node.parent.compareValue, node.compareValue
node = node.parent
# sift down
while node.leftChild != None:
if node.rightChild != None and node.rightChild.compareValue < node.leftChild.compareValue:
smallerChild = node.rightChild
else:
smallerChild = node.leftChild
if smallerChild.compareValue > node.compareValue:
break
node.data, smallerChild.data = smallerChild.data, node.data
node.compareValue, smallerChild.compareValue = smallerChild.compareValue, node.compareValue
node = smallerChild
def extractMin(self):
return self.remove(self.root)
class BLNode():
def __init__(self, compareValue, data):
self.parent = None
self.leftChild = None
self.rightChild = None
self.previousNode = None
self.nextNode = None
self.compareValue = compareValue
self.data = data
Code: Alles auswählen
from heapl import *
from heapq import *
import random
import time
import profile
size = 10000
data = []
def testheapq():
heap = []
for i in range(size):
heappush(heap, data[i])
for i in range(size):
heappop(heap)
def testheaplist():
heap = Heapl()
for i in range(size):
heap.insert(data[i])
for i in range(size):
heap.extractMin()
def showHeapList(node, text):
if node.rightChild != None:
showHeapList(node.rightChild, text + " ")
print text + str(node.compareValue)
if node.leftChild != None:
showHeapList(node.leftChild, text + " ")
def start():
for i in range(size):
data.append(random.randint(0,size))
print "--------------------------heapq--------------------------"
profile.run('testheapq()')
print "--------------------------heapl--------------------------"
profile.run('testheaplist()')
""" # heaplist seems to work
h = Heapl()
h.insert(1)
h.insert(3)
o = h.insert(9)
h.insert(4)
h.insert(2)
h.extractMin()
h.remove(o)
h.extractMin()
if h.root == None:
print "HEAPLIST IS EMPTY"
else:
showHeapList(h.root, "")"""
start()