4

まず第一に、この質問の性質は、私の知識に従ってすでに投稿されている他の質問とは異なることを明確にしたいと思います。そうでない場合はお知らせください。

与えられた

  1. 私は名前のリストを持っています〜3000。
  2. 1行に1つの名前で構成される約2500のファイルがあります（名前リストから取得）
  3. 各ファイルには最大3000の名前が含まれています（したがって、平均は400ですが、最大3000行です）

問題

ある時点で、2つのファイルが提供されます。両方のファイルに共通する名前のリストを作成する必要があります。

前処理

時間の複雑さを軽減するために、前処理を行い、すべてのファイルの名前を並べ替えました。

私のアプローチ

  1. 指定されたリストで名前を並べ替え、0から2999までのインデックスを付けました
  2. 各名前の各ファイル
  • グループ番号を計算しました（name_index / 30）
  • グループ値を計算しました（同じグループ内の名前ごとに（2 ^（name_index％30））を計算して追加します）
  • 「groupNumberblankSpacegroupValue」の形式で同じ名前の新しいファイルを作成します

結果

各ファイルに〜3000（平均は400）の名前を付ける代わりに、各ファイルに最大100行を含めるようになりました。次に、共通のグループ番号を確認する必要があります。次に、ビット操作を使用して、共通の名前を見つけることができます。

期待

誰かが問題のより短くてより良い解決策を提案できますか？前処理を実行して新しいファイルをアプリケーションに保存できるため、一般名を見つけるときに最小限の処理が必要です。

問題を解決するために間違った方向に進んでいる場合はお知らせください。前もって感謝します。

ポイント

私のアプローチでは、合計ファイルのサイズは258KB（グループ名とグループ値を使用したため）であり、各行の名前で保持されている場合、そのサイズは573KBです。これらのファイルはモバイルデバイスに保存する必要があります。そのため、可能な限りサイズを小さくする必要があります。また、データ圧縮を楽しみにしていますが、その方法がわかりません。それも説明してください。

4

4 に答える 4

4

次のことを試しましたか？

  1. list1 から名前を 1 つずつ読み取り、ハッシュセットに追加します。
  2. list2 から一度に 1 つずつ名前を読み取り、リスト 1 から作成されたハッシュセットで検索します。それらがハッシュセットにある場合、その名前は両方のファイルに共通であることを意味します。

速度を上げるために前処理を行う場合は、名前の数を各リストに保存し、短い方のリストを list1 として選択します。

于 2012-05-09T20:37:12.050 に答える
2

あはは！編集で述べた非常に低いメモリ要件を考えると、別のことができます。

私はまだあなたが他の答えが示唆する解決策に行くことができると思います. HashSet3000エントリの AはString大きくなりすぎません。16文字での私の簡単な概算は、Strings400 kB未満のヒープメモリを示唆しています。試してから戻ってください。プログラム全体で 25 行のコードに相当します。

ソリューションが大量のメモリを消費する場合は、次のようにすることができます。

  1. ファイル内の名前を並べ替えます。それは常に良いことです。
  2. 両方のファイルを開きます。
  3. 両方のファイルから 1 行を読み取ります。
    1. の場合line1 < line2、 から 1 行読み取りline1、繰り返します。
    2. の場合line1 > line2、 から 1 行読み取りline2、繰り返します。
    3. それ以外は同じで、結果に追加します。繰り返す。

それは事実上メモリを消費せず、compareTo()メソッド (名前のソートに使用した場合) とswitchステートメントを使用するのに適した場所だと思います。

ファイルのサイズは、メモリ使用量にまったく影響しません。

データ圧縮について - 使用できるツールとアルゴリズムはたくさんあります。これを試してください(関連する質問も見てください)、またはこれを試してください。

于 2012-05-10T09:10:55.137 に答える
0

リストを使用してセットを再実装しようとしています。そうしないでください。挿入の重複を自動的に処理する名前のセットを使用します。

両方のファイルを読み取る必要があります。それを回避する方法はありません。

// in pseudo-java
Set<String> names1 = new HashSet<String>();
for (String name : file1.getLine().trim()) {
  names1.put(name);
}

Set<String> names2 = new HashSet<String>();
for (String name : file2.getLine().trim()) {
  names2.put(name);
}

// with this line, names1 will discard any name not in names2
names1.retainAll(names2);

System.out.println(names1);

この例のように使用すると仮定するとHashSet、文字列のハッシュを比較することになり、パフォーマンスが劇的に向上します。

パフォーマンスが十分でない場合は、より高速なソリューションを探し始めます。それ以外は時期尚早な最適化であり、どれだけ速く実行する必要があるかわからない場合は、目標を設定しない最適化です。「最速」のソリューションを見つけるには、可能なすべてのソリューションを列挙して使い尽くす必要があります。まだチェックしていないソリューションの方が速い可能性があるからです。

于 2012-05-09T21:00:20.327 に答える
0

あなたの要件と状況を理解できたかどうかわかりません。

それぞれ 3000 語 (または 400 語?) のファイルが約 2,500 あります。複数のファイルで発生する単語の重複が多数あります。

ここで、file-345 と file-765 が共通する単語はどれか、と聞かれるでしょう。

すべての単語を保存するハッシュマップと、単語が出現するファイルのリストを作成できます。

ファイル 345 が 3000 語 (400?) ある場合は、ハッシュマップを調べて、ファイル 765 がリストのどこに記載されているかを確認します。

ただし、2 * 3000 はそれほど大きくありません。Scala (JVM 上で実行) で文字列の 2 つのリストを作成すると、次のようになります。

val g1 = (1 to 3000).map (x=> "" +  r.nextInt (10000))
val g2 = (1 to 3000).map (x=> "" +  r.nextInt (10000))

そして交差点を作る

g1.intersect (g2)

8 年前のラップトップで、結果 (678 要素) をすぐに取得できます。

では、いくつのリクエストに答える必要がありますか? ファイルの入力はどのくらいの頻度で変更されますか? まれに、2 つのファイルの読み取りが重要なポイントになる場合があります。

あなたにはいくつのユニークな言葉がありますか？おそらく、それらすべてをメモリに保持することはまったく問題ありません。

于 2012-05-09T21:21:02.513 に答える