Обработка больших списков строк в Java - PullRequest
Новая
       22

Обработка больших списков строк в Java

7 голосов
/ 02 октября 2011

У меня есть задача, где я должен пройти несколько миллиардов строк и проверить, является ли каждая из них уникальной.Все линии не могут быть размещены в оперативной памяти ПК.Кроме того, число строк, вероятно, будет больше, чем Integer.MAX_VALUE.

Я предполагаю, что лучший способ обработать этот объем данных - поместить хеш-коды каждой из строк в некоторыйHashTable.

Итак, вот мои вопросы:

  1. Что я должен использовать вместо String.hashCode()?(возвращаемое значение - int, но мне, вероятно, понадобится long)
  2. Какой самый быстрый способ / фреймворк для работы со списками такого размера?Что мне больше всего нужно, так это возможность быстро проверить, содержит ли список элемент

Ответы [ 2 ]

4 голосов
/ 02 октября 2011

Вы слишком обдумали проблему, все это можно сделать очень просто с помощью одной таблицы MySQL, которая сохраняет данные на диск вместо того, чтобы хранить все в памяти. Такой большой объем данных никогда не предназначался для эффективной обработки отдельным приложением. 

CREATE TABLE TONS_OF_STRINGS
(
  unique_string varchar(255) NOT NULL,
  UNIQUE (unique_string)
)

Просто переберите значения (при условии, что список разделен запятыми) и попробуйте вставить каждый токен. Каждый сбойный токен является дубликатом. 

public static void main(args) {
  Connection con = DriverManager.getConnection("jdbc:mysql://localhost/database","username","password");
  FileReader file = new FileReader("SomeGiantFile.csv");
  Scanner scan = new Scanner(file);
  scan.useDelimiter(",");
  String token;
  while ( scan.hasNext() ) {
    token = scan.next();
    try {
      PreparedStatement ps = con.prepareStatement("Insert into TONS_OF_STRING (UNIQUE_STRING) values (?)");
      ps.setString(1, token);
      ps.executeUpdate();
    } catch (SQLException e) {
      System.out.println("Found duplicate: " + token );
    }
  }
  con.close();
  System.out.println("Well that was easy, I'm all done!");
  return 0;
}

Не забудьте очистить таблицу, когда закончите, это много данных.

3 голосов
/ 02 октября 2011

Недостаточно просто хранить 32- или 64-битные хеш-коды, потому что две отдельные строки (из нескольких миллиардов) могут легко иметь один и тот же хеш-код.Если у вас есть две строки с одинаковым хеш-кодом, вам нужно сравнить фактические строки, чтобы увидеть, действительно ли они равны.

Вот способ, которым я бы решил эту проблему:

  1. Чтение файла / потока строк:

    1. Чтение каждой строки

    2. Вычисление хеш-кода для строки

    3. Запишите хеш-код и строку во временный файл с подходящим разделителем полей между

  2. Используйте приличную внешнюю программу сортировки для сортировкивременный файл, использующий поле хэш-кода в качестве первичного ключа сортировки и строковое поле в качестве вторичного ключа сортировки.

  3. Считывание временного файла по одной строке за раз.Если две последовательные строки имеют одно и то же поле хеш-кода и разные строковые поля, вы нашли дублирующую строку.

Примечание. Этот подход будет одинаково хорошо работать с 32- или 64-битными хеш-кодами.

...