V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
• 请不要在回答技术问题时复制粘贴 AI 生成的内容
Gabrielle70
V2EX  ›  程序员

[前端面试题: 请求/显示千万级别数量的任务]

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

    题目: 设计一个在地图(谷歌地图)上显示千万级别数量的任务的前端单页应用程序

    任务被分组到项目中。项目/任务被存储在后端 RDBMS 系统中. 每个任务所在的记录存有该任务的经纬度位置。

    前端请求后端 API, 拿到特定项目的任务数据, 并显示在前端谷歌地图上。 一次请求可以返回千万级条任务

    问题: 您将使用哪些关键概念/技术来实现在前端显示上千万级别数量的任务?

    我的思路:

    1. Throttling / Debouncing, 避免短时间内重复请求
    2. 按需请求/加载: 网页滚动到哪里, 先请求/加载当前视口能看得到的内容. 视口外的看不见的内容,不请求不加载
    3. 本地缓存

    请大佬提供思路!

    谢谢!

    9 条回复    2024-09-03 19:13:24 +08:00
    lic128
        1
    lic128  
       112 天前
    1. geo fencing, 只拉取并显示当前 map zoom level 和 geo boundary 内的 task 。
    2. clustering , 显示的时候只显示当前 level 的 clustered marker, zoom in/out 的时候再去拉更详细的数据。
    3. 如果这些 task 需要以列表的形式做展示,virtual scrolling
    tool2dx
        2
    tool2dx  
       112 天前
    这是来面试客户端吧,什么四叉树管理经纬度之类的算法。

    多学学 google earth ,web 直接上 wasm ,用客户端的思路开发前端。JS 代码再花里胡哨,也阻挡不了时代的步伐。
    rabbbit
        3
    rabbbit  
       112 天前
    面试:
    使用 KD-tree 算法聚合坐标
    使用 Web Worker 避免阻塞主线程
    使用 Emscripten c++ 加快计算速度

    干活:
    npm install supercluster
    murmur
        4
    murmur  
       112 天前
    我记得现在的地图插件都可以拿到缩放层级的,该聚合就聚合,算法都不需要,缩放太低了直接就显示粗略信息
    clf
        5
    clf  
       112 天前
    按缩放级别加载?然后限制单次请求的数据量,优先加载中心坐标近的该缩放等级的数据。
    sunchuo
        6
    sunchuo  
       112 天前
    感觉面试官卡在这个问题很久了。
    sillydaddy
        7
    sillydaddy  
       112 天前 via Android
    关于数据加载:请求完数据后,构建四叉树,四叉树的数据使用分块存储。根据视角所处的位置和 level 动态加载对应 level 的分块数据。同时可以预加载相邻的分块和相邻的 level 数据。

    关于显示:因为前端不可能同时显示 1000 万个对象,整个屏幕也就 100 万像素左右。根据需求,看最大需要同时显示多少个对象,来确定使用什么方式来显示这些对象。如果要尽可能密集,那只好绘制像素,如果只要显示 1 万个,那就可以简单些了。
    shadowyue
        8
    shadowyue  
       112 天前
    这个东西往深入挺复杂,不知道面试官需要的是能回答到什么程度。
    如果是工作中遇到这个,现在随便一个地图的 sdk 都支持海量数据展示处理,上面几位提到的算法都自带了,去查查文档就行。
    seeu2ex
        9
    seeu2ex  
       112 天前 via iPhone   ❤️ 1
    @shadowyue 万一他面的就是百度地图,腾讯地图,高德地图嘞🤣
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   3041 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 20ms · UTC 13:16 · PVG 21:16 · LAX 05:16 · JFK 08:16
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.