のAndroid - アプリケーションの起動を最適化

Question

---

EDIT：

---

私はあなたの良いアドバイスに従っていると私は私のdictionnaryを含むようにトライデータ構造を使用しました。私が選んだ構造は、興味のある人々のためにthis oneです。

しかし、今私は別の問題があります：私のアプリケーションを起動するたびに私のトライのデータ構造の構築は非常に長いです！たぶん私の辞書が大きすぎる、あるいは私が選んだトライの実装が単純な辞書にはあまりにも適切でないかもしれない。

登録されたデータベースのようにアプリケーションを終了した後でもこの構造を維持する方法があるのですか？その問題が実装によって引き起こされたと思われる場合は、もう1つお勧めできますか？

---

私はアンドロイドのプロジェクトに深刻な問題があります。と

• の言葉 '：ここ

  目標があることを行うには6つの文字

  のセリエで作ることができるすべての単語を計算することで、私は私のBDDに2つのテーブルをしました'_id'と 'mots'の2つの列

• 'temp'同じ列のテンポラリテーブル 。

「単語」には語彙のすべての単語が含まれています（「巨大」）。「temp」には、6文字（少なくとも3文字）で作成できるすべての文字の組み合わせが含まれます。

私はテーブル '単語'の中にあるように実際の単語をテーブル 'temp'で選択しようとしています。ここではそれを行うには、私のコードは次のとおりです。

私は良いの文字を含む単語（少なくとも3つの文字が使用されている）

db.execSQL("CREATE TABLE temp2 (_id integer primary key autoincrement, mots text not null);"); 
db.execSQL("INSERT INTO temp2 (_id, mots) SELECT * FROM words WHERE mots like '%"+lettres.tab_char.get(0)+"%' OR mots like '%"+lettres.tab_char.get(1)+"%' " 
        + "OR mots like '%"+lettres.tab_char.get(2)+"%' OR mots like '%"+lettres.tab_char.get(3)+"%' OR mots like '%"+lettres.tab_char.get(4)+"%' " 
        + "OR mots like '%"+lettres.tab_char.get(5)+"%';"); 

（lettre.tab_charは、ArrayListを（文字である）の最初の選択を行います私は私の中に値をつけた後

String MY_QUERY = "SELECT temp2._id, temp2.mots FROM temp2 INNER JOIN temp ON temp2.mots = temp.mots;"; 
Cursor test = db.rawQuery(MY_QUERY, null); 

：これは一時で組み合わせ）

私はテーブル「TEMP2」と「一時」の間に参加するかを作るために使用される文字が含まれていますリストビュー。

これは動作しますが、実際には非常に遅いです。お手伝いできますか？

Answer 1

一般に、使用しているアルゴリズムは非常に非効率的です。最初に、ワイルドカードマッチを使用してすべてのエントリを6回検索してから、この巨大な結果をデータセット全体に再び結合します。

SQLはおそらくこれを行うのに適切な場所ではありません。 SQLはクエリで優れていますが、これはより多くの計算です。コード内でマッチングを行います。

これを達成するにはさまざまな方法がありますが、適切な解決策を見つけることは要件によって異なります。文字を繰り返すことはできますか？どのくらいの語彙が「巨大」ですか？まだ数MBに収まるのでしょうか？このルックアップは、瞬間的に起こる必要がありますか？

更新：

要件を考えると、私はジョーに同意する必要があります。それはアルゴリズムよりも実際にはデータ構造ですが、トライが道のりです。あなたはアプリをロードしている間にトライを一度構築できなければなりません。そして、それぞれの「マッチ」はトライを歩いているかなり簡単なルックアップになります。

Answer 2

探しているアルゴリズムは、実際には "trie"（再trie valの略）と呼ばれています。彼らはと非常にの計算に適しています（Androidでは実際にSMSやメールアプリで使用して、顔文字の置き換えなどを行います）。適切に実行されると、そのパフォーマンスから驚くことでしょう。私はポールに同意します：あなたは間違いなくではありませんあなたのような質問をしてください。実際、多くの実装では、ディクショナリファイル全体をメモリ内のトライにロードして、そのトライをアプリケーションのライフタイム全体にわたる単語の参照と検証に使用します。スクラブルワードリスト（リンクは以下の質問にも含まれています：twl06.zip）はわずか1.9MBで、178kワードを含んでいます。メモリ内のトライは実際には1.9MBよりはるかに小さいはずです。複数の単語が共通のプレフィックスを共有するためです（例えば、 "stair"と "stare"はSTAプレフィックスを共有します。その上で、「R」]、および...）

はここで開始するには良い場所です：あなたが関心しているためAlgorithm to generate anagrams