Найти общие имена в двух файлах на Java

Question

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

Учитывая

1. У меня есть список имен ~ 3000.
2. Есть ~ 2500 файлов, которые состоят из имен одной в строке (взято из списка имен)
3. Каждый файл содержит ~ 3000 имен (и, следовательно, ~ 3000 строк, хотя в среднем составляет 400)

Задача

В данный момент мне предложат 2 файла. Я должен создать список имен, которые являются общими в обоих файлах.

Pre Processing

Для уменьшения времени сложности я делал предварительную обработку и отсортированный имена во всех файлах.

Моего подход

1. Отсортированных имена в данном списке и индексируются их от 0 до 2999
2. В каждом файле для каждого имени

---

• Рассчитана группа номер (имя_индекс/30)
• Расчетное значение группы (для каждого имени в той же группе Статистика (2^(name_index% 30)) и добавить)
• Создать новый файл с таким же именем в формате «groupNumber blankSpace groupValue»

---

Результат

Вместо ~ 3000 (хотя в среднем составляет 400) имена в каждом файле теперь будет иметь максимум 100 строк в каждом файле. Теперь мне нужно будет проверить общий номер группы, а затем с помощью манипуляции с битами я могу узнать общие имена.

Expectation

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

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

Очки

В моем подходе размер общих файлов 258KB (как я использовал имена групп и групповые ценности), и если она хранится имен в каждой строке его размер составляет 573KB. Эти файлы должны храниться на мобильном устройстве. Поэтому мне нужно уменьшить размер, насколько это возможно. Также я с нетерпением жду сжатия данных, и я не знаю, как это сделать. Пожалуйста, обратите внимание также на это.

Answer 1

Вы пробовали следующее?

1. Прочитайте имена 1 за раз из списка1, добавив их в хэшсет.
2. Прочитайте имена из списка2 по одному, просматривая их в hashset, созданном из списка. Если они находятся в hashset, это имя является общим для обоих файлов.

Если вы хотите предварительно обработать некоторую дополнительную скорость, сохраните # имен в каждом списке и выберите более короткий список как list1.

Answer 2

Вы пытаетесь переустановить набор со списком. Не делай этого. Используйте набор имен, который автоматически позаботится о дублированиях вставок.

Вам необходимо прочитать оба файла, это невозможно.

// in pseudo-java 
Set<String> names1 = new HashSet<String>(); 
for (String name : file1.getLine().trim()) { 
    names1.put(name); 
} 

Set<String> names2 = new HashSet<String>(); 
for (String name : file2.getLine().trim()) { 
    names2.put(name); 
} 

// with this line, names1 will discard any name not in names2 
names1.retainAll(names2); 

System.out.println(names1); 

Предполагая, что вы используете HashSet, как этот пример делает, вы будете сравнивать хэш струн, что позволит улучшить производительность резко.

Если вы обнаружите, что производительность недостаточна, затем начните искать более быстрые решения. Все остальное - это преждевременная оптимизация, и если вы не знаете, как быстро он должен работать, то это оптимизация без установки цели. Поиск «самого быстрого» решения требует перечислить и исчерпать каждый возможный решение, так как это решение вы еще не проверили может быть быстрее.

Answer 3

Я не уверен, понял ли я ваши требования и ситуацию.

У вас есть около 2.500 файлов, каждый из 3000 слов (или 400?). Существует много дубликатов слов, которые встречаются в нескольких файлах.

Теперь кто-нибудь спросит вас, какие слова имеют файл-345 и файл-765.

Вы можете создать Hashmap, в котором вы храните каждое слово, и список файлов, в котором происходят слова.

Если вы получаете файл 345 с его 3000 словами (400?), Вы просматриваете его в hashmap и видите, где в списке указан файл 765.

Однако 2 * 3000 не так много.Если я создаю 2 списков строк в Scala (который работает на JVM):

val g1 = (1 to 3000).map (x=> "" + r.nextInt (10000)) 
val g2 = (1 to 3000).map (x=> "" + r.nextInt (10000)) 

и построить пересечение

g1.intersect (g2) 

Я получаю результат (678 элементов) в почти нет времени на 8 летний ноутбук.

Итак, сколько запросов вы должны будете ответить? Как часто изменяется ввод файлов? Если редко, то чтение двух файлов может быть критической точкой.

Сколько уникальных слов у вас есть? Может быть, это не проблема, чтобы держать их всех в памяти.

Answer 4

Aha! Учитывая очень низкое требование к памяти, которое вы указали в редакции, есть еще одна вещь, которую вы могли бы сделать.

Хотя я все еще думаю, что вы могли бы найти решение, которое предлагают другие ответы. A HashSet с 3000 String записей не будет слишком большой. Мое быстрое приближение с 16-char Strings предлагает что-то ниже 400 kB памяти кучи. Попробуйте, затем вернитесь. Это похоже на 25 строк кода для всей программы.

---

Если решение ест слишком много памяти, то вы можете сделать это:

1. Сортировать имена в файлах. Это всегда хорошо.
2. Открыть оба файла.
3. Прочитайте строку из обоих файлов.
   1. Если line1 < line2, прочитайте строку от line1, повторите.
   2. Если line1 > line2, прочитайте строку от line2, повторите.
   3. Иначе они одинаковы, добавьте к результатам. Повторение.

Питается практически нет памяти, и это хорошее место, чтобы использовать метод compareTo() (если вы использовали его для сортировки имен, то есть) и switch заявление, я думаю.

Размер файлов вообще не влияет на использование памяти.

---

О сжатии данных - есть много инструментов и алгоритмов вы могли бы использовать, попробуйте this (посмотрите на смежные вопросы, тоже), или это this.