Быстрая загрузка элементов в массив / список с фиксированным индексом без дубликатов

Question

Мое требование - вводить в массив строки, которых нет в массиве.Мне также нужно поддерживать фиксированные индексы, так как этот массив будет использоваться с другой структурой данных, имеющей отношение один к одному с каждым индексом.В настоящее время я использую класс ArrayList и проверяю методом indexOf (), чтобы проверить, существует ли он первым, а если нет, то добавить его в список с помощью метода add () с одним аргументом.Я не знаком с классами в Java, и поэтому не мог понять, как я могу реализовать его с помощью HashMap или чего-то еще (три или еще), что сделает процесс загрузки быстрым.

Выполните indexOf () в ArrayList делает последовательный поиск?Моя цель - сократить время обработки при загрузке слов в массив, не вставляя дубликаты, и поддерживать фиксированный индекс элементов.Если проверенное слово уже находится в массиве, , то индекс, в который оно уже вставлено, требуется , так как этот индекс необходим для индексации в какой-либо другой структуре и выполнения некоторой обработки.Любые предложения, чтобы сделать этот процесс лучше?

ОБНОВЛЕНИЕ

Есть массив, у меня есть несколько документов, откуда мне нужно отсканировать каждое слово и найти уникальные слова вдокументы.Но также мне нужно посчитать количество дубликатов.Иными словами, мне нужно посчитать частоты терминов уникальных терминов, встречающихся в документах.Я поддерживаю ArrayList<Integer[]> частота терминов (количество терминов х количество документов).Я выбираю одно слово, а затем проверяю, есть ли оно в списке слов методом indexOf ().Если его нет в списке слов, тогда я вставляю слово в список и выделяю новую строку в массиве 2d (Array<Integer[]>), а затем устанавливаю счетчик элемента term в массиве 2d равным 1.Если слово уже находится в массиве слов, тогда я использую индекс слова в массиве для индексации в строке матрицы Array<Integer[]> и использую текущий номер документа при обработке, чтобы добраться до ячейки и увеличить счетчик..

Мой вопрос заключается в том, чтобы сократить время обработки 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