1

编辑：我听取了您的想法并决定使用 HashMaps 而不是 ArrayLists，这在执行搜索时被证明要快得多。不幸的是，我在实现 Join 函数时遇到了困难，因为它没有加入来自两个不同文本文件的数据。相反，它只输出我正在寻找的数据的索引号。谁能告诉我我做错了什么？

我有一些文本文件，其中包含大约 200,000 条数据。

文件如下： - Artists.txt（包含歌曲 ID 和艺术家姓名） - Albums.txt（包含歌曲 ID、歌曲名称、制作年份、艺术家 ID、制作人 ID、成本） - Production.txt（包含歌曲 ID、艺术家 ID，参与的艺术家数量）- studio.txt（包含工作室位置和制作人 ID）

我需要实现一个算法，它将在最短的时间内扫描文档以找到指定的数据。

我给你举个例子：我想找到艺术家的名字（来自artist.txt），他在特定年份制作了名为（来自albums.txt）的歌曲。我还想加入这两个表，因此输出将显示两个文件中的选定数据。

当前的实现需要很长时间才能找到指定的条目（显示所有以 A 开头的艺术家姓名需要 40 秒），因为它会扫描整个文档。我被告知我的代码应该能够在几分之一秒内解决这个问题。我正在考虑添加 HashMaps/TreeMaps 而不是 ArrayList，但我不确定这是否会改变任何东西。

您能否推荐一种更好的实施方式？我想知道我应该使用什么数据类型，以及处理这个问题的最快和最合适的算法是什么。

我需要说我对 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;
    }
}
4

1 回答 1

0

这是我的方法/设计：

  • 创建类艺术家{歌曲，艺术家}
  • 创建类专辑{歌曲，标题，年份，艺术家，制作人，成本}
  • 创建类 Production {歌曲，艺术家，艺术家数量}
  • 创建类工作室 { 位置，生产者 }

加载器实例化这些类并将对象引用添加到几个NavigableMaps中。

例如：查看专辑中的艺术家姓名，由年份和歌曲名称指定：

NavigableMap<Integer,Album> matchYear = albumsByYear.subMap( 2004, true, 2005, false );
NavigableMap<String,Album> matchTitle    = albumsBySongTitle.tailMap( title );
Set<Album> matchYearAndTitle = year2004.values().retainAll( titled.values());
for( Album a : matchYearAndTitle )
{
   System.out.println( a.getArtist());
}

等等...

您必须按索引列定义所有地图。

于 2012-10-16T21:39:45.623 回答