あえて作る
Common Lispでrangeをわざわざ作る必要は「ない」のですが、勉強になるかと思い、作ってみました。まずは普通に作ってみます。
(defun range-normal (start end &optional (step 1))
(if (> start end)
'()
(cons start (range-normal (+ start step) end step))))
* (time (range-normal 1 1000 3))
Evaluation took:
0.000 seconds of real time
0.000039 seconds of total run time (0.000037 user, 0.000002 system)
100.00% CPU
78,096 processor cycles
0 bytes consed
(1 4 7 10 13 16 19 22 25 28 31 34 37 40 43 46 49 52 55 58 61 64 67 70 73 76 79
82 85 88 91 94 97 100 103 106 109 112 115 118 121 124 127 130 133 136 139 142
145 148 151 154 157 160 163 166 169 172 175 178 181 184 187 190 193 196 199
202 205 208 211 214 217 220 223 226 229 232 235 238 241 244 247 250 253 256
259 262 265 268 271 274 277 280 283 286 289 292 295 298 301 304 307 310 313
316 319 322 325 328 331 334 337 340 343 346 349 352 355 358 361 364 367 370
373 376 379 382 385 388 391 394 397 400 403 406 409 412 415 418 421 424 427
430 433 436 439 442 445 448 451 454 457 460 463 466 469 472 475 478 481 484
487 490 493 496 499 502 505 508 511 514 517 520 523 526 529 532 535 538 541
544 547 550 553 556 559 562 565 568 571 574 577 580 583 586 589 592 595 598
601 604 607 610 613 616 619 622 625 628 631 634 637 640 643 646 649 652 655
658 661 664 667 670 673 676 679 682 685 688 691 694 697 700 703 706 709 712
715 718 721 724 727 730 733 736 739 742 745 748 751 754 757 760 763 766 769
772 775 778 781 784 787 790 793 796 799 802 805 808 811 814 817 820 823 826
829 832 835 838 841 844 847 850 853 856 859 862 865 868 871 874 877 880 883
886 889 892 895 898 901 904 907 910 913 916 919 922 925 928 931 934 937 940
943 946 949 952 955 958 961 964 967 970 973 976 979 982 985 988 991 994 997
1000)
0.000039 secondsかかっています。Common Lispの良いところは、このようなベンチマークをtimeというマクロで簡単に測定できることです。Pythonにもtimeitがありますが、Common Lispのtimeのほうがはるかに使いやすいです。今度は少し改良を加えて(末尾再帰)以下のようなものにしてみます。
(defun range-tail (start end acc step)
(if (> start end)
acc
(range-tail start (- end step) (cons end acc) step)))
(defun range (start end &optional (step 1))
(range-tail start end '() step))
* (time (range 1 1000 3))
Evaluation took:
0.000 seconds of real time
0.000008 seconds of total run time (0.000008 user, 0.000000 system)
100.00% CPU
15,110 processor cycles
0 bytes consed
(1 4 7 10 13 16 19 22 25 28 31 34 37 40 43 46 49 52 55 58 61 64 67 70 73 76 79
82 85 88 91 94 97 100 103 106 109 112 115 118 121 124 127 130 133 136 139 142
145 148 151 154 157 160 163 166 169 172 175 178 181 184 187 190 193 196 199
202 205 208 211 214 217 220 223 226 229 232 235 238 241 244 247 250 253 256
259 262 265 268 271 274 277 280 283 286 289 292 295 298 301 304 307 310 313
316 319 322 325 328 331 334 337 340 343 346 349 352 355 358 361 364 367 370
373 376 379 382 385 388 391 394 397 400 403 406 409 412 415 418 421 424 427
430 433 436 439 442 445 448 451 454 457 460 463 466 469 472 475 478 481 484
487 490 493 496 499 502 505 508 511 514 517 520 523 526 529 532 535 538 541
544 547 550 553 556 559 562 565 568 571 574 577 580 583 586 589 592 595 598
601 604 607 610 613 616 619 622 625 628 631 634 637 640 643 646 649 652 655
658 661 664 667 670 673 676 679 682 685 688 691 694 697 700 703 706 709 712
715 718 721 724 727 730 733 736 739 742 745 748 751 754 757 760 763 766 769
772 775 778 781 784 787 790 793 796 799 802 805 808 811 814 817 820 823 826
829 832 835 838 841 844 847 850 853 856 859 862 865 868 871 874 877 880 883
886 889 892 895 898 901 904 907 910 913 916 919 922 925 928 931 934 937 940
943 946 949 952 955 958 961 964 967 970 973 976 979 982 985 988 991 994 997
1000)
0.000008 secondsとなり、約1/5になりました。ちょっとしたことでこんなにも変わるものなのですね。lenもやってみる
同様の手口？でリストの長さを返すlenもやってみます。もちろんこれも作る必要のないものですが、勉強のため…
(defun len-tail (l acc)
(if (eql l '())
acc
(len-tail (cdr l) (1+ acc))))
(defun len (l)
(when (typep l 'list)
(len-tail l 0)))
whenのところで与えられた引数の型がlistだった場合のみlen-tailの処理を行います。そしてlen-tailでは、リストが空の場合、accの値、つまり0を返します。それ以外は(cdr l)を新たなlとし、accには(car l)があったということで、1加算します。この1+はもとの値を変化させず、加算した値を返すというもので、incfという同じような動きをするものなのですが、こちらはもとの値ごと変化させるというような違いがあります。
* (defparameter x 0)
X
* x
0
* (1+ x)
1
* x
0
* (incf x)
1
* x
1