1

製品機能マトリックスがあります。数千の行 (製品) と数百の機能があります。製品にこの機能があるかどうかを示すバイナリ値があります。したがって、40,000 行と 900 列のテーブルになる可能性があります。

Product-feature matrix
pr f1 f2 f3 fn ...
01 0 1 1 1
02 0 0 0 0
03 1 0 1 0
04 1 0 1 0
.....

まず、特定の機能セット QEg Q=(f1=1, f5=1, f27=1) を持つ製品を見つけなければなりません。簡単に言えば、青い車、ハッチバック、3ドアを見つけてください。

Result 1
Given Q=(f1=1, f5=1, f27=1)
Relevant products: 03, 04, 08...

次に、最も重要なことですが、一連の機能 Q を持ち、機能 f_i (ここで i - 1..n) も持つ製品がいくつあるかを見つけなければなりません。つまり、Qを満たす行を選択し、各列に1がいくつあるかを数えます（SUM集計を行います）。たとえば、青い車、ハッチバック、3 ドアには、ディーゼル エンジン、ガソリン エンジン、キセノン ライトも何台ありますか。

Result 2
Given Q=(f1=1, f5=1, f27=1)
sum f2 = 943
sum f3 = 543
sum f4 = 7
sum f6 = 432
....

もちろん、RDBMS を使用してこのタスクを解決することは可能ですが、それほど効果的ではありません。一般に、各列の製品と集計の両方を検索するためにフルスキャンが必要になります。少なくとも、このタスクに効果的な B ツリー インデックスを作成する方法がわかりません。Oracle ビットマップ インデックスは役に立ちますが、Oracle を使用できません。

現在、このタスクには MySQL を使用していますが、良い結果が得られていません。実際には、列の量を減らすために整数表現を使用しています (機能をグループ化し、bool 値ではなく整数を列に格納します)。

このマトリックスをスパース バイナリ マトリックスとして扱うことができます。そして、それを完全にメモリに保存することは大きな問題ではありません。また、いくつかのアルゴリズムを適用して、疎行列、ベクトル空間 (SVD、行列とベクトルの乗算など) を処理できるかどうか疑問に思っています。ただし、集計ではなく、ベクトル Q を満たす製品を見つけるのに役立つ可能性があります。問題は、スペースではなく、集約の時間にあります。

おそらく、製品を見つけて各列の集計を行うのに役立つマルチリンクリストとしてマトリックスを保存することは可能です。

最後に、問題はこのタスクをどのように処理するかです。特定の機能を備えた製品を見つけて、追加機能を備えた製品を数えるための最も効果的なアルゴリズムは何ですか (列ごとに集計)。

4

3 に答える 3

1

データを列ごとに並べ替えることができます。つまり、その機能を備えた車/列を一覧表示する列に1つのBitSetがあります。

これにより、BitSetが提供する高速な操作や操作を利用できます。

これらの機能を使用すると、各機能の検索とカウントで2マイクロ秒未満を達成できるはずです。

40,000 * 900データセットの場合、次のように出力されます

average search time 1396 ns.
average count time 1234 ns.

これは、RDBMSデータベースで取得できるよりも数桁速いはずです。100万行でも、それぞれ50マイクロ秒未満かかります。

public static void main(String... args) throws IOException {
    final int rows = 40 * 1000;
    final int cols = 900;

    List<BitSet> features = new ArrayList<BitSet>();
    features.add(new BitSet(rows));
    features.add(new BitSet(rows));
    for (int i = 2; i < cols; i++) {
        final BitSet bs = new BitSet(rows);
        for (int j = 0; j < rows; j++)
            bs.set(j, j % i == 0);
        features.add(bs);
    }

    // perform the search
    int[] factors = new int[]{2, 5, 7};
    BitSet matches = new BitSet();
    long runs =  1000*1000;
    {
        long start = System.nanoTime();
        for (int i = 0; i < runs; i++) {
            // perform lookup.
            lookup(matches, features, factors);
        }
        long avgTime = (System.nanoTime() - start) / runs;
        System.out.println("average search time " + avgTime  + " ns.");
    }
    {
        long start = System.nanoTime();
        int count9 = 0;
        BitSet col9matched = new BitSet(cols);
        for (int i = 0; i < runs; i++) {
            final int index = 9;
            final BitSet feature = features.get(index);
            count9 = countMatches(col9matched, matches, feature);
        }
        long avgTime = (System.nanoTime() - start) / runs;
        System.out.println("average count time " + avgTime + " ns.");
    }
}

private static int countMatches(BitSet scratch, BitSet matches, BitSet feature) {
    // recycle.
    scratch.clear();
    scratch.or(matches);
    scratch.and(feature);
    return scratch.cardinality();
}

private static void lookup(BitSet matches, List<BitSet> data, int[] factors) {
    matches.clear();
    matches.or(data.get(factors[0]));
    for (int i = 1, factorsLength = factors.length; i < factorsLength; i++) {
        matches.and(data.get(factors[i]));
    }
}
于 2010-11-01T15:20:07.283 に答える
1

少し前に私が行ったこの例を見てください。ジェイディーが正しく概説したものに従いますが、より詳細には、実行時間が 0.02 秒の 1 億 2500 万の poster_categories (car_features) に対して - あなたの場合、最悪の場合は 40K++ * 900 列になります= 3600 万行、つまり、赤ちゃんです!

mysql select を書き換えて時間を短縮し、tmp をディスクに書き込む

select count(*) from category
count(*)
========
500,000


select count(*) from poster
count(*)
========
1,000,000

select count(*) from poster_category
count(*)
========
125,675,688

select count(*) from poster_category where cat_id = 623
count(*)
========
342,820

explain
select
 p.*,
 c.*
from
 poster_category pc
inner join category c on pc.cat_id = c.cat_id
inner join poster p on pc.poster_id = p.poster_id
where
 pc.cat_id = 623
order by
 p.name
limit 32;

id  select_type table   type    possible_keys   key     key_len ref                         rows
==  =========== =====   ====    =============   ===     ======= ===                         ====
1   SIMPLE      c       const   PRIMARY         PRIMARY 3       const                       1   
1   SIMPLE      p       index   PRIMARY         name    257     null                        32  
1   SIMPLE      pc      eq_ref  PRIMARY         PRIMARY 7       const,foo_db.p.poster_id    1   

select
 p.*,
 c.*
from
 poster_category pc
inner join category c on pc.cat_id = c.cat_id
inner join poster p on pc.poster_id = p.poster_id
where
 pc.cat_id = 623
order by
 p.name
limit 32;

0.021: Query OK
于 2010-11-01T13:19:35.900 に答える
1

現在のソリューションを理解している場合、各製品の行と各機能の列を含む 1 つのテーブルがあります。これは、問題を解決するには非常に非効率的な方法です。

３テーブルでどうですか

"products" (product_ref, product_name) index product_ref (製品のリスト)

"features" (feature_ref、説明) index feature_ref (可能な機能のリスト)

と

"productfeatures" (product_ref, feature_ref) index product_ref,feature_ref および feature_ref,product_ref (各行は製品の機能を表します)

その後、テーブル間の結合を実行できます

select * from products t1 join productfeatures t2 join productfeatures t3 where t1.product_ref=t2.product_ref and t1.product_ref=t3.product_ref and t2.feature_ref=45 and t3.feature_ref=67 など.

于 2010-11-01T11:17:45.417 に答える