标签: theory

是否存在统一的缓存理论？也就是说,构建缓存和/或优化它们的定理和算法的集合？

问题是故意广泛的,因为我正在寻找的结果也很广泛.最大可实现加速的公式,缓存算法的指标,类似的东西.大学级的教科书可能是理想的.

首先,愚蠢的标题直接引用了本文:

http://eprints.eemcs.utwente.nl/7281/01/db-utwente-40501F46.pdf

我理解它的理论价值,因为它模拟了大多数(如果不是全部)编程语义.

基于此的编程范例可以最有效和最实际地解决哪些问题？什么问题不是？

想象一下整个程序的编写,其中80%的逻辑涉及这些操作符.我想知道强迫用户操作的语言是否可以利用他们的结构......

听到"高度优化的代码"或某些开发人员需要优化他们和诸如此类的东西,这是常见的.然而,作为一个自学成才的新程序员,我从来没有真正理解人们在谈论这些事情时究竟是什么意思.

关心一般的想法呢？此外,推荐一些阅读材料,无论你想在这件事上说什么.随意咆哮和讲道.

是否存在旅行推销员问题,其中最优解具有交叉边缘？

节点位于xy平面中,因此在这种情况下交叉意味着如果要绘制图形,则连接四个单独节点的两个线段将相交.

在这个流行的问题中,为什么substring在C#中占用O(n),所提出的主要答案之一认为,如果分配了一个大数组,并且通过让新字符串仅引用数组的一小部分来计算子字符串,那么垃圾收集器就会即使原始字符串不再被引用,也无法回收包含较大字符串的字符数组.

这似乎是一个非常有效的答案,但似乎理论上可以为数组构建一个垃圾收集器,允许对大多数数组进行垃圾收集,同时留下一些仍在使用的小型子数组.换句话说,如果有一个5​​0,000个元素的数组,其中只有一个小的100个元素的片仍然在使用,垃圾收集器可以将数组分成三个部分--100个元素切片之前的元素,100个元素切片本身,以及100个元素切片之后的元素 - 然后垃圾收集这些碎片的第一个和最后一个.

我的问题是,任何语言实现是否实际使用这种垃圾收集器,或者它是否仅在理论上存在.有没有人知道一个像这样的垃圾收集器的语言实现的例子？

要清楚,我不是在寻找NaN或无穷大,或者问x/0应该是什么答案.我正在寻找的是:

基于分工是如何在硬件中执行的(我不知道它是怎么做的),如果师们用的0除数来执行,处理器只是通过操作喝着十分满意,你会来的吧？

我意识到这很大程度上取决于股息,所以对于一个具体的答案,我问这样:如果计算机遵循标准的分工操作,计算机会吐出什么42 / 0？

更新:

我会试着更清楚一些.我问的是在位级别用数字完成的实际操作是为了达到解决方案.操作的结果只是位.当发现除数为零时,NaN和错误/异常发挥作用.如果分裂实际发生了,会出现什么位？

我正在阅读Lambda-Cube,我对System F-omega特别感兴趣,它允许"类型操作符",即类型取决于类型.这听起来很像GHC的类型系列.例如

type family Foo a
type instance Foo Int = Int
type instance Foo Float = ...
...

其中实际类型取决于类型参数a.我是否认为类型族是ala系统F-omega类型的一个例子？还是我在左外野？

当我看到有趣的声明时,我正在阅读HashSet上的javadoc:

此类为基本操作提供恒定的时间性能(添加,删除,包含和大小)

这让我很困惑,因为我不明白人们如何能够获得恒定的时间,O(1),比较操作的性能.这是我的想法:

如果这是真的,那么无论我将多少数据转​​储到我的HashSet中,我都能够在恒定时间内访问任何元素.也就是说,如果我在我的HashSet中放入1个元素,它将花费相同的时间来查找它,就好像我有一个googolplex元素.

但是,如果我有一个恒定数量的桶或一致的散列函数,这是不可能的,因为对于任何固定数量的桶,该桶中的元素数量将线性增长(尽管数量很大,但速度很慢) (足够)与集合中的元素数量.

然后,这种方法的唯一方法是每次插入元素时(或每隔几次)更改一个哈希函数.一个简单的哈希函数,永远不会发生任何冲突,满足这种需求.字符串的一个玩具示例可能是:获取字符串的ASCII值并将它们连接在一起(因为添加可能会导致冲突).

但是,这种散列函数以及此类任何其他散列函数可能会因足够大的字符串或数字等而失败.您可以形成的存储桶数量会立即受到您拥有的堆栈/堆空间量等因素的限制. ,不能无限期地跳过内存中的位置,所以你最终必须填补空白.

但是如果在某个时刻重新计算哈希函数,这只能与找到通过N个点的多项式或O(nlogn)一样快.

因此到了我的困惑.虽然我会相信HashSet可以在O(n/B)时间内访问元素,其中B是它决定使用的桶的数量,但我没有看到HashSet如何在O中执行添加或获取函数( 1次.

注意:这篇文章和这篇文章都没有解决我列出的问题.

我最近才知道在Java 8哈希映射中使用二叉树而不是链表,并使用哈希代码作为分支因子.我知道在高冲突的情况下,查找从O(n)减少到O(log n)通过使用二叉树.我的问题是它真正做了什么好处,因为摊销的时间复杂度仍然是O(1)并且如果你强制通过为所有键提供相同的哈希码来存储同一桶中的所有条目可以看到一个显着的时间差异,但没有一个人在他们正确的思想中会这样做.

二进制树比单链表使用更多空间,因为它存储左右节点.当除了一些虚假测试用例之外,当时间复杂度完全没有改善时,为什么增加空间复杂度.

我很好奇Event Loop和Promise之间的关系.
该演示揭示了这个问题.我希望它p1 fulfilled出现在中间,因为它们将任务排队到同一个任务队列并逐个执行.

var p1 = new Promise(function(resolve, reject){
    resolve(1)
})
setTimeout(function(){
  console.log("will be executed at the top of the next Event Loop")
},0)
p1.then(function(value){
  console.log("p1 fulfilled")
})
setTimeout(function(){
  console.log("will be executed at the bottom of the next Event Loop")
},0)

控制台结果是:

p1 fulfilled
will be executed at the top of the next Event Loop
will be executed at the bottom of the next Event Loop

可视化效果显示promise.then回调没有进入事件循环的任务队列.这是正确的？

【注意:问题与Promise vs setTimeout不一样,因为它更关注Event Loop和Promise之间的关系】