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

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: 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()
DasIch
User
Beiträge: 2465
Registriert: Montag 19. Mai 2008, 04:21
Wohnort: Berlin

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

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: 2465
Registriert: Montag 19. Mai 2008, 04:21
Wohnort: Berlin

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

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.
Antworten