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

WJ w_a_x_man at yahoo.com
Fri Mar 2 08:17:34 CET 2012


Xah Lee wrote:

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

NewLisp:

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



More information about the Python-list mailing list