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

149 天前
 Gabrielle70

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

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

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

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

我的思路:

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

请大佬提供思路!

谢谢!

1967 次点击
所在节点    程序员
9 条回复
lic128
149 天前
1. geo fencing, 只拉取并显示当前 map zoom level 和 geo boundary 内的 task 。
2. clustering ， 显示的时候只显示当前 level 的 clustered marker, zoom in/out 的时候再去拉更详细的数据。
3. 如果这些 task 需要以列表的形式做展示，virtual scrolling
tool2dx
149 天前
这是来面试客户端吧，什么四叉树管理经纬度之类的算法。

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

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

关于显示：因为前端不可能同时显示 1000 万个对象，整个屏幕也就 100 万像素左右。根据需求，看最大需要同时显示多少个对象，来确定使用什么方式来显示这些对象。如果要尽可能密集，那只好绘制像素，如果只要显示 1 万个，那就可以简单些了。
shadowyue
149 天前
这个东西往深入挺复杂，不知道面试官需要的是能回答到什么程度。
如果是工作中遇到这个，现在随便一个地图的 sdk 都支持海量数据展示处理，上面几位提到的算法都自带了，去查查文档就行。
seeu2ex
149 天前
@shadowyue 万一他面的就是百度地图，腾讯地图，高德地图嘞🤣

这是一个专为移动设备优化的页面（即为了让你能够在 Google 搜索结果里秒开这个页面），如果你希望参与 V2EX 社区的讨论，你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://tanronggui.xyz/t/1069906

V2EX 是创意工作者们的社区，是一个分享自己正在做的有趣事物、交流想法，可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX