読者です 読者をやめる 読者になる 読者になる

和歌山産pythonプログラマのブログ

和歌山出身プログラマmatsu7874が書いています。Python3と時々C++11を書きます。

メモ: 集合知プログラミング2章 推薦を行う

2章 - 推薦を行う

協調フィルタリングについての章

類似度を求める関数

入力

どのユーザーが、どのアイテムに、何点付けたか。
どのユーザーとどのユーザーの類似度を計算するか。

pref = [
    {'A':5, 'B':4, 'C':1, 'D':0},
    {'C':1, 'D':0},
    {'A':4, 'B':2, 'C':0},
]

?この点数は名義尺度, 順序尺度でも意味がある? --> 類似度の計算方法による。 cf. 尺度水準 - Wikipedia

出力

類似度が大きいほど、値が大きくなる値を返す。

ユークリッド距離を使うなり

def sim_euclidean(pref, a, b):
    duplicated = [x for x in pref[a] if x in pref[b]]
    if len(duplicated) == 0:
        return 0
    ss = 0
    for d in duplicated:
        ss += (pref[a][d] - pref[b][d]) ** 2
    return 1 / (1 + ss)

ピアソンの相関係数なり

def sim_pearson(pref, a, b):
    duplicated = [x for x in pref[a] if x in pref[b]]
    n = len(duplicated)
    if n == 0:
        return 0
    s = {person: sum([pref[person][it] for it in duplicated]) for person in [a,b]}
    ss = {person: sum([pref[person][it]**2 for it in duplicated]) for person in [a,b]}
    sp = sum([pref[a][it]*pref[b][it] for it in duplicated])
    num = sp - (s[a]*s[b]/n)
    den = ((ss[a]-s[a]**2/n) * (ss[b]-s[b]**2/n))**0.5
    if den == 0:
        return 0
    return num/den

レコメンド

類似のユーザーが知りたいわけではなく、おすすめのアイテムが知りたい。
類似度と評点の積を類似度の和で除したもの(以下、スコア)を順序付けすれば良い。

入力

  • どのユーザーが、どのアイテムに、何点付けたか。 = pref
  • どのユーザーに対してアイテムをレコメンドするか

    出力

  • おすすめのアイテム

アイテムベースのフィルタリング

ユーザーベースのフィルタリングのデータ数が増える事による問題 - ユーザーごとに評価しているアイテムがバラバラで類似度の計算が難しい。

辞書をどのアイテムが、どのユーザーに、何点を付けられたか。という持ち方に変更する。

まとめ

類似度の計算方法とデータセットの相性がキモ!

Competitive Programming Advent Calendar 2015, 2016まとめ

この記事はCompetitive Programming Advent Calendar 2016 - AdventarのDay 11の記事として作成されました。

最近hotな人の褌で相撲を取る的まとめ記事を作成しました。
Competitive Programming Advent Calendar 2015, 2016を中心に、言及されている記事を集めました。
私が特に「いいね」と思ったものについては★を付けています。

ICPC

コンテスト運営

マラソンマッチ

アルゴリズム

動的計画法

作問

言語解説

振り返り記事

入門記事

Topcoder

企業と競プロ

AtCoder

ゲームAI

オンラインジャッジ

コードゴルフ

グルーピングできないもの

※記事執筆者の皆様へリスペクトを

Python3, C++11, JavaScriptでの実行時間計測

Python3, C++11, JavaScriptでの実行時間計測

C++とJSを勉強中なのですが、Python,C++,JSの3言語で実行時間計測をどのように書くのか調べてみました。
サンプルとして$109$回足し算をする時間を計測します。

Python3

まずは普段使っているPython。バージョンはPython 3.5.1。

import time

def DoSomething():
    a = 0
    for i in range(1000000000):
        a += 1

START_TIME = time.time()

DoSomething()

ELAPSED_TIME = time.time() - START_TIME
print('Elapsed Time:', ELAPSED_TIME*1000 ,'[ms]')

C++11

バージョンはg++ (x86_64-win32-seh-rev0, Built by MinGW-W64 project) 5.1.0。
g++ -std=c++0xコンパイルしました。(最適化オプションは付けていません。)

#include <iostream>
#include <chrono>

long DoSomething(){
    long a=0;
    for(int i = 0; i<1000000000; ++i){
        ++a;
    }
    return a;
}

int main(){
    std::chrono::system_clock::time_point  start, end;
    start = std::chrono::system_clock::now();

    DoSomething();

    end = std::chrono::system_clock::now();
    double elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(end-start).count();
    std::cout << "Elapsed Time: " << elapsed << "[ms]" << std::endl;

}

JavaScript

最近競プロで使っているのですが、まだ速いのか遅いのか分からない言語。環境はNode.js v4.4.4。

function DoSomething() {
    var a;
    for (var i = 0; i < 1000000000; ++i){
        ++a;
    }
}

var start = new Date().getTime();

DoSomething();

var end = new Date().getTime();
console.log("Elapsed Time: " + (end - start) + "[ms]");

結果

C++Pythonの40倍速い!
JSもPythonの25倍速い!

言語 実行時間[ms] Python
Python3 91966 1
C++ 2216 0.0241
JS 3646 0.0396

これは強い人がC++を使うのも全くよく分かります。

追記

関数を渡すと実行時間と戻り値を表示してくれる関数にした方が使いやすいので、書き換えました。

def measure_elapsed_time(func):
    START_TIME = time.time()

    res = func()

    ELAPSED_TIME = time.time() - START_TIME

    print('Elapsed Time:', ELAPSED_TIME*1000 ,'[ms]')
    print(res)

if __name__ == '__main__':
    measure_elapsed_time(DoSomething)
template<class F>
void MeasureElapsedTime(F func){
    std::chrono::system_clock::time_point  start, end;
    start = std::chrono::system_clock::now();

    auto res = func();

    end = std::chrono::system_clock::now();
    double elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(end-start).count();
    std::cout << "Elapsed Time: " << elapsed << "[ms]" << std::endl;
    std::cout << res << std::endl;
}

int main(){
    MeasureElapsedTime(DoSomething);
}
function measureElapsedTime(func){
    var start = new Date().getTime();

    var res = func();

    var end = new Date().getTime();
    console.log("Elapsed Time: " + (end - start) + "[ms]");
    console.log(res);
}

measureElapsedTime(DoSomething);

Anacondaで環境構築するときの一例

Anaconda便利ですね。WindowsPython使うとインストールが不便なパッケージがたくさんあって困ります。 Anaconda使いましょう。 今回はソースコードを整形してくれるautopep8を使いたかったので環境を新しく作ってインストールしてみました。

conda create -n py35 python=3.5 anaconda
activate py35
conda install pep8
conda install pip
pip install autopep8
conda list --export > conda_requirements.txt
deactivate

ツイート時刻から生活リズムの可視化をする

もう10年も前の映画になるらしいですが、デスノートでLが被害者の死亡時刻を重ねると容疑者が大学生であることを割り出すシーンがあったのを覚えていますか?
あるいはGitHubでPunch cardって出るじゃないですか。なんとなく格好良くて好きです。
同じようなことがtweet時刻でも出来るのではないかと考え、tweet時刻から生活リズムが見えるか調べてみました。

やったこと

  • Twitterからツイートの投稿時間を取得
  • 曜日・時刻ごとに集計
  • ヒートマップにして表示

結果

  • 人によっては明白に寝てる時間が分かる。(社会人はちゃんと夜ちょっと寝ている)
  • 私の寝ている時間もなんとなく分かる。
  • 冬休みを挟んでしまっているので時間割までは分からない。 f:id:matsu7874:20160122131904p:plain

Twitterからtweet時刻の取得

  • GitHub - sixohsix/twitter: Python Twitter APIを使うと簡単。
  • ツイートの投稿時間は'create_at'です。
  • 'user'の'create_at'と間違えないように気をつけます。
  • 1アクセスで200tweet、最大3200tweetまでしか取得できません。ケチ!

集計

  • 時刻がUTCで与えられますので、Asia/Tokyoにします。

可視化

ソースコード

twitter apiの鍵情報はよく使うので以下の形で別ファイルにまとめている。

# twitter_keys.py
KEYS = {'consumer_key': 'xxxxxxxxxxxxxxxxxxxxxxxxx',
        'consumer_secret': 'xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx',
        'access_token': 'xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx',
        'access_secret': 'xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx'
        }
import twitter
from twitter_keys import KEYS
import seaborn


days = ['Mon', 'Tue', 'Wed', 'Thu', 'Fri', 'Sat', 'Sun']

t = twitter.Twitter(auth=twitter.OAuth(token=KEYS['access_token'], token_secret=KEYS['access_secret'],
                                       consumer_key=KEYS['consumer_key'], consumer_secret=KEYS['consumer_secret']))

users = ['matsu7874']
for username in users:
    timelog = [[0 for j in range(24)] for i in range(7)]
    total_tweets = 0
    latest_tweet = t.statuses.user_timeline(screen_name=username, count=1)[0]
    max_id = int(latest_tweet['id_str'])
    latest_date = latest_tweet['created_at']
    for i in range(16):
        response = t.statuses.user_timeline(screen_name=username, count=200, max_id=max_id)
        if response == []:
            break
        max_id = int(response[-1]['id_str']) - 1
        oldest_date = response[-1]['created_at']
        for tweet in response:
            s = tweet['created_at'].split()
            day = days.index(s[0])
            h = int(s[3].split(':')[0]) + 9
            if h >= 24:
                h %= 24
                day = (day + 1) % 7
            timelog[day][h] += 1
    for i in range(7):
        print(timelog[i])
        total_tweets += sum(timelog[i])
    seaborn.set()
    ax = seaborn.heatmap(timelog)
    title = str(username) + ' tweet log (n=' + str(total_tweets) +')\n'
    title += 'From ' + oldest_date + '\nTo ' + latest_date
    seaborn.plt.title(title)
    seaborn.plt.ylabel('day')
    seaborn.plt.xlabel('time(Asia/Tokyo)')
    seaborn.plt.yticks(range(7), list(reversed(days)))
    seaborn.plt.savefig(str(username) + '_log.png', dpi=300)

ページング

Working with Timelines | Twitter Developersに書いてあるように、
max_idを直前に処理したツイートのid(_str)-1をmax_idに指定してやれば上手く動きます。

感想

綺麗に真っ白の帯が出る生活がしたい。

もっと気持よくyukicoderで遊ぶためにテストケースを自動実行する。

solorab.net
このブログを読んだんですが、謎の呪文が1行だけ貼ってあって????ってなりました。

テストケースは自動で確かめる

ちょうどTwitterでも強い人はテストケースを自動実行しているようだということを見ていたので、自分もオシャレに自動でテストケース実行したいぞ!と思い、yukicoderからテストケースを一括でダウンロードさせていただいて、手元で一括実行することにしました。めっちゃ気持ちいいです。

yukicoderといえば、スマートサブミットや入力サンプルをコピーボタンがあって、めっちゃ使いやすい競技プログラミング練習サイトですね。ヘルプ - yukicoder

めっちゃ使いやすいyukicoderの唯一不便なところは、一覧の所に出てくるナンバリングとURLのナンバリングが異なる(リダイレクト機能はある)点で、手元でデータを管理するときにどちらかに揃えて管理したいのです。
私は問題一覧の所に出てくるナンバリングが好きなのでそちらに合わせます。

必要なもの

  • Python3.5(最新)
  • urllib3(pipでinstall)
  • beautifulsoup4(pipでinstall)

使い方

  1. 必要なものをインストールする
  2. ↓のソースを適当に名前をつけて保存(y.pyとか)
  3. python y.py 0320あるいはpython y.py 320どっちでも320は問題No.320 眠れない夜に - yukicoderに対応。
  4. 初回はテストケースがどかどか―っと./0320_test/にダウンロードされる。
  5. 各テストケースにたいして0320.py./0320_test/test_in/の各テストケースに対して実行
  6. ./0320_test/test_out/の各テストケースと比較してACとかWAとかTLE(とりあえず5秒)を表示
  7. ACだと気持ちいいい

f:id:matsu7874:20151231012733p:plain

ソース

import sys
import os


def download_testcase(problem_number):
    import urllib3
    import bs4
    http = urllib3.PoolManager()
    url = 'http://yukicoder.me/problems/no/' + str(problem_number)
    contents = http.urlopen('GET', url).data
    soup = bs4.BeautifulSoup(contents.decode('utf-8'), 'html.parser')

    problem_number = ('0000' + str(problem_number))[-4:]
    problem_id = soup.find('div', id='content').get('data-problem-id')
    url = 'http://yukicoder.me/problems/' + str(problem_id) + '/testcase.zip'

    filename = str(problem_number) + '-' + str(problem_id) + '-testcase.zip'

    data = http.urlopen('GET', url)
    if data.status == 200:
        f = open(filename, 'wb')
        f.write(data.data)
        f.close()
    return filename


def unzip(filename, place):
    import zipfile
    if not os.path.exists(place):
        os.mkdir(place)
    zf = zipfile.ZipFile(filename, 'r')
    for f in zf.namelist():
        fn = os.path.basename(place + f)
        dir_name = (place + f).replace(fn, '')
        if not os.path.exists(dir_name):
            os.mkdir(dir_name)

        uzf = open(place + f, 'wb')
        uzf.write(zf.read(f))
        uzf.close()
        print(place + f)
    zf.close()


def run_test(python_file, test_path):
    import time
    import subprocess

    testcases = os.listdir(test_path + 'test_in/')
    if not os.path.exists(test_path + 'my_out/'):
        os.mkdir(test_path + 'my_out/')

    count_testcase = len(testcases)
    count_AC = 0
    count_WA = 0
    count_TLE = 0

    for case in testcases:
        input_file = test_path + '/test_in/' + case
        expected_file = input_file.replace('test_in', 'test_out')
        output_file = input_file.replace('test_in', 'my_out')

        cmd = ['python', python_file, '<', input_file, '>', output_file]

        start_time = time.time()
        p = subprocess.Popen(cmd, shell=True, stdout=subprocess.PIPE, stderr=subprocess.PIPE)
        try:
            stdout_data, stderr_data = p.communicate(timeout=5)
            stdout_data = stdout_data.decode('utf-8')
            stderr_data = stderr_data.decode('utf-8')
        except subprocess.TimeoutExpired:
            p.kill()
            count_TLE += 1
            status = 'TLE'
        except Exception as e:
            raise
        else:
            cmd = ['diff',  expected_file, output_file]
            cp = subprocess.run(cmd, shell=True, stdout=subprocess.PIPE, stderr=subprocess.PIPE)
            if '' == cp.stdout.decode('utf-8'):
                status = 'AC'
                count_AC += 1
            else:
                status = 'WA'
                count_WA += 1
        elapsed_time = time.time() - start_time
        print(status, str(round(elapsed_time, 7)) + '[s]', end=' ')
        print(input_file.replace(test_path + '/test_in/', ''))

    print('AC', count_AC, '/', count_testcase)
    print('WA', count_WA, '/', count_testcase)
    print('TLE', count_TLE, '/', count_testcase)


if __name__ == '__main__':
    argvs = sys.argv
    problem_number = ('0000'+argvs[1])[-4:]
    current_directory = os.getcwd()
    python_file = '.\\' + problem_number + '.py'
    path = (current_directory + '\\' + problem_number + '_test\\')
    if not os.path.exists(path):
        zip_name = download_testcase(problem_number)
        unzip(zip_name, path)
    run_test(python_file, path)

苦労した所

素数は通れませんの裏話

Advent Calendar Contest Advent Calendar(以下ACCAC) 2015でNo.308 素数は通れません - yukicoderを出題させていただきました。 www.adventar.org

自分はyukicoderの★3を解くのにヒーヒー言う僕が、ACCACの初日に★4の問題を作れてしまったので、
作るときに何を考えていたかメモっておく記事です。

CodeFestivalでLayCurseさんの公演を聴く

みんな見ましょう。
www.youtube.com

ACCACの初日に無謀にも登録する

登録駆動作問ですね。もしかして強い人しか登録しないのかな?
大丈夫かな?などとビクビクしながら考える。

使いたいアルゴリズムを考える

今年一年で私自身が成長したことは幅優先探索がかけるようになったことなので、幅優先探索を使う問題が作りたい
幅優先探索といえば迷路を解く問題ですよね!

Twitterでこの画像をみる。

(google画像検索でソース分かるやろと思ってたらわからなくなってしまいました。分かる方教えて下さい。) f:id:matsu7874:20151226083001j:plain (!を足あとだと見る)

アドベントカレンダーを見る。

  • 私は初日 -> 25日まで行くとゴール
  • 解ける問題だけ通って25日に行けたらゴール。ゴールできるか判定する問題。
  • 簡単すぎ?何の変哲もない幅優先探索の問題になる?
  • でもどうせならゴールしたい。
  • ゴールできるように幅をずらせばいいのでは?
  • 幅を変えながら幅優先探索する問題。
  • 完成 それでいいのか?初日の問題だぞ?翌日LayCurseさんだぞ?作問講座の人だぞ?
  • もっと面白い問題にせねば!

通れるマスに規則性があったほうが面白いのでは?

  • 入力から通れるマスを受け取るより、ある規則に基づいて通れるますを生成できる方が考察が出来て面白いのでは?
  • 規則性といえば素数
  • 素数の方が少ないっぽいので素数は通れないことにしよう。

実験

  • 幅優先探索で書いてみる。
  • Nが小さい時はいろんな値が出てくる。
  • Nが大きい時は8と14しか答えにならないなー

証明

N-8とN-14が共に素数になる非素数Nが存在しないっぽい
とても分かりやすい解説ブログをお読みください。pekempeyさんありがとうございます。 pekempey.hatenablog.com

LayCurseさんの公演を思い出す。「制約を大胆に変えてみる」

  • 僕は大きい制約が好き。
  • 僕は僕はPythonが好き。
  • Pythonは遅い。でも多倍長整数が何も考えずに使える。

=> なんかNをめっちゃおおきくしたいなー

ミラーラビンを知る。

解けそう

  • 解けた。
  • Pythonでも制約が大きい問題が解けた!
  • N<1024の問題がTLEせずに解けた!

学び

  • テストケースが弱かった
    • N-8が擬素数になるようなNを出題する必要があった。のだろう。
  • 制約がきつすぎるとの声もあった
    • Pythonを使いましょう。
    • 競技プログラミングの醍醐味ってアルゴリズムの差で制約の格段に大きい問題を解けるところだと思います。
    • 「LLでは辛いかも」がOKなら「多倍長整数がない言語では辛いかも」もOK……OKですよね?
  • JavaにはBigIntegerも確率的素数判定もあるらしい
  • JavaScriptは誤差のない整数で扱える上限があるらしい。253乗より大きい数は浮動小数点で誤差あり。
  • 自分が作った問題を自分より強い人が解いてくれるのは嬉しい。
  • 自分が作った問題をたくさんの人が解いてくれるのは嬉しい。

yukicoderyukiさん、発起人の高♨級〠焼♨肉 (@camypaper) | Twitterさんありがとうございました。
参加者の皆さんありがとうございました。

僕は解説を見ながら★3の良問・難問を頑張りたいと思います。

追記

12/28
なぜ1024という中途半端な制約にしたのか説明し忘れていました。 Miller–Rabin primality test - Wikipedia, the free encyclopedia

if n < 3,317,044,064,679,887,385,961,981, it is enough to test a = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, and 41.

って書いていました。なので論文読んでないですが、この制約には約束されたACが存在します!!!
ロマンで書いても、実利で書いてもOKってやっぱりロマンですね。