1

次の問題を解決するためのより良い方法を考えることができません...? 行と列がある種のIDである大きなテーブルがあると想像してください。本のIDとしましょう

book_id-->1    2     3     .....
  1       1   0.92    0.33
  2
  3

この表のエントリは、各書籍がどの程度類似しているかを示しています。上の表から、書籍 1 と書籍 2 の類似度指数は 0.92 です。

だから、私はすでにバンクエンドでこれを計算しました..「n」エントリとしましょう。

n+1 から、データはリアルタイムで取得されます。

だから私がしなければならない最初のステップは、この新しい行を埋めることです..非常に単純なアプローチはこれです.

 i = 0; i < total_books ; i++
    sim(book(n+1),book(i)) 

本の類似性を計算する計算が非常に高速であるとしましょう。しかし、これは「n」回発生する必要があるため、合計すると..

そして、「m」個の新しい本がある場合、そのn ^ 2操作です(私は思います)。この計算を受け入れられるようにする、より優れたアルゴリズム/データ構造はありますか。

また、いくつかの背景を埋めるためだけに。この類似性は、2 つのベクトル間の内積に他なりません。(コサインの類似性をグーグルで検索すると、アイデアが得られます)。しかし、それは空想的なものではありません.. 2 つのベクトルの間の内積を取るだけです.. 0 と 1 の間の値を返します。

4

1 に答える 1

0

n 本のコレクションに 1 本を追加すると、n 操作を実行します n 本のコレクションに m 本を追加すると、(n) + (n+1) + ... (n+m-1) を実行します(確認する必要がある) 操作: n*m + (1+2 + ... (m-1)) したがって、O(n*m + m*m) である必要があります。

単純な方法でソリューションを実装した場合、id(book_i) < id(book_j) の場合にのみ sim(book_i,book_j) を計算して格納することで、計算時間を半分にすることができます (これによって複雑さは変わりません)。次に、sim(i,j) を取得する場合は、正しい順序で引数を使用していることを確認する必要があります。

于 2012-04-15T07:46:49.410 に答える