เพื่อนให้มาลองทำ

โจทย์:
1. เขียนโปรแกรม random string ความยาวเท่ากับ 3
2. รัน 1 ล้านรอบ
3. เก็บ และนับว่ามีจำนวน string ที่ได้ออกมาไม่ซ้ำกันกี่ตัว
4. ท้าทายใช้เวลาในการรันเท่าไหร่

ตัวอย่างเช่น
lfX = 2
Fd1 = 4
gg2 = 1
มีทั้งหมด 3 ตัว
รัน 7 รอบใช้เวลา 3 millisec

ลองตั้งเป้าไว้ที่ 1 ล้านรอบไม่เกิน 30 วินะ ภาษาอะไรก็ได้

แก้ยังไงดี
1. random string ความยาว = 3
solution(ของผม).

1. String ที่ว่าเอาตัวอะไรบ้าง น่าจะเป็น  พวกอักษรพิเศษอย่าง :,;'"}[]{|\ "... เราคงไม่เอา
   ABCEDFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789 (62 ตัว)
   แต่ว่าถ้าจะเอาไปทำ captcha ก็ตัด ไอ(I), แอล(l), โอ(O,o), ศูนย์(0), หนึ่ง(1) ออกไปเพื่อป้องกันอักษรอ่านยากก็จะเหลือ (หรือตัวไหนที่เห็นสมควรก็ลองตัดออกเองนะ)
   ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnpqrstuvwxyz23456789 (56 ตัว)
   เก็บพวกนี้ใส่ตัวแปรไว้เลยเพราะว่าเดี๋ยวได้ใช้ตลอด
   starting_str = "ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnpqrstuvwxyz23456789";
   
2. random ความยาวเท่ากับ 3
       random อักษรทีละตัวจากชุดตัวอักษรที่เรามีไว้ให้เลย โดยปกติแต่ละภาษาจะมี fn ที่ใช้ random ตัวเลข integer อยู่แล้วโดยจะมีลักษณะประมาณนี้ rand_int(begin,end) ก็จะได้เลขในช่วงตั้งแต่ begin ถึง end มาเราก็เอามา get ตำแหน่งของตัวอักษรใน String เริ่มต้นเลย
       a_char = starting_str.charAtIndex(rand_int(0,56)) // ไม่ใช้ length(starting_str) มันเสียเวลา
       ถ้าจะเอาความยืดหยุ่นเราก็คงต้องทำ function ให้กำหนดความยาวของ String ได้แต่ว่าถ้าจะเอาความเร็วเราก็คงจะให้มันต่อกันไปเองเรื่อยๆ เลย
       rand_str = strcat(
                               starting_str.charAtIndex(rand_int(0,56)),
                               starting_str.charAtIndex(rand_int(0,56)),
                               starting_str.charAtIndex(rand_int(0,56))
                              )
   

2. รันและนับ

1. รัน ล้านรอบ นี่มันก็เป็นแค่ loop อ่ะ เดี๋ยวค่อยครอบทีหลัง
   
2. เรื่องการเก็บข้อมูลและนับ
   
   1. มีตารางสำหรับเก็บแบบนี้

      String	count
      "xyz"	1
      "aBc"	3

   2. พอมีข้อมูลใหม่ก็เอามานับเพิ่ม count ถ้า random มาใหม่ไม่มีในตารางก็เพิ่มเข้าไป
3. เท่านี้โปรแกรมก็น่าจะทำงานได้แล้ว ถ้าจะนับว่ามันมีตัวที่ไม่ซ้ำกันกี่ตัวก็ดูที่แถวของตารางว่ามีเท่าไหร่  

3. เร็ว
    เรื่องนี้น่าจะเป็นเรื่องโครงสร้างข้อมูลที่ใช้ในการเก็บตารางที่ว่าแล้วจะทำได้เร็วขนาดในที่นี้ผมก็คิดว่าน่าจะใช้ hashtable ที่มีของแต่ละภาษาไปเลยน่าจะเร็วที่สุดแล้ว (dict ใน python, array ของ php, Hashtable ของ java)


ตัวอย่างที่ลองเขียนด้วย python

import random
from    datetime import datetime
instr = '1234567890abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'
def ranstr():
     return instr[random.randint(0,61)] + instr[random.randint(0,61)] + instr[random.randint(0,61)]
begin = datetime.now()
buffer = {}
for i in range(1000000):
    mystr = ranstr()
     if mystr in buffer:
         buffer[mystr] += 1
     else:
         buffer[mystr] =1
print "all string", buffer
print "distinct :",len(buffer)
end = datetime.now()
print "begin :",begin
print "end    :",end
print "diff :",(end - begin)

core2 1.7G, RAM 3 GB, ประมาณ 8 วิ :)