学习算法到意义是什么

北美农民 发表于 2013-11-22 16:12
感觉之前都白说了。我的观点一直是在于硬件软件鸿沟现实下的对比， 而你单独拎出算法讲多么多么重要，这不 ...

你讲得好的地方我前面就赞同了，我不懂的领域也说得很清楚，至于你瞎扯的地方当然要拍。

你首先假设大多数程序的瓶颈是IO和Disk/Memory之间的数据交换，证据在哪儿？在不同的领域，程序的瓶颈差异很大，你依据什么做出上述结论？就算只讨论瓶颈是Disk/Memory的程序，你根本就没考虑到估计算法时间复杂度时候的模型假设，想当然的认为算法就是只考虑普通指令执行的数量。举个最简单的例子，external sorting algorithms，目标就是在对存储于disk而非memory中的数据进行排序并尽量减少disk/memory之间数据交换的次数。这和你提高硬盘单次读写速度的优化有相互制约的关系？问题都没弄清楚还大谈特谈短板。
. 1point3acres.com
我举ML算法的例子就是为了说明算法不仅是运行快慢的问题，还解决原本不可能的问题。这与楼主的问题“学习算法的意义是什么”没有偏离。好，既然限制只谈速度，那就不用这个例子。就说SMT solver的例子，这个问题的瓶颈很明显就不是IO和数据交换。很多theory本身就是npc甚至undecidable的。你用普通brute-force算法能求解？用高级的算法是不是大大提高了速度？

我前面说的小创新很明确地是举了Python JIT的例子。你转进到其他领域干嘛？我有说过这些东西不是重大突破？我前面早就承认我在这方面很无知了，不具备评价资格。

论文我还没有读完，抱歉，毕竟不是我最熟悉的领域。我读完了自然会单独回一帖。

你说得很对，评价自己懂的领域比什么都强。最糟糕的是懂得几个名词和概念不求甚解，缺乏考证就堆砌起来做为论据。简单的问题就用简单的话和例子来说明，这样对楼主或者后来人都有帮助。堆术语大家都会，没什么意思。

北美农民 发表于 2013-11-22 16:39
. 1point 3 acres挺有意思的，截去上下文说我说算法意义不大自然是另外一层意思了。  本来还以为能学到点什么呢， 罢了。

有点争论总比现在整版死气沉沉的水贴好。要我说，这种帖就应该大家一起来吵，把楼盖起来然后置顶。省得过几天又有人发帖问同样的问题。

lyl 同学态度其实还挺好的

lyl 发表于 2013-11-22 13:09
你讲得好的地方我前面就赞同了，我不懂的领域也说得很清楚，至于你瞎扯的地方当然要拍。

你首先假设大 ...

"你首先假设大多数程序的瓶颈是IO和Disk/Memory之间的数据交换，证据在哪儿？"

很显然，我从头到尾指的都是计算机的运行的performance, 也就是硬件和软件的交互。
我想你误解了一个概念，计算机运行的瓶颈不是程序运行的瓶颈， 程序运行的瓶颈是 数据结构+算法+translate到可执行代码的质量
计算机运行的步骤我上个回复已经说过了。执行instr集只是计算机运行的一步而已， 算法数据结构也只是提高instr质量3个因素中的
2个。

回到正题， 其实看到这句觉得挺好笑的， 有空闲问我要这种常识性的证据还不如自己去连几个服务器或者谷歌两把关键字。行，你要证据那我替你谷歌一把http://laris.fesb.hr/predavanja/memorija.html， 见第一幅曲线图，这还是DRAM，而I/O的结果只会更糟。
请你告诉我， 你认为影响计算机performance和UE的瓶颈是什么？

”举个最简单的例子，external sorting algorithms，目标就是在对存储于disk而非memory中的数据进行排序并尽量减少disk/memory之间数据交换的次数。“

sorting算法是有严格证明下界的， 但是数据的交换速度没人知道能提高多少。 相反，我觉得如果直接在hard disk上排序， 这样更加证明了disk性能硬件的重要性，
算法是有严格下界的， 而disk不见得。请问你这是在支持我的观点吗？

”这和你提高硬盘单次读写速度的优化有相互制约的关系？问题都没弄清楚还大谈特谈短板。“

我觉得我不止一次提到他们并不冲突，可以同时提高同时改善。 把我没说过的话扣我头上这种把戏一而再出现有意思？
我的原话是研究别的方向的提高空间和投入产出比要更高，因为短板并不是算法。

”我举ML算法的例子就是为了说明算法不仅是运行快慢的问题，还解决原本不可能的问题。这与楼主的问题“学习算法的意义是什么”没有偏离。“
同意这句。

”好，既然限制只谈速度，那就不用这个例子。就说SMT solver的例子，这个问题的瓶颈很明显就不是IO和数据交换。很多theory本身就是npc甚至undecidable的。你用普通brute-force算法能求解？用高级的算法是不是大大提高了速度？“

NPC问题只能多项式复杂度验证是否最优而没有多项式算法去寻找最优, 方法大多数是类似A*, ANNEALING， GREEDY等启发式算法寻找尽量优的解，谁会用brute-force去寻找最优解？而且拿brute-force来比你不觉得很掉价？ 至少拿两个差别不大的NPC问题的启发式算法做例子啊？最关键的是，你用brute-force证明高级算法的重要性并不能支持目前提高算法比提高别的方面更有价值。

”我前面说的小创新很明确地是举了Python JIT的例子“

”小创新“这样的主观词汇，对我以及很多人来说并不是什么convincing的东西.

”最糟糕的是懂得几个名词和概念不求甚解，缺乏考证就堆砌起来做为论据。“
我挺喜欢算法， 也乐意了解算法。 而且目前为止给出文献，链接，数据的也是我。 敢问缺乏考证是在说我吗？

”有点争论总比现在整版死气沉沉的水贴好。要我说，这种帖就应该大家一起来吵，把楼盖起来然后置顶。省得过几天又有人发帖问同样的问题。“

个人觉得这样质量的交流收获并不大，不值得置顶。

我不打算继续了， 留给LZ和他人自辨吧。

小K 发表于 2013-11-22 14:26
lyl 同学态度其实还挺好的

是挺不错的， 不过感觉互相都没讨论到点上。

北美农民 发表于 2013-11-22 14:33
是挺不错的， 不过感觉互相都没讨论到点上。

agree to disagree 好了

北美农民 发表于 2013-11-23 03:30
"你首先假设大多数程序的瓶颈是IO和Disk/Memory之间的数据交换，证据在哪儿？"

很显然，我从头到尾指的 ...

真是白说了。我说的很清楚算法分析的模型要具体情况具体分析，不能随便就把IO什么的从算法分析里面剔除。其次，我后半句话就说了不同的application domain，性能瓶颈的原因相差很大，好好看着。

“在cpu和disk/memory性能的鸿沟下， 算法的意义并不是那么大就是了”这句话是你说的。我和之前一样完全不同意。既然你如此坚持，那也可能是我错了。或许目前在工业界的大多数user application就是这个情况，我完全不了解。但是不加条件的限制而把这句话当成真理，就是瞎扯。

小创新这样的主观词汇确实很不严谨，不过至少也是建立在我读了部分论文和作者自己写的介绍文章里面得出的结论。

缺乏考证说的就是你。JIT技术的发展进程你自己都不了解就敢用它来证明工业界技术领先学术界？恐怕你的论文也是现搜的，连related work那一小节都没看到吧？另外就在作者自己写的blog文章，很明白地列出了其他的好几个Python JIT编译器，这些你有至少扫一眼么？

最后再说论文，HotPar'12的论文，引用数为2。虽然不能仅从引用数就断言论文的价值，不过你把它做为证明工业界技术领先学术界的大创新不觉得搞笑么。这样的research，每年顶级会议的论文多少篇不至少是这个级别或以上的？这些论文有多少出自学术界多少出自工业界，你有至少把accepted papers扫一眼？

有一方信口开河而不加考证的交流价值当然会降低。

lyl 发表于 2013-11-22 15:15
真是白说了。我说的很清楚算法分析的模型要具体情况具体分析，不能随便就把IO什么的从算法分析里面剔除。 ...

什么app domain领域你说就是了。你告诉我业界哪些application应用在计算机上是不存在I/O 和mem瓶颈，哪些application算法的该进比改变硬件要大的多，什么external sorting算法改善了performance， 什么NPC问题的算法带来了压倒性的性能提高不就行了，什么具体事情具体分析这种套话和没说一样。 来点具体的，链接，相关的背景，性能测试都可以，我都很乐意学习。


你说话很不负责，曲解我意思不多计较了。 你说没我证据， 随手一搜就有的东西， 给出了又在这扯些没用的。。证据面前能给个准信很难？什么叫做”但是不加条件的限制而把这句话当成真理，就是瞎扯。“　你再回头看看我强调了多少次的东西，居然被说成不加条件限制。 你说编译器能提高有限的百分之几十就不错了。我给了你java的JIT如何使得java performance反超c++的lab和benchmark吧？ jdk 1.2到1.6性能的提高非常悬殊， 你正面回应了吗？ 没有。 我还给了你python的jit， 代码是开源的， 你自己测试一下就知道parakeet性能如何（benchmark和test都在这，https://github.com/iskandr/parakeet/tree/master/benchmarks），parakeet也是我在实验室干活自己用的东西，你倒好，随便一句说是我搜的。行， JIT我的确不懂，paper我也的确没读过，你说这个产品可能采用了学术界的idea也行， 但你得说点实在的让我信服的东西 。扯什么related work，这个related work的paper指不好还是起源于另一个工业界产品。
你说你不懂的地方我都跳过忽略了，刚好JIT在用所以提了出来。其实我涉猎稍微多一点的地方是分布式, 你说我扯术语玩虚的还真是冤枉。piccolo，mapreduce, dryad, paxos, bayou, RSM, 2PN,2PL，各种FS, 各种concurrency control, 各种fault tolerance模型， 各种consistency协议这些我都没说呢。 他们哪些是工业界的产品哪些是学术界的理论我都知道一些。 你要乐于自己考证我可以全部告诉你这一块工业界是如何领先的。 不过鉴于现在这样子我也觉得没什么必要了。

. 1point3acres

北美农民 发表于 2013-11-23 05:52
什么app domain领域你说就是了。你告诉我业界哪些application应用在计算机上是不存在I/O 和mem瓶颈，哪些 ...

我就挑比较著名的几个例子。
编译器领域，Static Single Assignment (SSA) form是大多数优化的基础，但是直到91年这篇论文之前R. Cytron, J. Ferrante, B. Rosen, M. Wegman, and K. Zadeck. Efficiently Computing Static Single Assignment Form and the Control Dependence Graph，构造SSA的算法速度太慢以至于SSA form被认为不实用。在那之后，大多数编译器包括GCC,LLVM都采用了SSA form。
Formal method领域，著名的model checking论文Symbolic Model Checking: 1020 States and Beyond首次将model checking能够探索的状态数提高到了1020。之后94年Pentium芯片设计有bug，整条生产线都要替换掉，Intel损失了很多钱。Model checking被证实可以发现这个bug，从此formal methods被广泛应用于硬件设计领域。
. 1point3acres.com 软件工程领域，由于Constraint solver的算法速度越来越快，很多基于constraint solving的应用才得以变得实用，包括symbolic execution, dynamic test generation, program synthesis。

这些技术如果单靠摩尔定律的累积作用，只怕现在都没办法用上。

关于Java JIT性能提升显著的例子我早就知道，不用你科普。我当时说的不准确。我实际上指的是Proebsting’s Law，即编译优化技术的提升导致程序效率翻番的周期大约是18年。jdk 1.2到1.6之间的性能提升更多是jdk逐渐成熟的结果，跟我说的不矛盾。更何况，这都不是重点。结合上下文语境，我当时想表达的是人家辛辛苦苦发明各种优化技术就为了提高那点常数，你倒好，直接把nlogn变成n^2还大言不惭没差别。

别装可怜，我上面说得是你论文是现搜的。看清楚再发言。

呵呵，你可以堆分布式方面的术语。我也可以堆我擅长方向的术语啊。有意思么？不过是对解释问题没有帮助的显摆而已。既然你分布式懂得多那你愿意就介绍一下工业界如何领先呗。我又没否定我不了解领域的情况。我也可以介绍software engineering, programming languages, formal methods, compilers方向学术界是如何走在工业界的前面。别人也可以介绍一下systems, architecture, networks, machine learning, artificial intelligence,security领域的情况。不要为了反对而反对，下结论严谨一些，在"CS领域"前面加个"某些"就没人说你了。

工业界的研究必然是driven-by-need，需要的是中短期能得到结果的东西。目标的不同也就决定了工业界不会在更加困难而短期看不到收益的领域里投入大量的财力。而学术界的研究就是捣鼓这些未来可能有用也可能没用的东西。只要明白了这一点，就不会随便说出CS领域工业界技术领先学术界这样的笑话了。

lyl 发表于 2013-11-22 22:52
我就挑比较著名的几个例子。
编译器领域，Static Single Assignment (SSA) form是大多数优化的基础，但是 ...

呵呵我想你误会了，我所指的领先是存在，是exist, 而非任意，不是for sufficient large areas， 进一步的观点是有相当一部分的exist。 倘若我的观点是任意大方向任意sub-areas都适用，这是毫无疑问不需要反驳的， 真是这样如此以来学术界存在的意义是什么？ 而且我在第二页第一个回复就说过定语”最近10年“，你选择性的无视说些打不着点的话, 引用90年代的论文作为举例并不能反驳什么，按照你的风格总能找到沾亲带故藕断丝连，所有的应用都用到了前人的理论前人的理论基础，无理取闹。
计算机科学的发展本来也是站在前人的肩膀上一步一步走到今天， 如果什么都要抠理论依据找源头证明这玩意应用的理论基础来自于学术界，没有意义，你不如直接说ENIAC的诞生就是在宾大的成果好了（事实上有发明者之一也是工程师）。可即便如此， 难道Bell Lab发明的晶体管，TI做出的IC， INTEL做出的4004(我得承认4004是谷歌出来的)直接推动了第二代，第三代，第四代计算机以及PC的问世就不算了吗？ 工业界的贡献就一定比祖师爷ENIAC小吗？ 此外ENIAC之前也存在更原始的计算机雏形，由于印象不深就不再深追了，深追到源头恐怕对你所支持的学术界更不利。另外一方面， 正是有了2，3代计算机才使得高级PL和编译器出现，这就更有意思了，第一个编译器是IBMFortran团队开发的。（抱歉弄错了，谷歌了编译器的雏形是ＥM公司的一名女程序员grace hopper写的）， 如果追溯编译器的源头似乎对你更不利哦~。

关于时间复杂度那个例子，之前我表态过了 N^2和NlogN的例子的确有夸张， 但我还说过也不算过分。 一个证据是OS里的Process Scheduling算法，用heap维护priority和用线性表维护，前者插入删除取出的复杂度分别是大O logN, logN, 1后者是大O N,N和1。 但是AVG CPU burst time, AVG waiting time, AVG CPU的利用率差别非常小， 而主要都消耗在I/O time上。这样的实验你自己都能做。这也是我说这个例子并不算过分的原因， 但是我还说了，如果是科学计算即使是常数时间的差别都很大， 你怎么就无视了呢？

这么久了我最想听东西你还是没说，也就是你对那篇论文idea和评价。那篇论文的ideas我晚上刚好请教了作者本人Alex，听起来其实挺简单的，主要idea是把phython代码转化成了C，似乎并不是什么高深理论，不过implement起来就未知了。 也许牛人总喜欢把东西解释得很简单吧。 当然这依旧也许是你口中的小创新而已。 嗯，带来前所未有的提高的小创新而已。 此外Proebsting’s Law是无法解释你所谓早就知道的但是说出自相矛盾结论的JDK的， JDK无论是跟早先自身比（纵向）， 还是和别的编译器比（比如g++， 横向）都有悬殊的提高， 如果这个law灵验那么应该是纵向提高显著而横向不显著。 像这类XX Law基本就是通过业界产品产能进步速度而做出的规律总结， 别当一回事了。




我从来不会为反驳而反驳， 这是很幼稚的表现， 而这2页你给我的感觉是你反驳都反驳不到点上，正面回应的point非常有限，我开始觉得这是浪费时间了。