M位置的圆移位阵列的最快算法是什么？
例如,[3 4 5 2 3 1 4]班次M = 2个位置应该是[1 4 3 4 5 2 3].
非常感谢.
我似乎无法理解这是如何工作的.
问题:
给定一个顺序文件,其中包含最多40个随机顺序的32位整数,找到一个不在文件中的32位整数(并且必须至少有一个缺失)
答:
根据代表每个整数的32位来查看这个二进制搜索是有帮助的.在算法的第一遍中,我们读取(最多)40亿个输入整数,并将具有前导零位的那些写入一个顺序文件,将那些具有前导一位的那些写入另一个文件.
其中一个文件最多包含20亿个整数,因此我们接下来将该文件用作当前输入并重复探测过程,但这次是在第二位.
所以通过一遍又一遍地分割文件(二进制搜索),这实际上会导致我丢失32位整数？
Jon Bentley在其编程珍珠的第1栏中介绍了一种使用位向量对非零正整数序列进行排序的技术.
我从这里获取了programort.c程序并粘贴在下面:
/* Copyright (C) 1999 Lucent Technologies */
/* From 'Programming Pearls' by Jon Bentley */
/* bitsort.c -- bitmap sort from Column 1
* Sort distinct integers in the range [0..N-1]
*/
#include <stdio.h>
#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1F
#define N 10000000
int a[1 + N/BITSPERWORD];
void set(int i)
{
int sh = i>>SHIFT;
a[i>>SHIFT] |= (1<<(i & MASK));
}
void clr(int i) { a[i>>SHIFT] &= ~(1<<(i & MASK)); }
int …摘自编程珍珠第15.2节
可在此处查看C代码:http://www.cs.bell-labs.com/cm/cs/pearls/longdup.c
当我使用suffix-array在Python中实现它时:
example = open("iliad10.txt").read()
def comlen(p, q):
i = 0
for x in zip(p, q):
if x[0] == x[1]:
i += 1
else:
break
return i
suffix_list = []
example_len = len(example)
idx = list(range(example_len))
idx.sort(cmp = lambda a, b: cmp(example[a:], example[b:])) #VERY VERY SLOW
max_len = -1
for i in range(example_len - 1):
this_len = comlen(example[idx[i]:], example[idx[i+1]:])
print this_len
if this_len > max_len:
max_len = this_len
maxi = i
我发现这idx.sort一步很慢.我认为它很慢,因为Python需要通过值而不是指针传递子串(如上面的C代码).
测试文件可以从这里 …
实际上这是编程珍珠第2版第8章的问题#10.它提出了两个问题:给定一个整数数组A [](正数和非正数),你怎么能找到一个A []的连续子数组,其总和最接近0？或者最接近某个值t？
我可以想办法解决最接近0的问题.计算前缀和数组S [],其中S [i] = A [0] + A [1] + ... + A [i].然后根据元素值和保留的原始索引信息对此S进行排序,以找到最接近0的子阵列和,只需迭代S数组并执行两个相邻值的差异并更新最小绝对差值.
问题是,解决第二个问题的最佳方法是什么？最接近某个值t？任何人都可以提供代码或至少一个算法吗？(如果有人有最接近零问题的解决方案,也欢迎回答)
从"编程珍珠"一书中解释(关于旧机器上的c语言,因为本书是从90年代后期开始的):
整数算术运算(+,-,*),而可能需要大约10纳秒%操作员最多需要100毫微秒.
/在时间方面它与division()相同吗？它在2.6节和问题2中,原始问题是这样的:
"鉴于包含4,300,000,000个32位整数的顺序文件,你怎么能找到至少出现两次的整数？"
我对这个练习的问题是:上述问题的技巧是什么？这个问题在于什么样的通用算法类别？
我今天开始阅读"Programming Pearls",在进行练习时,我遇到了这个问题"你将如何实现自己的位向量？".当我查看解决方案时,它是这样的:
#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1F
#define N 10000000
int a[1 + N/BITSPERWORD];
void set(int i) { a[i >> SHIFT] |= (1 << (i & MASK));
这个陈述让我感到困惑
1 << (i & MASK)
有人可以解释一下这里发生了什么吗？
这是描述的问题Programming pearls.我无法理解作者所描述的二进制搜索方法.任何人都可以帮忙详细说明吗？谢谢.
编辑:我一般可以理解二进制搜索.我只是无法理解如何在这种特殊情况下应用二进制搜索.如何确定缺失的数字是否在某个范围内,以便我们可以选择另一个.英语不是我的母语,这是我无法理解作者的一个原因.所以,请使用普通英语:)
编辑:谢谢大家的好评和评论!我从解决这个问题中学到的最重要的一课就是二元搜索不仅适用于排序数组!
我想知道是否有人知道最长重复非重叠子串的(最佳？)算法.
例如,在字符串中
ABADZEDGBADEZ
最长的反复出现是"不好".顺便提一下,如果没有这样的结果,算法应该警告这样的事情已经发生.我猜这是涉及后缀树.
我敢肯定这已经存在了.谢谢您的帮助!