侧边栏壁纸
  • 累计撰写 62 篇文章
  • 累计创建 35 个标签
  • 累计收到 8 条评论

目 录CONTENT

文章目录

软件构造Lab3-Lab5有感

生榆
2019-06-12 / 0 评论 / 0 点赞 / 304 阅读 / 10669 字
温馨提示:
本文最后更新于 2022-12-14,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

记一次这三个实验给我的一点感受:有的问题可能不在算法上。

什么意思呢,意思是有的问题不要复杂化了,不必要使用什么高级的数据结构或者算法,从问题的开始找原因。

肯定很多同学没有绕这个弯路,因此我作此文意在分享我的一个经历。

问题的缘起

Lab3实验的一部分是读取SocialNetworkCircle(以下简称社交网络)文件并绘制,但是这个社交网络呢有两个特点,一是添加人物必须是成对出现的,也就是说需要以“添加关系”的形式添加人物,二是关系的起点必须已经在图中,不然这个关系就是非法的,因为第二个人无法计算他的level,即无法计算他应该出现在第几级的圈圈中。

那么问题来了,每次给出一对关系的时候,应该如何计算第二个人在图中的level?在Lab3中,我考虑使用广度优先搜索的策略寻找这个人应该在的level,因此设计了如下的addRelation()代码:

/**
 * addRelation() 的第一版.
 * add a relation between p1 and p2.
 * 
 * @param p1     person 1 as source of a relation
 * @param p2     person 2 as target of a relation
 * @param weight weight
 * @return true
 */
private boolean addRelation(SocialPerson p1, SocialPerson p2, double weight) {
    if (p1 == orbit.getCenterObject()) {
    		// if p1 is the center person
        if (!orbit.containsLevel(1)) orbit.addTrack(1, 1);
        orbit.addRelation(p2, weight);
        if (orbit.containsObject(p2)) {
            int level1 = orbit.getLevelByObject(p2);
            orbit.addRelation(p1, p2, weight);
            int level2 = calculateLevel(p2.getName());
            if (level2 < level1) {
                // 从旧的位置里移除,加到新的里
                changePosition(p2, new Position(level2, level2, Math.abs((int) (random.nextDouble() * 1767) % 360)));
            }
        } else {
            orbit.addToTrack(p2, 1, 1, Math.abs((int) (random.nextDouble() * 1767) % 360));
            nameMap.put(p2.getName(), p2);
        }
    } else if (orbit.containsObject(p1)) {
        if (orbit.containsObject(p2)) {
            // p1 and p2 both are in the orbit
            int level1 = orbit.getLevelByObject(p2);
            orbit.addRelation(p1, p2, weight);
            int level2 = calculateLevel(p2.getName());
            if (level2 < level1) {
                // 从旧的位置里移除,加到新的里
                changePosition(p2, new Position(level2, level2, Math.abs((int) (random.nextDouble() * 1767) % 360)));
            }
        } else {
            // p2 is firstly be added
            orbit.addRelation(p1, p2, weight);
            int level = calculateLevel(p2.getName());
            if (!orbit.containsLevel(level)) orbit.addTrack(level, level);
            orbit.addToTrack(p2, level, level, random.nextDouble() % 360);
            nameMap.put(p2.getName(), p2);
        }

    }
    return true;
}

这段代码逻辑上没有明显问题,但是实际运行起来效率非常低,使用JProfiler分析之后发现,大部分的时间都花在了calculateLevel()方法上,那么当时这个方法的实现方式又是怎样的呢?如下:

/**
 * calculate which level should the person with name be in.
 *
 * @param name the person's name you want to calculate the level
 * @return level if succeeded find the level, -1 if name does not exist
 */
public int calculateLevel(String name) {
    return orbit.getDistance(orbit.getCenterObject().getName(), name);
}

……所以还要看getDistance()的实现,如下:

public int getDistance(String name1, String name2) {
    Set<String> visitedSet = new HashSet<>();
    // 用列表模拟队列
    LinkedList<Record> queue = new LinkedList<>();
    Record r1 = new Record(name1);
    queue.addLast(r1);		// 队列
    // 广度优先搜索
    while (!queue.isEmpty()) {
        Record sourceRecord = queue.pollFirst();
        // 遍历当前出队顶点所有的邻接点
        assert sourceRecord != null;
        Set<String> visitingRow = this.targets(sourceRecord.getPerson()).keySet();
        for (String p : visitingRow) {
            // 只有在未访问时才进行访问操作
            if (!visitedSet.contains(p)) {
                visitedSet.add(p);      // 标记已访问
                // 因为是第一次访问,所以队列中一定没有这个person,新建一个record对象,并设置距离,然后进队
                Record newVisited = new Record(p, sourceRecord.getDistance() + 1);
                queue.addLast(newVisited);
                if (name2.equals(p)) {
                		// 这个distance就是我们要找的距离,也就是level
                    return newVisited.getDistance();
                }
            }
        }
    }
    return -1;
}

可以将这段代码理解成在邻接表上进行的广度优先搜索,这个搜索方法中间有一个步骤,是获得与某一个节点相连的所有节点,在这段代码中就是调用的targets()方法。

不幸的是,在当时的targets()实现中,存在一个巨大的问题,它需要便利每一对关系,也就是在 $O(n)$ 时间内在能完成,更致命的是,关系在不断变多,这个方法花费的时间更是以肉眼可见的速度上涨,再结合上其他操作,这个getDistance()就成了影响程序性能最致命的因素。因此,计算Medium文件需要耗时约4分钟,Larger半个小时都计算不出来。经过我的不准确的测试,平均5秒钟能计算的关系对数不超过1000。

第一次改进

在Lab4中,我偶然发现了targets()方法是多么辣鸡,所以尝试去改进,于是我修改了曾经存储关系的数据结构,从原来的

private Set<ConcreteRelation<E, E>> relations = new HashSet<>();

修改成了

private Map<String, Map<String, Double>> relationMap = new HashMap<>();

(当然还有一些细节上的改进,在此不去赘述。)

这么一修改,targets()方法仅仅需要使用relationMap.get()方法就可以实现原来的所有功能,此时只需要 $O(1)$ 即可完成。在保证calculateLevel()方法相关的其他结构基本不变时,读取并计算同样的Medium文件只需要1秒左右,读取并计算Larger文件仅需要4秒左右,极大地提高了速度。

当然这么还没完,不然怎么对得起我最开头说到的“问题不在算法上”?

第二次改进

在写Lab5的时候,我左思右想,到底要怎么改进广度优先搜索的速度呢……谁知我再一次英语课上一拍脑袋意识到:为什么非要广度优先去计算level???

下面为了方便表述,作几个简单的说法上的统一:社交网络中的关系由source(起点)、target(终点)、weight(权重)组成

上面已经提到了,文件什么情况下存在不合法的关系,所以我们要利用文件的合法性啊!它每一行的关系都是预先设计好了的,也就是说每一行的关系都必须保证一点:第一个人已经在图中。所以这个图是一点一点延伸起来的,所以!我们压根不需要用什么广度优先去计算level!只需要用关系起点在图中的level就够了!

举个例子:

SocialTie ::= <TommyWong, LisaWong, 0.98>
SocialTie ::= <TommyWong, TomWong, 0.2>
SocialTie ::= <TomWong, FrankLee, 0.71>
SocialTie ::= <FrankLee, DavidChen, 0.02>
SocialTie ::= <TommyWong, DavidChen, 0.342>

对于这样的几对关系,因为TommyWong是中心人物,在社交网络中,他的level是0,所以在添加LisaWong时,可以立即知道她的level是1,TomWong同样;

我们看第三条关系,添加FrankLee时,因为已经知道TomWonglevel是1,所以FrankLeelevel必定是2,只需要在关系起点的level上+1就够了。

同理,在添加第4条关系的时候,可以知道DavidChenlevel是3,但是添加第5条关系的时候,发现DavidChenlevel应该是1,小于之前的3,所以需要进行修改。

经过这么一个思路下来,计算每一个level都只需要在 $O(1)$ 的时间内完成,修改后的addRelation()如下:

/**
 * add a relation between p1 and p2.
 *
 * @param p1     person 1 as source of a relation
 * @param p2     person 2 as target of a relation
 * @param weight weight
 * @return true
 * @throws ObjectNotExistException throws when p1 or p2 is not in the orbit
 */
public boolean addRelation(final SocialPerson p1,
                           final SocialPerson p2,
                           final double weight)
        throws ObjectNotExistException {
    if (p1 == orbit.getCenterObject()) {
        // p1 is center
        if (!orbit.containsLevel(1)) {      // make sure level 1 is in the orbit
            try {
                orbit.addTrack(1, 1);
            } catch (TrackDidExistException e) {
                e.printStackTrace();
                log.info("已存在" + 1 + "号轨道");
            }
        }
        if (orbit.containsObject(p2)) {
            // p1是中心,p2已存在
            int level1 = orbit.getLevelByObject(p2);
            orbit.addRelationWithCenter(p2, weight);
            if (level1 != 1) {
                // 从旧的位置里移除,加到新的里
                changePosition(p2, new Position(1, 1, Math.abs((random.nextInt() * 1767) % 360)));
            }
        } else {
            // p1是中心,p2不存在
            try {
                // 先添加p2这个人
                orbit.addToTrack(p2,
                        1,
                        1,
                        Math.abs((random.nextInt() * 1767) % 360));
                nameMap.put(p2.getName(), p2);
            } catch (NoSuchLevelOfTrackException e) {
                e.printStackTrace();
                log.error("仍然尝试向不存在的轨道添加物体");
                assert false;
            }
        }
        // add relation with center
        // 现在p2一定存在
        orbit.addRelationWithCenter(p2, weight);
    } else if (orbit.containsObject(p1)) {
        // 轨道里有p1
        if (orbit.containsObject(p2)) {
            // p1 and p2 both are in the orbit
            int level1 = orbit.getLevelByObject(p2);
            orbit.addRelation(p1, p2, weight);
            int level2 = orbit.getLevelByObject(p1) + 1;
            if (level2 < level1) {

                // 从旧的位置里移除,加到新的里
                changePosition(p2,
                        new Position(level2,
                                level2,
                                Math.abs((random.nextInt() * 1767) % 360)));
            }
        } else {
            // p2 is firstly be added
            try {
                int level2 = orbit.getLevelByObject(p1) + 1;
                if (!orbit.containsLevel(level2)) {
                    orbit.addTrack(level2, level2);
                }
                orbit.addToTrack(p2, level2, 1, 1);
                nameMap.put(p2.getName(), p2);
                orbit.addRelation(p1, p2, weight);
            } catch (NoSuchLevelOfTrackException e) {
                log.info("Dealing with NoSuchLevelOfTrackException...");
                if (!orbit.containsLevel(1)) {
                    log.info("Auto add level 1");
                    try {
                        orbit.addTrack(1, 1);
                        log.info("Successfully auto added track 1");
                    } catch (TrackDidExistException ignored) {
                    }
                }
            } catch (TrackDidExistException ignored) {
            }
        }
    } else {
        // 轨道里没p1
        throw new PersonNotExistException("名称为" + p1.getName() + "的人物不存在,因其作为起点,所以不能添加关系");
    }
    return true;
}

(这段代码还包含了Lab5中添加的异常机制)

所以最后的效果如何呢,计算Medium的速度已经超级超级快了(忘记具体多少了),计算Larger需要约0.1秒,计算Lab5提供的超大文件仅需要1秒!

0

评论区