ikemonn's blog

技術ネタをちょこちょこと

Dynamo - Cloud Computing & Big Data Group Discussion を読んだ

Dynamo: Amazon’s Highly Available Key-value Store を読んだのでメモ

メモのフォーマットは下記を参考にした。

どんなもの?

  • Dynamoは可用性とスケーラビリティのあるkey-value storage
    • primary keyアクセスでかつ1Mより小さいデータを扱うものをターゲットにしている
    • always writable
    • responseの99.9percentileが300ms以内(500req/sec)

先行研究とくらべて何がすごい?

  • 既存の技術の組み合わせで可用性とスケーラビリティのあるプロダクトを実装し本番で利用していること

技術や手法の肝は?

  • consistent-hashingでパーティションレプリケーションを行っている
  • gossipベースのfailure detection/membership protocol
  • weak-consistency(eventual consistency)によってパフォーマンス/スケーラビリティの向上
  • objectはversioningされてconsistencyを担保している
  • sloppy quoramとhinted hand offにより、nodeやネットワークの障害時でも可用性を担保
  • anti-entropyによりレプリカの同期を行う

どうやって有効と検証した?

  • 2006年12月のある日の12時間分のレスポンスタイムで検証
    • 99.9%は200ms以下でレスポンスが返ってきていた

議論はある?

  • eventual consistencyを用いているので、導入する際には対象のアプリケーションがweak consistencyでも大丈夫か検討する
  • nodeが増えれば増えるほど(数千nodeくらい)routing tableが大きくなって、routingのコストがかかってしまう

次に読むべき論文は?

Bigtable: A Distributed Storage System for Structured Data

統計検定2級に合格しました

概要

統計検定2級 (CBT方式試験) に合格しました。 79/100点でボーダーが60点でした。 Machine Learning | Coursera を受けた後に「統計学について何も知らないので勉強してみよう」と思ったのがきっかけです。 統計検定の勉強自体は2ヶ月ほどで、平日30分~1時間、土日2時間ほど勉強してました。

前提

文系(数ⅡBまで)で、微分積分は公式を見ると思い出せる程度でした。 微分積分をするのは10年ぶりです。

勉強法

最初の1ヶ月

マンガでわかる統計学

マンガでわかる統計学

マンガでわかる統計学 回帰分析編

マンガでわかる統計学 回帰分析編

まず1週間ほどで「マンガでわかる統計学」シリーズを読みました。 確かに分かりやすかったのですが、その分内容が薄いので、このシリーズは読まずに、後述する「よくわかる心理統計」を読めば良かったと思います。

Rによるやさしい統計学

Rによるやさしい統計学

次に2週間ほどで「Rによるやさしい統計学」を読みつつ、Rで検定していました。 Rで様々な検定を行っていくのですが、統計検定では自分で計算をする必要があるので、この本も読む必要はなかったと思います。 ただ実務ではRを使うことが多いと思うので、読むならば各検定の計算方法がわかった後が良かったです。

よくわかる心理統計 (やわらかアカデミズム・わかるシリーズ)

よくわかる心理統計 (やわらかアカデミズム・わかるシリーズ)

続いて「よくわかる心理統計」を読みました。 初学者にも分かりやすい良書です。 統計用語の説明がされていたり、各検定の例題と検定の仕方が詳しく書かれていたので、この本で理解が深まりました。 統計検定2級の内容をほぼ網羅している(回帰やベイズ等は含まれていない)ので、これから勉強を始める方はまずこの本を1ヶ月かけて何度も繰り返すと良いと思います。

二ヶ月目

引き続き「よくわかる心理統計」をこの月の1週目まで読んでいました。

日本統計学会公式認定 統計検定 2級 公式問題集[2014〜2016年]

日本統計学会公式認定 統計検定 2級 公式問題集[2014〜2016年]

一通り勉強が終わったので、週末に過去問を解いてみました。 最初は散々な結果だったのですが、「自分がどの部分が出来ていないのか」が理解できたので、次週からベイズや確率の勉強を始めました。

完全独習 ベイズ統計学入門

完全独習 ベイズ統計学入門

ベイズについては「よくわかる心理統計」に書かれていないので、この本で勉強しました。 極力「ベイズの公式」を使わずに理解させようという方針の本で、数式アレルギーがある方でもスッと理解できると思います。 この本を読んでからベイズの問題は得点源になりました。

確率変数の問題が苦手だったので、この本の確率変数の部分だけを読んで勉強しました。 微分積分の計算方法を思い出したり、確率密度関数から期待値や分散を出す計算を練習しました。

ここで、二ヶ月目の2週間が終わりました。

日本統計学会公式認定 統計検定 2級 公式問題集[2014〜2016年]

日本統計学会公式認定 統計検定 2級 公式問題集[2014〜2016年]

日本統計学会公式認定 統計検定 2級 公式問題集[2012〜2014年]

日本統計学会公式認定 統計検定 2級 公式問題集[2012〜2014年]

残りの期間はひたすら過去問を解いていました。 各年度3回くらい解いて、わからないところはその都度「よくわかる心理統計」等で復習をしていました。

統計学入門 (基礎統計学?)

統計学入門 (基礎統計学?)

統計学入門」も買ったのですが、内容が難しかったので使いませんでした。 「よくわかる心理統計」を何度も読み返していました。

まとめ

「文系卒で微積をするのは10年ぶり」でも、2ヶ月あれば統計検定2級合格できました。 もし2ヶ月前の自分にアドバイスするなら、下記の流れで勉強しろと言うと思います。

  1. 初日に2014年くらいの過去問を解く
  2. 「よくわかる心理統計」を2週間で読む
  3. 再度別の過去問を解いて、自分に足りない部分を把握する
  4. ベイズと確率の勉強をする
  5. 過去問を解きながら、「よくわかる心理統計」で復習する

「もっと初期に過去問を解く」「色んな参考書に目移りせずによくわかる心理統計だけやり込む」をすれば、もう少し短期間で合格出来たと思います。

機械学習の勉強のための基礎固めに!」と思っている方は、是非統計検定を受けてみてください!

SRM 647 Div2 250 PeacefulLine

問題文

TopCoder Statistics - Problem Statement

書いた

class PeacefulLine:
    def makeLine(self, x):
        counter = collections.Counter(x)
        count_arr = []

        for word, cnt in counter.most_common():
            count_arr.append(cnt)

        is_continue = True
        while is_continue:
            count_arr = sorted(count_arr)
            count_arr = map(lambda n:n-count_arr[0], count_arr)
            count_arr = filter(lambda n:n!=0, count_arr)

            if len(count_arr) <= 1:
                is_continue = False
        res = "impossible"
        if len(count_arr) <= 0 or count_arr[0] <= 1:
            res = "possible"

        return res

他の参加者のコード見た

class PeacefulLine:
    def makeLine(self, x):
        p = {}
        l = len(x)
        if (l%2==0):
            l=l/2
        else:
            l=(l//2)+1
        for i in x:
            p[i] = p.get(i,0)+1
        a = 0
        for i in p.keys():
            a = max(a,p[i])
        if(a>l):
            return "impossible"
        else:
            return  "possible"

その他

一番多い数の組が半分以上あればimpossibleだった。 数値の数を数える時に dict.get(i,0)+1 は使えそう

SRM 642 Div2 250 ForgetfulAddition

問題文

https://apps.topcoder.com/wiki/display/tc/SRM+642

書いた

class ForgetfulAddition:
    def minNumber(self, expression):
        num = str(expression)
        res = 0
        for i in xrange(1, len(num)):
            sum_num = int(num[:i]) + int(num[i:])
            if res == 0:
                res = sum_num
            res = min(res, sum_num)
        return res

他の参加者のコードみた

class ForgetfulAddition:
    def minNumber(self, expression):
        ans = 99999999
        for i in xrange(1, len(expression)):
            ans = min(ans, int(expression[i:]) + int(expression[:i]))
        return ans

感想

問題文の設定上99999999以上にはならないので、最初に設定しておけばif分無くていける。 ムダなstr変換無くす。

SRM 639 Div2 250 ElectronicPetEasy

問題文

https://apps.topcoder.com/wiki/display/tc/SRM+639

書いた

class ElectronicPetEasy:
    def isDifficult(self, st1, p1, t1, st2, p2, t2):

        first = []
        for i in xrange(t1):
            first.append(st1+(p1*i))

        second = []
        for i in xrange(t2):
            second.append(st2+(p2*i))

        res = "Easy"
        for i in first:
            if i in second:
                res = "Difficult"
                break
        return res

他の参加者のコードみた

class ElectronicPetEasy:
    def isDifficult(self, st1, p1, t1, st2, p2, t2):
        feed1 = set(range(st1, st1+p1*t1,p1))
        feed2 = set(range(st2, st2+p2*t2,p2))
        if feed1 & feed2 == set([]):
            return "Easy"
        return "Difficult"

感想

rangeでstart, stop, stepを指定すると等差数列を作れる。 set形だと&で共通する要素があるか比較できるので便利。

SRM 638 Div2 250 NamingConvention

問題文

https://community.topcoder.com/stat?c=problem_statement&pm=13521

書いた

class NamingConvention:
    def toCamelCase(self, variableName):
        while variableName.count('_') > 0:
            replace_char_index = variableName.index('_')
            variableName = variableName[:replace_char_index] + variableName[replace_char_index+1].upper() + variableName[replace_char_index+2:]
        return variableName

他の参加者のコードみたあと

result = ""
        variableName = list(variableName)
        for i, c in enumerate(variableName):
            if c == '_':
                variableName[i+1] = variableName[i+1].upper()
            else:
                result += c
        return result

感想

_ のindexを取得して、_を削除し、その後の文字を大文字にするということを考えたが、愚直に文字列をforで回したほうがシンプルだった。 pythonのstrは、Immutableなので直接書き換えることができない。 一旦Mutableなlistにしてから書き換える。

SRM 636 Div2 250 GameOfStones

問題文

Limak has found a large field with some piles of stones.

Limak likes perfection. It would make him happy if every pile had the same number of stones. He is now going to move some stones between the piles to make them all equal.

However, there is a catch. Limak's perfectionism does not allow him to carry just one stone at a time. As he has two hands, he must always carry exactly two stones: one in each hand. Thus, he can only make one type of an action: pick up two stones from one of the piles and carry both of them to some other pile. He is not allowed to remove a pile completely. Therefore, he cannot pick up stones from a pile that currently contains fewer than 3 stones.

You are given a int[] stones. Each element of stones is the initial number of stones in one of the piles. Compute and return the smallest number of actions Limak has to perform in order to make all piles equal. If it is impossible to make all piles equal using the allowed type of actions, return -1 instead.

書いた

# -*- coding: utf-8 -*-
import math,string,itertools,fractions,heapq,collections,re,array,bisect

class GameOfStones:
    def count(self, stones):
        if len(stones) <= 1:
            return 0
        sum_stones = sum(stones)

        if sum_stones % len(stones) != 0:
            return -1
        avg = sum_stones / len(stones)

        sum_gt_avg = 0
        for i in stones:
            if i > avg:
                diff = i - avg
                if (i-avg) % 2 != 0:
                    return -1
                sum_gt_avg += diff

        if sum_gt_avg % 2 != 0:
            return -1
        return sum_gt_avg / 2

他の参加者のコードみたあと

class GameOfStones:
    def count(self, stones):
        if len(stones) <= 1:
            return 0
        sum_stones = sum(stones)
        if sum_stones % len(stones) != 0:
            return -1
        avg = sum_stones / len(stones)

        result = 0
        for i in stones:
            if (i-avg) % 2 != 0:
                return -1
            if i > avg:
                result += (i-avg)/2

        return result