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

Discussion in 'Python' started by Xah Lee, Mar 1, 2012.

  1. Xah Lee

    Xah Lee Guest

    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::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
     
    Xah Lee, Mar 1, 2012
    #1
    1. Advertising

  2. Re: lang comparison: in-place algorithm for reversing a list inPerl, 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
    > list_a = 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, list_a[-i-1] = list_a[-i-1], list_a


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

    list_a.reverse()



    --
    Steven
     
    Steven D'Aprano, Mar 1, 2012
    #2
    1. Advertising

  3. Xah Lee

    Xah Lee Guest

    On Feb 29, 9:01 pm, Steven D'Aprano <steve
    > 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, list_a[-i-1] = list_a[-i-1], list_a


    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
     
    Xah Lee, Mar 1, 2012
    #3
  4. Re: Re: lang comparison: in-place algorithm for reversing a listin Perl, Python, Lisp

    On 2/29/2012 23:05, Dan Stromberg wrote:
    >
    > On Wed, Feb 29, 2012 at 8:07 PM, Xah Lee <
    > <mailto:>> wrote:
    >
    > This page tells you what's “In-place algorithm”, using {python,perl,
    > 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


    -----BEGIN PGP SIGNATURE-----
    Version: GnuPG v1.4.10 (MingW32)
    Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

    iQEcBAEBAgAGBQJPTxIgAAoJEAOzoR8eZTzglAUH/RB1S/HS/D3H8XGJg/S6ODiG
    HHov8G07iqd9Vl9qNMUVJ5yAFvaDWFjJZGx3jnOIesz64D6GLpDWdS+qhG5yjb3V
    UTMQ2cSKO0HHnien97s8EDrkklVqjWL91MSmN6aElTEBfppvUfl3ks9BKTuZGJXy
    VPzH9z1J1Dlc5fdsPvKcbk+5Sz67A8JGRF0R26K0Lzbv/tjfKmQTsKnMwobiuiFG
    UGlkzy4uyOQSrHcPVZbk8oWU/65cd69QsFOyT2KyAa8p4NEzWUYNe4kiSuCgc97r
    bT8N7CF7KbLN9/oo68wDYuL6z5mTrZae3WwnTD+9aEI8MvR6Xr5Fyy4q0rNBNRY=
    =kBlI
    -----END PGP SIGNATURE-----
     
    Evan Driscoll, Mar 1, 2012
    #4
  5. Xah Lee

    WJ Guest

    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 = 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::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))
    >


    MatzLisp:

    a = [2,3,5,8]
    ==>[2, 3, 5, 8]
    a.reverse!
    ==>[8, 5, 3, 2]
    a
    ==>[8, 5, 3, 2]
     
    WJ, Mar 1, 2012
    #5
  6. Re: lang comparison: in-place algorithm for reversing a list in Perl, Python, Lisp

    Xah Lee <> writes:

    [...]


    > # 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);


    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.
     
    Rainer Weikusat, Mar 1, 2012
    #6
  7. Xah Lee

    Xah Lee Guest

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

    On Mar 1, 7:04 am, Kaz Kylheku <> 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
     
    Xah Lee, Mar 1, 2012
    #7
  8. Xah Lee <> 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
    ....
     
    Rainer Weikusat, Mar 1, 2012
    #8
  9. Re: lang comparison: in-place algorithm for reversing a list inPerl,Python, Lisp

    On Fri, Mar 2, 2012 at 9:04 AM, 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.


    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
     
    Chris Angelico, Mar 2, 2012
    #9
  10. Xah Lee

    WJ Guest

    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 = 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::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)
     
    WJ, Mar 2, 2012
    #10
  11. Xah Lee

    Xah Lee Guest

    Re: lang comparison: in-place algorithm for reversing a list inPerl,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
     
    Xah Lee, Mar 2, 2012
    #11
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. ekzept
    Replies:
    0
    Views:
    372
    ekzept
    Aug 10, 2007
  2. Mark Tarver
    Replies:
    22
    Views:
    1,310
    J Kenneth King
    Apr 26, 2009
  3. nanothermite911fbibustards
    Replies:
    0
    Views:
    378
    nanothermite911fbibustards
    Jun 16, 2010
  4. nanothermite911fbibustards
    Replies:
    0
    Views:
    318
    nanothermite911fbibustards
    Jun 16, 2010
  5. Xah Lee
    Replies:
    5
    Views:
    766
Loading...

Share This Page