eigener heap optimieren

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.
meh11
User
Beiträge: 11
Registriert: Montag 24. November 2008, 16:27

eigener heap optimieren

Beitragvon meh11 » Montag 24. November 2008, 16:56

Hi,

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=]
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]


[code=]
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()[/code]
DasIch
User
Beiträge: 2405
Registriert: Montag 19. Mai 2008, 04:21
Wohnort: Berlin

Beitragvon DasIch » Montag 24. November 2008, 17:14

heapq verwendet wenn möglich in C geschriebene Funktionen und ansonsten schau dir an was bei dir viel Zeit kostet und schau wie es im Modul geregelt ist.
meh11
User
Beiträge: 11
Registriert: Montag 24. November 2008, 16:27

Beitragvon meh11 » Montag 24. November 2008, 18:24

Ich habe mir heapq angesehen, und dort werden diverse Sachen anders gemacht (zb bei remove nicht den letzten Knoten an die Stelle vom gelöschten Knoten packen), aber was ich bei heapq und generell nicht verstehe, ist warum ein array benutzt wird anstatt einer dynamischen Datenstruktur..?
DasIch
User
Beiträge: 2405
Registriert: Montag 19. Mai 2008, 04:21
Wohnort: Berlin

Beitragvon DasIch » Montag 24. November 2008, 18:29

meh11 hat geschrieben:[...]aber was ich bei heapq und generell nicht verstehe, ist warum ein array benutzt wird anstatt einer dynamischen Datenstruktur..?

Wie kommst du darauf dass dort ein Array verwendet wird?
BlackJack

Beitragvon BlackJack » Montag 24. November 2008, 18:54

@DasIch: Weil meh11 in den Quelltext geschaut hat? Okay es ist eine Liste, aber die ist ja auch als Array implementiert.

@meh11: Weil es ganz offensichtlich effizienter ist ein Array mit einem Verweis pro Element zu haben, als ein zusätzliches Objekt mit mehreren Verweisen auf andere Objekte zu erstellen, wobei die Verweise alle umständlich umgesetzt werden müssen, statt einfacher Berechnungen mit ganzen Zahlen durch zu führen um Elternknoten und Kinderknoten zu bestimmen.

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder