Как эффективно группировать строки?
1,00
р.
Нужное решить такую задачу:
Разбить множество уникальных строк на непересекающиеся группы по следующему критерию: Если две строчки имеют совпадения непустых значений в одной или более колонках, они принадлежат одной группе. Например, строчки 111 123 222 200 123 100 300 100
все принадлежат одной группе, так как первые две строчки имеют одинаковое значение 123 во второй колонке, а две последние одинаковое значение 100 в третьей колонке
Также есть ограничение на время работы программы (30 секунд). Также могу добавить количество строк - около миллиона. Вот мой код:
private static Set> findLineGroups(List lines) { Set> resultSet = new TreeSet<>((Comparator>) (trSet1, trSet2) -> { int diff = trSet2.size() - trSet1.size() if (diff != 0) return diff
Iterator iterator1 = trSet1.iterator() Iterator iterator2 = trSet2.iterator() while (iterator1.hasNext()) { diff = iterator1.next() - iterator2.next() if (diff != 0) return diff }
return 0 })
Map termLineGroupsPairs = new HashMap<>() List> lineNumGroups = new ArrayList<>()
for (int lineNum = 0 lineNum < lines.size() lineNum++) { String line = lines.get(lineNum) String[] lineElements = line.replaceAll("\"", "").replaceAll(" ", "").split(" ") Set termSet = new HashSet<>(Arrays.asList(lineElements)) termSet.remove("")
Integer groupNum = null TreeSet tempSet = new TreeSet<>(termLineGroupsPairs.keySet()) tempSet.retainAll(termSet) //оставляем только общие элементы if (!tempSet.isEmpty()) { String term = tempSet.first() groupNum = termLineGroupsPairs.get(term) lineNumGroups.get(groupNum).add(lineNum) }
if (groupNum == null) { TreeSet group = new TreeSet<>() group.add(lineNum) lineNumGroups.add(group) groupNum = lineNumGroups.size() - 1 } for (String term : termSet) { termLineGroupsPairs.put(term, groupNum) } if (lineNumGroups.size() % 1000 == 0) System.out.println(lineNumGroups.size()) }
resultSet.addAll(lineNumGroups) return resultSet }
И все мои решения работают слишком долго (а пробовал по-разному решать эту задачу). Правда, если строк меньше тысячи, то работает быстро (укладываюсь в указанное ограничение), и практически с любым моим алгоритмом.
Прошу подсказать, как можно решить эту задачку (или что изменить в моём решении, чтобы работало быстро).
Ответ
К какому решению "почти в лоб" я пришел:
храним результат в виде списка списков: [номер_группы -> [строки_группы]] используем вспомогательный список хэш-таблиц: [позиция_слова -> { слово -> номер_группы }] и вспомогательную хэш-таблицу для хранения какая группа в какую была влита каждую строку разбиваем на слова каждое слово строки ищем в соответствующей (позиции слова в строке) хэш-таблице
если слово есть, запоминаем номер группы (значение из хэш-таблицы), в которой оно найдено если слова нет, то добавляем его в список новых слов
если строка (а точнее её слова) найдена в группах, то берём первую из "живых" (объяснение этого позже) групп, иначе создаём новую группу добавляем новые слова в соответствующие хэш-таблицы с номером найденной/созданной группы объединяем найденные группы в одну, выбранную ранее. Так как группы хранятся в виде списка строк, то просто объединяем списки строк в один у выбранной группы, а более ненужные группы отмечаем как "мёртвые" (присваиваем null, дабы не перемещать элементы внутри списка) добавляем строку в список строк группы
Кода выходит ещё больше, чем слов:
//вспомогательный класс для добавления новых слов private static class NewWord { public String value public int position
public NewWord(String value, int position) { this.value = value this.position = position } }
private static List> findGroups(List lines) { List> wordsToGroupsNumbers = new ArrayList<>() //[позиция_слова:{слово:номер_группы}] List> linesGroups = new ArrayList<>() //[номер_группы:[строки_группы]] Map mergedGroupNumberToFinalGroupNumber = new HashMap<>() //{номер_слитой_группы:номер_группы_в_которую_слили} for (String line : lines) { String[] words = line.split(" ") TreeSet foundInGroups = new TreeSet<>() List newWords = new ArrayList<>() for (int i = 0 i < words.length i++) { String word = words[i]
if (wordsToGroupsNumbers.size() == i) wordsToGroupsNumbers.add(new HashMap<>())
if (word.equals("")) continue
Map wordToGroupNumber = wordsToGroupsNumbers.get(i) Integer wordGroupNumber = wordToGroupNumber.get(word) if (wordGroupNumber != null) { while (mergedGroupNumberToFinalGroupNumber.containsKey(wordGroupNumber)) wordGroupNumber = mergedGroupNumberToFinalGroupNumber.get(wordGroupNumber) foundInGroups.add(wordGroupNumber) } else { newWords.add(new NewWord(word, i)) } } int groupNumber if (foundInGroups.isEmpty()) { groupNumber = linesGroups.size() linesGroups.add(new ArrayList<>()) } else { groupNumber = foundInGroups.first() } for (NewWord newWord : newWords) { wordsToGroupsNumbers.get(newWord.position).put(newWord.value, groupNumber) } for (int mergeGroupNumber : foundInGroups) { if (mergeGroupNumber != groupNumber) { mergedGroupNumberToFinalGroupNumber.put(mergeGroupNumber, groupNumber) linesGroups.get(groupNumber).addAll(linesGroups.get(mergeGroupNumber)) linesGroups.set(mergeGroupNumber, null) } } linesGroups.get(groupNumber).add(line) } linesGroups.removeAll(Collections.singleton(null)) return linesGroups }
Возможно, у меня слишком быстрый для тестирования скорости работы "как им надо" компьютер, но для миллиона строк, каждая из которых состоит из 5 слов, каждое из которых, в свою очередь, состоит из 5 строчных букв английского алфавита, время выполнения составляет примерно 4 секунды.
Разбить множество уникальных строк на непересекающиеся группы по следующему критерию: Если две строчки имеют совпадения непустых значений в одной или более колонках, они принадлежат одной группе. Например, строчки 111 123 222 200 123 100 300 100
все принадлежат одной группе, так как первые две строчки имеют одинаковое значение 123 во второй колонке, а две последние одинаковое значение 100 в третьей колонке
Также есть ограничение на время работы программы (30 секунд). Также могу добавить количество строк - около миллиона. Вот мой код:
private static Set> findLineGroups(List lines) { Set> resultSet = new TreeSet<>((Comparator>) (trSet1, trSet2) -> { int diff = trSet2.size() - trSet1.size() if (diff != 0) return diff
Iterator iterator1 = trSet1.iterator() Iterator iterator2 = trSet2.iterator() while (iterator1.hasNext()) { diff = iterator1.next() - iterator2.next() if (diff != 0) return diff }
return 0 })
Map termLineGroupsPairs = new HashMap<>() List> lineNumGroups = new ArrayList<>()
for (int lineNum = 0 lineNum < lines.size() lineNum++) { String line = lines.get(lineNum) String[] lineElements = line.replaceAll("\"", "").replaceAll(" ", "").split(" ") Set termSet = new HashSet<>(Arrays.asList(lineElements)) termSet.remove("")
Integer groupNum = null TreeSet tempSet = new TreeSet<>(termLineGroupsPairs.keySet()) tempSet.retainAll(termSet) //оставляем только общие элементы if (!tempSet.isEmpty()) { String term = tempSet.first() groupNum = termLineGroupsPairs.get(term) lineNumGroups.get(groupNum).add(lineNum) }
if (groupNum == null) { TreeSet group = new TreeSet<>() group.add(lineNum) lineNumGroups.add(group) groupNum = lineNumGroups.size() - 1 } for (String term : termSet) { termLineGroupsPairs.put(term, groupNum) } if (lineNumGroups.size() % 1000 == 0) System.out.println(lineNumGroups.size()) }
resultSet.addAll(lineNumGroups) return resultSet }
И все мои решения работают слишком долго (а пробовал по-разному решать эту задачу). Правда, если строк меньше тысячи, то работает быстро (укладываюсь в указанное ограничение), и практически с любым моим алгоритмом.
Прошу подсказать, как можно решить эту задачку (или что изменить в моём решении, чтобы работало быстро).
Ответ
К какому решению "почти в лоб" я пришел:
храним результат в виде списка списков: [номер_группы -> [строки_группы]] используем вспомогательный список хэш-таблиц: [позиция_слова -> { слово -> номер_группы }] и вспомогательную хэш-таблицу для хранения какая группа в какую была влита каждую строку разбиваем на слова каждое слово строки ищем в соответствующей (позиции слова в строке) хэш-таблице
если слово есть, запоминаем номер группы (значение из хэш-таблицы), в которой оно найдено если слова нет, то добавляем его в список новых слов
если строка (а точнее её слова) найдена в группах, то берём первую из "живых" (объяснение этого позже) групп, иначе создаём новую группу добавляем новые слова в соответствующие хэш-таблицы с номером найденной/созданной группы объединяем найденные группы в одну, выбранную ранее. Так как группы хранятся в виде списка строк, то просто объединяем списки строк в один у выбранной группы, а более ненужные группы отмечаем как "мёртвые" (присваиваем null, дабы не перемещать элементы внутри списка) добавляем строку в список строк группы
Кода выходит ещё больше, чем слов:
//вспомогательный класс для добавления новых слов private static class NewWord { public String value public int position
public NewWord(String value, int position) { this.value = value this.position = position } }
private static List> findGroups(List lines) { List> wordsToGroupsNumbers = new ArrayList<>() //[позиция_слова:{слово:номер_группы}] List> linesGroups = new ArrayList<>() //[номер_группы:[строки_группы]] Map mergedGroupNumberToFinalGroupNumber = new HashMap<>() //{номер_слитой_группы:номер_группы_в_которую_слили} for (String line : lines) { String[] words = line.split(" ") TreeSet foundInGroups = new TreeSet<>() List newWords = new ArrayList<>() for (int i = 0 i < words.length i++) { String word = words[i]
if (wordsToGroupsNumbers.size() == i) wordsToGroupsNumbers.add(new HashMap<>())
if (word.equals("")) continue
Map wordToGroupNumber = wordsToGroupsNumbers.get(i) Integer wordGroupNumber = wordToGroupNumber.get(word) if (wordGroupNumber != null) { while (mergedGroupNumberToFinalGroupNumber.containsKey(wordGroupNumber)) wordGroupNumber = mergedGroupNumberToFinalGroupNumber.get(wordGroupNumber) foundInGroups.add(wordGroupNumber) } else { newWords.add(new NewWord(word, i)) } } int groupNumber if (foundInGroups.isEmpty()) { groupNumber = linesGroups.size() linesGroups.add(new ArrayList<>()) } else { groupNumber = foundInGroups.first() } for (NewWord newWord : newWords) { wordsToGroupsNumbers.get(newWord.position).put(newWord.value, groupNumber) } for (int mergeGroupNumber : foundInGroups) { if (mergeGroupNumber != groupNumber) { mergedGroupNumberToFinalGroupNumber.put(mergeGroupNumber, groupNumber) linesGroups.get(groupNumber).addAll(linesGroups.get(mergeGroupNumber)) linesGroups.set(mergeGroupNumber, null) } } linesGroups.get(groupNumber).add(line) } linesGroups.removeAll(Collections.singleton(null)) return linesGroups }
Возможно, у меня слишком быстрый для тестирования скорости работы "как им надо" компьютер, но для миллиона строк, каждая из которых состоит из 5 слов, каждое из которых, в свою очередь, состоит из 5 строчных букв английского алфавита, время выполнения составляет примерно 4 секунды.
