Tag: 算法

编辑距离递归算法 – Skiena

我正在阅读Steven Skiena撰写的算法设计手册，我正在动态编程章节。 他有一些编辑距离的示例代码，并使用了一些既不在书中也不在互联网上解释的function。 所以我很想知道 a）该算法如何工作？ b）indel和match函数有什么作用？ #define MATCH 0 /* enumerated type symbol for match */ #define INSERT 1 /* enumerated type symbol for insert */ #define DELETE 2 /* enumerated type symbol for delete */ int string_compare(char *s, char *t, int i, int j) { int k; /* counter */ int opt[3]; /* cost […]

两个一般六面体之间的碰撞检测

我有2个六面体。 唯一的保证是它们每个都有8个vertex3f（带有x，y和z分量的顶点）。 鉴于此，如何判断这些是否发生碰撞？

为什么以null结尾的字符串？ 或者：以空值终止与字符+长度存储

我正在用C编写语言解释器，我的string类型包含一个length属性，如下所示： struct String { char* characters; size_t length; }; 因此，我必须在我的解释器中花费大量时间手动处理这种字符串，因为C不包含对它的内置支持。 我考虑过切换到简单的以null结尾的字符串只是为了符合底层C，但似乎有很多理由不： 如果使用“length”而不是查找null，则内置边界检查。 您必须遍历整个字符串才能找到它的长度。 你必须做额外的事情来处理以null结尾的字符串中间的空字符。 以空值终止的字符串与Unicode处理不佳。 非空终止字符串可以实习更多，即“Hello，world”和“Hello”的字符可以存储在同一个地方，只是具有不同的长度。 使用以null结尾的字符串无法做到这一点。 字符串切片（注意：字符串在我的语言中是不可变的）。 显然第二个更慢（并且更容易出错：考虑添加对两个函数的begin和end错误检查）。 struct String slice(struct String in, size_t begin, size_t end) { struct String out; out.characters = in.characters + begin; out.length = end – begin; return out; } char* slice(char* in, size_t begin, size_t end) { char* out […]

当所有元素相同时，Quicksort的复杂性？

我有一个N个数字的数组是相同的。我正在应用快速排序。 在这种情况下，排序的时间复杂度应该是多少。 我盯着这个问题，但没有得到确切的解释。 任何帮助，将不胜感激。

连接/合并/连接两个AVL树

假设我有两个AVL树，并且第一个树中的每个元素都小于第二个树中的任何元素。 将它们连接成一个单独的AVL树的最有效方法是什么？ 我到处搜索，但没有找到任何有用的东西。

搜索快速/有效的直方图算法（带有预先指定的箱）

我没有在Matlab之外做太多编码，但我需要将我的Matlab代码导出到另一种语言，很可能是C.我的Matlab代码包括一个直方图函数histc（），它放置我的输入数据（这是双-precision，而不是整数）到指定的bin数组中，形成直方图。 我确信我可以拼凑几个嵌套循环来生成直方图函数，但我需要这个函数快速和内存轻，因为它将被重复和经常访问。 为了避免重新发明轮子，任何人都知道C语言是否有任何现有的直方图function可供使用，或者是否需要这样的人通常自己创建它？ 有人知道创建直方图的有效算法吗？ 伪代码很好。 提前致谢。

最佳的机器优化多项式极小极大近似于上的反正切？

为了以合理的精度简单有效地实现快速数学函数，多项式极小极大近似通常是选择的方法。 Minimax近似通常使用Remez算法的变体生成。 各种广泛使用的工具，如Maple和Mathematica，都具有内置function。 通常使用高精度算术来计算生成的系数。 众所周知，简单地将这些系数舍入到机器精度会导致所得实现中的次优精度。 相反，人们搜索密切相关的系数集合，这些系数可以精确地表示为机器编号，以生成机器优化的近似值。 两篇相关论文是： Nicolas Brisebarre，Jean-Michel Muller和Arnaud Tisserand，“计算机高效多项式近似”，ACM数学软件交易，Vol。 32，第2期，2006年6月，第236-256页。 Nicolas Brisebarre和Sylvain Chevillard，“高效多项式L∞近似”，第18届IEEE计算机算术研讨会（ARITH-18），蒙彼利埃（法国），2007年6月，第169-176页。 来自后一篇论文的LLL算法的实现可以作为Sollya工具的fpminimax()命令获得。 我的理解是，所有用于生成机器优化近似的算法都是基于启发式算法，因此通常不知道通过最佳近似可以实现什么样的精度。 我不清楚用于评估近似的FMA（融合乘法 – 加法）的可用性是否对该问题的答案有影响。 在我看来它应该是天真的。 我目前正在研究[-1,1]上的反正切的简单多项式近似，其在IEEE-754单精度算法中使用Horner方案和FMA进行评估。 请参阅下面的C99代码中的函数atan_poly() 。 由于目前无法访问Linux机器，我没有使用Sollya来生成这些系数，而是使用了我自己的启发式算法，可以将其简单地描述为最陡的体面和模拟退火的混合（以避免陷入局部最小值） 。 机器优化多项式的最大误差非常接近1 ulp，但理想情况下我希望最大ulp误差低于1 ulp。 我知道我可以改变我的计算以提高精度，例如使用表示超过单精度精度的前导系数，但我想保持代码完全一样（即尽可能简单）仅调整系数以提供最准确的结果。 “经过validation的”最佳系数集将是理想的，欢迎指向相关文献的指针。 我进行了一次文献检索，但找不到任何有助于超越Sollya的fpminimax() ，并且没有任何文章能够检查FMA（如果有的话）在这个问题上的作用。 // max ulp err = 1.03143 float atan_poly (float a) { float r, s; s = a * a; r = 0x1.7ed1ccp-9f; […]

strstr比算法快？

我有一个21056字节的文件。 我在C中编写了一个程序，将整个文件读入缓冲区，然后使用多个搜索算法在文件中搜索82个字符的标记。 我已经使用了“精确字符串匹配算法”页面中所有算法的实现。 我用过：KMP，BM，TBM和Horspool。 然后我使用strstr并对每个人进行基准测试。 我想知道的是，每次strstr优于所有其他算法。 有时候唯一更快的是BM。 不应该是最慢的吗？ 这是我的基准代码，其中包含基准测试BM的示例： double get_time() { LARGE_INTEGER t, f; QueryPerformanceCounter(&t); QueryPerformanceFrequency(&f); return (double)t.QuadPart/(double)f.QuadPart; } before = get_time(); BM(token, strlen(token), buffer, len); after = get_time(); printf(“Time: %f\n\n”, after – before); 有人可以向我解释为什么strstr优于其他搜索算法吗？ 如果需要，我会根据请求发布更多代码。

设计一个支持海量数据存储和查询的系统

面试官要求我设计一个存储千兆字节数据的系统，系统也必须支持某种查询。 描述： 在IDC中生成大量记录，每个记录由URL，访问URL的IP以及访问发生的时间组成。 该记录可能被声明为这样的结构，但我不确定应该选择哪种数据类型来代表它们： struct Record { url; //char * IP; //int? visit_time; //time_t or simply a number? } 要求： 设计一个存储1000亿条记录的系统，系统至少支持2种查询： 首先，给定时间段（t1，t2）和IP，查询该IP在给定时间段内访问了多少URL。 其次，给定时间段（t1，t2）和URL，查询该URL被访问的次数。 我被绊倒了，这是我的愚蠢解决方案： 分析： 因为每个查询都是在给定的时间段内执行的 ，所以： 1. 创建一个集合 ，将所有访问时间放入集合中，并根据从旧到最新的时间值保持集合的顺序。 2. 使用散列（visit_time）作为键创建散列表，该散列表称为时间散列表，然后特定桶中的每个节点 具有分别指向另外2个散列表的2个指针 。 另外两个哈希表是ip-hash-table和url-hash-table 。 ip-hash-table使用hash（ip）作为密钥，同一ip-hash-table中的所有ips具有相同的访问时间; url-hash-table使用hash（url）作为密钥，同一url-hash-table中的所有url都具有相同的访问时间。 给出如下图纸： time_hastbl [] [] []–>[visit_time_i]–>[visit_time_j]…[visit_time_p]–>NIL [] | | [] ip_hastbl url_hastbl [] [] : : [] [] […]

算法和数据结构最适合拼写检查器，字典和同义词库

实施的最佳方式 字典（有没有比Trie for Dictionary更好的DS） 词库（不知道，因为词语的含义相似，含义相似） 拼写检查器（比哈希映射更好的东西），如果可能的话，使用正确的拼写建议。 当在一小时的采访中被问到时，我们是否希望为算法编写ac / c ++代码？