V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
minglanyu
V2EX  ›  程序员

想了解下大佬们在工作中用过的数据结构

  •  1
     
  •   minglanyu · 2020-03-26 14:39:06 +08:00 · 4605 次点击
    这是一个创建于 1463 天前的主题,其中的信息可能已经有所发展或是发生改变。

    emmmmmm,说出来不怕丢人。

    昨天无意间刷 leetcode,发现一道题解法很妙,发现了新世界一样;今天做另一道题的时候发现 emmmmm,不是那么简单,还是得动动脑子的。 所以又对数据结构和算法在工作中的实际用途产生了困惑。

    平时大多数时间在用 Array 原型链上的forEach,map,filter等等,String 原型链,Object 原型链上的那一套,再搭配一些 es6+的Set(),...,Map这种等等。 偶尔遇到一些稍微复杂的会用 lodash 里的函数或者 for for,对服务端返回的数据做一些处理以供渲染。

    我写 PC 端的前端中后台系统,就是上面这些东西组合起来用,平时工作也够用了,性能也没啥问题。 如果是操作 DOM,基本上也是调 API,然后也很少有抓耳挠腮的感觉,一点一点能把需求做出来。 框架用的也算是蛮熟,接入第三方开源库也很快,源码也阅读过一些。

    学校里也学过数据结构,基本上就是一些数组,二叉树,链表之类等等(当前工作里用到最多的就是数组了,可能是我太菜也可能是没必要用所以后面两个几乎没用过,所以基本上忘光了)。

    偶尔刷刷 leetcode,起初是为了加深对 js 的语法的掌握,现在感觉语法啥的就那么回事,数据结构才更值得自己去深入学习一下,兴许以后写个什么复杂玩意儿就用上了。

    其他语言我不太懂,但是感觉下面这些很大程度简化了一些前端在数据结构和算法上花费的时间:

    • 面向对象的程序设计的设计思想:类和实例
    • js 语言的真香函数:Array,String,Object 原型
    • 框架的出现:Vue 生态,React 生态,JQuery
    • 各种库:UI 库,请求库,函数处理库,canvas 库

    还有太多太多了

    最近想花时间补补这方面的知识了,不仅仅是应对以后的面试,更多的是想在工作中写出优雅的代码来,毕竟一直 if else + for for 迭代 感觉有点···

    所以就想问问大佬们,你们在工作中用了什么数据结构,香不香?

    第 1 条附言  ·  2020-06-13 17:20:52 +08:00

    今天距离发贴已经79天了。 记录一下自己在这段时间刷LeetCode卡片和题目的收获。

    新学会的数据结构:栈、链表 新学会的算法:对撞指针、5种经典排序、二分、递归

    在自己的github博客做了一些总结⬇︎

    数据结构和算法

    leetcode javascript repo:leetcode-js

    数据结构

    算法

    做题目的过程中,巩固了很多js的常用方法,对js的运用也更加娴熟了

    思考:熟练运用一门语言,对于学习数据结构和算法,或者是做实验有很大的帮助。

    切身体会:

    • 当初学C语言的时候,语法都没搞懂,就直接做题,对于先天没有基础的同学真心不友善,对数据结构也就是脑子里有个概念吧,考试背一背是能过的
    • 后来虽然本专业使用Matlab做实验做仿真较多,但讲道理我对Matlab的语法也很懵,很多都是跟着感觉走,图像处理信号处理其实也是个不错的方向

    总而言之,在试图搞清楚数据结构和算法前,如果对语言的语法和特性掌握都不足够,不妨先磨磨刀,“磨刀不误砍柴工”

    43 条回复    2020-03-27 14:08:28 +08:00
    tabris17
        1
    tabris17  
       2020-03-26 15:16:33 +08:00
    跳表
    lithbitren
        2
    lithbitren  
       2020-03-26 15:25:43 +08:00 via iPhone
    映射表建树,组件递归之类的,反正就是很简单的东西,但很多人找不到轮子就是写不出来,或者找了个乐色轮子改半天也不能符合要求。还有字符串处理,很多框架熟练工连正则都不会写,emoji 识别也写不出,都是巨简单的东西,再难也难不过 leetcode 中等题。
    nekoneko
        3
    nekoneko  
       2020-03-26 15:30:54 +08:00
    二叉树,表栈队列还是别忘的好,说不定哪天就用上了
    Jacky23333
        4
    Jacky23333  
       2020-03-26 15:30:59 +08:00 via Android
    数组
    nekoneko
        5
    nekoneko  
       2020-03-26 15:33:30 +08:00
    比如说发一大堆消息时,会用到队列,但是又有了 vip 用户,svip 用户,要保证 svip 先于 vip 先于普通用户,这时候就要优先队列也就是大小顶堆了
    fancy111
        6
    fancy111  
       2020-03-26 15:33:48 +08:00
    只刷困难题的飘过。。。 数据结构也就那么多,很多时候可以靠算法自建。
    minglanyu
        7
    minglanyu  
    OP
       2020-03-26 16:53:53 +08:00
    @tabris17 @nekoneko 看来在服务端还是蛮有用的 如果我想写 node 的话真得加强了
    minglanyu
        8
    minglanyu  
    OP
       2020-03-26 16:55:26 +08:00
    @lithbitren 正则确实是字符串处理利器 框架熟练工不可怕 不知道自己是框架熟练工的才可怕
    minglanyu
        9
    minglanyu  
    OP
       2020-03-26 16:56:02 +08:00
    @Jacky23333 数组是真的好用 233
    minglanyu
        10
    minglanyu  
    OP
       2020-03-26 16:56:33 +08:00
    @fancy111 大佬牛杯 我就先刷刷 easy 和中等就好了
    isRealLeven
        11
    isRealLeven  
       2020-03-26 17:05:35 +08:00
    双链表
    wellsc
        12
    wellsc  
       2020-03-26 17:11:42 +08:00
    万物皆可 map
    Harv
        13
    Harv  
       2020-03-26 17:19:38 +08:00
    正巧刚用环形队列写了个存储接收数据的程序。
    minglanyu
        14
    minglanyu  
    OP
       2020-03-26 17:21:23 +08:00
    @wellsc 小 map + 大 Map
    minglanyu
        15
    minglanyu  
    OP
       2020-03-26 17:22:09 +08:00
    @Harv 厉害的
    Leonard
        16
    Leonard  
       2020-03-26 17:22:25 +08:00
    数组
    minglanyu
        17
    minglanyu  
    OP
       2020-03-26 17:24:34 +08:00
    @isRealLeven 刚学了下单链表的双指针,还蛮好用 用双链表写了啥啊大佬
    hauzi
        18
    hauzi  
       2020-03-26 17:24:38 +08:00
    数组最多啦
    cgh
        19
    cgh  
       2020-03-26 17:29:01 +08:00
    @Harv 什么场景,不能直接存储吗?
    angryfish
        20
    angryfish  
       2020-03-26 17:29:05 +08:00
    数据结构用得很多,但都是库有的啊。list,set,map,不天天用,不用自己实现而已。
    catinsides
        21
    catinsides  
       2020-03-26 17:30:40 +08:00
    想看“发现了新世界一样”的那道题
    minglanyu
        22
    minglanyu  
    OP
       2020-03-26 18:41:33 +08:00
    @catinsides 我夸张了一下 哈哈
    no1xsyzy
        23
    no1xsyzy  
       2020-03-26 18:44:47 +08:00
    Dict[Tuple, Any] 真香
    刷到动态规划题都直接继承 dict 写个 __missing__
    遇到计算顺序敏感的(即容易爆栈)再写个循环 touch 一下 result[X]
    不追求极限速度就一遍过,反正 leetcode 的 Python 运行时本身连启动都很慢。

    ——

    稍微看歪了
    想想,我发现我成天在改语法结构,改到静态检查器都不认了。
    minglanyu
        24
    minglanyu  
    OP
       2020-03-26 19:06:38 +08:00
    @no1xsyzy 我是谁 我在哪 我在干什么 v 站果然藏龙卧虎
    no1xsyzy
        25
    no1xsyzy  
       2020-03-26 19:31:43 +08:00
    @minglanyu 是中文有偏差,如果我说的改语法结构说成 tweak with syntax 就只剩下诡异了(
    also24
        26
    also24  
       2020-03-26 19:33:49 +08:00
    我最喜欢的数据结构还是并查集,实实在在的拓宽了思路,以至于有些不是并查集的题目,我也会用并查集来做着玩儿~~
    also24
        27
    also24  
       2020-03-26 19:35:27 +08:00
    另外,我最不喜欢的数据结构是 Trie 树,适用的场景相对比较少,对空间也比较浪费。
    ackfin01
        28
    ackfin01  
       2020-03-26 19:44:13 +08:00
    除了语言自带的那些数据结构,还会用下面的

    - 栈,队列
    - 链表:也很常用,用过双向循环链表在 LRU 缓存里,
    - 树:常用在搜索,二叉树是最基本的,还用过矩形树
    - 图->最常用的:DAG,是否有环

    还有很多算法真的是很有用,比如双指针,dfs,bfs,动态规划等

    其实总结一下,就是遇到一个问题进行分析的时候,就会考虑这些可能的数据结构和可能的算法实现,哪种应用起来最符合,使得问题简化效率提高,简化不仅是实现上,代码可读性上,还有运行效率上。
    bruce2000
        29
    bruce2000  
       2020-03-26 20:02:22 +08:00
    我除了 list 和 dict 啥也不会,最复杂的也就是 list 与 dickt 的各种嵌套,楼上的大佬说的我一脸懵逼
    jingcoco
        30
    jingcoco  
       2020-03-26 21:04:49 +08:00 via Android
    大部分程序员不需要 CS 证书,广度很重要在小公司,基本要求你啥都做。我自己主要是也像楼主一样想提高所以自己有看些。
    tingyunsay
        31
    tingyunsay  
       2020-03-26 21:47:07 +08:00
    布隆过滤器,个人小项目去重首选
    changz
        32
    changz  
       2020-03-26 22:13:24 +08:00 via Android
    优先队列
    yangzhezjgs
        33
    yangzhezjgs  
       2020-03-26 23:33:05 +08:00
    其实数据结构和算法使用最多的是底层的系统软件领域,一般应用开发还是 if eslse 这样的业务逻辑多
    xiaochun41
        34
    xiaochun41  
       2020-03-27 09:31:41 +08:00
    基本很少自己实现,用的最多的大概是:队列
    zjbztianya
        35
    zjbztianya  
       2020-03-27 09:43:15 +08:00
    @also24 web 框架的路由一般不就是用 trie 么?虽然是压缩前缀的(radix trie)...
    minglanyu
        36
    minglanyu  
    OP
       2020-03-27 09:47:19 +08:00
    @ackfin01
    @changz
    @xiaochun41 队列看起来还是蛮多的
    minglanyu
        37
    minglanyu  
    OP
       2020-03-27 09:48:22 +08:00
    @jingcoco
    @yangzhezjgs 确实是的 做应用层很多都是业务层的东西 而且其实也蛮有学问的
    RedisMasterNode
        38
    RedisMasterNode  
       2020-03-27 09:53:32 +08:00
    @tingyunsay 小项目去重应该直接 set()精确, 大项目才应该用 BloomFilter ?
    tingyunsay
        39
    tingyunsay  
       2020-03-27 10:57:18 +08:00 via iPhone
    @RedisMasterNode 对,实际情况得看数据量吧,可能我自己搞得那些项目量还比较大,所以习惯用 bloom 了😹sorry 有点以偏概全了
    jon
        40
    jon  
       2020-03-27 11:01:28 +08:00
    战马
    Hardrain
        41
    Hardrain  
       2020-03-27 11:05:02 +08:00 via Android
    数组
    双链表
    AVL 树
    971586331
        42
    971586331  
       2020-03-27 13:44:37 +08:00
    用的最多的是队列,链表和树,图还没用过
    neilq
        43
    neilq  
       2020-03-27 14:08:28 +08:00
    list,set,map, dictionary 之类就不说了到处都用,其他用的最多的还是队列,用来做消息处理、任务处理、循环任务之类的场景还是蛮多的。其次是树,什么菜单、组织架构。图,几年 crud 生涯只用过 2 次还是 3 次,基本都用映射表来做的
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   4093 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 36ms · UTC 05:22 · PVG 13:22 · LAX 22:22 · JFK 01:22
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.