lang comparison: in-place algorithm for reversing a list in Perl,Python, Lisp

[Xah Lee]

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

This page tells you what's “In-place algorithm”, using {python, perl,
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 = 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
list_a = 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:umper;

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:umper;
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

 

[WJ]

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

This page tells you what's “In-place algorithm”, using {python, perl,
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 = 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
list_a = 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:umper;

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:umper;
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))

MatzLisp:

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

 

[Rainer Weikusat]

[...]

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

use strict;
use Data:umper;
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);

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.

 

[Xah Lee]

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

 

[Rainer Weikusat]

[...]

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

 

[WJ]

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

This page tells you what's “In-place algorithm”, using {python, perl,
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 = 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
list_a = 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:umper;

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:umper;
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
NewLisp:

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

(8 5 3 2)