[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.lisp

Fast way to do or operations from two string

james

10/13/2015 2:49:00 PM

Input are two string "0101" "1010" which is binary format , the output is a bit-array

Expected behaviour is like (string-or "0101" "1010") --> #*1111
12 Answers

Christian Jullien

10/13/2015 3:02:00 PM

0

On Tuesday, October 13, 2015 at 4:48:59 PM UTC+2, james wrote:
> Input are two string "0101" "1010" which is binary format , the output is a bit-array
>
> Expected behaviour is like (string-or "0101" "1010") --> #*1111

Quick and dirty solution:

(defun string-or (s1 s2)
(let* ((*read-base* 2)
(i1 (read-from-string s1))
(i2 (read-from-string s2)))
(format nil "~b" (logior i1 i2))))

(format t "~a~%" (string-or "0101" "1010"))

Antsan

10/13/2015 4:03:00 PM

0

Am Dienstag, 13. Oktober 2015 16:48:59 UTC+2 schrieb james:
> Input are two string "0101" "1010" which is binary format , the output is a bit-array
>
> Expected behaviour is like (string-or "0101" "1010") --> #*1111

READ-FROM-STRING is probably slow.

There is the LOOP keyword ACROSS. With that you can loop over the input strings in
parallel, like this:
(loop for x from 0
for b1 across s1
for b2 across s2
...)
Prepare a bit vector with the correct size and :initial-element 0 and the rest
should be obvious.

Teemu Likonen

10/13/2015 4:13:00 PM

0

james [2015-10-13 07:48:50-07] wrote:

> Input are two string "0101" "1010" which is binary format , the output
> is a bit-array
>
> Expected behaviour is like (string-or "0101" "1010") --> #*1111

This should be pretty fast:


(defun string-or (&rest strings)
(loop :with max-length := (reduce #'max strings :key #'length)
:with bit-array := (make-array max-length :element-type 'bit)
:for i :from 0 :below max-length
:do (setf (aref bit-array (- max-length i 1))
(loop :for string :in strings
:for length := (length string)
:if (< i length)
:do (ecase (aref string (- length i 1))
(#\0)
(#\1 (return 1)))
:finally (return 0)))
:finally (return bit-array)))

Carlos

10/13/2015 5:17:00 PM

0

[james <dinglei2008@gmail.com>, 2015-10-13 07:48]
> Input are two string "0101" "1010" which is binary format , the
> output is a bit-array
>
> Expected behaviour is like (string-or "0101" "1010") --> #*1111

Yet another possibility:

CL-USER> (map 'bit-vector (lambda (a b)
(logior (- (char-code a) (char-code #\0))
(- (char-code b) (char-code #\0))))
"0101" "1101")
#*1101

I think it's the fastest (yet).
--

Pascal J. Bourguignon

10/13/2015 5:49:00 PM

0

Christian Jullien <christian.jullien@novasparks.com> writes:

> On Tuesday, October 13, 2015 at 4:48:59 PM UTC+2, james wrote:
>> Input are two string "0101" "1010" which is binary format , the output is a bit-array
>>
>> Expected behaviour is like (string-or "0101" "1010") --> #*1111
>
> Quick and dirty solution:
>
> (defun string-or (s1 s2)
> (let* ((*read-base* 2)
> (i1 (read-from-string s1))
> (i2 (read-from-string s2)))
> (format nil "~b" (logior i1 i2))))
>
> (format t "~a~%" (string-or "0101" "1010"))

Even quicker:

user1> (setf *read-base* 2 *print-base* 2)

10
user1> (logior 0101 1010)
1111


user1> (setf *read-base* 10. *print-base* 10.)

10


or else:

user1> (defun string-or (a b)
(format nil "~V,'0B"
(max (length a) (length b))
(logior (parse-integer a :radix 2)
(parse-integer b :radix 2))))
string-or
user1> (string-or "0101" "1010")
"1111"

--
__Pascal Bourguignon__ http://www.informat...
â??The factory of the future will have only two employees, a man and a
dog. The man will be there to feed the dog. The dog will be there to
keep the man from touching the equipment.� -- Carl Bass CEO Autodesk

Zach Beane

10/13/2015 7:24:00 PM

0

Carlos <angus@quovadis.com.ar> writes:

> [james <dinglei2008@gmail.com>, 2015-10-13 07:48]
>> Input are two string "0101" "1010" which is binary format , the
>> output is a bit-array
>>
>> Expected behaviour is like (string-or "0101" "1010") --> #*1111
>
> Yet another possibility:
>
> CL-USER> (map 'bit-vector (lambda (a b)
> (logior (- (char-code a) (char-code #\0))
> (- (char-code b) (char-code #\0))))
> "0101" "1101")
> #*1101
>
> I think it's the fastest (yet).

It is better to use digit-char-p than this subtraction stuff.

Zach

Teemu Likonen

10/13/2015 8:15:00 PM

0

Carlos [2015-10-13 19:16:51+02] wrote:

> CL-USER> (map 'bit-vector (lambda (a b)
> (logior (- (char-code a) (char-code #\0))
> (- (char-code b) (char-code #\0))))
> "0101" "1101")
> #*1101
>
> I think it's the fastest (yet).

In SBCL, it seems that my version is still the fastest. :-)
Here's slightly more optimized version:


(defun string-or (&rest strings)
(loop :with lengths := (mapcar #'length strings)
:with max-length := (reduce #'max lengths)
:with bit-array := (make-array max-length :element-type 'bit)
:for i :from 0 :below max-length
:do (setf (aref bit-array (- max-length i 1))
(loop :for string :in strings
:for length :in lengths
:if (< i length)
:do (ecase (aref string (- length i 1))
(#\1 (return 1))
(#\0))
:finally (return 0)))
:finally (return bit-array)))

Carlos

10/13/2015 9:42:00 PM

0

[Teemu Likonen <tlikonen@iki.fi>, 2015-10-13 23:15]
> Carlos [2015-10-13 19:16:51+02] wrote:
[...]
> > I think it's the fastest (yet).
>
> In SBCL, it seems that my version is still the fastest. :-)

Mine is faster in *my* SBCL (that's why it's mine ;-) but only because I
declare the parameter types; it gets a 3x speedup then.

Yours doesn't need that and accepts more parameters. Declaring the loop
variable as string shaves a 10% more and gives it the advantage (for
the only case I tested).

Here are both, with declarations:

CL-USER> (defun string-ior (a b)
(declare (string a b)
(optimize (speed 3)))
(map 'bit-vector (lambda (a b)
(logior (- (char-code a) (char-code #\0))
(- (char-code b) (char-code #\0))))
a b))
STYLE-WARNING: redefining COMMON-LISP-USER::STRING-IOR in DEFUN
STRING-IOR
CL-USER> (defun string-or (&rest strings)
(declare (optimize (speed 3)))
(loop :with lengths := (mapcar #'length strings)
:with max-length := (reduce #'max lengths)
:with bit-array := (make-array max-length :element-type 'bit)
:for i :from 0 :below max-length
:do (setf (aref bit-array (- max-length i 1))
(loop :for string :of-type string :in strings
:for length :in lengths
:if (< i length)
:do (ecase (aref string (- length i 1))
(#\1 (return 1))
(#\0))
:finally (return 0)))
:finally (return bit-array)))

STYLE-WARNING: redefining COMMON-LISP-USER::STRING-OR in DEFUN
STRING-OR
CL-USER> (time (dotimes (_ 1000000) (string-ior "01110111000010101" "01110101010011111")))
Evaluation took:
0.970 seconds of real time
0.756000 seconds of total run time (0.756000 user, 0.000000 system)
77.94% CPU
2,727,366,016 processor cycles
303,990,736 bytes consed

NIL
CL-USER> (time (dotimes (_ 1000000) (string-or "01110111000010101" "01110101010011111")))
Evaluation took:
0.956 seconds of real time
0.936000 seconds of total run time (0.936000 user, 0.000000 system)
97.91% CPU
2,689,284,626 processor cycles
127,998,096 bytes consed

NIL
--

Pascal J. Bourguignon

10/13/2015 9:48:00 PM

0

Teemu Likonen <tlikonen@iki.fi> writes:

> Carlos [2015-10-13 19:16:51+02] wrote:
>
>> CL-USER> (map 'bit-vector (lambda (a b)
>> (logior (- (char-code a) (char-code #\0))
>> (- (char-code b) (char-code #\0))))
>> "0101" "1101")
>> #*1101
>>
>> I think it's the fastest (yet).
>
> In SBCL, it seems that my version is still the fastest. :-)
> Here's slightly more optimized version:
>
>
> (defun string-or (&rest strings)
> (loop :with lengths := (mapcar #'length strings)
> :with max-length := (reduce #'max lengths)
> :with bit-array := (make-array max-length :element-type 'bit)
> :for i :from 0 :below max-length
> :do (setf (aref bit-array (- max-length i 1))
> (loop :for string :in strings
> :for length :in lengths
> :if (< i length)
> :do (ecase (aref string (- length i 1))
> (#\1 (return 1))
> (#\0))
> :finally (return 0)))
> :finally (return bit-array)))

Using high level code takes 20% less processor cycles:

(defun string-or (&rest strings)
(declare (optimize (speed 3)))
(loop :with lengths := (mapcar #'length strings)
:with max-length := (reduce #'max lengths)
:with bit-array := (make-array max-length :element-type 'bit)
:for i :from 0 :below max-length
:do (setf (aref bit-array (- max-length i 1))
(loop :for string :in strings
:for length :in lengths
:if (< i length)
:do (ecase (aref string (- length i 1))
(#\1 (return 1))
(#\0))
:finally (return 0)))
:finally (return bit-array)))

(defun string-or-h (&rest strings)
(declare (optimize (speed 3)))
(apply (function bit-ior)
(mapcar (lambda (string) (map 'bit-vector (function digit-char-p) string))
strings)))


cl-user> (progn (time (string-or *a* *b*)) (values))
Evaluation took:
0.000 seconds of real time
0.000000 seconds of total run time (0.000000 user, 0.000000 system)
100.00% CPU
1,692,040 processor cycles
0 bytes consed

; No value
cl-user> (progn (time (string-or-h *a* *b*)) (values))
Evaluation took:
0.001 seconds of real time
0.000000 seconds of total run time (0.000000 user, 0.000000 system)
0.00% CPU
1,345,796 processor cycles
31,904 bytes consed

; No value
cl-user>


--
__Pascal Bourguignon__ http://www.informat...
â??The factory of the future will have only two employees, a man and a
dog. The man will be there to feed the dog. The dog will be there to
keep the man from touching the equipment.� -- Carl Bass CEO Autodesk

james

10/14/2015 2:26:00 AM

0

On Tuesday, October 13, 2015 at 10:48:59 PM UTC+8, james wrote:
> Input are two string "0101" "1010" which is binary format , the output is a bit-array
>
> Expected behaviour is like (string-or "0101" "1010") --> #*1111

Thanks for all post, finally my test code could pass with the faster string-or.
I also googled "write fast lisp code" and find lots of tips.