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
--
http://mail.python.org/mailman/listinfo/python-list
