ikautak.log

C/C++, Python, CUDA, Android, Linux kernel, Network, etc.

pythonでファイルの分割・結合

ファイルを分割・結合するスクリプト。

まず分割する方。ファイル名を渡すと .frac0 などを末尾につけたファイルに分割される。
分割サイズはとりあえず1MB。

#!/usr/bin/env python

import sys
import os.path


def bin_div(f, size=1024*1024):
    l = os.path.getsize(f)
    div_num = (l + size - 1) / size
    last = (size * div_num) - l

    b = open(f, 'rb')
    for i in range(div_num):
        read_size = last if i == div_num-1 else size
        data = b.read(read_size)
        out = open(f + '.frac' + str(i), 'wb')
        out.write(data)
        out.close()
    b.close()


if __name__=='__main__':
    if len(sys.argv) > 1:
        bin_div(sys.argv[1])

次に結合する方。.frac0などを除いたファイル名と分割数を渡すと結合した.outを作成する。

#!/usr/bin/env python

import sys


def bin_cat(f, num):
    out = open(f + '.out', 'wb')

    for i in range(num):
        frac = open(f + '.frac' + str(i), 'rb')
        out.write(frac.read())
        frac.close()
    out.close()


if __name__=='__main__':
    if len(sys.argv) > 2:
        bin_cat(sys.argv[1], int(sys.argv[2]))

ダイクストラの最短経路アルゴリズム

courseraで課題になってたのでいろいろ参考にしながらpythonで実装した。

参考ページ
http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm#Pseudocode
http://taichino.com/programming/1333

./dijkstra.py graph_file start end のようにオプションを渡す。
graphデータのファイルは、各行に、vertexと、隣接したvertex,lengthを記述したもの。

1 2,3 3,3
2 3,1 4,2
3 4,50
4
#!/usr/bin/env python

import sys
from altgraph import Graph

def read_graph(f):
    g = Graph.Graph()
    for l in file(f):
        l = l.rstrip().split()
        # read vertex
        v = int(l[0])
        l.pop(0)

        # read neighbor & length
        for i in l:
            i = i.split(',')
            g.add_edge(v, int(i[0]), int(i[1]))

    return g

def dijkstra(graph, start):
    dist = {}
    for v in graph.nodes:
        dist[v] = sys.maxint

    prev = {}
    for v in graph.nodes:
        prev[v] = None

    dist[start] = 0
    Q = graph.nodes.copy()

    while len(Q):
        # find vertex with smallest distance.
        min_dist = sys.maxint
        u = Q.keys()[0] # first vertex
        for v in Q:
            if dist[v] < min_dist:
                u = v
                min_dist = dist[v]

        del(Q[u])
        if dist[u] == sys.maxint:
            break

        # find neighbors
        neighbors = {}
        for e in graph.edges.values():
            if e[0] == u:
                neighbors[e[1]] = e[2]

        for v in neighbors:
            alt = dist[u] + neighbors[v]
            if alt < dist[v]:
                dist[v], prev[v] = alt, u
    return dist, prev

if __name__=='__main__':
    if len(sys.argv) > 2:
        graph_file = sys.argv[1]
        start = int(sys.argv[2])
        end = int(sys.argv[3])

        g = read_graph(graph_file)
        dis = dijkstra(g, start)
        print dis[0][end]

1->3への最短経路

$ ./dijkstra.py graph.txt 1 3
3

HackerRank - Changing Bits

HackerRankのChanging Bitsを解いた。

AとB用にsize Nの配列を作り、setされるたびに指定indexのbitを更新する。
getのときにLSB側から愚直にA+Bを計算するとTime limit exceededになるのでA+Bの計算量を減らす工夫が必要。
ここでpythonからC++に変更。

getするindexのbitを決めるのはA[index]+B[index]だけでなく、下位bitからの繰り上がりもあるので、index部分からLSBに向かって繰り上がりがないかAとBを走査していく。A[i]とB[i]がともに1なら繰り上がりありで終了、ともに0ならなしで終了。
これでTLEは結構減るが、いくつかのテストデータはもう10%くらい処理時間を削る必要がある。

あるindex値xからLSB側に走査していき、y番目で繰り上がりあり・なしが確定して終了したとすると、
次に[x,y]内のindexがgetされた場合は、走査を省略して繰り上がりあり・なしを判断すれば計算量を減らせるので、
走査した結果をキャッシュしておくような仕組みを入れた。 ただ、このキャッシュ内にsetされると、無効化したり範囲を狭くしないとまずいのでややこしい…
これでローカルだと4倍以上速くなったが、submitしたら結構ギリギリのAcceptだった。

出題者の想定するアルゴリズムになってない気がするが、効率的な解き方があるんだろうか??
問題名でググるとStack Overflowとか海外のブログが引っかかるけど、斬新な解き方みたいな情報は見つからなかったし、途中であきらめてる人が多いっぽい。

HackerRank 2問解答

HackerRankのBasic Statistics WarmupMedianを解いた。

Basic Statisticsの5番目の95%信頼区間は、正規分布表から固定値をハードコーディングした。
scipy使ったサンプルとか拾ってきて試したけど微妙に誤差があって、パラメータの問題なんだろうけど調べるのに疲れたので自力で標準誤差から計算した。

Medianは愚直にリストの追加・削除をしていると後半のテストデータでTime limit exceededになるので2分探索する。
あとは割り切れる時は小数点を出力しないとか、出力ルールで最初Wrong answerになった。

HackerRankは日本人少なくて、JapanでフィルタするとScore 300でも今のところ10位とかになる。
日本で10位です(`・ω・´)キリッ とか言えば転職で有利だろうか?(全体だと2000位だけど。)