Nik*_* B. 26 algorithm xor time-complexity space-complexity
最初的问题陈述是这样的:
给定一个32位无符号整数数组,其中每个数字除了其中三个(恰好只出现一次)之外恰好出现两次,使用O(1)额外空格在O(n)时间内找到这三个数字.输入数组是只读的.如果有k个例外而不是3个怎么办？
如果由于输入限制(阵列最多可以包含2 33个条目)而接受非常高的常数因子,则很容易在?(1)时间和?(1)空间上解决这个问题:
for i in lst:
if sum(1 for j in lst if i == j) == 1:
print i
因此,为了这个问题,让我们放弃比特长度的限制,并专注于数字可以达到m比特的更普遍的问题.
推广k = 2的算法,我想到的是以下内容:
1和具有0单独的那些数字进行异或.如果对于两个分区,结果值不为零,我们知道我们已将非重复数字划分为两个组,每个组至少有一个成员不过,有一个特殊情况需要考虑.如果在对一个组进行分区后,其中一个组的XOR值都为零,我们不知道其中一个结果子组是否为空.在这种情况下,我的算法只是将该位丢弃并继续下一个,这是不正确的,例如它输入失败[0,1,2,3,4,5,6].
现在我的想法是不仅要计算元素的XOR,还要计算应用某个函数后的值的异或(我在f(x) = 3x + 1这里选择).有关此附加检查的反例,请参阅下面的Evgeny的答案.
现在虽然以下算法对于k> = 7是不正确的,但我仍然在这里包含实现以给你一个想法:
def xor(seq):
return reduce(lambda x, y: x ^ y, seq, 0)
def compute_xors(ary, mask, bits):
a = xor(i for i in ary if i & mask == bits)
b = xor(i * 3 + 1 for i in ary if i & mask == bits)
return a if max(a, b) > 0 else None
def solve(ary, high = 0, mask = 0, bits = 0, old_xor = 0):
for h in xrange(high, 32):
hibit = 1 << h
m = mask | hibit
# partition the array into two groups
x = compute_xors(ary, m, bits | hibit)
y = compute_xors(ary, m, bits)
if x is None or y is None:
# at this point, we can't be sure if both groups are non-empty,
# so we check the next bit
continue
mask |= hibit
# we recurse if we are absolutely sure that we can find at least one
# new value in both branches. This means that the number of recursions
# is linear in k, rather then exponential.
solve(ary, h + 1, mask, bits | hibit, x)
solve(ary, h + 1, mask, bits, y)
break
else:
# we couldn't find a partitioning bit, so we output (but
# this might be incorrect, see above!)
print old_xor
# expects input of the form "10 1 1 2 3 4 2 5 6 7 10"
ary = map(int, raw_input().split())
solve(ary, old_xor=xor(ary))
根据我的分析,这段代码的最坏情况是时间复杂度,O(k * m² * n)其中n输入元素的数量(XORing是O(m),并且最多k分区操作可以成功)和空间复杂度O(m²)(因为m最大递归深度和临时数字可以是长度m).
现在的问题是,当然,如果有一个正确的具有良好的渐近运行时间,有效的方法(我们假设k << n和m << n这里完整起见),这还需要一点额外的空间(例如,接近那种输入将不被接受,因为我们至少需要O(n)额外的空间,因为我们无法修改输入!).
编辑:既然上面的算法被证明是不正确的,那么看看如何使它变得正确当然很好,可能是因为它的效率要低一些.空间复杂度应该在o(n*m)(即输入位总数中的次线性).k如果这使得任务更容易,那么可以将其作为额外的输入.
Nor*_*sey 10
我离线并证明原始算法受到XOR技巧工作的猜想的影响.碰巧,XOR技巧不起作用,但下面的论点可能仍然引起一些人的兴趣.(我在Haskell中重新做了,因为当我有递归函数而不是循环时我发现证据更容易,我可以使用数据结构.但对于观众中的Pythonistas,我试图尽可能使用列表推导.)
http://pastebin.com/BHCKGVaV上的可编译代码.
问题:我们给出了一系列n个非零32位字,其中每个元素都是singleton或doubleton:
如果一个单词恰好出现一次,那就是单身.
如果一个单词恰好出现两次,则为双重.
没有任何单词出现三次或更多次.
问题是找到单身人士.如果有三个单体,我们应该使用线性时间和恒定空间.更一般地说,如果有k个单体,我们应该使用O(k*n)时间和O(k)空间.该算法依赖于一个关于异或的未经证实的猜想.
我们从这些基础知识开始:
module Singleton where
import Data.Bits
import Data.List
import Data.Word
import Test.QuickCheck hiding ((.&.))
为了解决这个问题,我将介绍一个抽象:描述一个32位字的最低有效$ w $位,我介绍一个Spec:
data Spec = Spec { w :: Int, bits :: Word32 }
deriving Show
width = w -- width of a Spec
一个Spec相匹配,如果至少显著一个字w位等于bits.如果w为零,则根据定义所有单词匹配:
matches :: Spec -> Word32 -> Bool
matches spec word = width spec == 0 ||
((word `shiftL` n) `shiftR` n) == bits spec
where n = 32 - width spec
universalSpec = Spec { w = 0, bits = 0 }
以下是关于Specs的一些说法:
所有单词都匹配universalSpec,宽度为0
如果matches spec word和width spec == 32,那么
word == bits spec
这是算法的关键思想:我们可以通过在规范中添加另一个位来扩展 a Spec.扩展a Spec
产生两个Specs 的列表
extend :: Spec -> [Spec]
extend spec = [ Spec { w = w', bits = bits spec .|. (bit `shiftL` width spec) }
| bit <- [0, 1] ]
where w' = width spec + 1
这是至关重要的主张:如果spec匹配word且if
width spec小于32,那么两个规格中的一个恰好extend spec匹配word.证据是通过案例分析相关位word.这个说法非常重要,我将其称为Lemma One Here这是一个测试:
lemmaOne :: Spec -> Word32 -> Property
lemmaOne spec word =
width spec < 32 && (spec `matches` word) ==>
isSingletonList [s | s <- extend spec, s `matches` word]
isSingletonList :: [a] -> Bool
isSingletonList [a] = True
isSingletonList _ = False
我们将定义一个给出一个Spec32位字序列的函数,返回一个与规范匹配的单例字列表.该函数将花费与输入长度成倍的时间乘以答案时间32的大小,以及与答案时间32的大小成比例的额外空间.在我们处理主函数之前,我们定义了一些恒定空间XOR函数.
函数xorWith f ws将函数f应用于每个单词ws
并返回异或结果.
xorWith :: (Word32 -> Word32) -> [Word32] -> Word32
xorWith f ws = reduce xor 0 [f w | w <- ws]
where reduce = foldl'
由于流融合(参见ICFP 2007),功能xorWith需要恒定的空间.
非零单词列表具有单例,当且仅当排他或非零,或者排他或非3 * w + 1非零.("if"方向是微不足道的."唯一的"方向是Evgeny Kluev反驳的猜想;对于反例,请参见testb下面的数组.我可以通过添加第三个函数使Evgeny的示例工作g,但显然这种情况需要证明,我没有.)
hasSingleton :: [Word32] -> Bool
hasSingleton ws = xorWith id ws /= 0 || xorWith f ws /= 0 || xorWith g ws /= 0
where f w = 3 * w + 1
g w = 31 * w + 17
我们的main函数返回一个匹配spec的所有单例的列表.
singletonsMatching :: Spec -> [Word32] -> [Word32]
singletonsMatching spec words =
if hasSingleton [w | w <- words, spec `matches` w] then
if width spec == 32 then
[bits spec]
else
concat [singletonsMatching spec' words | spec' <- extend spec]
else
[]
我们将通过感应宽度来证明其正确性
spec.
基本情况是spec宽度为32.在这种情况下,列表推导将给出完全相等的单词列表bits spec.当且仅当此列表只有一个元素时hasSingleton才会返回函数True,当bits spec单例格式为时,该函数将完全为真words.
现在让我们证明如果singletonsMatching对于m + 1是正确的,对于宽度m也是正确的,其中*m <32 $.(这与感应通常相反,但没关系.)
这是被破坏的部分:对于较窄的宽度,即使给出单个数组hasSingleton也可能返回False.这很悲惨.
调用extend spec上spec的宽度米返回具有宽度$ M + 1 $这两个标准.根据假设,singletonsMatching这些规格是正确的.为了证明:结果恰好包含那些匹配的单身人士spec.通过引理一,任何匹配的单词都与spec扩展规范中的一个完全匹配.通过假设,递归调用恰好返回与扩展规范匹配的单例.当我们将这些调用的结果组合在一起时concat,我们得到完全匹配的单例,没有重复且没有遗漏.
实际上解决问题是虎头蛇尾:单身人士都是符合空规的单身人士:
singletons :: [Word32] -> [Word32]
singletons words = singletonsMatching universalSpec words
testa, testb :: [Word32]
testa = [10, 1, 1, 2, 3, 4, 2, 5, 6, 7, 10]
testb = [ 0x0000
, 0x0010
, 0x0100
, 0x0110
, 0x1000
, 0x1010
, 0x1100
, 0x1110
]
除此之外,如果您想了解正在发生的事情,您需要了解QuickCheck.
这是规格的随机发生器:
instance Arbitrary Spec where
arbitrary = do width <- choose (0, 32)
b <- arbitrary
return (randomSpec width b)
shrink spec = [randomSpec w' (bits spec) | w' <- shrink (width spec)] ++
[randomSpec (width spec) b | b <- shrink (bits spec)]
randomSpec width bits = Spec { w = width, bits = mask bits }
where mask b = if width == 32 then b
else (b `shiftL` n) `shiftR` n
n = 32 - width
使用这个发生器,我们可以使用测试引理一
quickCheck lemmaOne.
我们可以测试看到声称是单身的任何单词实际上都是单身:
singletonsAreSingleton nzwords =
not (hasTriple words) ==> all (`isSingleton` words) (singletons words)
where isSingleton w words = isSingletonList [w' | w' <- words, w' == w]
words = [w | NonZero w <- nzwords]
hasTriple :: [Word32] -> Bool
hasTriple words = hasTrip (sort words)
hasTrip (w1:w2:w3:ws) = (w1 == w2 && w2 == w3) || hasTrip (w2:w3:ws)
hasTrip _ = False
这是另一个singletons使用排序来测试快速算法的属性.
singletonsOK :: [NonZero Word32] -> Property
singletonsOK nzwords = not (hasTriple words) ==>
sort (singletons words) == sort (slowSingletons words)
where words = [w | NonZero w <- nzwords ]
slowSingletons words = stripDoubletons (sort words)
stripDoubletons (w1:w2:ws) | w1 == w2 = stripDoubletons ws
| otherwise = w1 : stripDoubletons (w2:ws)
stripDoubletons as = as
当这些组中的至少一个被异或为非零值时,该算法使用以一个比特的值递归地将一组k个唯一值分成两组的可能性.例如,以下数字
01000
00001
10001
可能会分裂成
01000
和
00001
10001
使用最低有效位的值.
如果正确实现,这适用于k <= 6.但是这种方法在k = 8和k = 7时失败.假设m = 4并使用0到14的8个偶数:
0000
0010
0100
0110
1000
1010
1100
1110
除最不重要的位之外,每个位都有4个非零值.如果我们尝试对此集合进行分区,由于这种对称性,我们将始终获得具有2或4或0非零值的子集.这些子集的XOR始终为0.这不允许算法进行任何拆分,因此else部分只打印所有这些唯一值的XOR(单个零).
3x + 1 技巧没有帮助:它只是将这8个值混洗并切换最低有效位.
如果我们从上面的子集中删除第一个(全零)值,则完全相同的参数适用于k = 7.
由于任何一组唯一值可以被分成7或8个值的组和一些其他组,因此该算法也因k > 8而失败.
有可能不发明一种全新的算法,而是修改OP中的算法,使其适用于任何输入值.
每次算法访问输入数组的元素时,它都应该对该元素应用一些转换函数:y=transform(x).这个转换后的值y可以x与原始算法中使用的完全一样- 用于分区集和对值进行异或.
最初transform(x)=x(未经修改的原始算法).如果在这一步之后我们得到的结果少于k(一些结果是几个唯一值XORed),我们transform改为一些哈希函数和重复计算.这应该重复(每次使用不同的散列函数),直到我们得到精确的k值.
如果在算法的第一步获得这些k值(没有散列),则这些值是我们的结果.否则,我们应该再次扫描数组,计算每个值的散列并报告与k个散列之一匹配的值.
具有不同散列函数的每个后续计算步骤可以在原始k值集合上执行,或者(更好地)在前一步骤中找到的每个子集上执行.
要为算法的每个步骤获取不同的散列函数,可以使用Universal散列.散列函数的一个必要属性是可逆性 - 原始值应该(理论上)可以从散列值重建.这是为了避免将几个"唯一"值散列到相同的散列值.由于使用任何可逆m位散列函数没有太多机会解决"反例"问题,因此散列值应该长于m位.这种散列函数的一个简单示例是原始值的串联和该值的一些单向散列函数.
如果k不是很大,我们就不太可能得到一组类似于反例的数据.(我没有证据证明没有其他"坏"数据模式,具有不同的结构,但我们希望它们也不太可能).在这种情况下,平均时间复杂度不大于O(k*m 2*n).
solve(ary, h + 1...).相反,你应该从头开始重新搜索.可以在第31位上分割该组,并且对于位0上的一个结果子集具有唯一的分裂可能性.y = compute_xors(ary, m, bits)不需要第二个).您已经拥有整个集合的XOR和分割位非零的子集的XOR.这意味着您可以y立即计算:y = x ^ old_xor.这不是OP中实际程序的证明,而是它的想法.当其中一个结果子集为零时,实际程序当前拒绝任何拆分.当我们接受某些此类拆分时,请参阅建议的改进案例.因此,只有在if x is None or y is None将某个条件更改为考虑子集大小的奇偶校验或在添加预处理步骤以从阵列中排除唯一零元素之后,才能将以下证据应用于该程序.
我们有3个不同的数字.它们在至少2位位置应该是不同的(如果它们仅在一位中不同,则第三位必须等于其他位中的一位).solve函数中的循环找到最左边的这些位位置,并将这3个数字分成两个子集(单个数字和2个不同的数字).2位子集在此位位置具有相等的位,但数字仍然应该不同,因此应该有一个分裂位位置(显然,在第一个位置的右侧).第二次递归步骤很容易将这个2数字子集拆分成两个单个数字.i * 3 + 1这里的伎俩是多余的:它只会使算法的复杂性增加一倍.
以下是一组3个数字中第一次拆分的说明:
2 1
*b**yzvw
*b**xzvw
*a**xzvw
我们有一个循环遍历每个位的位置并计算整个单词的XOR,但另外,给定位置的真位的一个XOR值(A),假位的其他XOR值(B).如果数字A在该位置具有零位,则A包含一些偶数大小的值子集的XOR,如果非零 - 奇数大小的子集.B也是如此.我们只对偶数大小的子集感兴趣.它可以包含0或2个值.
虽然位值(位z,v,w)没有差异,但我们有A = B = 0,这意味着我们不能在这些位上分割数字.但是我们有3个不相等的数字,这意味着在某个位置(1)我们应该有不同的位(x和y).其中一个(x)可以在我们的两个数字(偶数大小的子集!)中找到,其他(y) - 在一个数字中.让我们看看这个偶数大小的子集中的值的XOR.从A和B中选择值(C),包含位置1的位0.但C只是两个不相等值的XOR.它们在位位置1处相等,因此它们必须在至少一个位位置(位置2,位a和b)上不同.所以C!= 0并且它对应于偶数大小的子集.这种拆分是有效的,因为我们可以通过非常简单的算法或通过该算法的下一次递归来进一步拆分这个偶数大小的子集.
如果阵列中没有唯一的零元素,则可以简化此证明.我们总是将唯一数字分成2个子集 - 一个有2个元素(并且由于元素不同,它不能异或为零),另外一个元素(根据定义非零).因此,几乎没有预处理的原始程序应该正常工作.
复杂度为O(m 2*n).如果您应用我之前建议的改进,此算法扫描阵列的预期次数是m/3 + 2.因为第一个分割位位置预计为m/3,所以需要单次扫描来处理2-元素子集,每个1元素子集不需要任何阵列扫描,最初需要再扫描一次(在solve方法之外).
这里我们假设应用了对原始算法的所有建议改进.
k = 4且k = 5:由于至少有一个位置具有不同的位,因此可以将这组数字拆分,使得其中一个子集的大小为1或2.如果子集的大小为1,则为非-zero(我们没有零唯一值).如果子集的大小为2,则我们有两个不同数字的XOR,这是非零的.所以在这两种情况下,拆分都是有效的.
k = 6:如果整个集合的XOR不为零,我们可以将该集合拆分为该XOR具有非零位的任何位置.否则,我们在每个位置都有偶数个非零位.由于至少有一个位置具有不同的位,因此该位置将该组拆分为大小为2和4的子集.大小为2的子集始终为非零XOR,因为它包含2个不同的数字.同样,在这两种情况下,我们都有有效的分裂.
对于k > = 7的反证显示了原始算法不起作用的模式:我们有一个大于2的子集,并且在每个比特位置我们有偶数个非零比特.但是我们总能找到一对非零位在单个数字中重叠的位置.换句话说,始终可以在大小为3或4的子集中找到一对位置,其中两个位置的子集中的所有位的非零XOR .这建议我们使用额外的分割位置:使用两个单独的指针迭代位位置,将数组中的所有数字分组为两个子集,其中一个子集在这些位置具有非零位,以及其他 - 所有剩余数字.这增加了我的m的最坏情况复杂度,但允许k更多的值.一旦没有更多可能获得大小小于5的子集,添加第三个"分裂指针",依此类推.每次ķ双打,我们可能需要一个额外的"分裂指针",这增加了最坏情况的复杂性我的米一次.
这可能被视为以下算法的证明草图:
最坏情况复杂度为O(k*m 2*n*m max(0,floor(log(floor(k/4))))),其可近似为O(k*n*m log(k)) = O(k*n*k log(m)).
该算法对于小k的预期运行时间比概率算法稍差,但仍然不比O(k*m 2*n)大得多.
一种概率方法是使用计数过滤器.
算法如下:
<= k真正的解决方案.(在这种情况下,误报是看起来不像的独特元素).k解决方案.这使用2m了一些空间(独立n).时间复杂度更复杂,但是知道在步骤2中找不到任何给定的唯一元素的概率是近似的,(1 - e^(-kn/m))^k我们将很快解决一个解决方案,但不幸的是我们并不是非常线性的n.
我理解这不能满足你的约束,因为它在时间上是超线性的,并且是概率性的,但考虑到原始条件可能不可满足,这种方法可能值得考虑.