編集:私はあなたのアイデアを聞いて、検索を実行するときにはるかに高速であることが証明されている ArrayLists の代わりに HashMaps を使用することにしました。残念ながら、Join 関数は 2 つの異なるテキスト ファイルのデータを結合しないため、Join 関数の実装に行き詰まりました。代わりに、探しているデータのインデックス番号のみを出力します。誰が私が間違っているのか教えてもらえますか?
約 200,000 エントリのデータを含むいくつかのテキスト ファイルがあります。
ファイルは次のとおりです。 - artist.txt (曲 ID とアーティスト名を含む) - albums.txt (曲 ID、曲名、制作年、アーティスト ID、プロデューサー ID、コストを含む) - production.txt (曲 ID、アーティスト ID、参加アーティスト数) - studio.txt (スタジオの場所とプロデューサー ID を含む)
ドキュメントをスキャンして指定されたデータを最短時間で見つけるアルゴリズムを実装する必要があります。
例を挙げましょう: 特定の年に (albums.txt から) というタイトルの曲を制作したアーティストの名前 (artists.txt から) を見つけたいとします。また、これら 2 つのテーブルを結合したいので、出力には両方のファイルから選択されたデータが表示されます。
現在の実装では、ドキュメント全体をスキャンするため、指定されたエントリを見つけるのに非常に長い時間がかかります (A で始まるすべてのアーティスト名を表示するのに 40 秒)。私のコードはこれを数秒で整理できるはずだと言われました。ArrayList の代わりに HashMaps/TreeMaps を追加することを考えていましたが、これで何かが変わるかどうかはわかりません。
これを実装するためのより良い方法をお勧めできますか? どのデータ型を使用すればよいか、この問題を処理するための最も迅速で最適なアルゴリズムは何かを考えています。
私はJAVAに非常に慣れていないため、このトピックについてはあまり知りませんが、あなたの推奨事項を試してみたいと思っています.
私はすぐに解決できる解決策を探しているわけではありません。このトピックに関するあなたの意見を知りたいだけで、希望する効果を得る方法についてのヒントが得られることを願っています.
編集されたコード:
import java.io.BufferedReader;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedHashMap;
public class Table {
String line;
int columns;
HashMap<String,ArrayList<String>> grid;
public Table(int columns)
{
grid = new HashMap<String,ArrayList<String>>();
this.columns = columns;
}
public Table(int columns, String filename) throws Exception
{
grid = new HashMap<String,ArrayList<String>>();
this.columns = columns;
BufferedReader fh =
new BufferedReader(new FileReader(filename));
int lineNum = 0;
//Add all the lines from text file
while(null != (line=fh.readLine()))
{
String[] parts = line.split("\t");
//Separate the text file into parts
String name = parts[0];
String id = parts[1];
//Create new ids
if(!grid.containsKey(id))
grid.put(id,new ArrayList<String>());
//Add a name to each id
grid.get(id).add(name);
}
}
public class comp implements Comparator<ArrayList<String>> {
int whichCol;
public int compare(ArrayList<String> o1, ArrayList<String> o2) {
return o1.get(whichCol).compareTo(o2.get(whichCol));
}
}
public Table SelectAll(int colNum, String val)
{
Table result = new Table(this.columns);
for(ArrayList<String> row:this.grid.values())
{
if (row.size()<=colNum)
System.out.println("Error: "+row.toString());
if (!row.get(colNum).startsWith(val))
{
result.grid.put(row.get(colNum), row);
System.out.println(row);
}
}
return result;
}
public Table Join(int col1, Table r, int col2)
{
Table result = new Table(this.columns+r.columns);
HashMap<String,ArrayList<String>> sorrid = (HashMap<String,ArrayList<String>>) this.grid.clone();
comp mycomp = new comp();
mycomp.whichCol = col1;
//For everyone in the first one, check everyone in second one
for(ArrayList<String> i: this.grid.values())
{
for(ArrayList<String> j: r.grid.values())
{
if(i.get(col1).equals(j.get(col2)))
{
ArrayList<String> newrow = new ArrayList<String>();
newrow.addAll(i);
newrow.addAll(j);
result.grid.put(newrow.get(0), newrow);
}
}
}
return result;
}
public void displayAll()
{
for(String r : grid.keySet())
{
System.out.println(r);
for(String n : grid.get(r))
System.out.println(" " + n);
}
}
public void displaySelected(String value)
{
for(String r : grid.keySet())
{
if(r.startsWith(value))
System.out.println(r);
}
}
public Table SelectEq(int colNum, String val)
{
Table result = new Table(this.columns);
for(ArrayList<String> row:this.grid.values())
{
if (row.size()<=colNum)
System.out.println("Error: "+row.toString());
if (row.get(colNum).equals(val))
result.grid.put(row.get(0), row);
}
return result;
}
public int size()
{
return this.grid.size();
}
public Table StartsWith(int colNum, String val)
{
Table result = new Table(this.columns);
for(String r : grid.keySet())
{
if (grid.size()<=colNum)
System.out.println("Error: "+r.toString());
if (r.startsWith(val))
result.grid.put(r, new ArrayList<String>());
}
return result;
}
}