将元素快速加载到具有固定索引且无重复的数组/列表中

Question

我的要求是将不在数组中的字符串输入到数组中。我还需要维护固定索引，因为该数组将与其他数据结构一起使用，与每个索引具有一对一的关系。目前我正在使用 ArrayList 类并使用 indexOf () 方法检查它是否首先存在，如果不存在则使用 将其添加到列表中带有一个参数的 add() 方法。我对java中的类不熟悉，因此无法理解如何使用HashMap或其他东西（trie或其他）来实现它，这将使加载过程更快。

ArrayList 中的 indexOf () 是否进行顺序搜索？ 我的观点是减少将单词加载到数组时的处理时间，不插入重复项，并保持元素的固定索引。如果测试的单词已在数组中，则需要已插入该单词的索引，因为需要该索引来索引到其他结构并进行某些处理。有什么建议可以让这个过程变得更好吗？

更新

有一个数组，我有一些文档，我需要扫描每个单词并在文档中查找唯一的单词。但我还需要计算重复项的数量。换句话说，我需要计算文档中出现的独特术语的术语频率。我正在维护术语频率的 ArrayList（术语数 x 文档数）。我正在获取一个单词，然后使用 indexOf () 方法检查它是否在单词列表中。如果它不存在于单词列表中，那么我将该单词插入到列表中，并在二维数组中分配一个新行（Array），然后设置二维数组中的术语元素计数为 1。如果该单词已经在单词数组中，那么我使用该单词在数组中的索引来索引该单词的行Array 矩阵，并使用当前正在处理的文档编号来获取单元格并递增计数。

我的问题是减少我当前使用的每个单词的 indexOf () 处理时间。我需要获取单词数组中单词的索引（如果它已经在其中），如果它不在那里，那么我需要将其动态插入到数组中。

示例代码

import java.io.*;
import java.util.ArrayList;
import static java.lang.Math.log;


class DocumentRepresentation
{
  private String dirPath;
  private ArrayList<String> fileNameVector;
  private ArrayList<String> termVector;
  private ArrayList<Integer[]> tf; /* store it in natural 2d array */
  private Integer df[]; /* do normal 1d array */
  private Double idf[]; /* do normal 1d array */
  private Double tfIdf[][]; /* do normal 2d array */

  DocumentRepresentation (String dirPath)
  {
    this.dirPath = dirPath;
    fileNameVector = new ArrayList<String> ();
    termVector = new ArrayList<String> ();
    tf = new ArrayList<Integer[]> ();
  }

  /* Later sepatere the internal works */
  public int start ()
  {
    /* Load the files, and populate the fileNameVector string */
    File fileDir = new File (dirPath);
    int fileCount = 0;
    int index;

    if (fileDir.isDirectory () == false)
    {
      return -1;
    }

    File fileList[] = fileDir.listFiles ();

    for (int i=0; i<fileList.length; i++)
    {
      if (fileList[i].isFile () == true)
      {
        fileNameVector.add (fileList[i].getName ());
        //      System.out.print ("File Name " + (i + 1) + ": " + fileList[i].getName () + "\n");
      }
    }

    fileCount = fileNameVector.size ();
    for (int i=0;i<fileNameVector.size (); i++)
    {
      System.out.print ("Name " + (i+1) + ": " + fileNameVector.get (i) + "\n");
    }

    /* Bind the files with a buffered reader */
    BufferedReader fileReaderVector[] = new BufferedReader [fileCount];
    for (int i=0; i<fileCount; i++)
    {
      try
      {
        fileReaderVector[i] = new BufferedReader (new FileReader (fileList[i]));
      }
      /* Not handled */
      catch (FileNotFoundException e)
      {
        System.out.println (e);
      }
    }

    /* Scan the term frequencies in the tf 2d array */
    for (int i=0; i<fileCount; i++)
    {
      String line;

      try
      {
            /*** THIS IS THE PLACE OF MY QUESTION **/
        while ((line = fileReaderVector[i].readLine ()) != null)
        {
          String words[] = line.split ("[\\W]");

          for (int j=0;j<words.length;j++)
          { 
            if ((index = termVector.indexOf (words[j])) != -1)
            {
              tf.get (index)[i]++;
              /* increase the tf count */
            }
            else
            {
              termVector.add (words[j]);
              Integer temp[] = new Integer [fileCount];

              for (int k=0; k<fileCount; k++)
              {
                temp[k] = new Integer (0);
              }
              temp[i] = 1;
              tf.add (temp);
              index = termVector.indexOf (words[j]);
            }

            System.out.println (words[j]);
          }
        }
      }
      /* Not handled */
      catch (IOException e)
      {
        System.out.println (e);
      }
    }

    return 0;
  }
}

class DocumentRepresentationTest
{
  public static void main (String args[])
  {
    DocumentRepresentation docSet = new DocumentRepresentation (args[0]);
    docSet.start ();
    System.out.print ("\n");
  }
}

注意：代码被剪断以将焦点集中在问题上

Answer 1

LinkedHashMap 能够一次性满足您的所有要求，具有良好的性能特点。

键将是您的项目，值将是索引。如果按照索引递增的顺序插入元素，则迭代映射也会按照索引递增的顺序返回元素。

以下是一些示例代码：

LinkedHashMap<Item,Integer> map = new LinkedHashMap<Item,Integer>();

获取项目的索引：

Integer index = map.get(item);
if (index != null) {
  // already in the map; use `index'
} else {
  // not in the map
}

将 item 添加到下一个索引：

if (!map.containsKey(item)) {
  map.put(item, map.size());
}

按索引递增的顺序迭代元素：

for (Entry<Item,Integer> e : map.entrySet()) {
  Item item = e.getKey();
  int index = e.getValue();
  ...
}

这不能有效地获取特定位置的值索引，但我对你的问题的阅读表明你实际上并不需要这个。

Answer 2

ArrayList.indexOf() 执行线性搜索，因此时间复杂度为 O(n)。

如果确实必须放入 ArrayList，您可以创建两个集合：ArrayList 和 HashSet。向两个集合添加和删除元素。在添加之前，调用HashSet.contains()来查看该元素是否已经存在。

将 ArrayList 和 HashSet 封装在它自己的类中。

Answer 3

如果你想离开ArrayList，你可以有一个HashSet作为支持，但代价是双倍的内存。

您可以使用 HashSet.add() 如果返回 true，您还可以将元素添加到 ArrayList