3

私のAndroidアプリでは、オートコンプリート付きの入力フィールドが必要です。アイテムの数は約300000になります。最善の解決策は、アイテムをファイル（sdcard上）に入れることです。1行に1つのアイテムがあり、各行の文字数は同じであるため、特定の行番号を探すことができます。 。ユーザーがテキストフィールドに何かを入力すると、ファイルを（RandomAccessFileを介して）バイナリ検索し、提案を表示します。

オートコンプリートを超高速（理想的には100ミリ秒未満ですが、不可能だと思います）にしたいのですが、どのような最適化を実行できますか？

更新1： ユーザー入力をスペース付きの小文字の英語文字（az）に変換します。したがって、「A/b」は「ab」に変換されてから検索されます。

Uodate 2： 単語の先頭の部分文字列を検索するために、追加のものが必要であることに気付きました。

4

11 に答える 11

6

テキストファイルではなく、 SQLite DBを使用してみませんか？
状況に応じて、ポータブルデータベースよりも速度的に優れた方法はないと思います。

于 2010-09-15T15:29:15.060 に答える
6

あなたが探しているものはTRIEと呼ばれています

http://forums.sun.com/thread.jspa?threadID=5295936

コンピュータサイエンスでは、トライまたはプレフィックスツリーは、キーが通常文字列である連想配列を格納するために使用される順序付けられたツリーデータ構造です。二分探索木とは異なり、ツリー内のどのノードもそのノードに関連付けられたキーを格納しません。代わりに、ツリー内のその位置は、関連付けられているキーを示します。ノードのすべての子孫には、そのノードに関連付けられた文字列の共通のプレフィックスがあり、ルートは空の文字列に関連付けられています。値は通常、すべてのノードに関連付けられるわけではなく、対象のキーに対応するリーフといくつかの内部ノードにのみ関連付けられます。

于 2010-09-15T16:09:29.323 に答える
3

Trieは明白な答えであり、すでに述べましたが、さらにtr13ライブラリがあなたが見ているものかもしれません。ガベージコレクターに対応し（単一のrawバイト配列またはバイトバッファー）、コンパクトで、ケースに十分な速度を備えています。キーは通常UTF-8文字列ですが、任意のバイトシーケンスにすることができます。同様に、値も同様ですが、非常にコンパクトな文字列から整数へのルックアップを取得するために使用される可変長整数（vints）の代替手段もあります（特に、intの小さいセットの場合）。

于 2010-09-15T17:29:48.007 に答える
2

1つの戦略は、RandomAccessFileおよびバイナリ検索を使用して結果を絞り込むことです。次に、可能なエントリが十分に小さくなったら、その部分をメモリにロードし、メモリ内検索を実行します。

これにより、パフォーマンスが向上します。ユーザーが入力すると、メモリにロードしたファイルの同じ部分をすばやく検索できるためです。

于 2010-09-15T15:35:05.817 に答える
1

この目的で標準ライブラリを使用できるかどうかを確認することをお勧めします。たぶん、apacheluceneはAndroid携帯で使用できます。その場合は、インデックスを作成できます（単語プレフィックス-> android sql liteの単語のID）。これは、luceneが使用しているアルゴリズムの一種についての説明です。

于 2010-09-15T15:44:35.930 に答える
1

1行あたり1ワードのストレージの主な問題は、一定時間内に行にランダムアクセスがないため（行Xへのアクセスは、ファイルの先頭からX個の改行文字をカウントすることです）、バイナリ検索で問題が発生することです。

この特定の（オートコンプリート）状況で必要なのは、プレフィックスツリーまたはそのバリエーションです（複数のノードを1つに結合するか、特定のサイズよりも小さいサブツリーを単純な古い並べ替えられた単語のリストに変換します）。

于 2010-09-15T15:45:23.913 に答える
1

これをチェックしてくださいhttp://en.wikipedia.org/wiki/Binary_search_algorithm

ソートされたファイルでは、O（log（n））の二分探索の最悪のケースがあります。次善の策は、O（1）になるようなハッシュマッピングですが、これは部分的な単語では複雑で、巨大なマッピングテーブルを生成します。

于 2010-09-15T15:29:57.820 に答える
1

実行時に実行するのではなく、事前に検索ツリーに可能性を前処理します。

于 2010-09-15T15:40:28.040 に答える
1

100msは十分な時間です。最大の心配はディスプレイの更新だと思います。

実際のデータベースを避けたい場合は、メインファイルに加えて単純なインデックスファイルを使用するだけで簡単に実行できます。

文字列の最初のNバイト（おそらく4バイト？）とファイルオフセットをメインファイルのメインファイルに32レコード程度ごとにインデックスに格納し、それをバイナリ検索することができます。バイナリ検索でかなり近づいた後、最大32レコードを線形に検索できます。

平均文字列長とメディアでの1回の読み取りのサイズを考慮して、32レコードから意味のあるものにインデックス頻度を調整できます。512バイトのファイルシステム読み取りと8バイトの平均文字列がある場合は、64レコードごとにインデックスを作成するなどです。最小ディスク読み取りサイズごとに複数のインデックスレコードを作成しても意味がありません。

インデックスファイルは簡単に生成でき、メインファイルは簡単なテキストエディタで管理できます。

于 2010-09-15T16:37:28.513 に答える
1

古いスレッドですが、これが必要です： Stringsearchライブラリ

Android用のアプリ「WordlistPro」に使用しましたが、とてもスピーディーです。

于 2012-04-30T12:44:12.207 に答える
0

私もこのようなことをすることができます（以下は前処理されたファイルです）：

aa - line 1
ab - line 17
.
.
zz - line 299819

ユーザーがaaで始まるものを入力した場合、1〜17行目を読み取り、それらを順番に検索します。

于 2010-09-15T15:49:42.803 に答える