Tag: 算法

C将内存部件移动到位

我正在实现几个数据结构和一个我要使用的原语如下：我有一个内存块A [N]（它有一个可变长度，但我的示例为100）并且在这个块中，有一个较小的部分长度为K的C（比方说30）我想要移动而不使用任何额外的内存。 另外的困难是，A“包裹”，即C可以从A [80]开始，然后C的前20个元素是元素A [80..100]，最后10个元素是元素A [ 0..10]。 此外，目标范围还可以以任何可能的方式“包裹”并与C重叠。 另外，我不想使用超过一定数量的额外内存，一切都应该到位。 此外，既不在目标范围内也不在源范围内的A部分可能包含重要的内容，因此也不能使用。 所以一个案例如下： A看起来像这样： | 456789ABCDEF0123456789AB | —– | 0123 | 应该转变为： | 89AB | —– | 0123456789ABCDEF01234567 | 只是将它委托给一个库或者从库中使用另一个数据结构不是一个选项，我想自己理解这个问题。 在第一眼看来，我认为这可能不是微不足道的，但是一旦你区分了几个案例，它就会变得清晰，但现在我遇到了严重的麻烦。 当然，如果它们不重叠或不包装，则存在微不足道的情况，但至少如果两者同时发生，则会变得混乱。 你可以从一个自由的地方开始并移动属于那里的部分，然后你在其他地方创建另一个免费部分，很难跟踪你可以使用哪些部分。 也许我完全错过了一些东西，但即使我的特殊情况，如果目标范围没有包装也有近100行（虽然它的一半是断言和注释）我可以更新它以便它也处理一般情况下一些额外的索引计算，但如果有人有一个优雅而简短的解决方案，我将不胜感激。 直觉上我认为这应该是微不足道的，但我还没有看到最好的解决方案。 注意：有趣的情况当然是，如果C几乎和A一样大。如果| C | <N / 2，这是微不足道的。 编辑：使用超过一定量的额外标志/索引计数作为额外的内存，我想尽可能避免这种情况。 编辑：有些人想看我的代码。 我的问题相当抽象，所以我不想发布它，但也许有人看到了如何改进它。 这很糟糕，它只适用于目标从头开始（但是，可以很容易地改变）并且非常长的情况，但它可以在O（n）中没有额外的内存。 #include #include #include #include void move_part(int* A, size_t N, size_t target, size_t […]

理解strlen实现中的代码

关于glibc中string.h中strlen的实现，我有两个问题。 该实现使用带有’holes’的幻数。 我无法理解这是如何工作的。 有人可以帮我理解这个片段： size_t strlen (const char *str) { const char *char_ptr; const unsigned long int *longword_ptr; unsigned long int longword, himagic, lomagic; /* Handle the first few characters by reading one character at a time. Do this until CHAR_PTR is aligned on a longword boundary. */ for (char_ptr = str; ((unsigned long int) […]

你是一个素数

我对多年来寻找更好的素数识别器的问题感兴趣。 我意识到这是一个巨大的学术研究和研究领域 – 我对此感兴趣只是为了好玩。 这是我在C（下面）中首次尝试可能的解决方案。 我的问题是，你能否提出一个改进（没有引用网上的其他参考，我正在寻找实际的C代码）？ 我想从中获得的是更好地理解确定这样的解决方案的性能复杂性。 我是否正确地得出结论，这个解决方案的复杂性是O（n ^ 2）？ #include #include /* isprime */ /* Test if each number in the list from stdin is prime. */ /* Output will only print the prime numbers in the list. */ int main(int argc, char* argv[]) { int returnValue = 0; int i; int ceiling; int […]

计算立方贝塞尔长度的便宜方法

对于立方贝塞尔长度的解析解似乎不存在，但这并不意味着不存在编码廉价解的编码。 便宜我的意思是在50-100 ns（或更少）的范围内。 有人知道这样的事吗？ 也许有两类： 1）较少的错误，如1％但更慢的代码。 2）更多错误如20％但更快？ 我通过谷歌扫描了一下，但它没有找到任何看起来像一个很好的解决方案。 只有像划分N个线段并将N sqrt相加的东西 – 太慢以获得更高的精度，并且对于2或3个段可能太不准确。 有更好的吗？

使用一组有限的操作对2个50000个数字的链表进行排序

所以我有这个项目用于学校：我有一个包含5万个数字和第二个空列表的链表。 我只有一个非常有限的指示小组。 他们是 ： “sa”交换了列表1的前两个元素 “sb”交换了清单2的前两个元素 “ss”同时是“sa”和“sb” “pa”：在列表1的顶部推送列表2的顶部元素 “pb”：在列表2的顶部推送列表1的顶部元素 “ra”：旋转列表1（第一个元素成为最后一个） “rb”：旋转列表2（第一个成为最后一个） “rr”：“ra”和“rb”立刻 “rra”：旋转列表1（最后成为第一个） “rrb”：旋转列表2（最后成为第一个） “rrr”：“rra”和“rrb”立刻 我必须在c中实现排序算法，目标是使用最少量的指令。 我尝试了一个非常简单的算法，旋转列表一直到最大值位于顶部，然后反复将其推入列表2，直到所有内容都在列表2中，然后将所有内容推回到列表1中，但我无法对列表进行排序在合理的时间内超过5k的数字

在文件系统中存储大量文件

我有数百万个音频文件 ，基于GUId（ http://en.wikipedia.org/wiki/Globally_Unique_Identifier ）生成。 如何将这些文件存储在文件系统中，以便我可以在同一文件系统中有效地添加更多文件 ，并可以有效地 搜索特定文件。 它也应该在未来可扩展。 文件基于GUId（唯一文件名）命名。 例如： [1] 63f4c070-0ab2-102d-adcb-0015f22e2e5c [2] ba7cd610-f268-102c-b5ac-0013d4a7a2d6 [3] d03cf036-0ab2-102d-adcb-0015f22e2e5c [4] d3655a36-0ab3-102d-adcb-0015f22e2e5c PL。 发表你的看法。 PS：我已经完成了。 我需要特定的数据结构/算法/逻辑，以便将来也可以扩展 。 EDIT1：文件数量约为1-2百万，文件系统为ext3（CentOS）。 谢谢， 纳文

查找整数分区的字典顺序

对于排列，给定N和k ，我有一个函数，它以字典顺序找到N第k个排列。 另外，给定一个置换perm ，我有一个函数，可以在N所有排列中找到排列的词典索引。 为此，我使用了本答案中建议的“因子分解”。 现在我想对N整数分区做同样的事情。 例如，对于N=7 ，我希望能够在索引（左）和分区（右）之间来回： 0 ( 7 ) 1 ( 6 1 ) 2 ( 5 2 ) 3 ( 5 1 1 ) 4 ( 4 3 ) 5 ( 4 2 1 ) 6 ( 4 1 1 1 ) 7 ( 3 3 1 ) 8 ( 3 […]

匹配集的数据结构

我有一个应用程序，我有许多集。 一套可能是 {4,7,12,18} 唯一的数字，都小于50。 然后我有几个数据项： 1 {1,2,4,7,8,12,18,23,29} 2 {3,4,6,7,15,23,34,38} 3 {4,7,12,18} 4 {1,4,7,12,13,14,15,16,17,18} 5 {2,4,6,7,13,15} 数据项1,3和4与集合匹配，因为它们包含集合中的所有项目。 我需要设计一个超快速的数据结构来识别数据项是否是集合的成员包括属于集合的所有成员（因此数据项是集合的超集）。 我目前最好的估计表明将会少于50,000套。 我当前的实现将我的集合和数据作为无符号64位整数和存储在列表中的集合。 然后检查一个数据项我遍历列表进行（（set＆data）== set）比较。 它有效并且它的空间效率很高但它很慢（O（n））并且我很乐意为一些性能交换一些内存。 有没有人对如何组织这个有更好的想法？ 编辑：非常感谢所有的答案。 看起来我需要提供有关该问题的更多信息。 我首先得到集合，然后逐个获取数据项。 我需要检查数据项是否与其中一个集匹配。 这些集很可能是“块状的”，例如对于给定的问题，1,3和9可能包含在95％的集合中; 我可以在一定程度上提前预测（但不是很好）。 对于那些建议记忆的人：这就是memoized函数的数据结构。 这些集代表已经计算的一般解决方案，数据项是函数的新输入。 通过将数据项与一般解决方案相匹配，我可以避免大量处理。

所有旅行时间的最小总和

我在interviewStreet网上找到了一个谜题，并尝试按如下方式解决： 有一个无限的整数网格，N人有他们的房子。 他们决定团结在一个共同的聚会场所，这是一个人的家。 从任何给定的小区，所有8个相邻小区在1个单位时间内可达。 例如：（x，y）可以在一个单位时间内从（x-1，y + 1）到达。 找到一个共同的会面地点，最大限度地减少所有人的旅行时间总和。 我首先想到的是及时编写n²复杂度的解决方案，但约束条件是 1 <= N <= 10 ^ 5并且输入中每个坐标的绝对值将至多为10 ^ 9 所以，我改变了我的第一种方法，而不是考虑距离和旅行时间的问题，我把不同的房子看作不同的身体，不同的重量。 而不是计算所有距离，我寻找这组物体的重心。 这是我的“求解”函数的代码，vectorToTreat是一个lengthX2表，存储有关网格上各点的所有数据，结果是打印到stdout的数字： long long solve(long long** vectorToTreat, int length){ long long resul = 0; int i; long long x=0; long long y=0; int tmpCur=-1; long long tmp=-1; for(i=0;i<length;i++){ x+=vectorToTreat[i][0]; y+=vectorToTreat[i][1]; } x=x/length; y=y/length; tmp = max(absol(vectorToTreat[0][0]-x),absol(vectorToTreat[0][1]-y)); […]

单精度浮点精度降低精度差

我正在尝试将范围缩减作为实现正弦函数的第一步。 我遵循KC NG的论文“减少巨大论据”中描述的方法 当使用0到20000的x的输入范围时，我得到的误差大到0.002339146.我的错误显然不应该那么大，我不知道如何减少它。 我注意到误差幅度与输入θ幅度与余弦/正弦相关。 我能够获得本文提到的nearpi.c代码，但我不确定如何将代码用于单精度浮点。 如果有人有兴趣，可以在以下链接找到nearpi.c文件： nearpi.c 这是我的MATLAB代码： x = 0:0.1:20000; % Perform range reduction % Store constant 2/pi twooverpi = single(2/pi); % Compute y y = (x.*twooverpi); % Compute k (round to nearest integer k = round(y); % Solve for f f = single(yk); % Solve for r r = single(f*single(pi/2)); % Find […]