Re: lang comparison: in-place algorithm for reversing a list in Perl, Python, Lisp
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))
>
MatzLisp:
a = [2,3,5,8]
==>[2, 3, 5, 8]
a.reverse!
==>[8, 5, 3, 2]
a
==>[8, 5, 3, 2]
--
http://mail.python.org/mailman/listinfo/python-list
Re: lang comparison: in-place algorithm for reversing a list in Perl, Python, Lisp
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)
--
http://mail.python.org/mailman/listinfo/python-list
Re: f python?
Xah Lee wrote: > > so recently i switched to a Windows version of python. Now, Windows > version takes path using win backslash, instead of cygwin slash. This > fucking broke my find/replace scripts that takes a dir level as input. > Because i was counting slashes. Slashes can work under windows, up to a point: C:\>cd info/source C:\info\source> Also, most languages I use under windows allow you to use slashes in paths: C:\>ruby -e "puts IO.read( 'c:/info/frag' )" 275439 10 102972 10 102972 11 102972 10 101085 108111 -- http://mail.python.org/mailman/listinfo/python-list
Re: Lisp refactoring puzzle
Xah Lee wrote: > it's funny, in all these supposedly modern high-level langs, they > don't provide even simple list manipulation functions such as union, > intersection, and the like. Not in perl, not in python, not in lisps. Ruby has them. Intersection: [2,3,5,8] & [0,2,4,6,8] ==>[2, 8] Union: [2,3,5,8] | [0,2,4,6,8] ==>[2, 3, 5, 8, 0, 4, 6] -- http://mail.python.org/mailman/listinfo/python-list
Re: Lisp refactoring puzzle
Petter Gustad wrote: > Xah Lee writes: > > > it's funny, in all these supposedly modern high-level langs, they > > don't provide even simple list manipulation functions such as union, > > intersection, and the like. Not in perl, not in python, not in lisps. > > In Common Lisp you have: > > CL-USER> (union '(a b c) '(b c d)) > (A B C D) > CL-USER> (intersection '(a b c) '(b c d)) > (C B) The order was changed. COBOL Lisp is always mindless. * (union '(2 2 3 4) '(7 7 8 9)) (4 3 2 2 7 7 8 9) The right way (MatzLisp): [2,2,3,4] | [7,7,8,9] ==>[2, 3, 4, 7, 8, 9] -- http://mail.python.org/mailman/listinfo/python-list
Re: toy list processing problem: collect similar terms
Pascal J. Bourguignon wrote:
> Xah Lee writes:
>
>
> > here's a interesting toy list processing problem.
> >
> > I have a list of lists, where each sublist is labelled by
> > a number. I need to collect together the contents of all sublists
> > sharing
> > the same label. So if I have the list
> >
> > ((0 a b) (1 c d) (2 e f) (3 g h) (1 i j) (2 k l) (4 m n) (2 o p) (4
> > q r) (5 s t))
> >
> > where the first element of each sublist is the label, I need to
> > produce:
> >
> > output:
> > ((a b) (c d i j) (e f k l o p) (g h) (m n q r) (s t))
> >
> > a Mathematica solution is here:
> > http://xahlee.org/UnixResource_dir/writ/notations_mma.html
> >
> > R5RS Scheme lisp solution:
> > http://xahlee.org/UnixResource_dir/writ/Sourav_Mukherjee_sourav.work
> > _gmail.scm by Sourav Mukherjee
> >
> > also, a Common Lisp solution can be found here:
> > http://groups.google.com/group/comp.lang.lisp/browse_frm/thread/5d1d
> > ed8824bc750b?
>
> It's too complex. Just write:
>
> (let ((list '((0 a b) (1 c d) (2 e f) (3 g h) (1 i j) (2 k l) (4 m n)
> (2 o p) (4 q r) (5 s t
>
> (mapcar (lambda (class) (reduce (function append) class :key
> (function rest)))
> (com.informatimago.common-lisp.list:equivalence-classes list :key
> (function first)))
>
>)
>
> --> ((S T) (Q R M N) (G H) (O P K L E F) (I J C D) (A B))
Clojure:
(def groups '((0 a b)(1 c d)(2 e f)(3 g h)(1 i j)(2 k l)(4 m n)
(2 o p)(4 q r) (5 s t)))
Using group-by:
(map (fn[[k v]](flatten (map rest v))) (group-by first groups))
Using reduce:
(map #(flatten(rest %)) (reduce (fn[h [k & v]]
(merge-with concat h {k v})) {} groups))
--
http://mail.python.org/mailman/listinfo/python-list
Re: toy list processing problem: collect similar terms
Xah Lee wrote: > here's a interesting toy list processing problem. > > I have a list of lists, where each sublist is labelled by > a number. I need to collect together the contents of all sublists > sharing > the same label. So if I have the list > > ((0 a b) (1 c d) (2 e f) (3 g h) (1 i j) (2 k l) (4 m n) (2 o p) (4 q > r) (5 s t)) > > where the first element of each sublist is the label, I need to > produce: > > output: > ((a b) (c d i j) (e f k l o p) (g h) (m n q r) (s t)) > Solving without hash-tables or "group-by". Using Guile: First, sort the groups by the numbers. (stable-sort groups (lambda(a b)(< (car a) (car b ((0 a b) (1 c d) (1 i j) (2 e f) (2 k l) (2 o p) (3 g h) (4 m n) (4 q r) (5 s t)) Next, flatten the list. (append-map identity step1) (0 a b 1 c d 1 i j 2 e f 2 k l 2 o p 3 g h 4 m n 4 q r 5 s t) Remove duplicate numbers. (delete-duplicates step2) (0 a b 1 c d i j 2 e f k l o p 3 g h 4 m n q r 5 s t) We now need a very useful function called "scan". ;; Yields sublists of contiguous items that satisfy func. (define (scan func lst) (let ((tail (find-tail func lst))) (if tail (cons (take-while func tail) (scan func (drop-while func tail))) '( (scan symbol? step3) ((a b) (c d i j) (e f k l o p) (g h) (m n q r) (s t)) -- http://mail.python.org/mailman/listinfo/python-list
