7 Replies - 6224 Views - Last Post: 27 June 2012 - 08:21 AM Rate Topic: -----

#1 atraub  Icon User is offline

  • Pythoneer
  • member icon

Reputation: 759
  • View blog
  • Posts: 2,010
  • Joined: 23-December 08

Data Structures

Post icon  Posted 23 June 2012 - 01:09 PM

Python sure does make it easy to build custom data structures! A friend of mine is in the process of learning Java, and I thought it would be fun to build some data structures with her when she's ready. Just for practice, I decided I'd build a data structure in Python today. You might have seen my tutorial on building a simple singly linked list. You might have even seen my Queue and Stack snippets, so I wanted something a little more involved. I decided that today I'd implement a PriorityQueue class. To build this, I will be using the Queue class that I built in the previous snippet and a dictionary. Here's the basic class that I have so far:

#Priority Queue
__author__ = "Adam Traub"
__date__ = "6/23/2012"

from Queue import Queue
import inspect

class PriorityQueue:
    def __init__(self):
        self.master = {}
        self.length = 0

    def enqueue(self, value, priority=1):
        if self.master.get(priority) != None:
            self.master.get(priority).enqueue(value)

        else:
            self.master[priority] = Queue()
            self.master[priority].enqueue(value)
            
        self.length += 1

    def dequeue(self):
        highestKey = self.__getFrontQueue()
        retVal = self.master.get(highestKey).dequeue()

        if self.master.get(highestKey).isEmpty():
            self.master.pop(highestKey)

        self.length -= 1

        return retVal

    def clear(self):
        self.master = {}
        self.length = 0

    def isEmpty(self):
        return self.length == 0

    def hasMore(self):
        return self.length >= 0

    def peek(self):
        return self.master.get(self.__getFrontQueue()).front()        

    def __len__(self):
        return self.length

    def __getFrontQueue(self):
        if self.length <= 0:
            raise IndexError((inspect.stack()[1][3]).title() +" can't be used on an empty PriortiyQueue")

        return sorted(self.master.keys())[-1]



Admittedly, this one wasn't as involved as I thought it would be. I only spent about 45 minutes on this, but I don't think it's too bad. I'm sure it's riddled with errors, but I am a little proud of my utilization of the inspect class for smarter error reporting on the __getFrontQueue method (This makes it so that the name of the function that called getFrontQueue gets reported when the error is raised, pretty nifty, yeah?).

I really do enjoy building data structures though. They're easy to make, but take time and skill to optimize. Now that I've basically gotten generators out of my system, I think I'll start working on more data structures. So, here's my question to the community, are there any data structures that are near and dear to your hearts? Sure, most of us are fond of arrays/lists/arraylists and dictionaries/hashtables, but what about the more complex ones? What data structures have you built? What have you struggled with? What are some of your prouder "structured" achievements?

This post has been edited by atraub: 23 June 2012 - 01:41 PM


Is This A Good Question/Topic? 4
  • +

Replies To: Data Structures

#2 atraub  Icon User is offline

  • Pythoneer
  • member icon

Reputation: 759
  • View blog
  • Posts: 2,010
  • Joined: 23-December 08

Re: Data Structures

Posted 23 June 2012 - 01:58 PM

Incidentally, I've been inspired to work on part 2 of the Linked List tutorial. I'll use more advanced and generally better techniques. That tutorial is a year old, and I've learned a lot since then.

This post has been edited by atraub: 23 June 2012 - 01:58 PM

Was This Post Helpful? 0
  • +
  • -

#3 Simown  Icon User is offline

  • Blue Sprat
  • member icon

Reputation: 319
  • View blog
  • Posts: 650
  • Joined: 20-May 10

Re: Data Structures

Posted 23 June 2012 - 05:10 PM

I'm like you, I love constructing data structures - it's a true art to optimize them without confusing anyone who is to look at/use your code.

One of my proudest structural achievements has got to be when I made a binary heap the day after learning about it, in Java too but of course, I coded it in Python :) That's a while ago now, I might have the code somewhere I can dig up. Or maybe worth rewriting it (I assume it can be improved) for a tutorial!

I have mixed feelings about linked lists as a data structure, I know the ins and outs of them learning nothing much but them for a whole year, I think I'll have a break from them for a while.
Was This Post Helpful? 0
  • +
  • -

#4 denting5  Icon User is offline

  • D.I.C Head

Reputation: 5
  • View blog
  • Posts: 84
  • Joined: 03-June 12

Re: Data Structures

Posted 25 June 2012 - 09:46 AM

I wonder why more operating systems are not written in python. If data structures can be so simply set up, why don't people make super fast filing systems for corporations and what not?
Was This Post Helpful? 0
  • +
  • -

#5 Simown  Icon User is offline

  • Blue Sprat
  • member icon

Reputation: 319
  • View blog
  • Posts: 650
  • Joined: 20-May 10

Re: Data Structures

Posted 25 June 2012 - 12:56 PM

Do you mean an operating system like Windows or Linux or more of an "organisational" system? If it's the latter then I couldn't agree more in most cases, Python is often exploited because of it's clear, readable syntax and rapid development.

The only thing about operating system is speed. Python is not the fastest language out there, and not generally used for the core of an OS. Python does play a big role (usually) in the Linux operating system though, providing countless utility functions.

An OS in Python is not beyond reason see: Python OS although still in early Alpha.

Getting back on topic! Python is great for creating data structures and for prototyping new ones, because of the rapid development mentioned previously, whether a data structure will stay implemented in Python is not always the case, but it's a good starting point.
Was This Post Helpful? 1
  • +
  • -

#6 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10821
  • View blog
  • Posts: 40,340
  • Joined: 27-December 08

Re: Data Structures

Posted 25 June 2012 - 02:03 PM

View Postdenting5, on 25 June 2012 - 12:46 PM, said:

I wonder why more operating systems are not written in python. If data structures can be so simply set up, why don't people make super fast filing systems for corporations and what not?

Like Simown said, OS development is about working closely with the hardware for low-level tasks. Technologies like C/C++ and Assembly come more into play here, with things like memory management.

In computer science, data structure is not really the same thing as a database. Relational databases are backed by B-Trees usually, which is a type of data structure.

More on topic, I'm a graph theorist. I have a soft spot for Trees in particular. I'll work on a Python tree implementation for later tonight hopefully.
Was This Post Helpful? 0
  • +
  • -

#7 McSick  Icon User is offline

  • D.I.C Head

Reputation: 33
  • View blog
  • Posts: 179
  • Joined: 02-September 10

Re: Data Structures

Posted 26 June 2012 - 01:29 PM

I love anything in Network Security. I have created python classes all around different encryption/decryption and sockets kinda stuff. So an RC4/AES/DES class all the way around to hashing/Port Sniffing. Oh and anything math related!!! I had to create a random number generator which then I had to modify it to make only odd numbers and then even more so check this number for primeality. Oh and these numbers had like large number of bits o.o which python made it a lot easier for.
Was This Post Helpful? 0
  • +
  • -

#8 atraub  Icon User is offline

  • Pythoneer
  • member icon

Reputation: 759
  • View blog
  • Posts: 2,010
  • Joined: 23-December 08

Re: Data Structures

Posted 27 June 2012 - 08:21 AM

I wrote a linux shell in Python while I was an undergrad... I named it Monty :)
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1