V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
aoizz
V2EX  ›  问与答

Java 中一个 size 为 10 万的 List<User>,怎么查找 name="张三"的 User 最快?

  •  
  •   aoizz · 2021-06-15 10:27:57 +08:00 · 3773 次点击
    这是一个创建于 1018 天前的主题,其中的信息可能已经有所发展或是发生改变。

    需求大概就是这样,我目前使用的是

    Optional<User> first = userList.stream().filter(e->e.getName().equals("张三")).findFirst();
    if (first.isPresent()){
       User user = first.get();
    }
    

    但我觉得这种方式效率有点低,请问有别的更快的方式吗?

    第 1 条附言  ·  2021-06-15 12:50:38 +08:00
    非常感谢各位大佬的解答,怪我提问时没有详细说明我的场景,

    12 楼我的回复能详细描述我的问题,其实将 List 转成 Map 是一种比较好的方案,

    因为只需要转一次,后续的循环里面只需要根据 hash 来查询对应的值,远远比每一次都遍历快,

    因为我提问的方式不正确( X-Y Problem,从 23 、24 楼两位大佬学到的),

    导致大家在错误的方向浪费时间,很抱歉。
    32 条回复    2021-06-16 08:34:26 +08:00
    justicelove
        1
    justicelove  
       2021-06-15 10:33:52 +08:00   ❤️ 1
    最好是插入的时候就通过一个固定算法来计算下标, 查找时同样 通过固定算法来获取对应下标, 这么做其实有点像自己实现一个类似 map 的快速查找结构
    vindac
        2
    vindac  
       2021-06-15 10:33:57 +08:00   ❤️ 1
    直接 fori,找到第一个返回
    timethinker
        3
    timethinker  
       2021-06-15 10:34:30 +08:00   ❤️ 2
    在不进行预处理的情况下,你可以简单的改为并行流然后查找,users.stream().parallel().filter...,或者 users. parallelStream().filter...
    aoizz
        4
    aoizz  
    OP
       2021-06-15 10:40:36 +08:00
    @justicelove #1 这个目前来看有点不现实,谢谢大佬
    @vindac #2 直接 fori 是不是和我现在的做法差不多啊。
    @qwe520liao #3 我研究一下,谢谢大佬
    amon
        5
    amon  
       2021-06-15 10:41:02 +08:00   ❤️ 1
    转成 Map,
    userList.stream().collect(Collectors.groupingBy(User::getName));
    qiuhang
        6
    qiuhang  
       2021-06-15 10:43:05 +08:00   ❤️ 3
    这种没啥好办法吧,要想查找快,那你在组织数据的时候就得多下功夫。比如按照字典顺序排列,然后用二分查找或者干脆存成查找树。你这无序的 list,就是天王老子来了它复杂度也得是 O(n)。
    InkAndBanner
        7
    InkAndBanner  
       2021-06-15 10:43:59 +08:00   ❤️ 1
    改成并行流会快,但是如果数据很少 并行流会慢
    gabon
        8
    gabon  
       2021-06-15 10:46:50 +08:00 via Android   ❤️ 1
    这数据总归不是内存里生成的吧,不能查的时候只查这一个吗
    yejinmo
        9
    yejinmo  
       2021-06-15 10:47:56 +08:00   ❤️ 1
    // 非预处理
    userList.FirstOrDefault(q => q.Name == name);
    // 预处理
    var userMap = userList.ToDictionary(q => q.Name, q => q);
    userMap.TryGetValue(name, out var user);
    Edcwsyh
        10
    Edcwsyh  
       2021-06-15 10:52:39 +08:00   ❤️ 1
    @justicelove 这好像就是哈希方法吧....但 Map 不是哈希啊, HashMap 才是
    justicelove
        11
    justicelove  
       2021-06-15 10:59:52 +08:00   ❤️ 1
    @Edcwsyh #10 其实 Tree Map 也是类似的思路
    aoizz
        12
    aoizz  
    OP
       2021-06-15 11:00:23 +08:00
    @gabon #8 这是从数据库根据 id 拿到的,因为外面还有一个循环,所以不能直接查数据库。这个需求我简化了。
    真正的大概是这样的,为了避免总是查询数据库,我将 CustomerList 里面的 userId 都拿了出来,然后根据 userIdList,查找所有符合要求的 User,然后再有下面的操作
    List<String> userIds = customerList.stream().map(Customer::getUserId).collect(Collectors.toList());

    List<User> userList = userService.getByIds(userIds);

    customerList.forEach(c->{

    Optional<User> first = userList.stream().filter(e->e.getName().equals(c.getName)).findFirst();

    if (first.isPresent()){
    User user = first.get();
    //别的操作
    }


    })
    aitaii
        13
    aitaii  
       2021-06-15 11:57:24 +08:00
    空间换时间
    Leviathann
        14
    Leviathann  
       2021-06-15 12:01:24 +08:00
    单次查询就这样啊
    多线程分段查也许能快点,但是 10w 这个量级也不好说
    多次查就转 map
    securityCoding
        15
    securityCoding  
       2021-06-15 12:04:56 +08:00
    解决问题的思路明显是错的
    timethinker
        16
    timethinker  
       2021-06-15 12:07:30 +08:00   ❤️ 2
    @aoizz 按照这个思路,很难想象你一次性要获取 10W 的用户(根据 getByIds,使用 SQL IN 语句?),优化的核心思路在于时间跟空间的平衡点,数据查找尽量使用 SQL 通过数据库来筛选数据,充分利用好数据库的索引功能,避免一次性获取大量数据,然后只使用里面的少量数据。

    不过最重要的还是看数据量与看场景,是 OLTP 还是 OLAP,前者尽量保证短时间内完成操作,后者更多的是通过提前创建派生数据来提高查找速度(以空间换时间)。
    bxb100
        17
    bxb100  
       2021-06-15 12:10:33 +08:00
    @aoizz #12 都放到 List 里面了, 为啥不直接生成 Map
    3dwelcome
        18
    3dwelcome  
       2021-06-15 12:17:03 +08:00
    我说一下 C++优化,有两点。

    1. 可以用 early skip,比如"张三"内存里 utf8 是 6 个字节,那么 List 里所有 Name 不是 6 个字节的,都可以快速跳过,而不用深度判断。

    2. 给 List 里每一条记录打 tag, 比如"张三"的 UTF8 是 E5 BC A0 E4 B8 89,按照 ASCII 排序整理一下就是 045889ABBCEE,去掉重复后的 tag 就是[0][4][5][8][9][A][B][C][E]。然后对比别的记录有没有这几个 TAG,如果没有就可以快速跳过,而不用对比。
    3dwelcome
        19
    3dwelcome  
       2021-06-15 12:18:34 +08:00
    @bxb100 都知道用 Map 可以解决,但楼主问的是 List 。
    Rwing
        20
    Rwing  
       2021-06-15 12:21:09 +08:00
    我来跑个题,各位不考虑一下 C# 吗,🙂
    var first = userList.First(e=>e.Name == "张三");
    loshine1992
        21
    loshine1992  
       2021-06-15 12:23:24 +08:00
    @Rwing

    这不是一样的么,并没有提升效率。
    icyalala
        22
    icyalala  
       2021-06-15 12:27:42 +08:00   ❤️ 2
    只就楼主目前写的问题来看,如果只需要查找一次,那就顺序遍历,无论如何都是 O(n) 的复杂度,无非就是在遍历或者比较这些地方稍微优化一些。如果需要多次查找,那就先转为 Map 再处理,但转 Map 这一步也还是 O(n) 复杂度。

    我感觉这是个 XY problem 。。
    Ariver
        23
    Ariver  
       2021-06-15 12:36:28 +08:00
    X/Y +1
    aoizz
        24
    aoizz  
    OP
       2021-06-15 12:44:28 +08:00
    @icyalala #22
    @Ariver #23 非常感谢,学习到了,今后提问题一定会描述清楚所有细节。转化为 Map 在处理这种方案我觉得是可行的,只需要转一次就可以,循环中根据 hash 查询,远比我循环比对查询来得快。
    gabon
        25
    gabon  
       2021-06-15 12:49:01 +08:00 via Android
    @aoizz 这样我感觉用 guava loading cache 之类的更合适
    pkwenda
        26
    pkwenda  
       2021-06-15 13:15:07 +08:00
    查了一下什么是楼上说的 xy 问题:
    https://www.wikiwand.com/en/XY_problem

    这个问题我也深有体会,我的组员有时会问一个很迷的问题,虽然他本质想解决 X 问题,但是他认为解决 Y 问题,X 问题可以迎刃而解。

    查询肯定是 散列表最快,但是空间大

    后续可能是否有范围查询?散列表没办法做 range,还是要有一定前瞻性
    zdt3476
        27
    zdt3476  
       2021-06-15 14:09:45 +08:00
    @pkwenda 可以考虑同时维护 list+map 。 或者是使用 B+树这类数据结构? Java 好像有个 TreeMap 之类的东西吧。
    vindurriel
        28
    vindurriel  
       2021-06-15 16:37:25 +08:00 via iPhone
    标准的面试题 哈哈
    内存能装下就建个 map 装不下就按 name 排序然后折半查找 至于如何排序 又是另一道面试题
    zhanggg
        29
    zhanggg  
       2021-06-15 19:35:46 +08:00
    二分或者多分并行遍历直接 equals 判断啊,转 map 还要额外的内存和 hash 计算开销
    vchroc
        30
    vchroc  
       2021-06-15 22:06:59 +08:00
    @zdt3476 LinkedHashMap
    hyqCrystal
        31
    hyqCrystal  
       2021-06-15 23:27:01 +08:00
    map 正解
    Cola98
        32
    Cola98  
       2021-06-16 08:34:26 +08:00
    先排个序,在二分?
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   2881 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 29ms · UTC 13:06 · PVG 21:06 · LAX 06:06 · JFK 09:06
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.