-
Notifications
You must be signed in to change notification settings - Fork 4
/
Copy pathlibfunc.tex
1328 lines (1183 loc) · 55.8 KB
/
libfunc.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
\chapter{Library Functions} \label{chap:libfunc}
% chapter 13: libfunc
예전에는, 특정 run-time library는 C 언어의 표준의 한 부분이 아니었습니다.
ANSI/ISO Standard C의 출현으로 대부분의 전통적인 (traditional) run-time
library는 (Chapter~\ref{chap:stdio}의 stdio 함수들을 포함) 표준이 되었습니다.
특별히 중요한 라이브러리 함수들은 각각 다른 section에 설명되었습니다; 메모리
할당에 관련된 \TT{malloc}과 \TT{free}에 관한 것은 \ref{chap:memalloc}~장에
설명되었으며, \verb+<stdio.h>+에 나온 ``standard I/O'' 함수들은
Chapter~\ref{chap:stdio}에 설명되었습니다.
이 chapter는 다음과 같이 나누어집니다:
\begin{description}
\item String Function: \ql{13.1}--\ql{13.7}
\item Sorting: \ql{13.8}--\ql{13.11}
\item Date and Time: \ql{13.12}--\ql{13.14}
\item Random Numbers: \ql{13.15}--\ql{13.21}
\item Other Library Functions: \ql{13.22}-\ql{13.28}
\end{description}
마지막 몇 개의 질문들은 (\ql{13.25}부터 \ql{13.28}까지) link시 문제가 되는
(예를 들면, ``undefined external'' 에러) 것을 다루었습니다.
\section{String Functions}
% from 13.1
\begin{faq}
\Q{13.1}
수치를 문자로 바꾸고 싶은데 (\TT{atoi} 함수의 반대 기능),
\TT{itoa()}라는 함수가 있나요?
\A
그냥 \TT{sprintf()}를 쓰시면 됩니다. (\TT{sprintf}가 너무
복잡하고, 큰 비용(시간이나 크기 면에서)이 든다고 생각할 지
모르나, 사실 효과적으로 동작합니다.) 질문 \ql{7.5a}에 대한 답변에
나온 예를 보기 바랍니다. 질문 \ql{12.21}을 참고하기 바랍니다.
\TT{long}이나 실수도 \TT{sprintf()}를 써서 바꿀 수 있습니다
(각각 \TT{\%ld}와 \TT{\%f}를 쓰면 됨); 즉, \TT{sprintf}를
\TT{atol}이나 \TT{atof}의 반대 역할을 하는 함수라고 생각할 수 있습니다.
게다가, 어떤 식으로 출력할 것인지도 제어할 수 있습니다. (그렇기 때문에,
C 언어는 \TT{itoa} 식의 함수보다, \TT{sprintf}를 제공하는 것입니다.)
꼭 \TT{itoa}를 직접 만들어야 한다면, 다음과 같은 사항들을 고려해야 합니다:
\begin{itemize}
\item K\&R은 단순한 버전의 \TT{itoa}를 제공합니다.
\item 돌려줄 버퍼를 어떻게 할당할 것인지 생각해 봐야 합니다;
질문 \ql{7.5}를 참고 바랍니다.
\item 단순히 만들었다면, 보통 가장 적은 음수(\verb+INT_MIN+,
보통 -32,768 또는 -2,147,483,648)를 올바르게 처리하지 못할
수도 있습니다.
\end{itemize}
질문 \ql{12.21}과 \ql{20.10}도 참고 바랍니다.
\R
\cite{kr1} \S\ 3.6 \page{60} \\
\cite{kr2} \S\ 3.6 \page{64}
\T
C99 표준에 새로 추가된 \TT{long long} 타입을 쓰려면, \TT{ll} length
modifier를 써야 합니다. 즉 \TT{long}을 출력하기 위해 \TT{\%ld}를
쓴 것처럼, \TT{\%lld}를 씁니다.
마찬가지로, \verb+size_t+ 타입의 값을 쉽게 출력할 수 있도록
\TT{printf}, \TT{scanf} 형태의
함수에 \TT{z} modifier를 추가했습니다. 정수 출력에 쓰이는 conversion인,
\TT{d}, \TT{i}, \TT{o}, \TT{u}, \TT{x}, \TT{X}에 \TT{z}를 붙여서
\verb+size_t+를 쉽게 출력할 수 있습니다. 예를 들면:
\begin{verbatim}
size_t sz;
...
printf("%zu\n", sz);
\end{verbatim}
\R
\cite{c99} \S\ 7.19.6.1, \S\ 7.19.6.2 \\
\cite{hs5} \S\ 15.11.6
\end{faq}
\begin{faq}
\Q{13.2} % 13.2 COMPLETE
왜 \TT{strncpy()}는 대상 문자열에 항상 \verb+\0+을 써 주지
않는 것일까요?
\A
\TT{strncpy()}의 원래 개발 목적은 고정 크기를 갖고, \verb+\0+으로
끝나지 않는 ``문자열''\footnote{예를 들어, 초창기 C 컴파일러와 링커는
내부적으로 처리하는 심볼 테이블에 8개의 글자를 갖는 고정된 문자열을
썼습니다. 지금도 어떤 버전의 UNIX는 14개의 글자를 갖는 고정된
문자열을 쓰기도 합니다. \TT{strncpy}는 이런 문자열을 위해, 짧은
문자열을 복사할 때, 남아있는 공간을 \TT{'\\0'}으로 채워줍니다.
따라서 이런 형태의 문자열을 비교할 때, 좀 더 효과적으로 처리할 수
있습니다. 왜냐하면, \TT{'\\0'}을 찾은 계산 대신, 아무 생각 없이
\TT{n}개의 바이트를 비교하면 되기 때문입니다.}도 처리할 수
있게 하는 것이 그 목적이었습니다.
따라서, 다른 목적으로 \TT{strncpy()}를 쓸 때에는 좀 번거로운 작업이
필요합니다; (\TT{strncpy()}의 한 가지 단점은 여분의 공간에 0을 계속
기록한다는 것입니다.) 복사한 문자열이 저장된 버퍼의 끝에
수동으로 \verb+'\0'+을 채워주어야 할 필요가 있습니다. 그래서 그리 자주
쓰이는 함수가 아닙니다.
그래서, \TT{strncpy()} 대신 \TT{strncat}을
쓰기도 합니다: 대상 버퍼가 비어있는 경우, \TT{strncat}은 여러분이
\TT{strncpy}에서 기대한 작업을 수행해 줍니다:
\begin{verbatim}
*dest = '\0';
strncat(dest, source, n);
\end{verbatim}
\noindent 위 코드는 최대 \TT{n}개의 문자를 복사하며, 항상 마지막에
\TT{\\0}을 붙여 줍니다.
또 다른 방법은 다음과 같습니다:
\begin{verbatim}
sprintf (dest, "\%.*s", n, source);
\end{verbatim}
정확하게는 위 코드는 \TT{n}이 509 이하일때에만 동작합니다.
문자열이 아닌 어떤 크기의 바이트를 복사하고자 한다면 \TT{strncpy()}
대신 \TT{memcpy()}를 쓰는 것이 더 효과적입니다.
\end{faq}
\begin{faq}
\Q{13.3} % COMPLETE
다른 언어에서 제공하는 ``substr'' (문자열에서 부분 문자열을 빼내는)
함수가 있나요?
\A
없습니다. (그 이유 중 하나는, C 언어에는 문자열을 취급하는 전용의
데이터 타입이 없기 때문입니다. 질문 \ql{7.2}와
Chapter~\ref{chap:charstr} 참고하기 바랍니다.)
원본 문자열의 \TT{POS}번째에서 시작해서 길이가 \TT{LEN}인 부분 문자열을
꺼내기 위해서 다음과 같이 할 수 있습니다:
\begin{verbatim}
char dest[LEN + 1];
strncpy(dest, &source[POS], LEN);
dest[LEN] = '\0'; /* ensure \0 termination */
\end{verbatim}
\noindent 또, 질문 \ql{13.2}에서 다룬 것처럼 다음과 같이 할 수 있습니다:
\begin{verbatim}
char dest[LEN + 1] = "";
strncat(dest, &source[POS], LEN);
\end{verbatim}
\noindent 다음과 같이 포인터 형태로 할 수도 있습니다:
\begin{verbatim}
strncat(dest, source + POS, LEN);
\end{verbatim}
\noindent (정의에 의해, \TT{\&source[POS]}는 \TT{source + POS}와
완벽히 같은 표현입니다; Chapter~\ref{chap:arrayptr} 참고)
\end{faq}
\begin{faq}
\Q{13.4} % 13.4 COMPLETE
모든 문자열을 대문자로 또는 소문자로 바꾸려면 어떻게 하죠?
\A
어떤 라이브러리들은 이 역할을 위해, \TT{strupr}와 \TT{strlwr}, 또는
\TT{strupper}와 \TT{strlower}를 제공합니다만, 이식성도 없고, 표준도
아닙니다. 헤더 파일 \verb+<ctype.h>+에 정의되어 있는 매크로인
\TT{toupper}와
\TT{tolower}를 써서 이 기능을 수행하는 함수를 만들면 됩니다;
질문 \ql{13.5}를 참고 바랍니다. (매우 간단하지만, 만들 함수가
전달받은 문자열을 고칠 것이냐, 아니면 따로 공간을 할당하고 변경된
문자열을 그 곳에 저장할 것이냐는 미리 생각해 두어야 합니다;
질문 \ql{7.5}를 참고 바랍니다.)
(다국적(multinatinoal) 문자 셋을 쓸 때에는 문자 또는 문자열을
대문자 또는 소문자로 바꾸는 것은 더 복잡합니다.)
\end{faq}
\begin{faq}
\Q{13.5} % 13.5 COMPLETE
어떤 버전의 \TT{toupper()}에, 대문자를 인자로 줄 경우,
이상하게 동작합니다. 이런 것을 예상해서인지 \TT{toupper()}를
부르기 전에 \TT{islower()}를 부르는 코드도 보았습니다.
\A
오래된 버전의 \TT{toupper()}와 \TT{tolower()}의 경우, 변환이 필요없는
값이 인자로 전달되면, 제대로 동작하지 않습니다. (즉 알파벳이 아닌
문자나, 또는 이미 변환이 된 알파벳인 경우). 그래서 오래된
(또는 이식성이 아주 높은) 코드는 \TT{toupper} 또는 \TT{tolower}를
부르기 전에, \TT{islower}와 \TT{isupper}를 부르는 경향이 있습니다.
그러나, C 표준은 이러한 함수들이 어떤 값이 전달되더라도
안전하게 동작한다고 말하고 있습니다. 즉, 변경이 필요없는 문자들은
변경되지 않습니다.
\R
\cite{ansi} \S\ 4.3.2 \\
\cite{c89} \S\ 7.3.2 \\
\cite{hs} \S\ 12.9 \Page{320--1} \\
\cite{pcs} \page{182}
\end{faq}
\begin{faq}
\Q{13.6} % 13.6 COMPLETE
문자열 내용을 공백 문자를 기준으로 구별된 단어들로 끊어내고 싶습니다.
\TT{main()}이 \TT{argc}와 \TT{argv}를 처리하는 것처럼 할려면 어떻게
해야 할까요?
\A
단어 (``token'') 단위로, 문자열을 끊어주는 표준 함수
\TT{strtok()}이 있습니다. 물론, 이 함수가 이러한 모든 일을 다 처리할 수
있는 것은 아닙니다. (예를 들어, 인용(quoting)된 문자열을
제대로 처리하기 힘듭니다.) 아래에 각각 필드를 얻어서 출력하는
예를 보입니다:
\begin{verbatim}
#include <string.h>
char string[] = "this is a test";
/* not char *; see Q16.6 */
char *p;
for (p = strtok(string, " \t\n"); p != NULL;
p = strtok(NULL, " \t\n"))
printf("\"%s\"\n", p);
\end{verbatim}
또, 아래는 \TT{argv}를 한꺼번에 만들어 주는 함수입니다:
\begin{verbatim}
#include <ctype.h>
int
makeargv(char *string, char *argv[], int argvsize)
{
char *p = string;
int i;
int argc = 0;
for (i = 0; i < argvsize; i++) {
/* skip leading whitespace */
while (isspace(*p))
p++;
if (*p != '\0')
argv[argc++] = p;
else {
argv[argc] = 0;
break;
}
/* scan over arg */
while (*p != '\0' && !isspace(*p))
p++;
/* terminate arg: */
if (*p != '\0' && i < argvsize - 1)
*p++ = '\0';
}
return argc;
}
\end{verbatim}
\TT{makeargv}는 다음과 같이 호출합니다:
\begin{verbatim}
char *av[10];
int i, ac = makeargv(string, av, 10);
for (i = 0; i < ac; i++)
printf("\"%s\"\n", av[i]);
\end{verbatim}
만약 구분(separator) 문자가 중요하다면 --- 즉, 두 개의 탭이
동시에 나올 때, 한 필드가 생략되었다는 것을 알리고 싶으면 ---
\TT{strchr} 함수를 쓰는 것이 더 편할 수 있습니다:
\begin{verbatim}
#include <string.h>
char *p = string;
while (1) { /* break in middle */
char *p2 = strchr(p, '\t');
if (p2 != NULL)
*p2 = '\0';
printf("\"%s\"\n", p);
if (p2 == NULL)
break;
p = p2 + 1;
}
\end{verbatim}
여기에 나온 모든 코드는 원본 문자열에, 각 필드가 끝날 때마다
\TT{\\0}을 넣어서 각 필드를 구분할 수 있게 만듭니다. 따라서 원본
문자열이 나중에 다시 필요하다면, 이 곳에 있는 코드를 실행하기 전에
먼저 복사해 두어야 합니다.
\R
\cite{kr2} \S\ B3 \page{250} \\
\cite{ansi} \S\ 4.11.5.8 \\
\cite{c89} \S\ 7.11.5.8 \\
\cite{hs} \S\ 13.7 \Page{333--4} \\
\cite{pcs} \page{178}
\end{faq}
\begin{faq}
\Q{13.7} % 13.7 COMPLETE
와일드 카드(wildcard)와 정규식(regular expression)을 처리하려고
합니다.
\A
다음과 같은 차이점을 먼저 알아두기 바랍니다:
\begin{itemize}
\item 우선 regular expression은 \TT{ed}나 \TT{grep}과 같은
UNIX 유틸리티에서 자주 쓰입니다. Regular expression에서,
마침표(\TT{.})는 아무런 글자 하나에 매치(match)되며,
\TT{.*}는 길이에 상관없이 여러 문자열에 매치됩니다.
(물론, regular expression에는 이보다 훨씬 더 많은 기능이
있습니다.)
\item Filename wildcard는 대부분 OS에서 자주 쓰이며, 여러가지
버젼이 존재합니다. 그러나 보통 \TT{?} 문자는 아무런 글자 하나에
매치되며, \TT{*}는 길이에 상관없이 여러 문자열에 매치됩니다.
\end{itemize}
정규식 매칭에 사용되는 패키지는 많습니다. 그리고 대부분의 패키지들은
두 가지 함수를 사용합니다: 하나는 정규식을 ``컴파일(compile)''하기
위한 것이고, 다른 하나는 이 ``컴파일된'' 정규식과 문자열을
비교해주는(execute) 함수입니다.
먼저 헤더 파일 \verb+<regex.h>+나 \verb+<regexp.h>+가 있는지,
그리고 \TT{regcmp/regex}, \TT{regcomp/regexec},
\verb+re_comp/re_exec+ 함수가 존재하는 지 (이 함수들은 대개
각각의 독립적인 라이브러리 형태로 제공됩니다.) 체크해보시기 바랍니다.
인기있고, 공개인 Henry Spencer씨의 regexp 패키지를
\TT{ftp.cs.toronto.edu}에서 \TT{pub/regexp.shar.Z}로 얻을 수
있습니다. GNU 프로젝트에서는 rx라고 하는 패키지를 제공합니다.
\seealso{\ql{18.16}}
Filename wildcard matching은 (때때로 ``globbing''이라고 함) 각각의
시스템에 따라 다르게 이루어집니다. UNIX에서는 와일드 카드를
shell이 처리해 주므로, 각각의 프로그램들은 이 와일드 카드에 대해
전혀 고려하지 않아도 됩니다. 그러나 MS-DOS에서는 shell이라
할 수 있는 command interpreter가 이를 처리해 주지 않으므로,
(컴파일러가 제공하는) 와일드 카드를 처리해주는 특별한 오브젝트
파일과 함께 링크해야 합니다. (이 오브젝트 파일은 \TT{agrv}를,
와일드 카드 처리한 다음의 상태로 만들어 줍니다)
그리고 (MS-DOS와 VMS를 포함한) 대부분의
시스템에서는 와일드카드로 파일을 리스팅해주거나, 파일을 open하는
시스템 서비스들을 제공합니다. 먼저 컴파일러/라이브러리의 문서를
참고하기 바랍니다. \seealso{\ql{19.20}, \ql{20.3}}
아래는 Arjan Kenter씨가 제공한 간단한 형태의 wildcard를 처리하는
함수입니다:
\begin{verbatim}
int match(char *pat, char *str)
{
switch (*pat) {
case '\0': return !*str;
case '*': return match(pat + 1, str) ||
*str && match(pat, str + 1);
case '?': return *str && match(pat + 1, str + 1);
default: return *pat == *src &&
match(pat + 1, str + 1);
}
\end{verbatim}
\noindent 이 함수를 \verb+match("a*b.c", "aplomb.c")+로 부르면,
1을 리턴합니다.
\R
Schumacher, ed., \EM{Software Solutions in C} \S\ 3 \Page{35--71}
\end{faq}
\section{Sorting}
% from 13.8
\begin{faq}
\Q{13.8} % 13.8 COMPLETE
\TT{qsort()} 함수를 써서 문자열의 배열을 (array of strings)
정렬하려고 합니다.
\TT{strcmp()} 함수를 비교 함수로 사용했는데 동작하지 않습니다.
\A
질문하신 ``문자열의 배열 (array of strings)''은 아마도
``문자에 대한 포인터의 배열 (array of pointers to char)''를
의미한 것일 것입니다. \TT{qsort}에 전달되는 비교 함수는
정렬하고자 하는 오브젝트에 대한 포인터를 인자로 받아야 합니다.
이 경우, 문자에 대한 포인터를 가리키는 포인터를 입력 받아야 합니다.
그런데 \TT{strcmp()}는 단순히 문자를 가리키는 포인터를 입력
받습니다. 그러므로 \TT{strcmp()}를 직접 비교 함수로 사용할 수는
없습니다. 다음과 같이 wrapper 함수를 만들어야 합니다:
\begin{verbatim}
/* compare strings via pointers */
int pstrcmp(const void *p1, const void *p2)
{
return strcmp(*(char * const *)p1, *(char * const *)p2);
}
\end{verbatim}
비교 함수의 인자는 ``범용 포인터''인 \verb+const void *+이어야
합니다. 그리고 함수 내부에서 이를 원하는 형태로 (예를 들면 문자를
가리키는 포인터) 바꾸어 씁니다. 즉 이 타입의 인자는 함수 내부에서
원래의 타입인 \TT{char **}로 바뀌어지고, 다시 실제로 가리키는 타입인
\TT{char *}를 얻어서 \TT{strcmp} 함수에 전달됩니다. (ANSI 이전
컴파일러에서 쓸 때에는 \TT{void *} 대신에 \TT{char *}를 쓰고,
모든 \TT{const}를 빼면 됩니다.)
실제 \TT{qsort}는 다음과 같이 부릅니다:
\begin{verbatim}
#include <stdlib.h>
char *strings[NSTRINGS];
int nstrings;
/* nstrings cells of strings[] are to be sorted */
qsort(strings, nstrings, sizeof(char *), pstrcmp);
\end{verbatim}
% The comparison function's arguments are expressed as "generic
% pointers," const void *. They are converted back to what they
% "really are" (pointers to pointers to char) and dereferenced,
% yielding char *'s which can be passed to strcmp().
(\cite{kr2} \S\ 5.11 \Page{119--20}에 나온 것을 혼동하면 안됩니다.
그것은 표준 함수인 \TT{qsort}와는 관계없으며, \TT{char *}와
\TT{void *}가 서로 같다는 불필요한 암묵적인 가정을 하고 쓴 것입니다.)
% (Don't be misled by the discussion in K&R2 \S\ 5.11 pp.\ 119-20,
% which is not discussing the Standard library's qsort).
\TT{qsort} 비교 함수에 대한 더 자세한 정보는 --- 어떻게 선언되고 어떻게
불리워지는가에 대한 --- 질문 \ql{13.9}를 보기 바랍니다.
\R
\cite{ansi} \S\ 4.10.5.2 \\
\cite{c89} \S\ 7.10.5.2 \\
\cite{hs} \S\ 20.5 \page{419}
\end{faq}
\begin{faq}
\Q{13.9}
Structure에 대한 배열을 \TT{qsort()}로 정렬하려 합니다.
제가 만든 비교 함수는 이 structure에 대한 포인터를 받도록 했지만,
컴파일러는 \TT{qsort}에 잘못된 타입의 비교 함수가 전달되었다고
불평합니다. 어떻게 함수 포인터를 캐스팅해야 컴파일러가 불평하지
않을까요?
\A
질문 \ql{13.8}에서 다룬 것처럼, 캐스팅은 비교 함수 안에서 이루어져야
합니다. 즉 비교 함수는 ``generic pointer''인 \TT{const void *} 타입을
인자로 받도록 만들어야 합니다. 예를 들어 아래처럼 structure를
만들었다고 합시다:
\begin{verbatim}
struct mystruct {
int year, month, day;
}
\end{verbatim}
\noindent 이 때, 비교 함수는 다음과 같이 만들어야 합니다:
\begin{verbatim}
int mystructcmp(const void *p1, const void *p2)
{
const struct mystruct *sp1 = p1;
const struct mystruct *sp2 = p2;
if (sp1->year < sp2->year) return -1;
else if (sp1->year > sp2->year) return 1;
else if (sp1->month < sp2->month) return -1;
else if (sp1->month > sp2->month) return 1;
else if (sp1->day < sp2->day) return -1;
else if (sp1->day > sp2->day) return 1;
else return 0;
}
\end{verbatim}
(Generic 포인터를 \TT{struct mystruct} 포인터로 변경하는 것은,
초기화할 때인 \TT{sp1 = p1}, \TT{sp2 = p2}에서 이루어졌습니다;
\TT{p1}과 \TT{p2}가 \TT{void} 포인터이기 때문에, 컴파일러는 이
conversion을 자동으로 해 줍니다. ANSI 이전의 컴파일러에서 쓰려면
강제로 캐스팅하고, \TT{char *} 포인터를 쓰면 됩니다.
질문 \ql{7.7} 참고)
이런 형태의 \TT{mystructcmp}를 쓰기 위해, 다음과 같이 \TT{qsort}를
부릅니다:
\begin{verbatim}
#include <stdlib.h>
struct mystruct dates[NDATES];
int ndates;
/* ndates cells of dates[] are to be sorted */
qsort(dates, ndates, sizeof(struct mystruct),
mystructcmp);
\end{verbatim}
만약, structure를 가리키는 포인터를 정렬하고 싶다면, 질문 \ql{13.8}에
나온 것처럼 indirection이 필요합니다. 이 때 비교 함수는 다음과 같이
시작합니다:
\begin{verbatim}
int myptrstructcmp(const void *p1, const void *p2)
{
struct mystruct *p1 = *(struct mystruct * const *)p1;
struct mystruct *p2 = *(struct mystruct * const *)p2;
\end{verbatim}
\noindent 그리고, 다음과 같이 부릅니다:
\begin{verbatim}
struct mystruct *dateptrs[NDATES];
qsort(dateptrs, ndates, sizeof(struct mystruct *),
myptrstructcmp);
\end{verbatim}
\TT{qsort} 함수에서 쓰이는 비교 함수에 왜 이런 포인터 변환이 필요한지
이해하기 위해서 (그리고 왜 \TT{qsort}를 부를때 함수 포인터를 캐스팅하는
것이 불가능한지) \TT{qsort}가 어떤 식으로 동작하는지 알 필요가 있습니다:
\TT{qsort}는 정렬할 대상이 어떤 타입인지, 어떤 식으로 표현되어 있는지
전혀 알지 못합니다. \TT{qsort}는 단지, 전달된 조그만 메모리 블럭(little
chunks of memory)들을 섞어 줄 뿐입니다. (이 메모리 블럭에 대해 알고
있는 것은, \TT{qsort}의 세번째 인자로 받은 블럭의 크기입니다.)
두 개의 블럭을 교환(swap)해야 할 경우, \TT{qsort}는 여러분이 만든
비교 함수를 부릅니다. (실제로 교환하는 것은 \TT{memcpy}가 하는 것과
같은 방식으로 이루어집니다.)
\TT{qsort}는 어떤 타입인지 알지 못하는, 일반적인 타입에 대한 정렬을
하므로, 정렬 대상을 가리키기 위해, generic 포인터를 (\TT{void *})
씁니다. \TT{qsort}가 비교 함수를 부를때, 여러분이 만든 비교 함수는
\TT{void *}를 인자로 받도록 만들어져 있어야 하며, 실제 정렬 대상에
대해 어떤 작업을 (예를 들어 실제 비교를 하기 위해) 수행하기 위해서,
인자로 받은 포인터를 원하는 타입으로 다시 변경해야 합니다.
어떤 시스템에서는 \TT{void} 포인터가 structure 포인터와 서로 다른
표현 방식을 씁니다; 예를 들어, 실제 포인터의 길이가 다를 수 있으며,
내부 표현 방식이 다를 수 있습니다. (그렇기 때문에 캐스팅이 필요합니다.)
어떤 Structure에 대한 배열을 정렬한다고 가정해봅시다. 그리고 비교
함수가 이 structure에 대한 포인터를 받는다고 하면 다음과 같습니다:
\begin{verbatim}
int mywrongstructcmp(struct mystruct *,
struct mystruct *);
\end{verbatim}
\noindent 만약 다음과 같이 \TT{qsort}를 부르게 되면:
\begin{verbatim}
qsort(dates, ndates, sizeof(struct mystruct),
(int (*)(const void *,
const void*)mywrongstructcmp);
/* WRONG */
\end{verbatim}
이 것은, 컴파일러가 ``\TT{qsort}에 전달된 비교 함수가
제대로 동작하지 않을 수 있다''고 경고하는 것만을 없애 줄 수 있을
뿐입니다. 여기서 사용한 캐스팅은 실제 \TT{qsort}가 여러분의 비교 함수를
부를 때에는 이미 알 수 없는 것입니다: 즉, \TT{qsort}는
\TT{const void *} 타입의 인자를 만들 것이고, 여러분이 만든 비교 함수는
이 인자를 반드시 받을 수 있어야 합니다. 어떠한 메카니즘도,
\TT{qsort}가 \TT{mywrongstructcmp}를 부를 때, \TT{void} 포인터를
\TT{struct mystruct} 포인터로 바꿔 줄 수 없습니다.
따라서, 일반적으로 위와 같이 단순히 컴파일러 경고를 없애기 위한
캐스팅은 매우 나쁜 방법입니다. 컴파일러 경고는 보통 여러분에게
어떤 사항을 알려 줄려고 나온 것이기 때문에, 여러분이 어떤 식으로
동작하는지 잘 모르고 이 경고를 무시한다면, 그 결과 매우 위험한
상태가 될 수 있습니다. \seealso{\ql{4.9}}.
\R
\cite{ansi} \S\ 4.10.5.2 \\
\cite{c89} \S\ 7.10.5.2 \\
\cite{hs} \S\ 20.5 \page{419}
\end{faq}
\begin{faq}
\Q{13.10}
`linked list'를 정렬하는 방법은?
\A
때때로, 리스트를 만들 때, 정렬하며 만드는 방법이 더 쉬울 때가
많습니다. (또는 리스트 대신에 트리(tree)를 쓰는 것이 더 편할 수
있습니다.) 삽입 정렬(insertion sort)이나
병합 정렬(merge sort) 같은 알고리즘은 리스트를 쓸 때, 매우 효과적입니다.
만약 표준 라이브러리 함수를 써서 정렬하고 싶다면, 먼저 이들
리스트를 가리키는 포인터의 배열을 (임시로) 만들고, \TT{qsort()}를 쓰면
됩니다. 그리고, 이 정렬된 포인터를 이용하여, 리스트를 정리하면
됩니다.
\R
\cite{knuth} \S\ 5.2.1 \Page{80--102}, \S\ 5.2.4 \Page{159--168} \\
\cite{calgo} \S\ 8 \Page{98--100}, \S\ 12 \Page{163--175}
\end{faq}
\begin{faq}
\Q{13.11}
메모리의 크기보다 더 큰 데이터를 정렬하고 싶은데, 어떻게 하죠?
\A
외부 정렬을 (external sort) 써야 합니다. 여기에 대한 것은
\cite{knuth}에 잘 나와 있습니다. 기본적인 아이디어는, 데이터를
(메모리에 불러올 수 있을 정도의) 작은 조각으로 나누고,
이 데이터를 정렬하고 난 다음, 이를 임시 파일에 저장하고,
다 반복하였으면, 이 임시 파일들을 합치는 (merge) 것입니다.
운영 체제에서 이러한 정렬 프로그램을 제공할 수도 있으니
프로그램 안에서 이러한 프로그램을 실행시키는 것을
생각할 수도 있습니다; 질문 \ql{19.27}과 \ql{19.30}, 그리고
질문 \ql{19.28}의 예를 참고하기 바랍니다.
\R
\cite{knuth} \S\ 5.4 \Page{247--378} \\
\cite{calgo} \S\ 13 \Page{177--187}
\end{faq}
\section{Date and Time}
% from 13.12
\begin{faq}
\Q{13.12} % 13.12 COMPLETE
현재 날짜와, 요일을 알아내려면 어떻게 하죠?
\A
\TT{time()}, \TT{ctime()}, \TT{localtime()}, 또는 \TT{strftime()}을
쓰면 됩니다. (이 함수들은 매우 오래 전부터 제공되었으며, 현재 ANSI
표준입니다.) 예를 들면 다음과 같습니다\footnote{ANSI 표준에 따르면
\TT{time} 함수는 실패할 수 있으며, 이 때 \TT{(time\_t)(-1)}을
리턴합니다}:
\begin{verbatim}
#include <stdio.h>
#include <time.h>
int main()
{
time_t now;
time(&now);
printf("It's %.24s.\n", ctime(&now));
return 0;
}
\end{verbatim}
\TT{localtime}과 \TT{strftime}은 다음과 같이 씁니다:
\begin{verbatim}
struct tm *tmp = localtime(&now);
char fmtbuf[30];
printf("It's %d:%02d:%02d\n",
tmp->tm_hour, tmp->tm_min, tmp->tm_sec);
strftime(fmtbuf, sizeof fmtbuf, "%A, %B %d, %Y", tmp);
printf("on %s\n", fmtbuf);
\end{verbatim}
\noindent (이 함수들이 주어진 값을 고치지 않는데도
\verb+time_t+ 변수에 대한 포인터를
인자로 받는 것에 주의하기 바랍니다.\footnote{이런 식의 인터페이스를
쓰는 이유는, 초창기 C 언어에서 \TT{long} 데이터 타입이 나오기 전에
두 개의 \TT{int}로 이루어진 배열을 써서 time 값을 저장했습니다.}
\R
\cite{kr2} \S\ B10 \Page{255--7} \\
\cite{ansi} \S\ 4.12 \\
\cite{c89} \S\ 7.12 \\
\cite{hs} \S\ 18
\end{faq}
\begin{faq}
\Q{13.13} % 13.13 COMPLETE
라이브러리 함수 \TT{localtime()}은 \verb+time_t+를
\verb+struct tm+ 형태로 바꾸어 줍니다. 그리고 \TT{ctime()}은
\verb+time_t+를 문자열로 바꾸어 줍니다. 거꾸로 변환하고 싶으면
어떻게 해야 할까요? 즉, 문자열이나 \verb+struct tm+을
\verb+time_t+ 타입으로 변경하고 싶습니다.
\A
ANSI C에서는 \TT{struct tm} 타입을 \verb+time_t+로 바꾸어 주는
\TT{mktime()} 함수를 제공합니다.
문자열을 \verb+time_t+로 바꾸는 것은 조금 힘듭니다. 왜냐하면,
각 나라 혹은 지역별로 사용하는 날짜와 시간 형식이 각각 다르기
때문입니다. 어떤 시스템은 \TT{strptime()}이라는 함수를 제공하며,
그 기능은 \TT{strftime()}의 반대입니다. 또 (RCS 패키지와 함께
제공되는) \TT{partime()}이라는 함수와 (최신의 C news 배포판에서
제공하는) \TT{getdate()}라는 함수도 자주 쓰입니다.
질문 \ql{18.16}을 보기 바랍니다.
\R
\cite{kr2} \S\ B10 \page{256} \\
\cite{ansi} \S\ 4.12.2.3 \\
\cite{c89} \S\ 7.12.2.3 \\
\cite{hs} \S\ 18.4 \Page{401--2}
\end{faq}
\begin{faq}
\Q{13.14} % 13.14 COMPLETE
주어진 날짜에 (\TT{N} days) 날짜를 더하는 기능이 있나요?
또 주어진 두 날짜를 비교하는 함수가 있을까요?
\A
이러한 문제를 해결하기 위해서, ANSI/ISO C 표준은
\TT{mktime}과 \TT{difftime} 함수를 제공합니다.
\TT{mktime()}은 정규화되지 않은 (non-normailized) 날짜를
\verb+struct tm+ 타입으로 입력받아 이것을 정규화시켜 줍니다.
즉, \TT{struct tm}의 변수에 기준 날짜 값을 넣고,
\verb+tm_mday+에서 원하는 날짜만큼 더하거나 뺀 다음, \TT{mktime}을
부르면 normalize된 년, 월, 일을 얻을 수 있습니다.
(추가적으로 이 값을 \verb+time_t+ 타입으로 변경시켜 줍니다.)
\TT{difftime()}은 두 개의 \verb+time_t+ 값을 입력받아 초 단위로
비교해 줍니다; 이 때 필요한 \verb+time_t+ 값은 \TT{mktime()}을 써서
얻습니다.
그러나 이 해결책들은 주어진 날짜 값이 \verb+time_t+ 범위 안에
있을 때만 동작합니다.
\verb+tm_days+ 필드는 \TT{int}이기 때문에 일(day) 수가
\TT{int} 값을 넘는 값일 경우 (예를 들어 32,736 이상), 오버플로우가
발생할 수 있습니다.
또한 daylight saving time(써머 타임)을 고려하면
하루는 24 시간이 아닐 수도 있습니다 (따라서 86400 seconds/day로 나누면
해결될 것이라는 생각을 하면 안됩니다).
다음은 October 24, 1994에서 90일을 빼는 코드입니다:
\begin{verbatim}
#include <stdio.h>
#include <time.h>
tm1.tm_mon = 10 - 1;
tm1.tm_mday = 24;
tm1.tm_year = 1994 - 1900;
tm1.tm_hour = tm1.tm_min = tm1_tm_sec = 0;
tm1.tm_isdst = -1;
tm1.tm_mday -= 90;
if (mktime(&tm1) == -1)
fprintf(stderr, "mktime failed.\n");
else
printf("%d/%d/%d\n",
tm1.tm_mon + 1, tm1.tm_mday, tm1.tm_year + 1900);
\end{verbatim}
\noindent (\verb+tm_isdst+를 -1로 설정하거나 \verb+tm_hour+를
12로 설정하면 daylight saving time 문제로부터 보호받는데
도움을 줍니다.)
아래 코드는 2000년 2월 28일과 2000년 3월 1일 사이의 날짜 차이를 구하는
코드입니다:
\begin{verbatim}
struct tm tm1, tm2;
time_t t1, t2;
tm1.tm_mon = 2 - 1;
tm1.tm_mday = 28;
tm1.tm_year = 2000 - 1900;
tm1.tm_hour = tm1.tm_min = tm1.tm_sec = 0;
tm1.tm_isdst = -1;
tm2.tm_mon = 3 - 1;
tm2.tm_mday = 1;
tm2.tm_year = 2000 - 1900;
tm2.tm_hour = tm2.tm_min = tm2.tm_sec = 0;
t1 = mktime(&tm1);
t2 = mktime(&tm2);
if (t1 == -1 || t2 == -1)
fprintf(stderr, "mktime failed\n");
else {
long d = (difftime(t2, t1) + 86400L/2) / 86400L;
printf("%ld\n", d);
}
\end{verbatim}
\noindent (위에서 추가적으로 쓴 \TT{86400L / 2}는 계산 결과를
원하는 근사값으로 만들어 줍니다; 질문 \ql{14.6} 참고)
``Julian day number''를 (또는 4013 BC\footnote{좀 더 정확히 말해,
그 날짜 GMT 정오부터입니다. 여기서 말하는 Julian day number는
데이터 프로세싱에 쓰이는 ``Julian dates''와 아무런 상관이 없습니다.
그리고 이 둘 다 모두 ``Julian calendar''와 아무 상관없습니다.} 1월 1일)
사용하는 방법도 있습니다. 아래는 Julian day로 바꾸는 함수의 선언입니다:
\begin{verbatim}
/* returns Julian for month, day, year */
long ToJul(int month, int day, int year);
/* returns month, day, year for jul */
void FromJul(long jul,
int *monthp, int *dayp, int *yearp);
\end{verbatim}
\noindent 이 때, \TT{n}일(day)을 더하는 것은 다음과 같이 합니다:
\begin{verbatim}
int n = 90;
int month, day, year;
FromJul(ToJul(10, 24, 1994) + n, &month, &day, &year);
\end{verbatim}
\noindent 또, 두 날짜의 차이(일 수 단위로)는 다음과 같이 구합니다:
\begin{verbatim}
ToJul(3, 1, 2000) - ToJul(2, 28, 2000)
\end{verbatim}
Julian day를 다루는 함수들은 Snippets 콜렉션에 (질문 \ql{18.15c} 참고)
있습니다. 그리고 이 콜렉션은 Simtel/Oakland 아카이브(archive)에서
(파일 \TT{JULCAL10.ZIP}, 질문 \ql{18.16} 참고) 얻을 수 있습니다.
아래의 ``Date conversions'' 기사도 참고하기 바랍니다.
\seealso{\ql{13.13}, \ql{20.31}, \ql{20.32}}
\R
\cite{kr2} \S\ B10 \page{256} \\
\cite{ansi} \S\ 4.12.2.2, \S\ 4.12.2.3 \\
\cite{c89} \S\ 7.12.2.2, 7.12.2.3 \\
\cite{hs} \S\ 18.4,18.5 \Page{401--2} \\
\cite{dateconv}
\end{faq}
\begin{faq}
\Q{13.14b}
C 언어는 2000년 문제에 어떤 문제가 있을까요?
\A
없습니다. 단지, 허술하게 작성된 C 프로그램에 문제가 있을 뿐입니다.
\TT{struct tm}의 \verb+tm_year+ 필드는 1900년대에서 시작한 년도를
가지고 있습니다. 따라서 2000년일 경우에 이 값은 100이 됩니다.
\verb+tm_year+를 제대로 사용하는 코드라면 (변환할 때, 1900을 더하거나
빼는) 전혀 문제될 것이 없습니다. 그러나 이 값을 두 자리 숫자로
바로 사용한다거나 다음과 갈은 코드를 썼다면:
\begin{verbatim}
tm.tm_year = yyyy % 100; /* WRONG */
\end{verbatim}
\noindent 또는, 다음과 같이 했다면:
\begin{verbatim}
printf("19%d", tm.tm_year); /* WRONG */
\end{verbatim}
\noindent 2000년 문제가 발생합니다. \seealso{\ql{20.32}}
\R
\cite{kr2} \S\ B10 \page{255} \\
\cite{c89} \S\ 7.12.1 \\
\cite{hs} \S\ 18.4 \page{401}
\end{faq}
\section{Random Numbers}
% from 13.15
\begin{faq}
\Q{13.15}
난수(random number) 발생기가 필요합니다.
\A
표준 C 라이브러리에는 \TT{rand()}라는 함수가 있습니다. 물론
각각의 시스템에 따라 이 함수의 구현(implementation)은 완전하지
않을 수 있습니다. 그러나, 이 함수보다 더 좋은 성능을 가진 함수를
직접 만들기란 쉬운 일이 아닙니다.
직접 난수 발생기를 만들려고 한다면, 읽어야 할 책들이 꽤 많습니다;
이 글 뒷부분에 있는 Reference를 보시기 바랍니다.
또한 인터넷 상에 많은 패키지가 이미 올라와 있습니다;
r250, RANLIB, FSULTRA로 검색해 보기 바랍니다.
(질문 \ql{18.16}도 참고.)
아래는 Park씨와 Miller씨에 의해 제안된, ``minimal standard''
generator입니다.
\begin{verbatim}
#define a 16807
#define m 2147483647
#define q (m / a)
#define r (m % a)
static long int seed = -1;
long int PMrand()
{
long int hi = seed / q;
long int lo = seed % q;
long int test = a * lo - r * hi;
if (test > 0)
seed = test;
else
seed = test + m;
return seed;
}
\end{verbatim}
% TODO: 다음 문장 번역.
\noindent (The ``minimal standard'' is adequately good; it is something
``against which all others should be judged'' and is recommended for
use ``unless one has access to a random number generator \EM{known}
to be better.'')
% TODO: 이 부분 책보고 채울것..
이 코드는 \TT{a = 16807}이고, \TT{m = 2147483647}(이 값은
$2^{31} - 1$입니다)이고, \TT{c = 0}인, 다음 generator를 구현합니다:
\[ X \leftarrow (aX + c) \bmod m \]
\noindent 나머지(modulus) 연산이 소수(prime) 연산이기 때문에,
이 generator는 질문 \ql{13.18}에 나온 문제가 발생하지 않습니다.
위에서 사용한 곱하기는 Sch\-rage씨에 의해 소개된 기법을 써서,
곱한 결과인
\TT{aX}가 overflow를 발생시키지 않습니다. 위 코드는 값의 범위가
\TT{[1, 2147483647]}를 만족하는 \TT{long int} 값을 돌려주며,
이 범위는 C 언어의 \TT{rand} 함수가 \TT{RAND\_MAX}보다 작은 값을
돌려 주는 것과 비슷한 방식입니다. (단지 위 코드가 만들어 내는 값에는
0이 들어가지 않는다는 것만 다릅니다.) 위 코드를 (Park씨와 Miller씨의
논문에 나온 것처럼) 범위 \TT{(0, 1)} 사이의 실수를 만들도록 고치려면,
위 함수의 선언을 다음과 같이 고치고:
\begin{verbatim}
double PMrand(void);
\end{verbatim}
\noindent 마지막 줄을 다음과 같이 고칩니다:
\begin{verbatim}
return (double)seed / m;
\end{verbatim}
\noindent 통계적으로 좀 더 좋은 결과를 얻으려면, (Park씨와 Miller씨의
추천에 따르면) \TT{a = 48271}을 쓰기 바랍니다.
\R
\cite{kr2} \S\ 2.7 \page{46}, \S\ 7.8.7 \page{168} \\
\cite{ansi} \S\ 4.10.2.1 \\
\cite{c89} \S\ 7.10.2.1 \\
\cite{hs} \S\ 17.7 \page{393} \\
\cite{pcs} \S\ 11 \page{172} \\
\cite{knuth} Vol.\ 2 Chap.\ 3 \Page{1--177} \\
\cite{random}
\end{faq}
\begin{faq}
\Q{13.16} % 13.16 COMPLETE
어떤 범위를 갖는 난수를 발생시키고 싶습니다.
\A
다음과 갈이 하는 것은 (0에서 N-1까지의 수치를 리턴함) 매우 서투른
방법입니다:
\begin{verbatim}
rand() % N /* POOR */
\end{verbatim}
\noindent 왜냐하면, 대부분의 난수 발생기에서 하위(low-order) 비트들은
그리 랜덤하지 않기 때문입니다. (질문 \ql{13.18}을 보기 바랍니다.)
따라서, 다음과 같이 하는 것이 좋습니다:
\begin{verbatim}
(int)((double)rand() / ((double)RAND_MAX + 1) * N)
\end{verbatim}
\noindent 실수를 쓰기 싫다면, 다음과 같이 해도 좋습니다:
\begin{verbatim}
rand() / (RAND_MAX / N + 1)
\end{verbatim}
\noindent 두 방법 모두 (ANSI 표준에 의해 \verb+<stdlib.h>+에
정의되어 있는) \verb+RAND_MAX+를 사용하고, \TT{N}이
\verb+RAND_MAX+보다 아주 작은 값이라는 것을 가정한 방법입니다.
만약 \TT{N}이 \verb+RAND_MAX+에 가깝고, random number generator의
범위가 \TT{N}의 배수가 아니라면 (즉,
\verb?RAND_MAX + 1 % N != 0?인
경우) 위 모든 방법이 나쁜 방법이 됩니다: 어떤 범위의 수치들이 다른
범위보다 훨씬 더 많이 나타나게 됩니다. (실수를 쓴다고 해결될 문제가
아닙니다. 문제는 \TT{rand} 함수가 서로 다른
\verb!RAND_MAX + 1!가지의 값을 리턴하고, 이 것을 \TT{N}개의 묶음으로
공평하게 나눌 수 없기 때문에 발생하는 것입니다.)
만약 이것이 문제가 된다면, \TT{rand}를 여러 번 불러서, 특정 값들을
무시하면 됩니다:
\begin{verbatim}
unsigned int x = (RAND_MAX + 1u) / N;
unsigned int y = x * N;
unsigned int r;
do {
r = rand();
} while (r >= y);
return r / x;
\end{verbatim}
또, \TT{[M, N]}의 범위를 가지는 random number를 구하고 싶다면,
위 결과를 shift해서 얻을 수 있습니다:
\begin{verbatim}
M + rand() / (RAND_MAX / (N - M + 1) + 1)
\end{verbatim}
(어쨋든, \verb+RAND_MAX+는 \TT{rand()}가 리턴할 수 있는 최대 수치를
나타내는 상수라는 것을 알아 두시기 바랍니다. \verb+RAND_MAX+에
여러분이 다른 수치를 대입할 수는 없으며, \TT{rand()}가 다른 범위의
수치를 리턴하도록 해 주는 방법은 존재하지 않습니다.)
만약에 여러분이 (질문 \ql{13.15}의 마지막 \TT{PMrand} 함수 또는
질문 \ql{13.21}의 \TT{drand48} 함수처럼) 0과 1 사이의 범위를 가지는
난수 발생기를 가지고 있다면, 그리고 0과 N-1 사이의 범위를 가지는 정수
난수를 만들고 싶다면, 단순히 그 난수 발생기의 수치에 N을 곱하면 됩니다:
\begin{verbatim}
(int)(drand48() * N)
\end{verbatim}
\R
\cite{kr2} \S\ 7.8.7 \page{168} \\
\cite{pcs} \S\ 11 \page{172}
\end{faq}
\begin{faq}
\Q{13.17}
프로그램을 실행시킬 때마다, \TT{rand()}는 일정한 순서로 난수를
(random number) 발생시킵니다. 왜 그러죠?
\A
대부분 가상(pseudo) random generator의 특징은 (C 라이브러리의
\TT{rand}도 마찬가지), 항상 같은 번호에서 시작해서 똑같은 sequence로
값이 나온다는 것입니다. (Among other things, a bit of predictability
can make debugging much easier.)
% TODO: 위 문장 제대로 번역.
예상 불가능한 난수를 발생시키고 싶으면, \TT{srand} 함수를 불러서,
이 pseudo-random generator의 초기값(seed)으로, 진짜 random 값을 하나
주면 됩니다. 보통 이 seed 값으로, 현재 시간을 쓰거나, 사용자가 키를
누르기까지의 시간 간격 등을 쓰게 됩니다. (물론 키를 누르기까지의
경과된 시간을 얻는 것은 이식성 있는 범위 안에서 만들기가 힘듭니다.
질문 \ql{19.37} 참고) 아래는 현재 시간을 써서 seed 값을 설정하는
코드입니다.
\begin{verbatim}
#include <stdlib.h>
#include <time.h>
srand((unsigned int)time((time_t *)NULL));
\end{verbatim}
\noindent (일반적으로 프로그램 내에서는 \TT{srand()} 함수를
한번만 불러주어도 충분합니다. \TT{rand()}를 부를 때마다,
\TT{srand()}를 부른다면, random number를 얻을 수 없습니다.)
\R
\cite{kr2} \S\ 7.8.7 \page{168} \\
\cite{ansi} \S\ 4.10.2.2 \\
\cite{c89} \S\ 7.10.2.2 \\
\cite{hs} \S\ 17.7 \page{393}
\end{faq}
\begin{faq}
\Q{13.18}
참/거짓을 나타내는 random number(난수)가 필요합니다.
\verb+rand() % 2+를 썼는데, 계속 0, 1, 0, 1, 0 만을 반복합니다.
\A
(불행하게도 어떤 시스템에서 제공하는 것과 같은) 엉성하게 만들어진
pseudo-random number generator는 하위 (low-order) 비트들에 대해서는
그렇게 랜덤하지 않습니다.
% TODO: 다음 문장 번역
(In fact, for a pure linear congruential random number generator
with period $2^e$, and this tends to be how random number generates
for e-bit machines are written, the low-order \EM{n} bits repeat
with period $2^n$.) 이러한 이유에서,
상위 (high-order) 비트를 쓰는 것이 더 바람직합니다:
질문 \ql{13.16}을 보기 바랍니다.
\R
\cite{knuth} \S\ 3.2.1.1 \Page{12--14}
\end{faq}
\begin{faq}
\Q{13.19}
반복되지 않는, random number의 sequence를 얻으려면 어떻게 해야 할까요?
\A
여러분이 찾고 있는 것은 보통, ``random permutation(순열)'', 또는
``shuffle''이라고 부릅니다. 한가지 방법으로, 뒤섞이기 원하는
값들을 배열에 넣고, 이 배열의 임의의 두 element의 값을 서로
바꾸는 작업을 반복해서 얻을 수 있습니다:
\begin{verbatim}
int a[10], i, nvalues = 10;
for (i = 0; i < nvalues; i++)
a[i] = i + 1;
for (i = 0; i < nvalues - 1; i++) {
int c = randrange(nvalues - i);
int t = a[i]; a[i] = a[i + c]; a[i + c] = t; /* swap */