标签: computer-science

我正在寻找一种如此未知但有用的算法或数据结构,您认为这是计算机科学或编程社区的可怕疏忽.如果只有我们都可以学习这样一两件事,有很多好会做很多未来的计划.

我能想出的最好的是插值搜索,只有极少数程序员知道,而每个人都知道二进制搜索.我认为毫无疑问,快速搜索有序列表是一种非常有用且基本的算法.

这两者几乎完全相同 - 所以这不是问题.

它对均匀分布的数据执行O(log(log(n))),而不是二进制搜索O(log(n)).这意味着搜索40亿个数字只需要5个探测器而不是32个,那就更好了!

在非完美统一的数据上,它在大多数情况下仍然表现得非常好.只有当数据真正偏离时才会像二进制搜索一样糟糕或者更糟糕.当数据高度偏斜时,这是O(n)最坏的情况,但在大多数现实情况下这种情况非常罕见.

即便如此,人们也可以构造一个偶数/奇数算法来在两者之间交替,并得到最差的二分搜索情况,并使用插值搜索的平均情况来缓解极端情况.

大多数程序员/图书馆都忽略了这一点.

谁能打败那个人？

当我们开始进入算法设计和更多离散的计算机科学主题时,我们最终必须一直在证明事物.每当我看到有人问如何变得非常擅长证明时,常见的(也可能是懒惰的)答案就是"练习".

如果你掌握了基础知识,那么练习就没有问题,但是你如何进入数学证明的思维定势？什么时候感应点击？哪些资源最适合教授这些主题？在沉迷于校对之前,应该研究哪些基础课题？

我正在复习算法和数据结构.

我对树的深度与高度的概念感到困惑.在许多情况下,特别是在关注面试评估的网站上,在我看来,这些术语可以互换使用.

在我看来,基本的文学将它们定义为适用于节点并不会在一棵树上.

所以根(它是一个节点)的深度是0.根(或任何子节点)的高度是其子节点的最大高度.

但是当你在树上应用这些术语,即找到树的最大深度时,似乎这些术语现在是"无意义的"并且可以互换使用,即找到最大深度只计算最大高度.

例如,在这篇文章中检查树是否平衡,答案集中在树的高度,而平衡的定义可以在树的深度上

我的理解是正确的还是我搞砸了这些基本原理？

流行的C++编译器使用什么算法用于std :: sort和std :: stable_sort？我知道标准只提供了某些性能要求,但我想知道流行实现在实践中使用哪些算法.

如果引用每个实现的引用,答案会更有用.

当我需要一些复杂的算法时,我首先检查互联网上是否已发布任何相关内容.十分之十,我会发现有人已经找到了比我想象的更聪明的解决方案.

除了通用的Google搜索,我使用:

• Citeseer 有很多来自大学的理论报告
• Dobb博士的门户比Citeseer更实用,但往往对特定技术或语言过于具体
• Arxiv更理论包含草稿和预印本(以防万一我绝望:))

我还发现了J.UCS(通用计算机科学杂志)包含一些有趣的文章(但我没有真正使用过我在那里发现的任何信息).

你知道其他任何可以免费搜索和阅读好CS文章的地方吗？

我最近问了一个关于Dijkstra算法之一的问题(shunting-yard).但几乎所有人都认为"Dijkstra算法"意味着他的最短路径算法.

Dijkstra开发了哪些其他算法？

我将在大学学习Ruby,Haskell和Prolog.现在,我想知道什么应该得到我的大部分注意力.我有半年的时间来做这三个,这意味着我需要决定一种语言来获得我的课外时间.其他我将学到的就是在课程中做得非常好.

我对Haskell和Prolog很熟悉,知道学习它们会教会我一些非常重要的计算机科学概念.我不太确定红宝石.

通过一些教程和介绍,我得到的印象是红宝石有很多浅薄的魔力.现在我问红宝石人:在我花了半年的时间学习它之后,我决定再也不用它了,我会得到什么,Python还没教过我.

这个问题并非旨在为红宝石"提出理由",尽管我意识到这是一个很有争议的潜在话题.

我现在使用Python进行所有CS工作.我也用它做了很多函数式编程.我也已经非常熟悉面向对象编程(在Java,Python和C#中).正如我所说,我会用Prolog做一些逻辑编程.

然后留给Ruby教我什么？

进一步淡化问题:

• 我对编写有趣的程序或酷的Web应用程序不感兴趣.我只对计算机科学课感兴趣.实现算法,数据结构等.(虽然玩得开心肯定不会受伤)

• 理想情况下,所讨论的概念需要在大约1.000小时内可以学习.

• 我对Rails一点也不感兴趣.在这种情况下,任何隐藏复杂性的技术都是有害的.

我无法帮助这个问题具有争议性.但是这个问题的理想答案将提到一个非常重要的理论计算机科学概念,红宝石帮助程序员使用和理解,以获得科学的辅助知识.

我想到的候选人是元编程和多线程.我不知道红宝石是否特别适合学习其中任何一种.

我找不到主要的区别.当我们可以使用继承并且我们可以使用子类型时,我很困惑.我找到了一些定义,但不是很清楚.

面向对象编程中的子类型和继承有什么区别？

从纯计算机科学(或计算语言学)的角度来看,我想知道这些词之间的区别:

• 装饰
• 属性
• 方面
• 特征

各种语言以不同的方式使用这些单词和功能.在Python中,例如,Decorators [根据Python Wiki](强调我的):

装饰器动态地改变函数,方法或类的功能,而不必直接使用子类或更改正在装饰的函数的源代码.

这让我感觉非常类似于面向方面的编程工具,如PostSharp或DynamicProxy.即:

   [Profile]
   private static void SleepSync()
   {
       Thread.Sleep(200);
   }

来源:PostSharp示例

在C#和Java(以及无数其他语言)中,属性可以表示Decorator-ish模式(C#)或字段(Java).

在C++中通过boost或PhP通过内置特征词,我们可以使用特征来扩展类,如下所示:https://en.wikipedia.org/wiki/Trait_ (computer_programming)

因此,从"纯粹"的角度来看,所有这些实际上是什么的规范定义是什么？有没有更好的方法来定义它们？

更具体地说，在编程中，当我们指的是另一段代码运行所需的软件组件时，我们使用术语“依赖” 。

您将需要依赖项才能运行的那段代码称为什么？我想我不知道这个词从相反的角度代表了这种关系。