JBL Pebbles 買っちゃった
色々と評判の良いJBL Pebblesですが…
gentooの場合、ただ単にusbに突き刺しただけでは動かないと思います。
PulseAudioは強力です。そして、JBL Pebblesのようなチャラいデバイスを使いたがるようなユーザーにはX Windowsは絶対必要です。use="pulseaudio X"しましょう。また、Pulse AudioのGUI クライアントは、個別パッケージになってますので、わざわざインストールしてやらないといけません。でも、このpavucontrolはマジ便利なんで、インストールして損はしません。
emerge -auvDN world
emerge pavucontrol
次に、たった今インストールしたpulse Audio用のgui clientを起動します。
pavucontrol
最初に、設定タブで、JBL Pebbles をDigital Audioに設定します。デフォルトではAnalog Audioになってると思いますが、低音がボコボコいって気持悪い音がすると思います。せっかく、DACを内臓してるんですから、是非とも使いましょう。
次に、僕たちは、JBL Pebblesをデフォルトの出力装置に設定したいので、出力タブでJBL Pebblesの右上の緑のアイコンを押します。
これで、あなたのデフォルトの音声出力先が JBL Pebblesに設定されました。適当な動画を再生しましょう。素敵なボーカルを楽しんでください。
二宮愛(Ai Ninomiya)の素敵なアルトボイスを堪能してください。
■
家族用のPCのグラボが飛んでしまったようで、外さないとBIOSも上がらなくなってしまった。マザーがM2Vで、unichrome-proな内蔵グラフィックがあるので、これを使えないか試してみた所、案外簡単に動いてしまったのでメモ。
Loading...をみると、svnを使ってソースを取ってくるみたいな説明があるけど、今はportageにopenchromeが取り込まれているのでそんなことをする必要はなくなっている。
まずは、/etc/make.confを編集する。
VIDEO_CARDS="openchrome via"
次に、カーネルコンフィグ
CONFIG_BLK_DEV_VIA82CXXX=y CONFIG_SATA_VIA=y CONFIG_PATA_VIA=y CONFIG_NET_VENDOR_VIA=y # CONFIG_VIA_RHINE is not set # CONFIG_VIA_VELOCITY is not set CONFIG_HW_RANDOM_VIA=y # CONFIG_I2C_VIA is not set # CONFIG_I2C_VIAPRO is not set # CONFIG_SENSORS_VIA_CPUTEMP is not set # CONFIG_SENSORS_VIA686A is not set # CONFIG_VIA_WDT is not set CONFIG_DRM_VIA=y # CONFIG_FB_VIA is not set CONFIG_SND_HDA_CODEC_VIA=y CONFIG_SND_VIA82XX=y # CONFIG_SND_VIA82XX_MODEM is not set
フレームバッファやセンサーは面倒臭いので割愛。
あとは、emerge -udN @world; emerge --depcleanして、新しいカーネルで再起動すればok。
pythonのheapqが強力すぎる
お題は、10x10の二次元迷路の経路探索なんですけど、これにheapqを使ったらやたら早かった、というお話です。
使うアルゴリズムは、スタート地点(1, 1)から移動可能な経路のリストをバッファに積んでいって、最初にゴール(10,10)に到着した経路を出力するだけのものです。まずは、迷路なんだけど全然迷路じゃない地図を探索するという、非常に意地悪な問題の実行結果をごらんください。
solve_with_stack(data) SSSSSSSSSENNNNNNNNNESSSSSSSSSENNNNNNNNNESSSSSSSSSENNNNNNNNNESSSSSSSSSENNNNNNNNNESSSSSSSSSE 1524 function calls in 0.002 seconds (中略) solve_with_deque_fifo(data) EEEEEEEEESSSSSSSSS 31796002 function calls in 54.238 seconds (中略) solve_with_heapq(data) EEEEEEEEESSSSSSSSS 348 function calls in 0.000 seconds
S(NEW)は南(北東西)に行くという意味です。
スタック(LIFO)を使うと、実行時間はまぁまぁですが、経路が無駄に長い答えを見つけてきます。キュー(FIFO)を使うと、最短経路を先に見つけてくれるけど、実行時間が滅茶苦茶長くなる。heapqを使うと、関数呼出の回数が飛躍的に少なくなるのに、最短経路を先に見つけてくれます。優れた待ち行列だといえると思います。
ところで、heapqって何?
スタックやキューが要素を追加された順番で保持するのに対して、heapqは要素をソートして保持します。heapqでpopして出てくる要素は、heapqの要素の中で最小の物であることが保証されています。
どうやって使うの?
heapqは要素をソートする為のキーが必要になります。追加する要素がそのままでソート可能であれば問題はありませんが、そうでなければ要素をpushしたりpopする代わりに、(key, 要素)のタプルをpushしたりpopしたりします。それと、stackやdequeがオブジェクト指向風のインターフェイスなのに対して、heapqはC言語みたいなインターフェイスです。
#stack stack = [] # スタックの作成 stack.append(x) # 要素の追加 y = stack.pop() # 要素の取り出し #heapq import heapq # heapq のインポート hq = [] # heapqの作成 heapq.heappush(hq, (key(x), x)) # 要素の追加 _, y = heapq.heappop(hq) # 要素の取り出し keyは要らないので捨てる
今回のソース
経路をソートするキーとして、経路の末尾からゴールまでの距離(道程)を与えてみました。これで、ゴールに近い経路を優先して探索してくれるようになりました。
from collections import deque import heapq def solve_with_stack(maze_map): buf = [[(1, 1)]] while buf: route = buf.pop() for x in get_adjoin_pathes(route[-1], maze_map): if x == (10, 10): print(get_answer(route + [x])) return elif x not in route: buf.append(route + [x]) print('bad maze; no way to goal') def solve_with_deque_fifo(maze_map): buf = deque([[(1, 1)]]) while buf: route = buf.popleft() for x in get_adjoin_pathes(route[-1], maze_map): if x == (10, 10): print(get_answer(route + [x])) return elif x not in route: buf.append(route + [x]) print('bad maze; no way to goal') def solve_with_heapq(maze_map): dist = lambda x: 20 - x[0] - x[1] buf = [] heapq.heappush(buf, (dist((1, 1)), [(1, 1), ])) while buf: _, route = heapq.heappop(buf) for x in get_adjoin_pathes(route[-1], maze_map): if x == (10, 10): print(get_answer(route + [x])) return elif x not in route: heapq.heappush(buf, (dist(x), route + [x])) print('bad maze; no way to goal') snew = {(0, 1): 'E', (1, 0): 'S', (0, -1): 'W', (-1, 0): 'N'} def get_answer(route): _diff = lambda a, b: (b[0] - a[0], b[1] - a[1]) _move = lambda x: _diff(route[x], route[x + 1]) genexp = (_move(i) for i in range(len(route) - 1)) return ''.join(snew[x] for x in genexp) def get_adjoin_pathes(last, maze_map): _in_pathes = lambda x: maze_map[x[0]][x[1]] == 0 _add_to_last = lambda x: (x[0] + last[0], x[1] + last[1]) return filter(_in_pathes, map(_add_to_last, snew.keys())) if __name__ == '__main__': # 0が通路 1が壁 (1, 1)がスタート (10, 10)がゴール data = [ [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]] import cProfile test1 = 'solve_with_stack(data)' test2 = 'solve_with_deque_fifo(data)' test3 = 'solve_with_heapq(data)' test_list = [test1, test2, test3] for x in test_list: print(x) cProfile.run(x)
ところで、pythonでlambdaを多用すると、プロファイルがちょっと見にくいですね。
行列式 3
import System.Random randomList :: Random a => a -> a -> IO [a] randomList a b = fmap (randomRs (a, b)) newStdGen pmat :: Int -> [[a]] -> [[a]] pmat n d = [tail x | x <- left ++ tail right] where (left, right) = splitAt n d det:: (Num a) => [[a]] -> a det [[x]] = x det [[a, b], [c, d]] = a * d - b * c det d = sum [s * head x * det (pmat i d) | (s, i, x) <- zip3 (cycle [1, -1]) [0..] d] getMat :: (Num a) => Int -> [a] -> [[a]] getMat _ [] = [] getMat n x = [take n x] ++ getMat n (drop n x) main = do hoge <- randomList 1 9 :: (IO [Int]) let n = 10 let d = getMat n $ take (n^2) hoge print d print $ det d
関数sig は、1と-1を交互に返すだけなので、わざわざ関数とするまでもないなと。zip3というのを見つけたので、これを使うことにした。トータルの実行時間は2.5秒程度にまで改善した。これくらい違うと、haskellを使ってみてもいいかなと思える。
haskell版 行列式
import System.Random randomList :: Random a => a -> a -> IO [a] randomList a b = fmap (randomRs (a, b)) newStdGen pmat :: Int -> [[a]] -> [[a]] pmat n d = [tail x | x <- left ++ tail right] where (left, right) = splitAt n d sig :: (Integral a, Num b) => a -> b sig a = if mod a 2 == 0 then 1 else -1 det:: (Num a) => [[a]] -> a det [[x]] = x det [[a, b], [c, d]] = a * d - b * c det d = sum [(sig i) * head x * det (pmat i d) | (i, x) <- zip [0..] d] getMat :: (Num a) => Int -> [a] -> [[a]] getMat _ [] = [] getMat n x = [take n x] ++ getMat n (drop n x) main = do hoge <- randomList 1 9 :: (IO [Int]) let n = 10 let d = getMat n $ take (n^2) hoge print d print $ det d
haskellのリストはリンクリストなんで、 x !! i みたいなアクセスは時間がかかるらしい。
それで、!!関数を使わないようにしてみた。
行列式のhaskell版
pmat :: Int -> [[a]] -> [[a]] pmat n d = [tail (d !! i) | i <- [0..length d - 1], i /= n] sig :: (Integral a, Num b) => a -> b sig a = if mod a 2 == 0 then 1 else -1 det :: (Num a, Fractional a) => [[a]] -> a det [[x]] = x det [[a, b], [c, d]] = a * d - b * c det d = sum [sig i * head (d !! i) * det (pmat i d) | i <- [0..length d - 1]] main = do let xs = [1..] let d = [[x | x <- take 10 xs] | _ <- take 10 xs] print (det d)
pythonだと8秒弱かかるのが、haskellだと5秒くらい。この差が大きのか小さいのかは
よくわからない。ただ、haskellはコンパイラに文句言われるのがちょっと面倒。