哈明數
 |
||
|
哈明數 |
|
此問題經常被提出，用來解釋為何「x 程式設計」比較好（特別是 x 的值為：函數式 和 邏輯式）。如果忽略處理大數字的成本，則可行解為 O(n)（其中 n 為數字序列的大小）。在 [Lambda the Ultimate] 上的某個有趣 [討論串] 中深入探討，分析指出成本可能是 O(n^(4/3))。
Haskell 解決這個問題的方法簡潔明瞭，
-- Merges two infinite lists merge :: (Ord a) => [a] -> [a] -> [a] merge (x:xs)(y:ys) | x == y = x : merge xs ys | x < y = x : merge xs (y:ys) | otherwise = y : merge (x:xs) ys -- Lazily produce the hamming sequence hamming :: [Integer] hamming = 1 : merge (map (2*) hamming) (merge (map (3*) hamming) (map (5*) hamming))
儘管有更簡短的解答。上述解答的重點在於 lazy evaluation（延遲求值）的 Haskell，因此無限序列 hamming 可用於自我參照。Lua 可以透過某種「承諾」來做到這一點。以下程式碼僅實作夠用的 bignum（大數字）以進行 2、3 及 5 倍增運算，並列印結果。（哈明數 7305 是 2^52，因此如果您想要計算更多哈明數，便需要 Bignum 支援。實際上，bignum 介面僅增加約 33% 的計算成本；有趣的是，實作哈明數的所有程式碼完全不需要了解數字的實際實作，只要實作支援 <、== 和與小整數相乘即可。
透過計算值從 50,000 到 1,000,000 的 hamming(k) 來檢查程式效能；效能似乎大致為 O(n)（在空間和時間上），儘管我未嘗試最佳化，且空間消耗有點多。
usec RSS
n sec. Mb /n kb/n value
------- ---- ----- ---- ---- --------------------------------------------------------------------
50000 1.99 3768 39.8 75.4 2379126835648701693226200858624
100000 4.41 5524 44.1 55.2 290142196707511001929482240000000000000
150000 6.87 6784 45.8 45.2 136551478823710021067381144334863695872000000
200000 9.42 7932 47.1 39.7 4479571262811807241115438439905203543080960000000
250000 11.99 8932 48.0 35.7 29168801439715713801701411811093381120000000000000000
300000 14.57 9944 48.6 33.1 62864273786544799804687500000000000000000000000000000000
350000 17.18 10768 49.1 30.8 60133943158606419031489628585123616917982648729600000000000
400000 20.06 14240 50.1 35.6 30774090693237851027531250000000000000000000000000000000000000
450000 23.10 16104 51.3 35.8 9544028161703913537712243143807801346335324481500000000000000000
500000 25.98 17392 52.0 34.8 1962938367679548095642112423564462631020433036610484123229980468750
550000 28.98 18724 52.7 34.0 286188649932207038880389529600000000000000000000000000000000000000000
600000 32.05 19256 53.4 32.1 31118367413797724237140050340541118674764220486395061016082763671875000
650000 35.27 20332 54.3 31.3 2624748786803793305341077210881955201024000000000000000000000000000000000
700000 38.13 21372 54.5 30.5 177288702931066945536000000000000000000000000000000000000000000000000000000
750000 41.34 21536 55.1 28.7 9844116074857088479400896102109753641824661421606444941755765750304761446400
800000 44.51 22280 55.6 27.9 458936503790258814279745536000000000000000000000000000000000000000000000000000
850000 47.59 23896 56.0 28.1 18286806033409508387421738007105886936187744140625000000000000000000000000000000
900000 50.64 23952 56.3 26.6 632306706993546185913146473467350006103515625000000000000000000000000000000000000
950000 54.02 26552 56.9 27.9 19221158232427643481897048859403926759149694825267200000000000000000000000000000000
1000000 57.36 26800 57.4 26.8 519312780448388736089589843750000000000000000000000000000000000000000000000000000000
以下是程式碼
do local meta = {} function meta:__index(k) if k == "tail" then local rv = self.gen(self) self.tail, self.gen = rv, nil return rv end end function Seq(h, gen) return setmetatable({head = h, gen = gen}, meta) end end function SMap(func, seq) return Seq(func(seq.head), function() return SMap(func, seq.tail) end) end function SMerge(seq1, seq2) local head1, head2 = seq1.head, seq2.head local step if head1 < head2 then function step() return SMerge(seq1.tail, seq2) end elseif head2 < head1 then function step() return SMerge(seq1, seq2.tail) end head1 = head2 else function step() return SMerge(seq1.tail, seq2.tail) end end return Seq(head1, step) end function Times(k) if k then return function(x) return x * k end else return function(x, y) return x * y end end end function Hamming() local init = 1 if Bignum then init = Bignum(init) end local seq = Seq(init) local seq2, seq3, seq5 = SMap(Times(2), seq), SMap(Times(3), seq), SMap(Times(5), seq) function seq.gen() return SMerge(seq2, SMerge(seq3, seq5)) end return seq end function SeqTail(seq, k) for i = 1, k do seq = seq.tail end return seq end if arg then local start, finish, inc = tonumber(arg[1]), tonumber(arg[2]), tonumber(arg[3]) if not start then start, finish, inc = 1, 20, 1 end local h = SeqTail(Hamming(), start-1) print("hamming", start, h.head) if finish then while start + inc <= finish do start = start + inc h = SeqTail(h, inc) print("hamming", start, h.head) end end end
以下是一些更有趣的無限序列函數，包括費氏數列產生器（儘管我不建議您實際使用，但它可以在常數空間和大致線性時間下執行。）
function SAlways(val) return Seq(val, function(seq) return seq end) end function SDist(func, init, seq) return Seq(init, function(self) return SDist(func, func(self.head, seq.head), seq.tail) end) end function SMap2(func, seq1, seq2) return Seq(func(seq1.head, seq2.head), function() return SMap2(func, seq1.tail, seq2.tail) end) end function Plus(k) if k then return function(x) return x + k end else return function(x, y) return x + y end end end Iota = SDist(Plus(), 1, SAlways(1)) function Fib(i, j) i, j = i or 1, j or 1 local seq = Seq(Bignum(i)) seq.tail = SDist(Plus(), Bignum(j), seq) return seq end
以下是簡單的 Bignum 實作（如果您想要測試上述程式碼，請先定義這個）
do -- very limited bignum stuff; just enough for the examples here. -- Please feel free to improve it. local base = 1e15 local fmt = "%015.0f" local meta = {} function meta:__lt(other) if self.n ~= other.n then return self.n < other.n end for i = 1, self.n do if self[i] ~= other[i] then return self[i] < other[i] end end end function meta:__eq(other) if self.n == other.n then for i = 1, self.n do if self[i] ~= other[i] then return false end end return true end end function meta:__mul(k) -- If the base where a multiple of all possible multipliers, then -- we could figure out the length of the result directly from the -- first "digit". On the other hand, printing the numbers would be -- difficult. So we accept the occasional overflow. local offset = 0 if self[1] * k >= base then offset = 1 end local carry = 0 local result = {} local n = self.n for i = n, 1, -1 do local tmp = self[i] * k + carry local digit = tmp % base carry = (tmp - digit) / base result[offset + i] = digit end if carry ~= 0 then n = n + 1 if offset == 0 then for i = n, 2, -1 do result[i] = result[i - 1] end end result[1] = carry end result.n = n return setmetatable(result, meta) end -- Added so that Fib would work; other must be a Bignum function meta:__add(other) local result = {} if self.n < other.n then self, other = other, self end local n, m = self.n, other.n local diff = n - m local carry = 0 local result = {} for i = m, 1, -1 do local tmp = self[i + diff] + other[i] + carry if tmp < base then carry = 0 else tmp = tmp - base carry = 1 end result[i + diff] = tmp end for i = diff, 1, -1 do local tmp = self[i] + carry if tmp < base then carry = 0 else tmp = tmp - base carry = 1 end result[i] = tmp end if carry > 0 then n = n + 1 for i = n, 2, -1 do result[i] = result[i - 1] end result[1] = carry end result.n = n return setmetatable(result, meta) end function meta:__tostring() local tmp = {} tmp[1] = ("%.0f"):format(self[1]) for i = 2, self.n do tmp[i] = fmt:format(self[i]) end return table.concat(tmp) end function Bignum(k) return setmetatable({k, n = 1}, meta) end end
供參考，時間/空間圖表（標題除外）是使用以下程式建立的（可能只適用於 FreeBSD 或類似的作業系統）
for ((i = 50000; $i<=1000000; i = $i + 50000)) do /usr/bin/time -apl -o hamming.log ./hamming.lua $i >> hamming.log; done
egrep '(hamming|user|maximum)' hamming.log | \
lua -e 'local a = io.read"*a"; \
for n, res, time, size in string.gfind(a, "(%d+)%s+(%d+)%D+([%d.]+)%s+(%d+)") do \
print(string.format("%8i %8.2f %8i %6.1f %6.1f %s", \
n, time, size, (time*1e6)/n, (size*1e3)/n, res)) \
end' > hamming.res
--RiciLake