Tag Archives: Algorithm

แก้ Euler Project 551

ไปเจอปัญหาจาก Euler Project ข้อ 551 สรุปได้ว่า กำหนดลำดับ a(0), a(1), a(2), … โดย

a(n) = d(a(n-1)) + d(a(n-2)) + d(a(n-3)) + .. + d(a(1)) + d(a(0))

โดย a(0)=1 และ d(n) คือการเอาตัวเลขโดดของทุกหลักของเลข n มาบวกกัน (sum of digits) โจทย์ให้หาค่าของ a(1015)

ดูดีๆ จะเห็นว่า a(n) = d(a(n-1)) + a(n-1) ด้วยเช่นกัน ถ้าจะแก้แบบ recursive งานนี้ถ้าจะแก้กันง่ายๆ ตรงไปตรงมา เขียนด้วยภาษาสคริป Python ได้ว่า

def d(n):
    r = 0
    while n:
        r += n % 10
        n //= 10
    return r   

a=1
for i in xrange(1, 10**6):
    a+=d(a)

ซึ่งคำนวณถึงแค่ a(106) ก็ได้ค่า 31054319 ตรงกับที่ตัวอย่างให้มา ถ้าจะเอาให้ถึงตามโจทย์ สงสัยต้องหาทางแก้ non-homogeneous linear recurrence relation ให้ได้ก่อนครับ ก็อาจจะได้สมการที่มียกกำลัง n ออกมา หรืออาจต้องหาทางว่า มีความสัมพันธ์ที่จะย่อย n ให้ลงไปเป็เท่าๆ ตัว เช่น a(2n) = … ที่มี a(n..)

ปล. มีคนแจก source code วิธีแก้ในภาษา Python แล้วครับ ผมรันดูแล้วเสร็จในแป็ปเดียว https://git.icpc-camp.org/ftiasch/acm-icpc/blob/6d1d563a1dea39b8a8f525c836c5f3b0a243678b/project-euler/p551/p551.py

แก้ Euler Project 501

มีปัญหา Euler Project หมายเลข 501 ให้หาจำนวนตั้งแต่ 1 ถึง 1012 ว่ามีกี่ตัว ที่จำนวนตัวหารซึ่งหารแล้วลงตัวของมันนั้น มีเท่ากับ 8 ตัว

ถ้าใช้วิธีวนลูปตรงๆ คืิอไล่เลข 1 ถึง 1012 ที่ละตัว เอามาหารด้วยเลข 1 จนถึงตัวมันเอง แล้วนับว่ามีหารลงตัวแปดตัวหรือไม่ ช้าแน่ ต้องหาวิธีอื่น โดยใช้หลักคณิตศาตร์มาช่วย คือเมื่อเอาตัวเลขมาแยกตัวประกอบ ให้กลายเป็นผลคูณของจำนวนเฉพาะ ถ้าจำนวนเฉพาะมีซ้ำกันให้เขียนเป็นเลขยกกำลัง จำนวนของตัวหารที่ลงตัว เท่ากับเอาเลขชี้กำลังของแต่ละจำนวนเฉพาะนั้น มาบวกเพิ่มอีกหนึ่งแล้วคูณกัน

เช่น 24 = 2331 เลขชี้กำลังมี 3 และ 1 เอามาบวกเพิ่มอีก 1 จะได้ 4 และ 2 เมื่อคูณกันได้ 8 คือมีจำนวนตัวหารเท่ากับ 8 ตัว (24 นี้มี 1, 2, 3, 4, 6, 8, 12, 24) โดยเลข 8 สามารถได้มาจากการคูณ 8×1, 4×2, 2×4, 2x2x2 ถ้าเราจะไล่หาจำนวนที่มีตัวหารลงตัวแปดตัวโดยทำย้อนไป โดยเอาจำนวนเฉพาะมายกกำลังและคุณกัน โดยเลขชี้กำลังต้องเข้ากับเงื่อนไขที่จะทำให้มีตัวหารลงตัวแปดตัว ก็จะมีได้สี่กรณี

p7
p3q1
p1q3
p1q1r1

โดย 1 < p < q < r และทั้งสามเป็นจำนวนเฉพาะ

ลอง coding คร่าวๆ

##

import itertools
import math

def is_prime(num):
    if num < 2:
        return False
    for x in range(2, int(math.sqrt(num))+1):
        if num % x == 0:
            return False
    else:
        return True

def fd0(p, lmbd):
    r=0
    for x in (itertools.combinations(p, lmbd.__code__.co_argcount)):
        if lmbd(*x):
            r+=1
    return r
    
nn=100
lp=list(filter(is_prime, range(1, nn+1)))
a=fd0(lp, lambda x: x**7 <= nn)
b=fd0(lp, lambda x, y: x**3 *y <= nn)
c=fd0(lp, lambda x, y: y**3 *x <= nn)
d=fd0(lp, lambda x, y, z: x*y*z <= nn)
t1=a+b+c+d

nn=1000
lp=list(filter(is_prime, range(1, nn+1)))
a=fd0(lp, lambda x: x**7 <= nn)
b=fd0(lp, lambda x, y: x**3 *y <= nn)
c=fd0(lp, lambda x, y: y**3 *x <= nn)
d=fd0(lp, lambda x, y, z: x*y*z <= nn)
t2=a+b+c+d


##

แต่ถ้าทำถึงเลข 1012 ยังช้าอยู่นะครับ ต้องหาทางออกจากวนลูปเอง เมื่อการคูณเกินจำนวนที่กำหนดไว้

##
def is_prime(num):
    if num < 2:
        return False
    x=2
    while x*x<=num:
        if num % x == 0:
            return False
        x+=1
    return True

nn=10**6
lp=list(filter(is_prime, range(1, nn//6 +2)))
lp.sort()

r=0
for i in range(len(lp)):
    if lp[i]**7 > nn:
        break
    else:
        r+=1

for i in range(len(lp)):
    for j in range(i+1, len(lp)):
        if lp[i]**3 *lp[j] > nn:
            break
        else:
            r+=1

for i in range(len(lp)):
    for j in range(i+1, len(lp)):
        if lp[j]**3 *lp[i] > nn:
            break
        else:
            r+=1

for i in range(len(lp)):
    for j in range(i+1, len(lp)):
        if lp[i]*lp[j] > nn:
            break
        for k in range(j+1, len(lp)):
            if lp[i]*lp[j]*lp[k] > nn:
                break
            else:
                r+=1
          
print(r)
##

ทดลองบีบย่อไฟล์แบบ Brotli

เคยทดลองวิธีบีบย่อไฟล์ด้วยโปรแกรม Zopfli มาก่อน ตอนนี้มีรูปแบบใหม่จาก Google มาอีก คือ Brotli ซึ่งใช้ไฟล์รูปแบบใหม่ไม่เหมือน deflat เลยจะเปิดด้วย deflate ไม่ได้ ไหนๆ เคยทดลอง Zopfli มาแล้ว ลองกับ Brotli บ้างจะเป็นไร สร้างโปรแกรมนี้จาก git โดยพลันครับ

git clone https://github.com/google/brotli.git
cd brotli/tools
make -j4

จะได้ไฟล์โปรแกรม bro มาใช้ ก็ทดสอบคร่าวๆ เหมือนคราวก่อน โดยสั่ง time ไว้ด้วย

time ./bro --quality 11 --input enwik8 --output enwik8.bro --verbose
Brotli compression speed: 0.159104 MB/s

real    10m2.654s
user    9m54.819s
sys    0m4.588s

ได้ไฟล์บีบแล้วชื่อ enwik8.bro ขนาด 27,721,194 ไบต์ บีบมาจากไฟล์ enwik8 ขนาด 100,000,000 ไบต์

ถ้าพิมพ์คำสั่ง bro เฉยๆ มันจะรอรับข้อมูลจาก stdin ซึ่งมักจะเป็น keyboard นะครับ
ผ่านทาง http://www.cnx-software.com/2015/09/24/brotli-compression-algorithm-combines-high-compression-ratio-and-fast-decompression/

ใช้ Zopfli แบบขนานด้วย Pigz

ต่อจาก Zopfli คราวที่แล้ว มันค่อนข้างจะใช้เวลานานมาก และเมื่อไล่โค้ด deflat.c บรรทัดที่ 688 ดูเหมือนว่ามันเป็น loop ที่ไม่ได้เอาข้อมูลจาก loop รอบที่แล้วมาใช้ จึงน่าจะทำการประมวลผลแบบขนานให้ทำ ZopfliDeflatePart() ของหลายๆ block ไปพร้อมๆ กันได้

แต่ก็ไปอ่านเจอว่า โปรแกรม pigz เวอร์ชันล่าสุด 2.3 ได้ผนวก Zopfli มาให้แล้ว โดย pigz เป็นโปรแกรม gzip แบบที่จะแบ่งงานเป็นส่วนๆ ไปให้ตัวประมวลผลที่มีอยู่หลายคอร์หรือหลายเท็รด ช่วยกันทำงานขนานกัน จะได้เสร็จเร็วๆ เลย yum install ดู พบว่ายังไม่ใช่เวอร์ชัน 2.3 จึงต้องเอา source code มา make เอง ตอนที่ make ต้องใส่ -lm เข้าไปในไฟล์ Makefile ด้วยครับ เพราะมันไม่เห็นฟังก์ชันคณิตศาสตร์ log() เมื่อ make เสร็จก็บีบไฟล์ enwik8 เหมือนเดิม โดยใช้ออฟชัน -11 ให้ pigz ใช้อัลกอริทึมบีบย่อ Zopfli

zopfli-pigz-compressing-enwik8

พบว่า ขนาดไฟล์เล็กกว่า zip แต่ก็ใหญ่กว่า Zopfli แบบที่ลูป -i1000 แต่ก็ใช้เวลาบีบน้อยกว่า ผมไม่แน่ใจว่า pigz มันใช้ Zopfli แบบลูปนานแค่ไหน

แล้วก็มีคนพบว่า Zopfli ยังบีบไม่สุด คือใช้โปรแกรม DeflOpt หรือ Defluff ซึ่งสามารถบีบไฟล์ที่เป็น gzip เพิ่มได้ โดยมันจะคำนวณ huffman code ในไฟล์ใหม่ ให้ได้ไฟล์เล็กสุดๆ มันยังบีบได้อีก เดาว่าเดี๋ยว Zopfli น่าจะมีเวอร์ชั่นใหม่ๆ มาล่ะครับ

อัลกอริทึมใหม่จากกูเกิล Zopfli บีบอัดไฟล์อัตราส่วนดีกว่า 7-zip จริงหรือ

มีข่าวว่า “กูเกิลเปิดตัว Zopfli อัลกอริทึมบีบอัดไฟล์แบบใหม่ที่ให้อัตราส่วนดีกว่า 7-zip” เลยขอพิสูจน์หน่อย อีกทั้งไปเห็นที่ CNX-Soft ได้ทดลองแล้ว ลองกับเขาบ้าง จะใช้ไฟล์ enwik8 ซึ่งมีขนาดร้อยล้านไบต์พอดีเปะจาก http://mattmahoney.net/dc/textdata.html ซึ่งใช้เพื่อ Large Text Compression Benchmark

เลียนแบบวิธีใน CNX-Soft แต่ใช้แค่ -i1000 ครับ บีบแล้วได้ขนาด 34,988,599 ไบต์ ทวีตข้อความผิดไปหน่อย แต่ในรูปที่ capture มานั้นถูกแล้ว

วันต่อมา จึงลองกับ 7-Zip พบว่าสำหรับไฟล์นี้ 7-Zip บีบย่อได้ดีกว่าครับ โดยใช้ option ให้บีบอัดเต็มที่โดยไม่ได้ระบุอัลกอริทึม ซึ่งมันจะใช้แบบ LZMA ก็พบว่าบีบได้เล็กกว่าครับ คือ 24,861,205 ไบต์

enwik8-compare-7z-zip-zopfli

อันที่จริงที่ link ข้างบน Large Text Compression Benchmark ก็มีพูดถึง 7-Zip เหมือนกันครับ ใช้วิธีคล้ายๆ กัน แต่ใส่ option ให้ทำเป็น self-extractor ขนาดก็พอๆ กับที่ผมทดลอง

links แปะอ่าน
https://code.google.com/p/zopfli/source/browse/deflate.c (จุดนี้กำลังไล่ดูอยู่ครับ อัลกอริทึมนี้จะบีบย่อไฟล์ให้ได้ฟอร์แมตที่อัลกอริทึมคลายไฟล์แบบเดิม คลายได้)
http://encode.ru/threads/1689-Google-Compress-Data-More-Densely-with-Zopfli?p=32537&viewfull=1#post32537
https://twitter.com/ohmohm/status/308073421814763522