Tag: algorithm

如何判断一个数组是否是O（n）中的一个置换？

input：包含从1到N的整数值的N个元素的只读数组（某些整数值可以多次出现！）。 和一个固定大小的存储区（10,100,1000等 – 不依赖于N）。 如何判断O（n）是否代表排列？ – 我到目前为止所取得的成绩（答案certificate这不好）： – 我使用有限的内存区域来存储数组的总和和乘积。 我把这个和与N *（N + 1）/ 2和N的乘积进行比较！ 我知道，如果条件（2）是真的，我可能有一个排列。 我想知道是否有办法certificate条件（2）足以说明我是否有一个置换。 到目前为止，我还没有想出这个…

在多个实体之间同步数据最聪明和简单的方法是什么？

在当今世界，大量计算机，移动设备或Web服务共享数据或像集线器一样工作，同步变得更加重要。 正如我们都知道同步不是最舒适的解决scheme，最好不要同步。 我仍然很好奇你将如何实现一个同步解决scheme来在多个实体之间进行同步。 已经有很多不同的方法，比如比较一个已更改的date字段或散列，并使用最新的数据，或者让用户在冲突情况下select他想使用的内容。 另一种方法是尝试自动合并冲突的数据（在我看来，这并不是那么聪明，因为机器无法猜测用户的意思）。 无论如何，下面是一些与同步相关的问题，我们应该在开始实施同步之前回答： 什么是最近的数据？ 我如何表示呢？ 如果发生冲突，我该怎么办？ 合并？ 我是否提示并询问用户该怎么做？ 当我处于不一致的状态（例如，由于移动式networking连接而断开连接）时，我该怎么办？ 当我不想陷入不一致的状态时，我该怎么办？ 如何恢复当前中断的同步？ 如何处理数据存储（例如，Web服务上的MySQL数据库，iPhone上的Core Data;以及如何合并/同步数据，而不需要大量的胶水代码）？ 我应该如何处理同步期间发生的用户编辑（在后台运行，因此UI未被阻止）？ 我如何以及在哪个方向传播更改（例如，用户在他的计算机上创build“Foo”条目并且不同步;然后他正在移动并创build另一个“Foo”条目;当他尝试同步两个设备时会发生什么）？ 用户是否有两个具有不同唯一ID的“Foo”条目？ 用户只有一个入口，但哪一个？ 我有分层数据时应该如何处理同步？ 自顶向下？ 自下而上？ 我是否以primefaces的方式对待每一个条目，还是只看一个超级节点？ 简单的事情和投入太多的时间之间的权衡有多大？ … 还有很多其他的问题，我希望我能激励你。 同步是一个相当普遍的问题。 一旦find了一个好的，多function的同步方法，应该更容易将其应用于具体应用，而不是从头开始思考。 我意识到，已经有很多应用程序试图解决（或成功解决）同步，但是它们已经相当具体，并且不能给同步方法提供足够的答案。

查找一个点是否在一个凸点内部，而不计算船体本身

testingP点是否在由一组点X构成的凸包内部的最简单方法是什么？ 我想要一个在高维空间（也就是多达40个维度）工作的algorithm，它没有明确计算凸包本身。 有任何想法吗？

给定一个audiostream，find一个门砰的一声（声压级计算？）

与拍手检测器（“拍手！ 拍手拍手拍手！ 拍手拍手拍手，拍手，拍手！ 拍手拍手 ”）不同，我需要检测何时关门。 这是在一辆车，比一个房间或家门更容易： 听着： http : //ubasics.com/so/van_driver_door_closing.wav 看： 这是在16位4khz采样，我想避免大量的样品处理或存储。 当你用大胆或其他波形工具来观察它时，它是非常独特的，并且由于车内声压的增加而几乎总是被剪断 – 即使窗户和其他门打开： 听： http : //ubasics.com/so/van_driverdoorclosing_slidingdoorsopen_windowsopen_engineon.wav 看： 我期望有一个相对简单的algorithm，可以读取4kHz，8位的数据，并跟踪“稳定状态”。 当algorithm检测到声音水平的显着增加时，它将标记该点。 你怎么看？ 你如何检测这个事件？ 有声压级计算的代码示例可能有帮助吗？ 我可以不经常采样（1kHz甚至更慢）吗？ 更新：玩八度（开源数值分析 – 类似于Matlab），看看是否均方根会给我我需要什么（这导致了一些非常类似于SPL） Update2：在简单情况下，计算RMS可以轻松地closures门： 现在我只需要看一下困难的情况（无线电，高温热气等）。 CFAR看起来非常有趣 – 我知道我将不得不使用自适应algorithm，CFAR当然符合这个法案。 -亚当

插入项目或将它们添加到sorting列表后sorting列表是否更快？

如果我有一个sorting列表（比如sorting快速sorting），如果我有很多值要添加，最好是暂停sorting，并将其添加到最后，然后sorting，或使用二进制印章正确放置项目join他们。 如果项目是随机的，或者已经或多或less地有所不同，它会有所作为吗？

O（polylog（n））的含义是什么？ 特别是，polylog（n）是如何定义的？

简要： 当学术（计算机科学）论文说“O（polylog（n））”时，它们是什么意思？ 我没有被我所熟悉的“Big-Oh”符号，而是由函数polylog（n）所迷惑。 他们不是在谈论复杂的分析函数Li s （Z）我认为。 还是他们？ 完全不同的东西也许？ 更多详情： 主要是为了个人兴趣，我最近一直在研究压缩后缀数组的各种论文，例如向后search的优点 – 有效的二级存储器和压缩后缀数组的分布式实现 。 估计的计算复杂度有时涉及到polylog（n），这是我不熟悉的函数。 Wikipedia给出了polylog s （z）的定义，似乎主要是关于复杂的分析和parsing数论。 我的怀疑是，它与压缩文件中的多词（n）没有关系，尽pipe我很乐意听到其他知识渊博的人。 如果是这样的话，为什么认为省略下标是合理的呢？ 我唯一的猜测是，也许O（polylog（n））应该是“渐近于log（n）的多项式函数”。 但这只是一个猜测：我没有证据certificate，这将是一个滥用符号启动。 无论如何，我们将不胜感激一个合理的权威定义。

为什么selectsorting不稳定？

这可能是微不足道的，但我不明白为什么selectsorting的默认实现不稳定？ 在每次迭代中，您会在剩余数组中find最小元素。 当find这个最小值时，可以select你find的第一个最小值，只有当元素小于它时才更新。 所以，在每次迭代中select的元素是第一个最小值 – 这意味着，它是以前的sorting顺序。 所以，就我的理解而言，当前的sorting不会破坏以前sorting的等于元素的顺序。 我错过了什么？

T9字典背后的数据结构

T9字典是如何工作的？ 它背后的数据结构是什么？ 如果我们input“4663”，当我们按下button时，我们会变得“好”，我们会“走出去”，然后“回家”等等。 编辑：如果用户键入46，那么它应该显示“去”，当按下箭头应显示“走了”等…

find高质量和低质量，像素化图像之间的匹配 – 有可能吗？ 怎么样？

我有个问题。 我的公司给了我一个非常无聊的任务。 我们有两个对话框的数据库。 其中一个数据库包含可怕的质量图像，另一个质量很高。 不幸的是，可怕的质量对话包含其他信息的重要映射。 我一直负责手动处理所有不好的图像，并将它们匹配到良好的图像。 是否有可能在任何程度上自动化这个过程？ 以下是两个对话框（从Google图像中随机抽取）的示例： 所以我现在正在用C＃编写一个程序，把这些照片从数据库中拉出来，循环遍历它们，find具有相同形状的照片，然后返回它们的ID。 我最好的select是什么？

目前最先进的HFT交易系统有多快？

你一直听到关于高频交易（HFT）的信息，以及这些algorithm的速度有多快。 但是我想知道 – 这些日子过得怎么样？ 更新 我没有考虑交易所和运行交易应用程序的服务器之间的物理距离造成的延迟，而是程序本身引入的延迟。 更具体的说明：从应用程序中的线路到达该应用程序的事件的时间是多less，在线路上输出一个命令/价格？ 即蜱交易时间。 我们在说毫秒吗？ 还是亚微秒？ 人们如何实现这些延迟？ 在汇编编码？ FPGA的？ 古老的C ++代码？ 更新 最近发表了一篇关于ACM的有趣文章，为今天的HFT技术提供了许多细节，这是一个很好的阅读： 在网关的野蛮人 – 高频交易和交换技术