主页 / 问题 / 816854
Accepted
Max Lich
Asked:2020-04-20 18:42:38 +0000 UTC2020-04-20 18:42:38 +0000 UTC

如何有效地对行进行分组？

  • 772

需要解决以下问题：

根据以下标准将唯一字符串集拆分为不重叠的组：

如果两行在一列或多列中有匹配的非空值，则它们属于同一组。

例如，线条

111;123;222
200;123;100
300;;100

都属于同一个组，因为前两行在第二列中具有相同的值，而后两行在第三列中123具有相同的值100

程序运行时间（30 秒）也有限制。我还可以添加行数——大约一百万。这是我的代码：

private static Set<TreeSet<Integer>> findLineGroups(List<String> lines) {
    Set<TreeSet<Integer>> resultSet = new TreeSet<>((Comparator<TreeSet<Integer>>) (trSet1, trSet2) -> {
        int diff = trSet2.size() - trSet1.size();
        if (diff != 0)
            return diff;

        Iterator<Integer> iterator1 = trSet1.iterator();
        Iterator<Integer> iterator2 = trSet2.iterator();
        while (iterator1.hasNext()) {
            diff = iterator1.next() - iterator2.next();
            if (diff != 0)
                return diff;
        }

        return 0;
    });

    Map<String, Integer> termLineGroupsPairs = new HashMap<>();
    List<TreeSet<Integer>> lineNumGroups = new ArrayList<>();

    for (int lineNum = 0; lineNum < lines.size(); lineNum++) {
        String line = lines.get(lineNum);
        String[] lineElements = line.replaceAll("\"", "").replaceAll(" ", "").split(";");
        Set<String> termSet = new HashSet<>(Arrays.asList(lineElements));
        termSet.remove("");

        Integer groupNum = null;
        TreeSet<String> 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<Integer> 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;
}

而且我所有的解决方案都工作太久（我试图以不同的方式解决这个问题）。诚然，如果少于一千行，那么它可以快速运行（我符合指定的限制），并且几乎可以使用我的任何算法。

请告诉我如何解决这个问题（或在我的解决方案中进行哪些更改以使其快速运行）。

java

2 个回答

  1. Best Answer

    我得出了“几乎在额头上”的解决方案：

    • 将结果存储为列表列表：[номер_группы -> [строки_группы]]
    • 使用哈希表的辅助列表：[позиция_слова -> { слово -> номер_группы }]
    • 和一个辅助哈希表，用于存储哪个组被合并到哪个组中
    • 将每一行分成单词
    • 在对应的（字符串中单词的位置）哈希表中搜索字符串的每个单词
      • 如果有单词，请记住在其中找到它的组的编号（来自哈希表的值）
      • 如果没有单词，则将其添加到新单词列表中
    • 如果在组中找到字符串（或者更确切地说是它的单词），那么我们采用第一个“实时”（稍后解释）组，否则我们创建一个新组
    • 使用找到/创建的组的编号将新词添加到相应的哈希表中
    • 将找到的组合并为一个，之前选择。由于组存储为字符串列表，因此我们只需将字符串列表组合为所选组的一个，并将更多不必要的组标记为“死”（指定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<List<String>> findGroups(List<String> lines)
{
    List<Map<String, Integer>> wordsToGroupsNumbers = new ArrayList<>(); //[позиция_слова:{слово:номер_группы}]
    List<List<String>> linesGroups = new ArrayList<>(); //[номер_группы:[строки_группы]]
    Map<Integer, Integer> mergedGroupNumberToFinalGroupNumber = new HashMap<>(); //{номер_слитой_группы:номер_группы_в_которую_слили}
    for (String line : lines)
    {
        String[] words = line.split(";");
        TreeSet<Integer> foundInGroups = new TreeSet<>();
        List<NewWord> 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<String, Integer> 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 秒。

    • 6

  2. 有这样一个数据结构——不相交集的森林（disjoint sets union）。它的排列非常简单，并且可以让您快速组合相关元素。

    在这种情况下，如果我们忽略关于需要匹配列号的语句，则每个集合（组）必须包含类型为 123 等元素的哈希表（映射）。

    每个新行都被划分为元素，并检查这些元素在现有组中的存在。
    - 如果没有元素匹配，则创建一个新组。
    - 如果有一个匹配，则将该行添加到该组中。
    - 如果有两个或更多 - 线用作连接组的链接 - 它们被组合，并且线被添加到组合组中。

    在考虑列数的情况下，设定最大列数对应的map数，在每个map中进行搜索。

    • 4

相关问题