V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐学习书目
Learn Python the Hard Way
Python Sites
PyPI - Python Package Index
http://diveintopython.org/toc/index.html
Pocoo
值得关注的项目
PyPy
Celery
Jinja2
Read the Docs
gevent
pyenv
virtualenv
Stackless Python
Beautiful Soup
结巴中文分词
Green Unicorn
Sentry
Shovel
Pyflakes
pytest
Python 编程
pep8 Checker
Styles
PEP 8
Google Python Style Guide
Code Style from The Hitchhiker's Guide
carlhan
V2EX  ›  Python

LeetCode 上普遍 C/C++的 runtime 要甩开其他语言 但这个题目却很奇葩

  •  
  •   carlhan ·
    haishanh · 2015-07-06 18:31:50 +08:00 · 3041 次点击
    这是一个创建于 3428 天前的主题,其中的信息可能已经有所发展或是发生改变。

    LeetCode这个题目Python的速度为什么会比C和C++快那么多?

    9 条回复    2015-07-10 18:24:28 +08:00
    Monad
        1
    Monad  
       2015-07-06 18:56:16 +08:00 via iPhone
    目测是被vector::push_back坑了 没有先reserve
    我回去试试
    Monad
        2
    Monad  
       2015-07-06 19:57:16 +08:00
    呃 试了一下并不是…坐等莫非是编译选项不对导致STL太慢了?
    坐等解答
    br00k
        3
    br00k  
       2015-07-06 20:16:11 +08:00
    java已哭晕,貌似再简单基本都在200ms+
    zhyu
        4
    zhyu  
       2015-07-06 20:33:26 +08:00
    快两年前写的,cpp 80ms……
    picasso250
        5
    picasso250  
       2015-07-07 20:02:08 +08:00
    用C写了一个,果然很慢。500+ms

    思路:用二分法找到左边需要复制的,再用二分法找到右边需要复制的,算出 returnSize ,malloc,再用memcpy复制。

    难道这题有什么其他算法?
    alexapollo
        6
    alexapollo  
       2015-07-07 21:21:58 +08:00
    @picasso250 感觉二分法在极限场景不讨好
    picasso250
        7
    picasso250  
       2015-07-08 15:23:01 +08:00
    @alexapollo 对,我最先试验的是顺序查找,结果和二分法差不多。
    ChangxuBlack
        8
    ChangxuBlack  
       2015-07-10 17:39:11 +08:00
    怎么不考虑用线段树啊?
    ChangxuBlack
        9
    ChangxuBlack  
       2015-07-10 18:24:28 +08:00
    会不会是测试数据不一样导致C/C++慢那么多?
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1120 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 23ms · UTC 23:50 · PVG 07:50 · LAX 15:50 · JFK 18:50
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.