The old Google Groups will be going away soon, but your browser is incompatible with the new version.
lang comparison: in-place algorithm for reversing a list in Perl, Python, Lisp
 There are currently too many topics in this group that display first. To make this topic appear first, remove this option from another topic. There was an error processing your request. Please try again. Standard view   View as tree
 11 messages

From:
To:
Cc:
Followup To:
Subject:
 Validation: For verification purposes please type the characters you see in the picture below or the numbers you hear by clicking the accessibility icon.

More options Feb 29 2012, 11:07 pm
Newsgroups: comp.lang.lisp, comp.emacs, comp.lang.python, comp.lang.perl.misc
From: Xah Lee <xah...@gmail.com>
Date: Wed, 29 Feb 2012 20:07:49 -0800 (PST)
Local: Wed, Feb 29 2012 11:07 pm
Subject: lang comparison: in-place algorithm for reversing a list in Perl, Python, Lisp
fun example.

in-place algorithm for reversing a list in Perl, Python, Lisp
http://xahlee.org/comp/in-place_algorithm.html

plain text follows
----------------------------------------

What's “In-place Algorithm”?

Xah Lee, 2012-02-29

emacs lisp} code to illustrate.

Here's Wikipedia In-place algorithm excerpt:

In computer science, an in-place algorithm (or in Latin in situ) is an
algorithm which transforms input using a data structure with a small,
constant amount of extra storage space. The input is usually
overwritten by the output as the algorithm executes. An algorithm
which is not in-place is sometimes called not-in-place or out-of-
place.

Python

Here's a python code for reversing a list. Done by creating a new
list, NOT using in-place:

# python
# reverse a list

list_a = ["a", "b", "c", "d", "e", "f", "g"]

list_length = len(list_a)
list_b = [0] * list_length

for i in range(list_length):
list_b[i] = list_a[list_length -1 - i]

print list_b
Here's in-place algorithm for reversing a list:

# python
# in-place algorithm for reversing a list

list_a = ["a", "b", "c", "d", "e", "f", "g"]

list_length = len(list_a)

for i in range(list_length/2):
x = list_a[i]
list_a[i] = list_a[ list_length -1 - i]
list_a[ list_length -1 - i] = x

print list_a
Perl

Here's a perl code for reversing a list. Done by creating a new list,
NOT using in-place:

# perl

use strict;
use Data::Dumper;

my @listA = qw(a b c d e f g);

my \$listLength = scalar @listA;
my @listB = ();

for ( my \$i = 0; \$i < \$listLength; \$i++ ) {
\$listB[\$i] = \$listA[ \$listLength - 1 - \$i];

}

print Dumper(\@listB);

# perl
# in-place algorithm for reversing a list.

use strict;
use Data::Dumper;
use POSIX; # for “floor”

my @listA = qw(a b c d e f g);

my \$listLength = scalar @listA;

for ( my \$i = 0; \$i < floor(\$listLength/2); \$i++ ) {
my \$x = \$listA[\$i];
\$listA[\$i] = \$listA[ \$listLength - 1 - \$i];
\$listA[ \$listLength - 1 - \$i] = \$x;

}

print Dumper(\@listA);
__END__

emacs lisp

;; emacs lisp
;; reverse a array

(setq arrayA ["a" "b" "c" "d" "e" "f" "g"])

(setq arrayLength (length arrayA))

(setq arrayB (make-vector arrayLength 0))

(dotimes (i arrayLength )
(aset arrayB i (aref arrayA (- (1- arrayLength) i)) )
)

(print (format "%S" arrayB))
;; emacs lisp
;; in-place algorithm for reversing a array

(setq arrayA ["a" "b" "c" "d" "e" "f" "g"])

(setq arrayLength (length arrayA))

(dotimes (i (floor (/ arrayLength 2)))
(let (x)
(setq x (aref arrayA i))
(aset arrayA i (aref arrayA (- (1- arrayLength) i)))
(aset arrayA (- (1- arrayLength) i) x) ) )

(print (format "%S" arrayA))

Xah

To post a message you must first join this group.
You do not have the permission required to post.
More options Mar 1 2012, 12:01 am
Newsgroups: comp.lang.python
From: Steven D'Aprano <steve+comp.lang.pyt...@pearwood.info>
Date: 01 Mar 2012 05:01:30 GMT
Local: Thurs, Mar 1 2012 12:01 am
Subject: Re: lang comparison: in-place algorithm for reversing a list in Perl, Python, Lisp

On Wed, 29 Feb 2012 20:07:49 -0800, Xah Lee wrote:
> Here's in-place algorithm for reversing a list:

> # python
> # in-place algorithm for reversing a list

> list_a = ["a", "b", "c", "d", "e", "f", "g"]
> list_length = len(list_a)
> for i in range(list_length/2):
>     x = list_a[i]
>     list_a[i] = list_a[ list_length -1 - i]
>     list_a[ list_length -1 - i] = x

> print list_a

This is a good example of code written by somebody not very familiar with
Python idioms. You don't need a temporary variable to swap two values in
Python. A better way to reverse a list using more Pythonic idioms is:

for i in range(len(list_a)//2):
list_a[i], list_a[-i-1] = list_a[-i-1], list_a[i]

But the best way (even more idiomatic and much, much faster) is this:

list_a.reverse()

--
Steven

To post a message you must first join this group.
You do not have the permission required to post.
More options Mar 1 2012, 12:39 am
Newsgroups: comp.lang.python
From: Xah Lee <xah...@gmail.com>
Date: Wed, 29 Feb 2012 21:39:37 -0800 (PST)
Local: Thurs, Mar 1 2012 12:39 am
Subject: Re: lang comparison: in-place algorithm for reversing a list in Perl, Python, Lisp
On Feb 29, 9:01 pm, Steven D'Aprano <steve

+comp.lang.pyt...@pearwood.info> wrote:
> You don't need a temporary variable to swap two values in
> Python. A better way to reverse a list using more Pythonic idioms is:

> for i in range(len(list_a)//2):
>     list_a[i], list_a[-i-1] = list_a[-i-1], list_a[i]

forgive me sir, but i haven't been at python for a while. :)
i was, actually, refreshing myself of what little polyglot skills i
have.

Xah

To post a message you must first join this group.
You do not have the permission required to post.
More options Mar 1 2012, 1:07 am
Newsgroups: comp.lang.python
From: Evan Driscoll <drisc...@cs.wisc.edu>
Date: Thu, 01 Mar 2012 00:07:21 -0600
Local: Thurs, Mar 1 2012 1:07 am
Subject: Re: Re: lang comparison: in-place algorithm for reversing a list in Perl, Python, Lisp

On 2/29/2012 23:05, Dan Stromberg wrote:

> On Wed, Feb 29, 2012 at 8:07 PM, Xah Lee <xah...@gmail.com
> <mailto:xah...@gmail.com>> wrote:

>     emacs lisp} code to illustrate.

> Aren't in-place reversals rather non-functional?

There is one place where they're reasonably idiomatic in Lispy
languages, at least by my understanding. That occurs when you are
writing a function that returns a list and there is a natural recursive
way to build up the answer -- but backwards. The idiom then is to build
up a temporary list up backwards, then call an in-place reversal
function. (NREVERSE in Common Lisp. I thought there was a reverse! in
Scheme, but apparently not.)

This doesn't break the external view of a pure function because the list
that's being reversed is a fresh, temporary list, which is why this
idiom would even fit in pretty well in Scheme.

Evan

To post a message you must first join this group.
You do not have the permission required to post.
 Discussion subject changed to "lang comparison: in-place algorithm for reversing a list in Perl,Python, Lisp" by WJ
More options Mar 1 2012, 1:37 am
Newsgroups: comp.lang.lisp, comp.emacs, comp.lang.python, comp.lang.perl.misc
Followup-To: comp.lang.lisp
From: "WJ" <w_a_x_...@yahoo.com>
Date: 1 Mar 2012 06:37:45 GMT
Local: Thurs, Mar 1 2012 1:37 am
Subject: Re: lang comparison: in-place algorithm for reversing a list in Perl,Python, Lisp

MatzLisp:

a = [2,3,5,8]
==>[2, 3, 5, 8]
a.reverse!
==>[8, 5, 3, 2]
a
==>[8, 5, 3, 2]

To post a message you must first join this group.
You do not have the permission required to post.
 Discussion subject changed to "lang comparison: in-place algorithm for reversing a list in Perl, Python, Lisp" by Rainer Weikusat
More options Mar 1 2012, 9:39 am
Newsgroups: comp.lang.lisp, comp.emacs, comp.lang.python, comp.lang.perl.misc
From: Rainer Weikusat <rweiku...@mssgmbh.com>
Date: Thu, 01 Mar 2012 14:39:25 +0000
Local: Thurs, Mar 1 2012 9:39 am
Subject: Re: lang comparison: in-place algorithm for reversing a list in Perl, Python, Lisp

Xah Lee <xah...@gmail.com> writes:

[...]

Better algorithm for that (expects an array reference as first
argument)

sub rev
{
my \$a = \$_[0];
my (\$n0, \$n1, \$x);

\$n0 = 0;
\$n1 = \$#\$a;
while (\$n0 < \$n1) {
\$x = \$a->[\$n0];
\$a->[\$n0] = \$a->[\$n1];
\$a->[\$n1] = \$x;

++\$n0;
--\$n1;
}

}

NB: The fact that a sufficiently sophisticated compiler might be able
to fix this automatically emphasizes the deficiencies of the original
attempt, it doesn't excuse them.

To post a message you must first join this group.
You do not have the permission required to post.
 Discussion subject changed to "lang comparison: in-place algorithm for reversing a list in Perl,Python, Lisp" by Xah Lee
More options Mar 1 2012, 5:04 pm
Newsgroups: comp.lang.lisp, comp.lang.python, comp.lang.perl.misc
From: Xah Lee <xah...@gmail.com>
Date: Thu, 1 Mar 2012 14:04:10 -0800 (PST)
Local: Thurs, Mar 1 2012 5:04 pm
Subject: Re: lang comparison: in-place algorithm for reversing a list in Perl,Python, Lisp
On Mar 1, 7:04 am, Kaz Kylheku <k...@kylheku.com> wrote:
lisp:
(floor (/ x y)) --[rewrite]--> (floor x y)

Thanks for this interesting point.

I don't think it's a good lang design, more of a lang quirk.

similarly, in Python 2.x,
x/y
will work when both x and y are integers. Also,
x//y
works too, but that // is just perlish unreadable syntax quirk.

similarly, in perl, either one
require POSIX; floor(x/y);
the require POSIX instead of Math is a quirk. But even, floor should
really be builtin.
or
using a perl hack
int(x/y)

all of the above are quirks. They rely on computer engineering by-
products (such as int), or rely on the lang's idiosyncrasy. One easy
way to measure it is whether a programer can read and understand a
program without having to delve into its idiosyncrasies. Problem with
these lang idioms is that it's harder to understand, and whatever
advantage/optimization they provide is microscopic and temporary.

best is really floor(x/y).

idiomatic programing, is a bad thing. It was spread by perl, of
course, in the 1990s. Idiomatic lang, i.e. lang with huge number of
bizarre idioms, such as perl, is the worst.

Xah

To post a message you must first join this group.
You do not have the permission required to post.
More options Mar 1 2012, 5:14 pm
Newsgroups: comp.lang.lisp, comp.lang.python, comp.lang.perl.misc
From: Rainer Weikusat <rweiku...@mssgmbh.com>
Date: Thu, 01 Mar 2012 22:14:35 +0000
Local: Thurs, Mar 1 2012 5:14 pm
Subject: Re: lang comparison: in-place algorithm for reversing a list in Perl,Python, Lisp

Xah Lee <xah...@gmail.com> writes:

[...]

> similarly, in perl, either one
> require POSIX; floor(x/y);
> the require POSIX instead of Math is a quirk. But even, floor should
> really be builtin.
> or
> using a perl hack
> int(x/y)

> all of the above are quirks. They rely on computer engineering by-
> products (such as int),

Integral numbers are not 'a computer engineering byproduct'.

> or rely on the lang's idiosyncrasy. One easy way to measure it is
> whether a programer can read and understand a program without having
> to delve into its idiosyncrasies. Problem with these lang idioms is
> that it's harder to understand, and whatever advantage/optimization
> they provide is microscopic and temporary.

It's hard to understand for someone who knows only mathematical
idiosyncrasies and who is also convinced that this should really be
more than enough for a lifetime. But that's not some kind of 'natural
knowledge' people just happen to have but systematically drilled into
pupils from a very early age, despite most of them won't ever have any
use for any of it insofar it goes beyond + - * /.

[...]

> idiomatic programing, is a bad thing.

If you have to use something (like a particular programming language)
but you resent learning how to use it and rather make lofty excuses,
chances are that you are rather a lazy f*cker than a great philosopher
...

To post a message you must first join this group.
You do not have the permission required to post.
More options Mar 2 2012, 2:11 am
Newsgroups: comp.lang.python
From: Chris Angelico <ros...@gmail.com>
Date: Fri, 2 Mar 2012 18:11:29 +1100
Local: Fri, Mar 2 2012 2:11 am
Subject: Re: lang comparison: in-place algorithm for reversing a list in Perl,Python, Lisp

On Fri, Mar 2, 2012 at 9:04 AM, Xah Lee <xah...@gmail.com> wrote:
> One easy
> way to measure it is whether a programer can read and understand a
> program without having to delve into its idiosyncrasies.

Neither the behavior of ints nor the behavior of IEEE floating point
is a "quirk" or an "idiosyncracy". These are data types with
well-defined semantics, and you need to understand them to use them.
The fact that dividing two positive integers and producing (or casting
to) a third integer rounds the result down is just as much a part of
the definition as is two's complement negatives, which most people can
safely ignore because they "just work" the way you expect.

Learn what you're working with, if you expect to get decent results from it.

ChrisA

To post a message you must first join this group.
You do not have the permission required to post.
More options Mar 2 2012, 2:17 am
Newsgroups: comp.lang.lisp, comp.emacs, comp.lang.python, comp.lang.perl.misc
Followup-To: comp.lang.lisp
From: "WJ" <w_a_x_...@yahoo.com>
Date: 2 Mar 2012 07:17:34 GMT
Local: Fri, Mar 2 2012 2:17 am
Subject: Re: lang comparison: in-place algorithm for reversing a list in Perl,Python, Lisp

NewLisp:

> (setq lst '(2 3 5 8))
(2 3 5 8)
> (reverse lst)
(8 5 3 2)
> lst

(8 5 3 2)

To post a message you must first join this group.
You do not have the permission required to post.
More options Mar 2 2012, 6:30 am
Newsgroups: comp.lang.python, comp.lang.lisp
From: Xah Lee <xah...@gmail.com>
Date: Fri, 2 Mar 2012 03:30:29 -0800 (PST)
Local: Fri, Mar 2 2012 6:30 am
Subject: Re: lang comparison: in-place algorithm for reversing a list in Perl,Python, Lisp

Xah Lee wrote:

«… One easy way to measure it is whether a programer can read and
understand a program without having to delve into its idiosyncrasies.
…»

Chris Angelico wrote:

«Neither the behavior of ints nor the behavior of IEEE floating point
is a "quirk" or an "idiosyncracy". …»

they are computer engineering by-products. Are quirks and
idiosyncracies. Check out a advanced lang such as Mathematica. There,
one can learn how the mathematical concept of integer or real number
are implemented in a computer language, without lots by-products of
comp engineering as in vast majority of langs (all those that chalks
up to some IEEEEEEE. (which, sadly, includes C, C++, java, perl,
python, lisp, and almost all. (lisp idiots speak of the jargon “number
tower” instead IEEEE.) (part of the reason almost all langs stick to
some IEEEEEEEE stuff is because it's kinda standard, and everyone
understand it, in the sense that unix RFC (aka really fucking common)
is wide-spread because its free yet technically worst. (in a sense,
when everybody's stupid, there arise a cost to not be stupid.)))).

Xah