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

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

  •  
  •   aoizz · 347 天前 · 3387 次点击
    这是一个创建于 347 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

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

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

    第 1 条附言  ·  347 天前
    非常感谢各位大佬的解答,怪我提问时没有详细说明我的场景,

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

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

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

    导致大家在错误的方向浪费时间,很抱歉。
    32 条回复    2021-06-16 08:34:26 +08:00
    justicelove
        1
    justicelove  
       347 天前   ❤️ 1
    最好是插入的时候就通过一个固定算法来计算下标, 查找时同样 通过固定算法来获取对应下标, 这么做其实有点像自己实现一个类似 map 的快速查找结构
    vindac
        2
    vindac  
       347 天前   ❤️ 1
    直接 fori,找到第一个返回
    qwe520liao
        3
    qwe520liao  
       347 天前   ❤️ 2
    在不进行预处理的情况下,你可以简单的改为并行流然后查找,users.stream().parallel().filter...,或者 users. parallelStream().filter...
    aoizz
        4
    aoizz  
    OP
       347 天前
    @justicelove #1 这个目前来看有点不现实,谢谢大佬
    @vindac #2 直接 fori 是不是和我现在的做法差不多啊。
    @qwe520liao #3 我研究一下,谢谢大佬
    amon
        5
    amon  
       347 天前   ❤️ 1
    转成 Map,
    userList.stream().collect(Collectors.groupingBy(User::getName));
    qiuhang
        6
    qiuhang  
       347 天前   ❤️ 3
    这种没啥好办法吧,要想查找快,那你在组织数据的时候就得多下功夫。比如按照字典顺序排列,然后用二分查找或者干脆存成查找树。你这无序的 list,就是天王老子来了它复杂度也得是 O(n)。
    InkAndBanner
        7
    InkAndBanner  
       347 天前   ❤️ 1
    改成并行流会快,但是如果数据很少 并行流会慢
    gabon
        8
    gabon  
       347 天前 via Android   ❤️ 1
    这数据总归不是内存里生成的吧,不能查的时候只查这一个吗
    yejinmo
        9
    yejinmo  
       347 天前   ❤️ 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  
       347 天前   ❤️ 1
    @justicelove 这好像就是哈希方法吧....但 Map 不是哈希啊, HashMap 才是
    justicelove
        11
    justicelove  
       347 天前   ❤️ 1
    @Edcwsyh #10 其实 Tree Map 也是类似的思路
    aoizz
        12
    aoizz  
    OP
       347 天前
    @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  
       347 天前
    空间换时间
    Leviathann
        14
    Leviathann  
       347 天前
    单次查询就这样啊
    多线程分段查也许能快点,但是 10w 这个量级也不好说
    多次查就转 map
    securityCoding
        15
    securityCoding  
       347 天前
    解决问题的思路明显是错的
    qwe520liao
        16
    qwe520liao  
       347 天前   ❤️ 2
    @aoizz 按照这个思路,很难想象你一次性要获取 10W 的用户(根据 getByIds,使用 SQL IN 语句?),优化的核心思路在于时间跟空间的平衡点,数据查找尽量使用 SQL 通过数据库来筛选数据,充分利用好数据库的索引功能,避免一次性获取大量数据,然后只使用里面的少量数据。

    不过最重要的还是看数据量与看场景,是 OLTP 还是 OLAP,前者尽量保证短时间内完成操作,后者更多的是通过提前创建派生数据来提高查找速度(以空间换时间)。
    bxb100
        17
    bxb100  
       347 天前
    @aoizz #12 都放到 List 里面了, 为啥不直接生成 Map
    3dwelcome
        18
    3dwelcome  
       347 天前
    我说一下 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  
       347 天前
    @bxb100 都知道用 Map 可以解决,但楼主问的是 List 。
    Rwing
        20
    Rwing  
       347 天前
    我来跑个题,各位不考虑一下 C# 吗,🙂
    var first = userList.First(e=>e.Name == "张三");
    loshine1992
        21
    loshine1992  
       347 天前
    @Rwing

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

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

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

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

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