• 实用小算法


    开头提醒:

    打开自己本地任意一个SpringBoot项目,复制代码到test包下跟着敲。

    后面几篇文章不再提醒,希望大家养成习惯。看10篇文章,不如自己动手做一次。

    我们不执着于一天看多少篇,但求把每一篇都搞懂,慢就是快。

    给大家分享一个非常、非常、非常实用的小算法。严格意义上,它不是一个算法,而是一种编码技巧。但其中涉及的思想层面的东西是共通的,如果能熟练掌握它,在某些场景下将大幅提升我们程序的执行效率。

    这个算法能解决什么问题呢?它主要处理两个数据集合的匹配问题。

    比如,现在有两个数据集合:

    1. public class Demo {
    2. public static void main(String[] args) {
    3. // 老公组
    4. List<Couple> husbands = new ArrayList<>();
    5. husbands.add(new Couple(1, "梁山伯"));
    6. husbands.add(new Couple(2, "牛郎"));
    7. husbands.add(new Couple(3, "干将"));
    8. husbands.add(new Couple(4, "工藤新一"));
    9. husbands.add(new Couple(5, "罗密欧"));
    10. // 老婆组
    11. List<Couple> wives = new ArrayList<>();
    12. wives.add(new Couple(1, "祝英台"));
    13. wives.add(new Couple(2, "织女"));
    14. wives.add(new Couple(3, "莫邪"));
    15. wives.add(new Couple(4, "毛利兰"));
    16. wives.add(new Couple(5, "朱丽叶"));
    17. }
    18. }
    19. @Data
    20. @AllArgsConstructor
    21. class Couple{
    22. private Integer familyId;
    23. private String userName;
    24. }

    要求对数据进行处理,最终输出:

    梁山伯爱祝英台

    牛郎爱织女

    干将爱莫邪

    工藤新一爱毛利兰

    罗密欧爱朱丽叶

    第一版算法

    优秀的代码都不是一蹴而就的,需要不断地优化和重构。所以一开始我们不要想太多,先把需求完成了再说:

    1. public static void main(String[] args) {
    2. // 用于计算循环次数
    3. int count = 0;
    4. // 老公组
    5. List<Couple> husbands = new ArrayList<>();
    6. husbands.add(new Couple(1, "梁山伯"));
    7. husbands.add(new Couple(2, "牛郎"));
    8. husbands.add(new Couple(3, "干将"));
    9. husbands.add(new Couple(4, "工藤新一"));
    10. husbands.add(new Couple(5, "罗密欧"));
    11. // 老婆组
    12. List<Couple> wives = new ArrayList<>();
    13. wives.add(new Couple(1, "祝英台"));
    14. wives.add(new Couple(2, "织女"));
    15. wives.add(new Couple(3, "莫邪"));
    16. wives.add(new Couple(4, "毛利兰"));
    17. wives.add(new Couple(5, "朱丽叶"));
    18. for (Couple husband : husbands) {
    19. for (Couple wife : wives) {
    20. // 记录循环的次数
    21. count++;
    22. if (husband.getFamilyId().equals(wife.getFamilyId())) {
    23. System.out.println(husband.getUserName() + "爱" + wife.getUserName());
    24. }
    25. }
    26. }
    27. System.out.println("----------------------");
    28. System.out.println("循环了:" + count + "次");
    29. }

    输出结果

    梁山伯爱祝英台

    牛郎爱织女

    干将爱莫邪

    工藤新一爱毛利兰

    罗密欧爱朱丽叶

    ----------------------

    循环了:25次

    总结一下第一版算法的优缺点。

    • 优点:代码逻辑非常直观,外层for遍历husband,内层for根据husband的familyId匹配到wife
    • 缺点:循环次数过多

    当前数据量较小,可能看不出明显差距。实际上这是非常糟糕的一种算法。

    想象一下,如果现在男女cp各1000人,那么全部匹配需要1000*1000 = 100w次循环。

    如何改进?

    我们要明确,在当前这个需求中,每位男嘉宾只能选一位女嘉宾。比如当外层for刚好轮到牛郎时,内层for需要遍历wives找出织女。一旦牛郎和织女牵手成功,其实就没必要继续往下遍历wives了,遍历完了又如何呢,反正只能带走织女。所以明智的做法是,牛郎匹配到织女后,就赶紧下去,换干将上场。

    后面的三次其实是没必要的

    第二版算法

    1. public static void main(String[] args) {
    2. // 用于计算循环次数
    3. int count = 0;
    4. // 老公组
    5. List<Couple> husbands = new ArrayList<>();
    6. husbands.add(new Couple(1, "梁山伯"));
    7. husbands.add(new Couple(2, "牛郎"));
    8. husbands.add(new Couple(3, "干将"));
    9. husbands.add(new Couple(4, "工藤新一"));
    10. husbands.add(new Couple(5, "罗密欧"));
    11. // 老婆组
    12. List<Couple> wives = new ArrayList<>();
    13. wives.add(new Couple(1, "祝英台"));
    14. wives.add(new Couple(2, "织女"));
    15. wives.add(new Couple(3, "莫邪"));
    16. wives.add(new Couple(4, "毛利兰"));
    17. wives.add(new Couple(5, "朱丽叶"));
    18. for (Couple husband : husbands) {
    19. for (Couple wife : wives) {
    20. // 记录循环的次数
    21. count++;
    22. if (husband.getFamilyId().equals(wife.getFamilyId())) {
    23. System.out.println(husband.getUserName() + "爱" + wife.getUserName());
    24. // 牵手成功,换下一位男嘉宾
    25. break;
    26. }
    27. }
    28. }
    29. System.out.println("----------------------");
    30. System.out.println("循环了:" + count + "次");
    31. }

    输出结果:

    梁山伯爱祝英台

    牛郎爱织女

    干将爱莫邪

    工藤新一爱毛利兰

    罗密欧爱朱丽叶

    ----------------------

    循环了:15次

    我们发现,循环次数从第一版的25次减少到了15次,区别仅仅是增加了一个break:一旦牵手成功,就换下一位男嘉宾。

    break:跳出当前循环(女嘉宾for循环),但不会跳出男嘉宾的for循环。

    总结一下第二版算法的优缺点。

    • 优点:执行效率比第一版高
    • 缺点:理解难度稍微提升了一些

    这是最终版了吗?不,远远不够。

    哈?还能优化吗?

    问大家一个问题:

    看过《非诚勿扰》吗?一位男嘉宾和一位女嘉宾牵手成功后,这位女嘉宾就要离开舞台了,对吧?

    对呀?怎么了?

    请你重新看看我们的第二版代码,你会发现即使牛郎和织女牵手成功了,下一位男嘉宾(干将)入场时还是会在循环中碰到织女。织女在上一轮循环中,已经确定和牛郎在一起了,本次干将再去遍历织女是没有意义的。

    在前两轮中,梁山伯、牛郎已经确定牵手祝英台、织女,应该把她们两个从舞台请下去

    第三版算法

    1. public static void main(String[] args) {
    2. // 用于计算循环次数
    3. int count = 0;
    4. // 老公组
    5. List<Couple> husbands = new ArrayList<>();
    6. husbands.add(new Couple(1, "梁山伯"));
    7. husbands.add(new Couple(2, "牛郎"));
    8. husbands.add(new Couple(3, "干将"));
    9. husbands.add(new Couple(4, "工藤新一"));
    10. husbands.add(new Couple(5, "罗密欧"));
    11. // 老婆组
    12. List<Couple> wives = new ArrayList<>();
    13. wives.add(new Couple(1, "祝英台"));
    14. wives.add(new Couple(2, "织女"));
    15. wives.add(new Couple(3, "莫邪"));
    16. wives.add(new Couple(4, "毛利兰"));
    17. wives.add(new Couple(5, "朱丽叶"));
    18. for (Couple husband : husbands) {
    19. for (Couple wife : wives) {
    20. // 记录循环的次数
    21. count++;
    22. if (husband.getFamilyId().equals(wife.getFamilyId())) {
    23. System.out.println(husband.getUserName() + "爱" + wife.getUserName());
    24. // 牵手成功,把女嘉宾从舞台请下来,同时换下一位男嘉宾上场
    25. wives.remove(wife);
    26. break;
    27. }
    28. }
    29. }
    30. System.out.println("----------------------");
    31. System.out.println("循环了:" + count + "次");
    32. }

    输出结果:

    梁山伯爱祝英台

    牛郎爱织女

    干将爱莫邪

    工藤新一爱毛利兰

    罗密欧爱朱丽叶

    ----------------------

    循环了:5次

    我们发现,循环次数从第二版的15次减少到了5次,因为牵手成功的女嘉宾都被请下舞台了:wives.remove(wife)。

    如果说,第二版算法是打断wives的循环,那么第三版算法则是直接把wives请出场外。

    总结一下第三版算法的优缺点。

    • 优点:执行效率比第二版高了不少
    • 缺点:理解难度稍微提升了一些,平均性能不高

    我靠,这还有缺点啊?太牛逼了好吗,我都想不到。什么叫“平均性能不高”?

    比如我现在把男嘉宾的出场顺序倒过来:

    1. public static void main(String[] args) {
    2. // 用于计算循环次数
    3. int count = 0;
    4. // 老公组,原先梁山伯第一个出场,现在换罗密欧第一个
    5. List<Couple> husbands = new ArrayList<>();
    6. husbands.add(new Couple(5, "罗密欧"));
    7. husbands.add(new Couple(4, "工藤新一"));
    8. husbands.add(new Couple(3, "干将"));
    9. husbands.add(new Couple(2, "牛郎"));
    10. husbands.add(new Couple(1, "梁山伯"));
    11. // 老婆组
    12. List<Couple> wives = new ArrayList<>();
    13. wives.add(new Couple(1, "祝英台"));
    14. wives.add(new Couple(2, "织女"));
    15. wives.add(new Couple(3, "莫邪"));
    16. wives.add(new Couple(4, "毛利兰"));
    17. wives.add(new Couple(5, "朱丽叶"));
    18. for (Couple husband : husbands) {
    19. for (Couple wife : wives) {
    20. // 记录循环的次数
    21. count++;
    22. if (husband.getFamilyId().equals(wife.getFamilyId())) {
    23. System.out.println(husband.getUserName() + "爱" + wife.getUserName());
    24. // 牵手成功,把女嘉宾从舞台请下来,同时换下一位男嘉宾上场
    25. wives.remove(wife);
    26. break;
    27. }
    28. }
    29. }
    30. System.out.println("----------------------");
    31. System.out.println("循环了:" + count + "次");
    32. }

    输出结果

    罗密欧爱朱丽叶

    工藤新一爱毛利兰

    干将爱莫邪

    牛郎爱织女

    梁山伯爱祝英台

    ----------------------

    循环了:15次

    循环次数从5次变成15次,和第二版算法是一样的。

    这是怎么回事呢?

    第一次是顺序遍历的:

    第一位男嘉宾梁山伯上场:遇到第一位女嘉宾祝英台,直接牵手成功。

    第二位男嘉宾牛郎上来了,此时祝英台不在了,他遇到的第一位女嘉宾是织女,也直接牵手成功。

    第三位男嘉宾干将上场后一看,这不是莫邪吗,也牵手成功走了。

    ...

    但是颠倒顺序后:

    之前顺着来的时候,梁山伯带走了祝英台,牛郎出场就直接跳过祝英台了,这就是上一次循环对下一次循环的影响。

    而这次,罗密欧错了4次以后终于带走了朱丽叶,但是工藤新一上场后,还是要试错3次才能找到毛利兰。提前离场的朱丽叶在毛利兰后面,所以罗密欧试错积累的优势无法传递给下一次循环。

    对于某些算法而言,元素的排列顺序会改变算法的复杂度。在数据结构与算法中,对一个算法往往有三个衡量维度:

    • 最好复杂度
    • 平均复杂度
    • 最坏复杂度

    现实生活中,我们往往需要结合实际业务场景与算法复杂度挑选出合适的算法。

    在本案例中,第三版算法在男嘉宾顺序时可以得到最好的结果(5次),如果倒序则得到最差的结果(15次)。

    第四版算法

    终于要向大家介绍第四种算法了。

    第四种算法是一种复杂度一致的算法,无论男嘉宾的出场顺序如何改变,效率始终如一。

    这是一种怎么样的算法呢?

    不急,我们先思考一个问题:

    我们为什么要用for遍历?

    咋一听,好像有点莫名其妙。不用for循环,我怎么遍历啊?

    其实无论何时,使用for都意味着我们潜意识里已经把数据泛化,牺牲数据的特性转而谋求统一的操作方式。想象一下,假设一个数组存了国家男子田径队的队员们,比如110米栏的刘翔、100米项目的苏炳添和谢震业。你如果写一个for循环:

    1. for(sportsMan : sportsMen){
    2. sportsMan.kualan();
    3. }

    在循环中,你只能调用运动员身上的一项技能执行。

    • 你选跨栏吧,苏炳添和谢震业不会啊...
    • 你选100米短跑吧,刘翔肯定比不过专业短跑运动员啊...

    所以,绝大多数情况下,for循环意味着抽取共同特性,忽略个体差异。好处是代码通用,坏处是无法发挥个体优势,最终影响效率。

    回到案例中来。

    每次男嘉宾上场后,他都要循环遍历女嘉宾,挨个问过去:你爱我吗?

    哦,不爱。我问问下一位女嘉宾。

    他为什么要挨个问?因为“女人心海底针”,他根本不知道哪位女嘉宾是爱他的,所以场上女嘉宾对他来说就是无差异的“黑盒”。

    如果我们给场上的女嘉宾每人发一个牌子,让他们在上面写上自己喜欢的男嘉宾号码,那么男嘉宾上场后就不用挨个问了,直接找到写有自己号码的女嘉宾即可牵手成功。

    这个算法的思想其实就是让数据产生差异化,外部通过差异快速定位目标数据。

    1. public static void main(String[] args) {
    2. // 用于计算循环次数
    3. int count = 0;
    4. // 老公组
    5. List<Couple> husbands = new ArrayList<>();
    6. husbands.add(new Couple(1, "梁山伯"));
    7. husbands.add(new Couple(2, "牛郎"));
    8. husbands.add(new Couple(3, "干将"));
    9. husbands.add(new Couple(4, "工藤新一"));
    10. husbands.add(new Couple(5, "罗密欧"));
    11. // 老婆组
    12. List<Couple> wives = new ArrayList<>();
    13. wives.add(new Couple(1, "祝英台"));
    14. wives.add(new Couple(2, "织女"));
    15. wives.add(new Couple(3, "莫邪"));
    16. wives.add(new Couple(4, "毛利兰"));
    17. wives.add(new Couple(5, "朱丽叶"));
    18. // 给女嘉宾发牌子
    19. Map<Integer, Couple> wivesMap = new HashMap<>();
    20. for (Couple wife : wives) {
    21. // 女嘉宾现在不在List里了,而是去了wivesMap中,前面放了一块牌子:男嘉宾的号码
    22. wivesMap.put(wife.getFamilyId(), wife);
    23. count++;
    24. }
    25. // 男嘉宾上场
    26. for (Couple husband : husbands) {
    27. // 找到举着自己号码牌的女嘉宾
    28. Couple wife = wivesMap.get(husband.getFamilyId());
    29. System.out.println(husband.getUserName() + "爱" + wife.getUserName());
    30. count++;
    31. }
    32. System.out.println("----------------------");
    33. System.out.println("循环了:" + count + "次");
    34. }

    输出结果

    梁山伯爱祝英台

    牛郎爱织女

    干将爱莫邪

    工藤新一爱毛利兰

    罗密欧爱朱丽叶

    ----------------------

    循环了:10次

    此时无论你如何调换男嘉宾出场顺序,都只会循环10次。

    男嘉宾出场后,无需遍历女嘉宾,直接“按图索骥”找到配偶

    小结

    第一版和第二版就不讨论了,我们只谈谈第三版和第四版代码。

    假设两组数据长度分别是n和m:

    第三版的循环次数是n ~

    ,是波动的,最好效率是n,这是非常惊人的(最差效率同样惊人...)。

    第四版始终是 n + m。

    在数据量较小的情况下,其实两者差距不大,CPU执行时间差可以忽略不计。我们设想n, m=1000的情况。

    此时第三版的循环次数是:1000 ~

    最好的结果是1000,固然可喜。但是最差的结果是1000+999+...+1=500500。

    而此时第四版的循环次数是 1000+1000=2000,与第三版最好的结果相比也只差了1000次而已,对于CPU而言可以忽略不计。

    考虑到实际编程中,数据库的数据往往是非常杂乱的,使用第三版算法几乎不可能得到最大效率。

    所以推荐使用第四版算法。

    它的精髓就是利用HashMap给其中一列数据加了“索引”,每个数据的“索引”(Map的key)是不同的,让数据差异化。

    了解原理后,如何掌握这简单有效的小算法呢?

    记住两步:

    • 先把其中一列数据由线性结构的List转为Hash散列的Map,为数据创建“索引”
    • 遍历另一列数据,依据索引从Map中匹配数据

    相比第三版在原有的两个List基础上操作数据,第四版需要额外引入一个Map,内存开销稍微多了一点点。算法中,有一句特别经典的话:空间换时间。第四版勉强算吧。但要清楚,实际上Couple对象并没有增多,Map只是持有原有的Couple对象的引用而已。新增的内存开销主要是Map的索引(Key)。

    请大家务必掌握这个小算法,后面很多地方会用到它。

    拓展思考

    我们都知道,实际开发中我们从数据库查询得到的数据都是由Mapper封装到单个List中,也就是说不具备“两个数据集合匹配”这种前提呀。

    此时转换一下思维即可,比如前端要全量获取城市,而且是二级联动:

    |-浙江省

        |-杭州市

        |-宁波市

        |-温州市

        |-...

    |-安徽省

        |-合肥市

        |-黄山市

        |-芜湖市

        |-...

    而数据库查出来的是:

    id    name     pid

    1     浙江省    0

    2    杭州市     1

    3    宁波市     1

    4    温州市     1

    5    安徽省     0

    6    合肥市     5

    7    黄山市     5

    8    芜湖市     5

    此时,List需要“自匹配”。

    我们可以把“自匹配”转为“两个数据集合匹配”(List转Map,然后List和Map匹配):

    是不是觉得似曾相识呀。

    上面这种情况属于自关联匹配,强行把同一张表的数据当成两个数据通过id和pid匹配。而实际开发中,更为常见的是两张表的数据匹配:

    因为有些公司不允许过多的JOIN查询,此时就只能根据主表先把分页的10条数据查出来,再根据主表数据的ids把从表的10条数据查出来,最后在内存中匹配。(其实对于10条数据,用for循环也没问题)

    尝试封装工具类

    很多时候,我们只是想做一下List转Map,写一大串Stream确实挺烦的,此时可以考虑专门封装一个转换类:

    1. public class ConvertUtil {
    2. private ConvertUtil() {
    3. }
    4. /**
    5. * 将List转为Map
    6. *
    7. * @param list 原数据
    8. * @param keyExtractor Key的抽取规则
    9. * @param Key
    10. * @param Value
    11. * @return
    12. */
    13. public static <K, V> Map<K, V> listToMap(List<V> list, Function<V, K> keyExtractor) {
    14. if (list == null || list.isEmpty()) {
    15. return new HashMap<>();
    16. }
    17. Map<K, V> map = new HashMap<>(list.size());
    18. for (V element : list) {
    19. K key = keyExtractor.apply(element);
    20. if (key == null) {
    21. continue;
    22. }
    23. map.put(key, element);
    24. }
    25. return map;
    26. }
    27. /**
    28. * 将List转为Map,可以指定过滤规则
    29. *
    30. * @param list 原数据
    31. * @param keyExtractor Key的抽取规则
    32. * @param predicate 过滤规则
    33. * @param Key
    34. * @param Value
    35. * @return
    36. */
    37. public static <K, V> Map<K, V> listToMap(List<V> list, Function<V, K> keyExtractor, Predicate<V> predicate) {
    38. if (list == null || list.isEmpty()) {
    39. return new HashMap<>();
    40. }
    41. Map<K, V> map = new HashMap<>(list.size());
    42. for (V element : list) {
    43. K key = keyExtractor.apply(element);
    44. if (key == null || !predicate.test(element)) {
    45. continue;
    46. }
    47. map.put(key, element);
    48. }
    49. return map;
    50. }
    51. /**
    52. * 将List映射为List,比如List personList转为List nameList
    53. *
    54. * @param originList 原数据
    55. * @param mapper 映射规则
    56. * @param 原数据的元素类型
    57. * @param 新数据的元素类型
    58. * @return
    59. */
    60. public static <T, R> List<R> resultToList(List<T> originList, Function<T, R> mapper) {
    61. if (originList == null || originList.isEmpty()) {
    62. return new ArrayList<>();
    63. }
    64. List<R> newList = new ArrayList<>(originList.size());
    65. for (T originElement : originList) {
    66. R newElement = mapper.apply(originElement);
    67. if (newElement == null) {
    68. continue;
    69. }
    70. newList.add(newElement);
    71. }
    72. return newList;
    73. }
    74. /**
    75. * 将List映射为List,比如List personList转为List nameList
    76. * 可以指定过滤规则
    77. *
    78. * @param originList 原数据
    79. * @param mapper 映射规则
    80. * @param predicate 过滤规则
    81. * @param 原数据的元素类型
    82. * @param 新数据的元素类型
    83. * @return
    84. */
    85. public static <T, R> List<R> resultToList(List<T> originList, Function<T, R> mapper, Predicate<T> predicate) {
    86. if (originList == null || originList.isEmpty()) {
    87. return new ArrayList<>();
    88. }
    89. List<R> newList = new ArrayList<>(originList.size());
    90. for (T originElement : originList) {
    91. R newElement = mapper.apply(originElement);
    92. if (newElement == null || !predicate.test(originElement)) {
    93. continue;
    94. }
    95. newList.add(newElement);
    96. }
    97. return newList;
    98. }
    99. // ---------- 以下是测试案例 ----------
    100. private static List<Person> list;
    101. static {
    102. list = new ArrayList<>();
    103. list.add(new Person("i", 18, "杭州", 999.9));
    104. list.add(new Person("am", 19, "温州", 777.7));
    105. list.add(new Person("iron", 21, "杭州", 888.8));
    106. list.add(new Person("man", 17, "宁波", 888.8));
    107. }
    108. public static void main(String[] args) {
    109. Map<String, Person> nameToPersonMap = listToMap(list, Person::getName);
    110. System.out.println(nameToPersonMap);
    111. Map<String, Person> personGt18 = listToMap(list, Person::getName, person -> person.getAge() >= 18);
    112. System.out.println(personGt18);
    113. }
    114. @Data
    115. @AllArgsConstructor
    116. @NoArgsConstructor
    117. static class Person {
    118. private String name;
    119. private Integer age;
    120. private String address;
    121. private Double salary;
    122. }
    123. }

    大家还可以继续自行扩展哟~

    比如,现在的listToMap()方法只支持 key:object,如果我希望是key:field,该怎么封装呢?(答案见评论区)

    部分同学可能会觉得有点难,甚至会有一系列疑问:这参数什么意思啊?哪来的接口?写法好诡异…等等,这是因为缺少泛型和Java8的相关知识。不要慌,暂时有个印象即可,我们会在学习Java8新特性后再复习上面这段代码。

    留个坑

    我在第三版算法中留了一个坑,但它是隐性的,刚好这个场景下不会暴露。大家可以试着把第三版的break去掉,看看会不会出问题。

    作者简介:大家好,我是smart哥,前中兴通讯、美团架构师,现某互联网公司CTO

    进群,大家一起学习,一起进步,一起对抗互联网寒冬

  • 相关阅读:
    code2vec 代码的连续分布式矢量表示
    0918 框架理论知识
    生物芯片技术-原理、应用与未来发展
    DDD进阶_领域设计的分层架构
    【计算机网络面试题(62道)】
    华为发布LampSite X室内数字化创新解决方案,释放数字世界无限潜能
    Kali系统MSF模块暴力破解MySQL弱口令漏洞
    查看使用Android API接口创建的AppLinking链接的分析数据
    电脑复制和粘贴的时候会出现Hello!
    华为OD北京研究所技术加面手撕代码实录:求最长回文子串
  • 原文地址:https://blog.csdn.net/smart_an/article/details/134486898