V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐关注
Meteor
JSLint - a JavaScript code quality tool
jsFiddle
D3.js
WebStorm
推荐书目
JavaScript 权威指南第 5 版
Closure: The Definitive Guide
mikej
V2EX  ›  JavaScript

看到一道面试题:<ul>有 10000 个<li>子元素,如何将这 10000 个<li>颠倒顺序。

  •  2
     
  •   mikej · 2014-02-19 22:58:16 +08:00 · 38369 次点击
    这是一个创建于 3690 天前的主题,其中的信息可能已经有所发展或是发生改变。
    要求是效率尽量要高。不光是算法效率,还要考虑DOM元素操作的效率。大家有什么想法?
    还有就是遇到类似这种问题解题技巧?
    104 条回复    2016-10-24 21:06:21 +08:00
    1  2  
    democ
        1
    democ  
       2014-02-19 23:13:59 +08:00   ❤️ 1
    1. 先复制一份 (不要插入到DOM中,频繁的操作DOM消耗资源是很大的)
    2. 对复制出的这份做操作. 方法是从最后一个开始拿插入到一个新的<ul>中 (这一步也不需要插入到DOM中)
    3. 将DOM中的<ul>更换为从新排序的<ul>

    有不合适的地方请楼下指出.
    learnshare
        2
    learnshare  
       2014-02-19 23:29:08 +08:00
    在内存中操作完成,然后插入到页面中
    kfll
        3
    kfll  
       2014-02-19 23:31:23 +08:00
    @democ 复制的实现复杂效率也不高,`cloneNode` 也不克隆事件
    @mikej 我的话会掐半用 `replaceChild` 首尾交换
    关系到 DOM 的优先考虑浏览器 API 再考虑算法..
    不一定对...
    bombless
        4
    bombless  
       2014-02-19 23:34:35 +08:00
    先remove掉ul,首尾交换上面的li再把ul插回去
    P233
        5
    P233  
       2014-02-19 23:39:30 +08:00   ❤️ 87
    ul {transform: rotate(180deg)}

    li {transform: rotate(180deg)}

    搞定
    tinyhill
        6
    tinyhill  
       2014-02-19 23:45:38 +08:00   ❤️ 1
    [].slice.call(nodeList).reverse(); 循环一次组成字符串插回 ul 节点
    chairuosen
        7
    chairuosen  
       2014-02-19 23:46:07 +08:00 via Android
    卧槽,楼上机智!!
    fakefish
        8
    fakefish  
       2014-02-19 23:49:55 +08:00
    fragementElement+=(lastchild--)
    parent.append(fragementElement)
    大概是这么个意思,把从最后的一个子元素开始复制到fragmentElement,组装完再一起插入原处
    fakefish
        9
    fakefish  
       2014-02-19 23:53:22 +08:00
    速度最快的肯定不能让dom在每次循环的时候有变化。
    blacktulip
        10
    blacktulip  
       2014-02-19 23:54:08 +08:00 via iPhone
    五楼正解
    sneezry
        11
    sneezry  
       2014-02-19 23:54:26 +08:00
    最快的方法我感觉是innerHTML
    sneezry
        12
    sneezry  
       2014-02-19 23:55:09 +08:00
    @P233 五楼你碉堡了。。。
    Sunyanzi
        13
    Sunyanzi  
       2014-02-19 23:57:54 +08:00
    只有我觉得只要简单的遍历一遍然后生成一个反向的大字符串写入 innerHTML 就好吗 ...

    这样的优点是快 ... 生成字符串绝对比任何的 DOM 操作来得都要高效 ...

    缺点是重新生成了列表 ... 所有原来元素上面的事件和属性都没了 ...

    如果要保持原来的元素 ... 大概也只能二分之后 replaceChild 了吧 ...
    clippit
        14
    clippit  
       2014-02-20 00:05:27 +08:00
    http://jsperf.com/reverse-li

    10000的时候确实用数组 reverse 比较快,但是如果 DOM 节点比较少的时候,反而是直接操作比较快呢
    crs0910
        15
    crs0910  
       2014-02-20 00:12:26 +08:00 via Android
    http://stackoverflow.com/questions/5530472/how-to-handle-10000-li-efficiently
    手机chrome测试,字符串和DOM操作响应差不多。
    democ
        16
    democ  
       2014-02-20 00:54:59 +08:00
    @clipplt 涨姿势了.数据说话.
    alay9999
        17
    alay9999  
       2014-02-20 02:23:37 +08:00
    五楼!五体投地!
    jprovim
        18
    jprovim  
       2014-02-20 03:20:25 +08:00
    @P233 非常好的Trick
    FrankFang128
        19
    FrankFang128  
       2014-02-20 09:08:29 +08:00 via Android
    这题哪看到的?
    mikej
        20
    mikej  
    OP
       2014-02-20 09:10:30 +08:00
    @clippit 佩服,真会解决问题
    @P233 太颠覆了。。。
    @fakefish 不错啊,思路挺清晰,代码也很简练。
    mikej
        21
    mikej  
    OP
       2014-02-20 09:12:45 +08:00
    @FrankFang128 知乎
    laoona
        22
    laoona  
       2014-02-20 09:13:43 +08:00
    给五楼跪了!
    FrankFang128
        23
    FrankFang128  
       2014-02-20 09:32:35 +08:00 via Android
    @mikej 这个问题是我出的。。。我只是随口一说的,想不到有人转到V2了 :)
    mengzhuo
        24
    mengzhuo  
       2014-02-20 09:46:46 +08:00
    5楼太机智了!怒赞一个!
    以后的倒序直接加class就over了,js代码又省了很多
    doublleft
        25
    doublleft  
       2014-02-20 09:47:53 +08:00
    @P233 好机制!!!!!!
    ccccccc
        26
    ccccccc  
       2014-02-20 10:02:48 +08:00
    可以用css3 flex order改变排序
    geew
        27
    geew  
       2014-02-20 10:41:18 +08:00
    5楼碉堡了, 10086个怒赞
    paloalto
        28
    paloalto  
       2014-02-20 10:48:57 +08:00
    5楼太颠覆了!!! !
    RoshanWu
        29
    RoshanWu  
       2014-02-20 10:51:45 +08:00
    我是来看5楼的,啊,真是个机智的骚年
    EPr2hh6LADQWqRVH
        30
    EPr2hh6LADQWqRVH  
       2014-02-20 11:02:29 +08:00
    次奥怒赞5楼
    shiye515
        31
    shiye515  
       2014-02-20 11:03:12 +08:00
    @P233
    learnshare
        32
    learnshare  
       2014-02-20 11:07:06 +08:00
    五楼... 给跪了
    January
        33
    January  
       2014-02-20 11:42:29 +08:00
    五楼笑死我了
    atian25
        34
    atian25  
       2014-02-20 11:46:46 +08:00   ❤️ 1
    赞5楼...
    还有个:
    <ol reversed>
    <li>list item one</li>
    <li>list item two</li>
    <li>list item three</li>
    <li>list item four</li>
    <li>list item five</li>
    </ol>
    http://www.w3schools.com/tags/att_ol_reversed.asp
    mikej
        35
    mikej  
    OP
       2014-02-20 11:46:57 +08:00
    @FrankFang128 是吗?呵呵,没想到还能在这里遇到。。
    iamjs
        36
    iamjs  
       2014-02-20 12:02:41 +08:00
    5楼。。直接面试官崩溃的节奏。。
    Sight4
        37
    Sight4  
       2014-02-20 12:05:55 +08:00
    @P233 神回复!!
    shiny
        38
    shiny  
       2014-02-20 12:12:13 +08:00
    5楼是嘲弄面试官呀
    kevinroot
        39
    kevinroot  
       2014-02-20 12:23:50 +08:00
    @P233 碉堡~样式大神
    honk
        40
    honk  
       2014-02-20 12:42:59 +08:00
    @P233 不得不贊!!
    refresh
        41
    refresh  
       2014-02-20 12:44:23 +08:00
    @P233 不是css3不支持吧
    spheee
        42
    spheee  
       2014-02-20 13:31:02 +08:00
    @P233 太厉害了
    jacob
        43
    jacob  
       2014-02-20 13:59:17 +08:00
    @P233 css对js强力逆袭啊。
    Ellison
        44
    Ellison  
       2014-02-20 14:41:55 +08:00
    5楼怒赞...
    fim8
        45
    fim8  
       2014-02-20 14:48:55 +08:00
    热情的转到知乎。
    unnya
        46
    unnya  
       2014-02-20 14:59:31 +08:00
    @P233 忍不住点个赞
    aisensiy
        47
    aisensiy  
       2014-02-20 15:14:09 +08:00
    @sneezry 我觉得也是
    P233
        48
    P233  
       2014-02-20 16:11:50 +08:00
    @refresh IE9+ 都支持
    P233
        49
    P233  
       2014-02-20 16:11:59 +08:00
    感谢大家!
    tonitech
        50
    tonitech  
       2014-02-20 16:14:32 +08:00
    @P233 厉害厉害!!!哈哈哈!
    shiniv
        51
    shiniv  
       2014-02-20 19:09:09 +08:00
    怒赞
    sanddudu
        52
    sanddudu  
       2014-02-20 19:48:03 +08:00
    @atian25 这个只颠倒序号。所以只支持有序列表,题目用的是无序的
    zztczcx
        53
    zztczcx  
       2014-02-20 20:17:48 +08:00
    我是来看5楼的
    princexu
        54
    princexu  
       2014-02-20 20:22:14 +08:00
    5楼碉堡了....
    jieorlin
        55
    jieorlin  
       2014-02-20 20:24:06 +08:00
    ### fdsafdfdsf
    jieorlin
        56
    jieorlin  
       2014-02-20 20:25:38 +08:00   ❤️ 1
    lichgo
        58
    lichgo  
       2014-02-20 21:01:53 +08:00
    5楼的解法让我想到一道经典算法题:
    Reverse words in a sentence: "I am a geek" => "geek a am I"。

    另外,应用CSS在10000个DOM元素上,每个元素都要重画(repaint)吧?效率如何?会比JS更高?
    lnehe
        59
    lnehe  
       2014-02-20 21:06:08 +08:00
    把显示器倒过来。。。。
    ericls
        60
    ericls  
       2014-02-20 21:55:32 +08:00
    5 楼碉堡了!
    Artotria
        61
    Artotria  
       2014-02-20 22:20:05 +08:00
    我是来围观5楼的,机智的骚年~
    ccming
        62
    ccming  
       2014-02-20 22:20:16 +08:00
    好腻害
    MingZhe
        63
    MingZhe  
       2014-02-20 22:36:48 +08:00
    由于不是搞前端的,对五楼的说法刚开始没注意。没想到下面这么多人赞,果断去查。。。确实碉堡了。给赞一个
    iamjs
        64
    iamjs  
       2014-02-20 22:43:30 +08:00
    @lichgo 难说 因为几乎不可能在真实的场景中遇到。典型的面试题目。
    如果我是面试官。给我一个js转换方法和这个答案。我想后者更能给考官留下深刻印象吧。。
    FrankFang128
        65
    FrankFang128  
       2014-02-20 23:06:41 +08:00
    @iamjs 大家喜欢抖机灵的答案
    RIcter
        66
    RIcter  
       2014-02-21 00:04:31 +08:00
    @FrankFang128 不过不失为一个好办法。
    donkeylucky
        67
    donkeylucky  
       2014-02-21 08:54:10 +08:00
    5楼的 大大的机智
    andy12530
        68
    andy12530  
       2014-02-21 09:00:52 +08:00
    如果不考虑普通低级浏览器,5楼的办法是最简单好用的。
    qazwsxedc
        69
    qazwsxedc  
       2014-02-21 10:11:46 +08:00
    围观5楼
    shiye515
        70
    shiye515  
       2014-02-21 10:45:00 +08:00
    @lichgo js添加元素不也要重绘么,还要加上操作dom的时间
    hilenlai
        71
    hilenlai  
       2014-02-21 11:05:33 +08:00
    5楼太机智了!!
    siyang1982
        72
    siyang1982  
       2014-02-21 11:05:55 +08:00
    在本页玩了一下:`$('#Main .box:eq(1), #Main .box:eq(1) > *').css('transform', 'rotate(180deg)')`
    fen
        73
    fen  
       2014-02-21 11:46:52 +08:00
    @P233 5 楼无敌
    YufunHe
        74
    YufunHe  
       2014-02-21 11:50:14 +08:00
    围观五楼
    ffts
        75
    ffts  
       2014-02-21 12:40:58 +08:00
    卧槽,看了演示之后才知道5楼的想法多NB
    lidonghao
        76
    lidonghao  
       2014-02-21 12:45:06 +08:00
    5楼的答案 面试官也不能说错啊 哈哈
    airski
        77
    airski  
       2014-02-21 13:10:32 +08:00
    大赞机智的5楼。
    lijsh
        78
    lijsh  
       2014-02-21 13:27:21 +08:00
    HeyMan
        79
    HeyMan  
       2014-02-21 13:27:30 +08:00
    想象力真强!
    flynngao
        80
    flynngao  
       2014-02-21 13:52:46 +08:00
    5楼鸡汁超越人类
    adam
        81
    adam  
       2014-02-21 14:01:56 +08:00
    可以作为一条面试题~~
    est
        82
    est  
       2014-02-21 14:03:49 +08:00
    @siyang1982 卧槽居然成功了
    rekey
        83
    rekey  
       2014-02-21 15:18:30 +08:00
    特地赶来赞5楼的.
    Keinez
        84
    Keinez  
       2014-02-21 16:38:20 +08:00 via Android
    @P233 五楼已经颠覆我对CSS3的认知
    zzNucker
        85
    zzNucker  
       2014-02-21 16:45:27 +08:00
    @lichgo CSS3动画是不需要repaint的。
    FrankFang128
        86
    FrankFang128  
       2014-02-21 19:02:20 +08:00 via Android
    @RIcter 充分说明前端思维角度和后台是不同的
    sampeng
        87
    sampeng  
       2014-02-21 20:51:34 +08:00
    由于我带前端团队。。
    这个题目,我刚看到。第一反应是,这是个好题。。第二反应,取出来。用算法,然后插入dom。这个是常规的。第三反应,css是控制显示的。如果用css控制呢?我不懂css。所以,我会先用个第二种方式上线,因为开发快。写代码,不一定要精细到极致,一切都是可改的。完全可以满足产品需求,回头再改(如果记得的话)。然后再找时候去网上找找css有没办法。。。收工。
    如果面试的用上面的这个思路来回答,我会直接弄进来。。赶紧去给我去干活
    otakustay
        88
    otakustay  
       2014-02-21 20:57:22 +08:00
    @zzNucker 你确定?不需要relayout/reflow我知道,repaint也不需要那屏幕上的东西是如何改变的?CSS3的translate3D顶多也就是让浏览器支持图层缓存,不用repaint感觉有点太厉害了啊
    otakustay
        89
    otakustay  
       2014-02-21 20:59:55 +08:00
    @lichgo 效率比JS高那是轻轻松松,JS这么做一是DOM结构变化的计算,二是函数调用的损耗(JS<->DOM不是一般的JS函数调用,往往要走一个代理或者序列化),三是引起重布局的损耗,四是有没有浏览器做GPU加速之类的优化的区别
    zzNucker
        90
    zzNucker  
       2014-02-21 21:23:21 +08:00
    @otakustay 唔,我这样表达确实不太对,是不做传统意义上的那种非常耗资源的repaint,就是整个renderlayer tree的重绘。 而用CSS Translate3D这种的话,在开启了硬件合成加速以后会直接在GPU RAM里作为texture改变,就相当于改变的部分很少,而且基本不占用CPU资源。
    zzNucker
        91
    zzNucker  
       2014-02-21 21:38:33 +08:00
    刚发现chrome新版取消了windows下的强制合成的选项。
    zzNucker
        92
    zzNucker  
       2014-02-21 21:40:14 +08:00
    难道已经默认启用了。
    P233
        93
    P233  
       2014-02-21 23:10:34 +08:00
    @lichgo
    @shiye515
    @otakustay
    @zzNucker

    做了个简单的测试(可能并不严谨),Chrome 下 10000 个 li 元素,page paint time 在 3.4ms - 4.7ms 左右;使用 ul,li {transform: rotate(180deg)} 反转后(不会开启 GPU 加速),骤增到 13.2ms - 16.6ms 左右;translateZ(0) 强制开启 GPU 加速后,page paint time 只有 1.5ms - 1.8ms
    otakustay
        94
    otakustay  
       2014-02-22 00:05:42 +08:00
    @P233 感谢实验,理论上translateZ因为有贴图缓存支持肯定够快,DOM操作可能会因为li中的内容复杂度有很大的区别,而transform我理解应该和内容复杂度关系不呈线性
    mikej
        95
    mikej  
    OP
       2014-02-22 00:17:54 +08:00
    @otakustay
    @zzNucker
    @P233
    研究得够深!都是前端牛人啊。
    lygmqkl
        96
    lygmqkl  
       2014-02-22 01:11:41 +08:00
    做了6年后端了,说实话 五楼的想法让我眼前一亮,web 不只是数据。 哈哈
    P233
        97
    P233  
       2014-02-22 07:03:26 +08:00
    @otakustay 应该是这样的,贴两张测试截图





    开启 GPU 加速后,recalculate 时间竟然增加了很多,但 paint time 毫无疑问减少了
    iLluSioN
        98
    iLluSioN  
       2014-02-22 10:24:08 +08:00
    ……给五楼跪
    jabbany
        99
    jabbany  
       2014-02-23 05:39:30 +08:00
    太机智了.......
    sobigfish
        100
    sobigfish  
       2014-02-26 20:02:44 +08:00
    @siyang1982 也是直接论坛最近回复在前的解决方法
    1  2  
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   2852 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 47ms · UTC 13:42 · PVG 21:42 · LAX 06:42 · JFK 09:42
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.