آموزش | ساخت استرینگ سودو-رندم در کلوژر

سلام.
قصد دارم یه سری تاپیک بزنم برای آموزش کلوژر و توی این تاپیکها یه مساله‌ای که برای خودم پیش اومده رو معرفی کنم و براشون راه حل ارائه بدم. یه جورایی مثالهای برنامه نویسی.
نمیدونم چقدر این‌کار درست باشه و چقدر استقبال بشه، ولی حس میکنم برای کسانی که تازه میخوان با این پارادایم ذهنی شروع به کار کنن، خیلی مفید باشه اگه بتونن در کنار یه سری سورس‌کد (که توی ریپازیتوریهای پابلیک وجود داره)، مسیر فکری برنامه‌نویسها رو ببینن.
تاپیک به صورت ویکی نوشته میشه، اگر جایی اشتباه کردم و یا نتیجه‌ی نهایی کارم به اندازه‌ی کافی خوب نبود و نیاز بود چند پاراگراف بهش اضافه بشه، دوستان حرفه‌ای زحمتش رو بکشن.


ساخت استرینگ سودو-رندم در کلوژر

+اولا که چرا رندم واقعی نیست؟
-چون رندم واقعی در دنیای کامپیوتر وجود نداره و ساخت رندم واقعی یکی از مسائل حل نشده‌ی دنیای کامپیوتره. همونطور که توی دنیای ریاضی نمیتونیم یه تابع داشته باشیم که یک مقدار واقعا رندم داشته باشه، توی کامپیوتر هم نمیتونیم!
(اگه از این به بعد از واژه‌ی رندم استفاده کردم، منظور pseudo random هست.)

ما الآن میخوایم یه تابع داشته باشیم که با هربار صدا زدن، یک استرینگ رندم با سایز مشخص شامل اعداد و حروف بزرگ و کوچک بهمون بده.
شاید بهتر باشه یک لیست از کاراکترهای مجاز تهیه کنیم:

(def valid-chars
  (map char (concat (range 48 58) ; 0-9
                    (range 65 91) ; A-Z
                    (range 97 123)))) ; a-z

الآن باید تابع ما هربار که اجرا میشه، این مقدار (که به صورت global هست) رو بخونه. میتونستیم اینو توی یه let در تابع اصلیمون قرار بدیم که هربار تابع صدا زده میشه، این لیست رو بسازه، ولی در این صورت، تابع ما خیلی کند میشد چون هربار باید یک سری محاسبات انجام میداد.
توی این روش، درسته که تابع ما با مقادیری که خارج از خودش هستن کار میکنه، ولی چون این مقادیر immutable هستن، پس مشکلی پیش نمیاد. از طرف دیگه تابع اصلی به هر حال قراره مقدار رندم خروجی بده پس pure function نیست، ما هم زیاد گیر نمیدیم!
از طرف دیگه، وقتی به این شکل کار میکنیم، استرینگ valid-chars در زمان کامپایل ساخته میشه و وسط اجرای برنامه فشاری به cpu نمیاره.

الآن یک لیست از 62 کارکتری که لازم داریم، ساختیم:

user=> valid-chars
(\0 \1 \2 \3 \4 \5 \6 \7 \8 \9 \A \B \C \D \E \F \G \H \I \J \K \L \M \N \O \P \Q \R \S \T \U \V \W \X \Y \Z \a \b \c \d \e \f \g \h \i \j \k \l \m \n \o \p \q \r \s \t \u \v \w \x \y \z)
user=> (count valid-chars)
62

و میتونیم یکیشونو به صورت رندم انتخاب کنیم:

(nth valid-chars (rand-int (count valid-chars)))
# \Y

میشه با استفاده از threading-macro به شکل زیر هم نوشت ولی من روش بالا رو بیشتر دوست دارم:

(nth valid-chars (-> valid-chars
                     count
                     rand-int))
# \T

شاید بهتر باشه اینو تبدیل کنیم به یک تابع. تا بتونیم به تعداد دلخواه صداش بزنیم:

(defn- get-char
  "Get one random character out of `valid-chars`."
  []
  (nth valid-chars (-> valid-chars
                       count
                       rand-int)))

(به جای defn از defn- استفاده کردم، چون این تابع قرار نیست از خارج این namespace صدا زده بشه، و فقط قراره توابعی که داخل همین namespace هستن بتونن صدا بزننش.)
و به تعداد دفعاتی که میخوایم، این تابع رو صدا بزنیم.

(take 10 (repeatedly #(get-char)))
# (\8 \G \I \8 \6 \q \p \X \e \5)

الآن یه لیست (یک seq) شامل ۱۰ کاراکتر تصادفی داریم. میشه خیلی راحت باهاش یک استرینگ ساخت.

user=> (apply str (take 10 (repeatedly #(get-char))))
"CKT6HSiAqb"
user=> (reduce str (take 10 (repeatedly #(get-char))))
"n0j1d6LM6U"
user=> (clojure.string/join "" (take 10 (repeatedly #(get-char))))
"D7KKmqw9bW"

سه تا راه برای اینکار وجود داره، به نظرم آخری مناسب نیست. مطمئنا برای چیز دیگه‌ای ساخته شده. پس با apply و reduce پیش میریم.
اینجا apply و reduce یک خروجی رو بهمون ارائه میدن ولی یک مقدار طرز کارشون فرق میکنه پس همیشه مثل هم نیستن. به عنوان مثال:

(apply + (list 1 2 3 4 5))
; translates to: (+ 1 2 3 4 5)
(reduce + (list 1 2 3 4 5))
; translates to: (+ (+ (+ (+ 1 2) 3) 4) 5)

(apply hash-map [:a 5 :b 6])
; translates to: {:a 5, :b 6}
(reduce hash-map [:a 5 :b 6])
; translates to: {{{:a 5} :b} 6}

به نظر میاد apply برای نیاز ماا گزینه‌ی بهتری باشه. چون یک بار تابع ما رو صدا میزنه و همه‌ی ورودیها رو یکجا بهش میده در حالی که reduce چندبار تابع رو صدا میزنه.
توی استرینگهای کوتاه شاید به چشم نیاد ولی جلوتر سرعت این‌دوتا رو با هم مقایسه میکنیم.

حالا بیایم کد بالا رو تبدیل به تابع کنیم که سایز استرینگ رو از کارابر بگیره.

(defn random-str [size]
  (apply str
    (take size (repeatedly #(get-char)))))

user=> (random-str 32)
"kwQG7Qy7nEBUNHVxsWr1kumgY7FgAmPj"

به نظر میاد موفق شدیم!
یه لیست از کاراکترهای مجاز داریم، یه تابع که یکی از اون کاراکترها رو به صورت رندم پیدا میکنه و یه تابع دیگه که به تعداد دفعات دلخواه تابع قبلی رو صدا میزنه و بهمون استرینگ رندم میده.

ولی یه کم نیاز به تمیز‌کاری داره. مثلا اینکه میشه همش (بجز لیست کاراکترهای مجاز) توی یک تابع باشه و البته تابع رو طوری بنویسیم که موارد استفادش یه کم بیشتر باشه. مثلا اگه کاربر سایز استرینگ مورد نظرش رو تعیین نکرد، استرینگی با سایز ۸ کاراکتر ساخته بشه.

(defn random-str2
  ([] (random-str2 8))
  ([n]
   (apply str (take n (repeatedly #(rand-nth valid-chars))))))

اینجا از rand-nth استفاده کردیم. یکی از توابع اصلی کلوژر که یک لیست (وکتور یا seq) دریافت میکنه و یکی از مقادیر داخل اون لیست رو بهمون برمیگردونه:

(rand-nth [:a :vector :of :five :element])
; :element

خوب. کوتاهتر شد. ولی چرا حس میکنم بهینه نیست؟
شاید به خاطر اینکه هربار که میخوایم یک کاراکتر از لیست کاراکترهای مجاز انتخاب کنیم، یک بار range میگیریم.
به سورس rand-nth دقت کنید:

user=> (source rand-nth)
(defn rand-nth
  "Return a random element of the (sequential) collection. Will have
  the same performance characteristics as nth for the given
  collection."
  {:added "1.2"
   :static true}
  [coll]
  (nth coll (rand-int (count coll))))

(در repl با صدا زدن تابع source میشه سورس‌کد توابع رو مشاهده کرد)
همونطور که مشخصه، یک کالکشن دریافت میکنه به نام coll و تعداد مقدارهای داخلش رو با count پیدا میکنه و بر اساس اون یک عدد رندم میسازه و بر اساس اون عدد رندم، یکی از مقدارهای داخل coll رو بهمون برمیگردونه.

تقریبا مثل اینه که تابع rand-str2 رو اینطوری نوشته باشیم:

(defn random-str2
  ([] (random-str2 8))
  ([n]
   (apply str (take n (repeatedly #(nth valid-chars (rand-int (count valid-chars))))))))

(از threading macro استفاده نکردم که شکل کد شبیه کد قبلی باشه)

توی این کاری که ما میخوایم انجام بدیم، سایز valid-chars همیشه یکسانه. یعنی نیازی نداریم هردفعه count رو اجرا کنیم.
پس میتونیم به جاش بنویسیم:

(defn random-str3
  ([] (random-str3 8))
  ([n]
   (apply str (take n (repeatedly #(nth valid-chars (rand-int 62)))))))

به نظر که درست کار میکنه. حالا یه تست ساده (برای بنچمارک گرفتن راههای بهتری هم هست) انجام بدیم:

user=> (time (random-str 1000000))
"Elapsed time: 3388.6 msecs"
user=> (time (random-str2 1000000))
"Elapsed time: 3602.0 msecs"
user=> (time (random-str3 1000000))
"Elapsed time: 1123.4 msecs"

(خروجی واقعی تا ۶رقم اعشار بود که من کمترش کردم. البته هرکدوم از توابع رو ۵بار اجرا کردم و جوابها رو میانگین گرفتم. البته اختلاف زیادی با هم نداشتن. تستها روی intel corei7 4790k انجام شده. 4GHz قدرت پردازش هر هسته. با DDR3 RAM)
همونطور که مشخصه، سرعت random-str3 تقریبا ۳ برابر بیشتر از دو تابع دیگست و ما فقط count رو ازش حذف کردیم!
اگه همین تستها رو برای استرینگهای ۳۲کاراکتری اجرا کنید، دو تابع اول در حدود ۰.۲میلی‌ثانیه جواب میدن و تابه سوم حدود ۰.۰۷میلی‌ثانیه.

حالا اگه تابع random-str رو یه کم تغییر بدیم و به جای apply از reduce استفاده کنیم، فکر میکنید چقدر طول میکشه تا یک استرینگ رندم یک ملیون کاراکتری بسازه؟
اشتباه حدث زدید! 117502.7 میلی ثانیه. یعنی تقریبا ۲ دقیقه! صدای فن کامپیوتر هم یه مقدار اعصاب آدمو خورد میکنه.

حالا یک تغییر دیگه. اگه بخوایم توی هرکدوم از درخواستها، واقعا valid-chars رو بسازیم و توی هر بار استفاده count کنیم چه اتفاقی میفته؟
حدود 6109.6 میلی‌ثانیه.

اگه هر بار valid-chars رو بسازیم و به جای apply از reduce استفاده کنیم چطور؟
حدود 116602.0 میلی‌ثانیه.


اینطور که به نظر میرسه، شناخت مساله و شناخت ابزار کافی نیست. نیاز به شناخت عمیق ابزارها داریم.
بدون خوندن سورس‌کد زبان و لایبرریها، نمیشه کدهای بهینه نوشت. خوندن داکیومنت برای شروع خوبه ولی برای ادامه کافی نیست.

امیدوارم توضیحاتم واضح بوده باشه.
امیدوارم روشی که استفاده کردم درست باشه (هنوز توی دنیای کلوژر تازه‌وارد هستم).
امیدوارم مطالبی که نوشتم صحیح باشن.

1 Like