Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #29613 > unrolled thread

Algorithms using Python?

Back to article view | Back to comp.lang.python

Contents

  Algorithms using Python? Mayuresh Kathe <mayuresh@kathe.in> - 2012-09-21 14:26 +0530
    Re: Algorithms using Python? Joel Goldstick <joel.goldstick@gmail.com> - 2012-09-21 10:41 -0400
    Re: Algorithms using Python? Dennis Lee Bieber <wlfraed@ix.netcom.com> - 2012-09-21 15:45 -0400
    Re: Algorithms using Python? Ian Kelly <ian.g.kelly@gmail.com> - 2012-09-21 14:07 -0600
    Re: Re: Algorithms using Python? Evan Driscoll <driscoll@cs.wisc.edu> - 2012-09-21 15:43 -0500
    Re: Algorithms using Python? Dennis Lee Bieber <wlfraed@ix.netcom.com> - 2012-09-21 17:14 -0400
      Re: Algorithms using Python? Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2012-09-22 01:28 +0000
        Re: Algorithms using Python? Dennis Lee Bieber <wlfraed@ix.netcom.com> - 2012-09-22 00:29 -0400
    Re: Algorithms using Python? Wayne Werner <wayne@waynewerner.com> - 2012-09-26 10:55 -0500
      Re: Algorithms using Python? 88888 Dihedral <dihedral88888@googlemail.com> - 2012-09-27 04:15 -0700
      Re: Algorithms using Python? 88888 Dihedral <dihedral88888@googlemail.com> - 2012-09-27 04:15 -0700

#29613 — Algorithms using Python?

Is there a good book on foundational as well as advanced algorithms 
using Python?

Thanks.

[toc] | [next] | [standalone]

#29644

On Fri, Sep 21, 2012 at 4:56 AM, Mayuresh Kathe <mayuresh@kathe.in> wrote:
> Is there a good book on foundational as well as advanced algorithms using
> Python?
>
> Thanks.
>
> --
> http://mail.python.org/mailman/listinfo/python-list

There is one on Apress that I've seen

http://www.amazon.com/Python-Algorithms-Mastering-Language-Experts/dp/1430232374

-- 
Joel Goldstick

[toc] | [prev] | [next] | [standalone]

#29663

On Fri, 21 Sep 2012 14:26:04 +0530, Mayuresh Kathe <mayuresh@kathe.in>
declaimed the following in gmane.comp.python.general:

> Is there a good book on foundational as well as advanced algorithms 
> using Python?
>
	Depends on what you mean by "foundational"...

	Since Python has dynamic lists and dictionaries, I suspect you won't
find any textbook focusing on linked-list or hashed lookup algorithms
using Python.

	You can probably implement them, but they're not going to be very
efficient. (And never "remove" an element from the linked-list
implementation because Python would shift all the other elements, hence
your "links" become invalid).
-- 
	Wulfraed                 Dennis Lee Bieber         AF6VN
        wlfraed@ix.netcom.com    HTTP://wlfraed.home.netcom.com/

[toc] | [prev] | [next] | [standalone]

#29670

On Fri, Sep 21, 2012 at 1:45 PM, Dennis Lee Bieber
<wlfraed@ix.netcom.com> wrote:
>         You can probably implement them, but they're not going to be very
> efficient. (And never "remove" an element from the linked-list
> implementation because Python would shift all the other elements, hence
> your "links" become invalid).

I'm not sure what you mean by that last comment.

class Node(object):
    def __init__(self, data, next):
        self.data = data
        self.next = next

class LinkedList(object):
    def __init__(self):
        self._head = None
    def __iter__(self):
        node = self._head
        while node:
            yield node.data
            node = node.next
    def insert_front(self, value):
        self._head = Node(value, self._head)
    def remove(self, value):
        prior, node = None, self._head
        while node:
            if node.data == value:
                if prior:
                    prior.next = node.next
                else:
                    self._head = node.next
                break
            prior, node = node, node.next
        else:
            raise ValueError("value not found")

>>> li = LinkedList()
>>> for char in 'edcba':
...     li.insert_front(char)
...
>>> print ''.join(li)
abcde
>>> li.remove('c')
>>> print ''.join(li)
abde

It seems to work fine to me.

[toc] | [prev] | [next] | [standalone]

#29680

[Multipart message — attachments visible in raw view] — view raw

On 09/21/2012 02:45 PM, Dennis Lee Bieber wrote:
> On Fri, 21 Sep 2012 14:26:04 +0530, Mayuresh Kathe <mayuresh@kathe.in>
> declaimed the following in gmane.comp.python.general:
> 
>> Is there a good book on foundational as well as advanced algorithms 
>> using Python?
>>
> 	Depends on what you mean by "foundational"...
> 
> 	Since Python has dynamic lists and dictionaries, I suspect you won't
> find any textbook focusing on linked-list or hashed lookup algorithms
> using Python.

I wouldn't be so sure; C++ and Java both have standard libraries with
dictionaries (and thus are mostly lacking a literal syntax). But it's
easy to find books talking about the simple stuff.

I'd suggest looking at the books used in MIT's intro classes:

6.000 (Intro to CS and programming):

http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-00sc-introduction-to-computer-science-and-programming-spring-2011/Syllabus/

  Zelle, John M. Python Programming: An Introduction to Computer Science
  Budd, Timothy. Exploring Python
  Shaw, Zed A. Learn Python the Hard Way [online]
  Swaroop, CH. A Byte of Python


6.006 (Intro to algorithms):

http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-spring-2008/syllabus/

  Miller and Ranum. Problem Solving with Algorithms and Data Structures
Using Python.
  [CLRS isn't Python]

and see if they have anything to offer. (I didn't actually look.)


> 	You can probably implement them, but they're not going to be very
> efficient. (And never "remove" an element from the linked-list
> implementation because Python would shift all the other elements, hence
> your "links" become invalid).

Huh?

Evan

[toc] | [prev] | [next] | [standalone]

#29686

On Fri, 21 Sep 2012 14:07:01 -0600, Ian Kelly <ian.g.kelly@gmail.com>
declaimed the following in gmane.comp.python.general:

> 
> It seems to work fine to me.

	You are working with dynamically allocated memory for the nodes; I
was envisioning the implementation of linked lists in what would have
been statically allocated arrays (or one large dynamic memory block with
all data tracking kept internally) (ie; a naive attempt using a Python
list where nodes are [nxtIndex, data], and accidently removing a node
from that list).

-- 
	Wulfraed                 Dennis Lee Bieber         AF6VN
        wlfraed@ix.netcom.com    HTTP://wlfraed.home.netcom.com/

[toc] | [prev] | [next] | [standalone]

#29705

On Fri, 21 Sep 2012 17:14:14 -0400, Dennis Lee Bieber wrote:

> On Fri, 21 Sep 2012 14:07:01 -0600, Ian Kelly <ian.g.kelly@gmail.com>
> declaimed the following in gmane.comp.python.general:
> 
> 
>> It seems to work fine to me.
> 
> 	You are working with dynamically allocated memory for the nodes; 

Doesn't everybody? :)


> I was envisioning the implementation of linked lists in what would have
> been statically allocated arrays (or one large dynamic memory block with
> all data tracking kept internally) (ie; a naive attempt using a Python
> list where nodes are [nxtIndex, data], and accidently removing a node
> from that list).

Writing Fortran77 in Python!

:)



-- 
Steven

[toc] | [prev] | [next] | [standalone]

#29719

On 22 Sep 2012 01:28:04 GMT, Steven D'Aprano
<steve+comp.lang.python@pearwood.info> declaimed the following in
gmane.comp.python.general:


> 
> Writing Fortran77 in Python!
>

	Well, if one really wants to learn "linked lists" from the core
concept where the links refer directly to offsets within the memory
block (array) <G>; then expand to where the links refer to dynamically
allocated memory... Do the same with stacks, queue, and deques... Much
easier to debug if all one needs to dump is a snapshot of an array and
analyze for "lost free memory" (any array entry that is not "pointed to"
when traversing the chain of data nor the chain of free cells) -- since
such would be uncollected garbage in lower-level languages. Python masks
such concerns -- you unlink a node, and it gets garbage collected...

	You should have seen the final project in my algorithms class (ca.
1979)... A hashed-head multiple-linked list * ... Done using a version
of BASIC that only supported four open files at a time (on top of which,
I used chain-loading to move from the master controller (user interface,
if you will) to each functional operation). The instructor had made the
mistake of stating the project could be done in any language /he/ knew
(so he received my BASIC, a lot of FORTRAN-IV, and at least one
Meta-Symbol).


* And in the last 30+ years, I've seen only ONE non-classroom use of an
HHMLL -- the directory structure of AmigaOS!

-- 
	Wulfraed                 Dennis Lee Bieber         AF6VN
        wlfraed@ix.netcom.com    HTTP://wlfraed.home.netcom.com/

[toc] | [prev] | [next] | [standalone]

#30219

On Fri, 21 Sep 2012, Dennis Lee Bieber wrote:

> On Fri, 21 Sep 2012 14:26:04 +0530, Mayuresh Kathe <mayuresh@kathe.in>
> declaimed the following in gmane.comp.python.general:
>
>> Is there a good book on foundational as well as advanced algorithms
>> using Python?
>>
> 	Depends on what you mean by "foundational"...
>
> 	Since Python has dynamic lists and dictionaries, I suspect you won't
> find any textbook focusing on linked-list or hashed lookup algorithms
> using Python.
>
> 	You can probably implement them, but they're not going to be very
> efficient. (And never "remove" an element from the linked-list
> implementation because Python would shift all the other elements, hence
> your "links" become invalid).

It's quite inefficient, but it would be fairly trivial to create a LL 
implementation like this:

class Link:
     def __init__(self):
         self.next = None
         self.value = None

class LinkedList:
     def __init__(self):
         self.head = None

     def add(self, value):
         node = Link()
         node.value = value
         self.append(node)

     def append(self, node):
         # Write some code

It's fairly easy to use reference types as one would use pointers in 
<language>.

But it might actually require understanding pointers and such in the first 
place...

I'm not really aware of any algorithm that's impossible/harder to 
implement in Python - Python just makes most things a lot easier so you 
never have to deal with the lower level algorithms. Which makes *me* happy 
:)

-Wayne

[toc] | [prev] | [next] | [standalone]

#30289

Wayne Werner於 2012年9月27日星期四UTC+8上午12時05分31秒寫道：
> On Fri, 21 Sep 2012, Dennis Lee Bieber wrote:
> 
> 
> 
> > On Fri, 21 Sep 2012 14:26:04 +0530, Mayuresh Kathe <mayuresh@kathe.in>
> 
> > declaimed the following in gmane.comp.python.general:
> 
> >
> 
> >> Is there a good book on foundational as well as advanced algorithms
> 
> >> using Python?
> 
> >>
> 
> > 	Depends on what you mean by "foundational"...
> 
> >
> 
> > 	Since Python has dynamic lists and dictionaries, I suspect you won't
> 
> > find any textbook focusing on linked-list or hashed lookup algorithms
> 
> > using Python.
> 
> >
> 
> > 	You can probably implement them, but they're not going to be very
> 
> > efficient. (And never "remove" an element from the linked-list
> 
> > implementation because Python would shift all the other elements, hence
> 
> > your "links" become invalid).
> 
> 
> 
> It's quite inefficient, but it would be fairly trivial to create a LL 
> 
> implementation like this:
> 
> 
> 
> class Link:
> 
>      def __init__(self):
> 
>          self.next = None
> 
>          self.value = None
> 
> 
> 
> class LinkedList:
> 
>      def __init__(self):
> 
>          self.head = None
> 
> 
> 
>      def add(self, value):
> 
>          node = Link()
> 
>          node.value = value
> 
>          self.append(node)
> 
> 
> 
>      def append(self, node):
> 
>          # Write some code
> 
> 
> 
> It's fairly easy to use reference types as one would use pointers in 
> 
> <language>.
> 
> 
> 
> But it might actually require understanding pointers and such in the first 
> 
> place...
> 
> 
> 
> I'm not really aware of any algorithm that's impossible/harder to 
> 
> implement in Python - Python just makes most things a lot easier so you 
> 
> never have to deal with the lower level algorithms. Which makes *me* happy 
> 
> :)
> 
> 
> 
> -Wayne

In python  long integers of varried lengths of precesions, doubles, 
complex numbers,  immutable tuples, modifiable lists, modifiable dictionaries,
and functions and classes are all name resolved  basic built in types.


It is more interesting to implement a binary tree in python from 
a dictionary.

Also the set part can be implemented by long integers or dictionaries.

The symbolic computation part as in sympy is also a good example 
of high level programmings in python.

But this also means a lot kids will finish their calculous  homeworks 
trivially by machines instead of  reasoning and learning in person.

[toc] | [prev] | [next] | [standalone]

#30290

Wayne Werner於 2012年9月27日星期四UTC+8上午12時05分31秒寫道：
> On Fri, 21 Sep 2012, Dennis Lee Bieber wrote:
> 
> 
> 
> > On Fri, 21 Sep 2012 14:26:04 +0530, Mayuresh Kathe <mayuresh@kathe.in>
> 
> > declaimed the following in gmane.comp.python.general:
> 
> >
> 
> >> Is there a good book on foundational as well as advanced algorithms
> 
> >> using Python?
> 
> >>
> 
> > 	Depends on what you mean by "foundational"...
> 
> >
> 
> > 	Since Python has dynamic lists and dictionaries, I suspect you won't
> 
> > find any textbook focusing on linked-list or hashed lookup algorithms
> 
> > using Python.
> 
> >
> 
> > 	You can probably implement them, but they're not going to be very
> 
> > efficient. (And never "remove" an element from the linked-list
> 
> > implementation because Python would shift all the other elements, hence
> 
> > your "links" become invalid).
> 
> 
> 
> It's quite inefficient, but it would be fairly trivial to create a LL 
> 
> implementation like this:
> 
> 
> 
> class Link:
> 
>      def __init__(self):
> 
>          self.next = None
> 
>          self.value = None
> 
> 
> 
> class LinkedList:
> 
>      def __init__(self):
> 
>          self.head = None
> 
> 
> 
>      def add(self, value):
> 
>          node = Link()
> 
>          node.value = value
> 
>          self.append(node)
> 
> 
> 
>      def append(self, node):
> 
>          # Write some code
> 
> 
> 
> It's fairly easy to use reference types as one would use pointers in 
> 
> <language>.
> 
> 
> 
> But it might actually require understanding pointers and such in the first 
> 
> place...
> 
> 
> 
> I'm not really aware of any algorithm that's impossible/harder to 
> 
> implement in Python - Python just makes most things a lot easier so you 
> 
> never have to deal with the lower level algorithms. Which makes *me* happy 
> 
> :)
> 
> 
> 
> -Wayne

In python  long integers of varried lengths of precesions, doubles, 
complex numbers,  immutable tuples, modifiable lists, modifiable dictionaries,
and functions and classes are all name resolved  basic built in types.


It is more interesting to implement a binary tree in python from 
a dictionary.

Also the set part can be implemented by long integers or dictionaries.

The symbolic computation part as in sympy is also a good example 
of high level programmings in python.

But this also means a lot kids will finish their calculous  homeworks 
trivially by machines instead of  reasoning and learning in person.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.python

csiph-web