2016年9月17日

巡回セールスマン問題における最短経路をpgRoutingで探索する

先日、PostgreSQLアンカンファレンスを開催した際、「pgRoutingを使って巡回セールスマン問題を解く」という発表を国府田さんがされていました。
非常に面白そうな機能で、私も少し使ってみましたので、今回はその使い方や使用例などを含めてご紹介します。

■「巡回セールスマン問題」とは何か


「巡回セールスマン問題」というのは、以下のようなものです。
巡回セールスマン問題（じゅんかいセールスマンもんだい、英: traveling salesman problem、TSP）は、都市の集合と各2都市間の移動コスト（たとえば距離）が与えられたとき、全ての都市をちょうど一度ずつ巡り出発地に戻る巡回路の総移動コストが最小のものを求める（セールスマンが所定の複数の都市を1回だけ巡回する場合の最短経路を求める）組合せ最適化問題である。
巡回セールスマン問題 - Wikipedia
簡単に言うと、「セールスマンが何か所か回る時、回る場所が増えれば増えるほど、可能性のある経路の候補が爆発的に増えていくので、最短経路を導き出すのが困難になる」ということです。回る場所の数「n」に対して、計算量はその階乗「n!」のオーダーとなります。

続きを読む »
Posted by at 0 件のコメント:
Labels: ,

2016年9月4日

9月10日（土）に第8回PostgreSQLアンカンファレンスを開催します

開催まであと1週間を切りましたが、9/10にPostgreSQLアンカンファレンスを開催します。多分、8回目くらいだと思います。
いつもの通り、プログラムやタイムテーブルは当日集まってから募集して調整します。

PostgreSQLに興味があって、いろんな技術レベルの人が集まっていますので、初めての方もお気軽にご参加ください。

いつもオープニングの時に聞いているのですが、参加者のうち、だいたい2/3くらいは初めて参加の方っぽいですので。

では、来週末お会いしましょう。
Posted by at 0 件のコメント:
Labels: ,

2016年8月4日

【翻訳】 On Uber’s Choice of Databases （データベースにおけるUberの選択について）

数日前、Uberのブログで「Why Uber Engineering Switched from Postgres to MySQL」というエントリが公開されました。
それに対して、PostgreSQLコミュニティ界隈でもいろいろなブログエントリが公開されました。
今回は、そのエントリの中でも、「Use The Index, Luke!」でおなじみのMarkus Winand氏のエントリ「On Uber’s Choice of Databases」が個人的に興味深かったので、同氏の翻訳許可をいただきまして、ここに対訳形式で公開します。

なお、当然ですが翻訳に際しての文責は翻訳者である永安にありますので、問題を見つけた場合にはコメント欄またはTwitter (@snaga)などで連絡いただけますと幸いです。

では、どうぞ。

■On Uber’s Choice of Databases （データベースにおけるUberの選択について）


On 7-29-2016
By Markus Winand

続きを読む »
Posted by at 2 件のコメント:
Labels: , ,

2016年7月19日

TF-IDFでデータベース内の類似テキストを検索する Part 4 （MADlib svec編）

TF-IDF 感動巨編3部作は前回のエントリで完結したわけですが、今回はその番外編、スピンオフとして「MADlib svec編」をお送りします。

MADlib には、sparse（疎）な配列、つまり多くの要素がゼロであるような配列を扱うデータ型として svec というデータ型があります。
本エントリでは、TF-IDF のベクトルに MADlib の svec を使って、通常の float8[] などとどのように違うのかを見てみます。

■「MADlib」とは何か


MADlib については、ガッツリと割愛します。以前のエントリで詳しくご紹介しましたので、そちらを参照してください。

■「svec」 とは何か


svec は、ゼロの多い sparse な配列を圧縮して保持するデータ型です。データ分析をしていると、頻繁に遭遇するデータの構造になります。

例えば、float8 の配列で以下のようにゼロが並ぶデータがあったとします。 
'{0, 33,...40,000個のゼロ..., 12, 22 }'::float8[]
続きを読む »
Posted by at 0 件のコメント:
Labels: , ,

2016年7月13日

TF-IDFでデータベース内の類似テキストを検索する Part 3 （性能改善編）

PostgreSQL 感動巨編 TF-IDF 3部作の最終回、「性能改善編」です。 前回の最後で、今回作成した UDF である euclidean_distance の処理に時間がかかってそうだ、ということが分かってきました。

そのため、本エントリではこの UDF をもう少し詳細に見ながら、パフォーマンスを改善する方法を探ります。

■euclidean_distanceの性能分析


処理時間がかかっていることが分かった euclidean_distance 関数ですが、改めて処理を詳細に見ていきます。 
CREATE OR REPLACE FUNCTION euclidean_distance(tfidf_a jsonb, tfidf_b jsonb)
  RETURNS float8
AS $$
    from sklearn.metrics.pairwise import euclidean_distances
    import json

    aa = json.loads(tfidf_a)
    bb = json.loads(tfidf_b)
    w = list(set(aa.keys()).union(set(bb.keys())))
    vec_a = []
    vec_b = []
    for t in w:
        if t in aa:
            vec_a.append(aa[t])
        else:
            vec_a.append(0)
        if t in bb:
            vec_b.append(bb[t])
        else:
            vec_b.append(0)
    distance = euclidean_distances([vec_a], [vec_b])
    return distance[0][0]
$$
LANGUAGE 'plpython2u';
まず、ボトルネックの確認のため、少しずつこの関数のコードをコメントアウトして実行時間を比較してみると、

続きを読む »
Posted by at 0 件のコメント:
Labels: , , ,
登録: 投稿 (Atom)