算法/随机化
当人们试图用确定性算法解决难题时，它们会被推到极限，因此，一个有用的加速计算的技术是随机化。在随机算法中，算法可以访问一个随机源，可以想象成在计算过程中抛硬币。根据抛硬币的结果，算法可能会分叉它的计算路径。
随机算法主要有两种类型：拉斯维加斯算法和蒙特卡罗算法。在拉斯维加斯算法中，算法可以使用随机性来加速计算，但算法必须始终返回输入的正确答案。蒙特卡罗算法没有后者的限制，也就是说，它们可以返回错误的返回值。但是，返回错误返回值的概率必须很小，否则该蒙特卡罗算法就没有用。
许多近似算法使用随机化。
在介绍随机技术之前，我们将从一个确定性问题开始，它会引导到一个使用随机化的问题。假设你有一个无序的数值数组，你想找到
- 最大值，
- 最小值，以及
- 中位数。
用我们以前一位计算机科学教授的话来说，“你怎么做呢？”
首先，找到最大元素相对简单
// find-max -- returns the maximum element
function find-max(array vals[1..n]): element
let result := vals[1]
for i from 2 to n:
result := max(result, vals[i])
repeat
return result
end
将result初始设置为也可以，但这对max函数来说是一个无用的调用，因为第一个比较的元素将被设置为result。通过将result初始化为这样的值，函数只需要进行n-1次比较。（此外，在支持元编程的语言中，数据类型可能不是严格的数字，可能没有好的方法来分配；使用vals[1]是类型安全的。）
可以通过调用min函数而不是max函数来执行类似的查找最小元素的例程。
但是现在假设你想同时找到最小值和最大值；这里有一个解决方案
// find-min-max -- returns the minimum and maximum element of the given array
function find-min-max(array vals): pair
return pair {find-min(vals), find-max(vals)}
end
因为find-max和find-min都对max或min函数进行了n-1次调用（当vals有n个元素时），find-min-max中进行的总比较次数为.
但是，有一些冗余的比较。可以通过将min和max函数“编织”在一起来消除这些冗余。
// find-min-max -- returns the minimum and maximum element of the given array function find-min-max(array vals[1..n]): pair let min := let max := if n is odd: min := max := vals[1] vals := vals[2,..,n] // we can now assume n is even n := n - 1 fi for i:=1 to n by 2: // consider pairs of values in vals if vals[i] < vals[i + 1]: let a := vals[i] let b := vals[i + 1] else: let a := vals[i + 1] let b := vals[i] // invariant: a <= b fi if a < min: min := a fi if b > max: max := b fi repeat return pair {min, max} end
这里，我们只循环次，而不是n次，但每次迭代我们进行三次比较。因此，进行的比较次数为，比原始算法快了。
只需要进行三次比较，而不是四次，因为根据构造，总是满足 。 （在 "if" 的第一部分，我们实际上更确切地知道 ，但在 else 部分，我们只能得出结论 。）利用这个性质，我们可以注意到，a 不需要与当前最大值比较，因为 b 已经大于或等于 a，类似地，b 不需要与当前最小值比较，因为 a 已经小于或等于 b。
在软件工程中，使用库和编写自定义算法之间存在着矛盾。在本例中，为了获得更快的 查找最小值最大值 例程，没有使用 min 和 max 函数。在实际程序中，这种操作可能不会成为瓶颈：但是，如果测试表明该例程应该更快，则应该采用这种方法。通常，重用库的解决方案总体上优于编写自定义解决方案。诸如开放式实现和面向方面编程之类的技术可以帮助管理这种争论，从而实现两全其美，但无论如何，这是一个有用的区别，值得认识到。
查找中位数
[edit | edit source]最后，我们需要考虑如何找到中位数值。一种方法是对数组进行排序，然后从位置提取中位数vals[n/2]:
// find-median -- returns the median element of vals function find-median(array vals[1..n]): element assert (n > 0) sort(vals) return vals[n / 2] end
如果我们的值不是足够接近的值（或者不能通过基数排序进行排序），上面的排序将需要 步。
但是，可以在 时间内提取第 n 个顺序统计量。关键在于消除排序：我们实际上并不需要对整个数组进行排序才能找到中位数，因此对整个数组进行排序会造成一些浪费。我们将使用的一种技术是随机性。
在介绍非排序 查找中位数 函数之前，我们介绍一种称为 分区 的分治式操作。我们想要的是一个例程，它在数组中找到一个随机元素，然后将数组分成三个部分
- 小于或等于随机元素的元素；
- 等于随机元素的元素；以及
- 大于或等于随机元素的元素。
这三个部分由两个整数表示：j 和 i。分区是在数组中“就地”执行的
// partition -- break the array three partitions based on a randomly picked element
function partition(array vals): pair{j, i}
请注意，当选取的随机元素在数组中实际出现三次或更多次时，所有三个分区中的条目都可能与随机元素具有相同的值。虽然这种操作可能听起来并不实用，但它具有一个可以利用的强大特性：当分区操作完成后，随机选取的元素在数组中的位置将与对数组进行完全排序后相同！
这种特性可能听起来并不那么强大，但请回想一下 查找最小值最大值 函数的优化：我们注意到，通过先将数组中的元素成对选取并相互比较，我们可以减少所需的总比较次数（因为当前的最小值和最大值只需要与每个值比较一次，而不是两次）。这里也使用了类似的概念。
虽然 分区 的代码并不神奇，但它有一些棘手的边界情况
// partition -- break the array into three ordered partitions from a random element
function partition(array vals): pair{j, i}
let m := 0
let n := vals.length - 2 // for an array vals, vals[vals.length-1] is the last element, which holds the partition,
// so the last sort element is vals[vals.length-2]
let irand := random(m, n) // returns any value from m to n
let x := vals[irand]
swap( irand,n+ 1 ) // n+1 = vals.length-1 , which is the right most element, and acts as store for partition element and sentinel for m
// values in vals[n..] are greater than x
// values in vals[0..m] are less than x
while (m <= n ) // see explanation in quick sort why should be m <= n instead of m < n in the 2 element case,
// vals.length -2 = 0 = n = m, but if the 2-element case is out-of-order vs. in-order, there must be a different action.
// by implication, the different action occurs within this loop, so must process the m = n case before exiting.
while vals[m] <= x // in the 2-element case, second element is partition, first element at m. If in-order, m will increment
m++
endwhile
while x < vals[n] && n > 0 // stops if vals[n] belongs in left partition or hits start of array
n—endwhile
if ( m >= n) break;
swap(m,n) // exchange vals[n] and vals[m]
m++ // don't rescan swapped elements
n—endwhile
// partition: [0..m-1] [] [n+1..] note that m=n+1
// if you need non empty sub-arrays:
swap(m,vals.length - 1) // put the partition element in the between left and right partitions
// in 2-element out-of-order case, m=0 (not incremented in loop), and the first and last(second) element will swap.
// partition: [0..n-1] [n..n] [n+1..]
end
我们可以使用 分区 作为一般 查找 操作的子例程
// find -- moves elements in vals such that location k holds the value it would when sorted
function find(array vals, integer k)
assert (0 <= k < vals.length) // k it must be a valid index
if vals.length <= 1:
return
fi
let pair (j, i) := partition(vals)
if k <= i:
find(a[0,..,i], k)
else-if j <= k:
find(a[j,..,n], k - j)
fi
TODO: debug this!
end
这让我们得到了关键点
// find-median -- returns the median element of vals function find-median(array vals): element assert (vals.length > 0) let median_index := vals.length / 2; find(vals, median_index) return vals[median_index] end
你可能会想到的一个问题是“随机调用真的有必要吗？”例如，我们可以始终选取中间元素，而不是随机选取枢轴。鉴于我们的算法适用于所有可能的数组，我们可以得出结论，在所有可能的输入上，所有可能输入的平均运行时间与我们使用随机函数的分析相同。这里的推理是，在所有可能的数组集合中，中间元素与其他任何元素一样“随机”。但这种推理存在一个陷阱：通常，程序中算法的输入并非随机。例如，输入比随机情况下更有可能被排序。同样，由于它是来自真实程序的真实数据，因此数据可能具有其他模式，这些模式会导致次优结果。
换句话说，对于随机化中位数查找算法，它以极低的概率运行次优，与输入无关；而对于只选取中间元素的确定性算法，它在它将接收的某些最常见输入类型上运行不良的可能性更大。这让我们得出以下准则
| 随机化准则 如果你的算法依赖于随机性，请确保你自己引入随机性，而不是依赖数据是随机的。 |
请注意，存在“反随机化”技术，可以将平均情况快速算法转换为完全确定性算法。有时反随机化的开销太大，需要非常大的数据集才能获得任何收益。尽管如此，反随机化本身在理论上具有价值。
随机化 查找 算法是由 C. A. R. "Tony" Hoare 发明的。虽然 Hoare 是计算机科学界的重要人物，但他可能最广为人知的是他在一般圈子里快速排序算法，我们将在下一节中讨论。
快速排序
[edit | edit source]上一节中的中位数查找分区算法实际上非常接近完整排序算法的实现。构建快速排序算法留作练习，建议读者在阅读下一节之前先尝试（与合并排序相比，快速排序是魔鬼般的，合并排序是一种没有随机化步骤改进的排序）。
快速排序的关键部分是选择正确的中位数。但是为了快速运行，首先假设数组是未排序的，并且每个数组的最右边的元素与任何其他元素一样可能是中位数，并且我们完全乐观地认为最右边元素碰巧不是最大键，这意味着我们将在每一步只删除一个元素（分区元素），并且没有右数组要排序，并且有一个 n-1 左数组要排序。
这就是 随机化 对于快速排序很重要的原因，即选择更优的分区键，这对快速排序高效工作非常重要。
比较快速排序与插入排序所需的比较次数。
对于插入排序，在对随机数组进行升序排序时，查找最小的第一个元素的平均比较次数为 n /2 。
第二个元素的平均比较次数为 (n-1)/2;
第三个元素为 (n- 2) / 2。
总比较次数为 [ n + (n - 1) + (n - 2) + (n - 3) .. + (n - [n-1]) ] 除以 2，即 [ n x n - (n-1)! ] /2 或约为 O(n 平方) 。
在快速排序中，如果选择了真正的中位数，则每次划分步骤中的比较次数都会减半，因为左半部分的划分不需要与右半部分的划分进行比较，但在每一步中，由先前划分级别创建的所有划分的元素数量仍然为n。
比较n个元素的级别数是将n除以2的步骤数，直到n = 1。或者反过来，2 ^ m ~ n，所以m = log2 n。
因此，比较总数为n（元素）x m（扫描级别）或n x log2n，
因此，比较次数为O(n x log 2(n) )，小于插入排序的O(n^2)或O( n x n )。
（比较O(n x log 2(n) )与O( n x n )，可以消除公因子n，比较为log2(n) vs n，随着n变大，呈指数级差异。例如，比较n = 2^16，或16 vs 32768，或32 vs 4 gig）。
要在由先前递归调用确定的数组的一部分上就地实现划分，需要从该部分的两端进行扫描，每当左扫描的当前位置的值大于划分值且右扫描的当前位置的值小于划分值时，就进行交换。因此，初始步骤是：-
Assign the partition value to the right most element, swapping if necessary.
因此，划分步骤是：-
increment the left scan pointer while the current value is less than the partition value. decrement the right scan pointer while the current value is more than the partition value , or the location is equal to or more than the left most location. exit if the pointers have crossed ( l >= r), OTHERWISE perform a swap where the left and right pointers have stopped , on values where the left pointer's value is greater than the partition, and the right pointer's value is less than the partition.
最后，在由于左右指针交叉而退出循环后，将最右侧的划分值与左向前扫描指针的最后一个位置进行交换，因此它最终位于左右划分之间。
确保此时，在最终交换后，正确处理了两个元素有序数组和两个元素无序数组的情况，这意味着所有情况都应得到正确处理。这是使快速排序正常工作的良好调试步骤。
对于有序的两个元素情况，左指针停留在划分或第二个元素上，因为找到划分值。右指针从划分之前的第一个元素开始向后扫描，并在到达最左侧位置时停止。
指针交叉，循环在进行循环交换之前退出。在循环之外，将左指针在最右侧位置的内容和划分值（也在最右侧位置）进行交换，对有序的两个元素情况没有任何改变。
对于无序的两个元素情况，左指针扫描并在第一个元素处停止，因为它大于划分值（左扫描值停止交换大于划分值的值）。
右指针从第一个元素开始并在第一个元素处停止，因为它已到达最左侧元素。
循环退出是因为左指针和右指针在第一个位置相等，并且左指针在第一个位置的内容和划分值在最右侧（另一个）位置的内容被交换，将先前无序的元素排列成有序的。
另一个实现问题是如何在扫描过程中移动指针。在外部循环结束时移动它们似乎很合乎逻辑。
partition(a,l,r) {
v = a[r];
i = l;
j = r -1;
while ( i <= j ) { // need to also scan when i = j as well as i < j ,
// in the 2 in-order case,
// so that i is incremented to the partition
// and nothing happens in the final swap with the partition at r.
while ( a[i] < v) ++i;
while ( v <= a[j] && j > 0 ) --j;
if ( i >= j) break;
swap(a,i,j);
++i; --j;
}
swap(a, i, r);
return i;
使用预增/减一元运算符，可以在 while 循环的测试条件中进行测试之前进行扫描，但这意味着指针应分别在开头偏移 -1 和 +1：因此，算法看起来像：-
partition (a, l, r ) {
v=a[r]; // v is partition value, at a[r]
i=l-1;
j=r;
while(true) {
while( a[++i] < v );
while( v <= a[--j] && j > l );
if (i >= j) break;
swap ( a, i, j);
}
swap (a,i,r);
return i;
}
qsort 算法是
qsort( a, l, r) {
if (l >= r) return ;
p = partition(a, l, r)
qsort(a , l, p-1)
qsort( a, p+1, r)
}
最后，划分元素的随机化。
random_partition (a,l,r) {
p = random_int( r-l) + l;
// median of a[l], a[p] , a[r]
if (a[p] < a[l]) p =l;
if ( a[r]< a[p]) p = r;
swap(a, p, r);
}
这可以在调用 qsort() 中的划分之前调用。
洗牌数组
[edit | edit source] This keeps data in during shuffle
temporaryArray = { }
This records if an item has been shuffled
usedItemArray = { }
Number of item in array
itemNum = 0
while ( itemNum != lengthOf( inputArray) ){
usedItemArray[ itemNum ] = false None of the items have been shuffled
itemNum = itemNum + 1
}
itemNum = 0 we'll use this again
itemPosition = randdomNumber( 0 --- (lengthOf(inputArray) - 1 ))
while( itemNum != lengthOf( inputArray ) ){
while( usedItemArray[ itemPosition ] != false ){
itemPosition = randdomNumber( 0 --- (lengthOf(inputArray) - 1 ))
}
temporaryArray[ itemPosition ] = inputArray[ itemNum ]
itemNum = itemNum + 1
}
inputArray = temporaryArray
相等的多元多项式
[edit | edit source][TODO：截至目前，没有已知的确定性多项式时间解决方案，但存在随机化多项式时间解决方案。最常用的例子是IsPrime，但已找到确定性多项式时间解决方案。]
哈希表
[edit | edit source]哈希依赖于哈希码函数，将键随机地均匀分布到可用的槽中。在 Java 中，这是通过将一个中等大小的素数（31 * 17）添加到一个整型键，然后对哈希表的大小取模来完成的。对于字符串键，初始哈希值是通过将每个字符的序数值乘以 31 的乘积相加得到的。
维基百科的数据结构/哈希表章节很好地涵盖了这个主题。
跳跃表
[edit | edit source][TODO：谈论跳跃表。重点是说明随机化有时可以使结构更容易理解，而不是平衡树的复杂性。]
字典或映射是一个通用概念，其中值在某个键下插入，并通过键检索。例如，在某些语言中，字典概念是内置的（Python），而在另一些语言中，它是核心库的一部分（C++ S.T.L. 和 Java 标准集合库）。提供库的语言通常允许程序员在哈希算法或平衡二叉树实现（红黑树）之间进行选择。最近，跳跃表已经出现，因为它们提供了在多线程应用程序中高度并发的实现优势。
哈希是一种技术，它依赖于键通过哈希函数时的随机性，以找到一个哈希值，该值对应于线性表中的索引。哈希运行得和哈希函数一样快，但只有当插入的键在数组中均匀分布时才能很好地工作，因为任何哈希到相同索引的键都必须作为哈希冲突问题处理，例如通过为表中的每个槽保留一个链表，并在链表中迭代以比较每个键值对的完整键与搜索键。
哈希的缺点是无法使用这种数据结构进行有序遍历。
二叉树可以用来表示字典，并且可以通过访问节点（访问左子节点，访问当前节点，访问右子节点，递归地）对二叉树进行有序遍历。当二叉树“不平衡”时，例如，插入的键值对的键以升序或降序插入时，可能会导致搜索效率低下，因此它们实际上看起来像链表，没有左子节点，并且所有右子节点都是自平衡的。二叉树可以通过概率（使用随机性）或确定性（使用子节点链接颜色为红色或黑色）进行，通过局部 3 节点树旋转操作。旋转只是将父节点与子节点交换，但保留顺序，例如，对于左子节点旋转，左子节点的右子节点成为父节点的左子节点，父节点成为左子节点的右子节点。
红黑树更容易理解，如果检查相应的2-3-4 树。2-3-4 树是一棵树，节点可以有 2 个子节点、3 个子节点或 4 个子节点，其中 3 个子节点节点在 3 个子节点之间有两个键，4 个子节点节点在 4 个子节点之间有 3 个键。4 节点被积极地拆分为 3 个单键 2 节点，中间 2 节点向上传递以与父节点合并，如果父节点是一个键的 2 节点，则成为一个键的 3 节点；或者如果是一个键的 3 节点，则成为一个键的 4 节点，它将在以后被拆分（向上）。拆分一个三键 4 节点的行为实际上是一个再平衡操作，它可以防止出现祖父母、父节点、子节点的三个节点字符串，而不会发生平衡旋转。2-3-4 树是B 树的有限例子，B 树通常具有足够多的节点以适合物理磁盘块，以便促进无法容纳在物理 RAM 中（现在这种情况不太常见）的非常大的索引的缓存。
红黑树是 2-3-4 树的二叉树表示，其中 3 节点由一个父节点和一个红色子节点建模，4 节点由一个父节点和两个红色子节点建模。4 节点的拆分由父节点和 2 个红色子节点表示，将红色子节点翻转为黑色，并将父节点翻转为红色。父节点永远不会是红色的情况，因为还会发生平衡操作，如果有一个祖父母节点、一个红色父节点和一个红色子节点，则祖父母节点被旋转为父节点的子节点，父节点变为黑色，祖父母节点变为红色；这与之前的翻转场景统一，该场景由 2 个红色子节点表示一个 4 节点。实际上，可能是这种对 4 节点的标准化，以及对倾斜或锯齿状 4 节点的强制旋转，导致了二叉树的再平衡。
一个新的优化是将任何单个右红色子节点左旋转为单个左红色子节点，以便只发生左倾斜内联 4 节点（3 个红色节点内联）的右旋转，从而简化了再平衡代码。
跳跃表以单链表为模型，不同之处在于节点是多层的。高节点很少见，但插入操作确保节点在每个级别都连接起来。
跳跃表的实现需要创建随机高度的多层节点，然后插入它们。
节点是通过随机函数的迭代创建的，其中高层节点在迭代中出现得更晚，而且更罕见，因为迭代已经经历了许多随机阈值（例如 0.5，如果随机数在 0 到 1 之间）。
插入需要一个临时的前一个节点数组，其高度与生成的插入节点相同。它用于存储给定级别的最后一个指针，该指针的键小于插入键。
扫描从跳跃列表的头部开始，在头部节点的最高级别，并继续横向扫描，直到找到一个键高于插入键的节点，并将前一个指针存储在临时前一个节点数组中。然后从该节点开始扫描下一个更低级别，依此类推，以锯齿形向下走，直到到达最低级别。
然后在临时前一个节点数组的每个级别执行列表插入，以便前一个节点的下一个节点在每个级别上都成为插入节点的下一个节点，并且插入节点成为前一个节点的下一个节点。
搜索涉及从头部节点的最高级别迭代到最低级别，并沿每个级别的下一个指针扫描，直到找到大于搜索键的节点，向下移动到下一个级别，并继续扫描，直到找到最低级别上具有更高键的节点，或者找到搜索键。
创建当更高时更不频繁的随机高度节点，以及在每个级别上链接所有节点的过程，正是跳跃列表具有优势的整体结构的原因。
一种跳跃列表实现方法：实现前瞻单链表，然后测试，然后转换为跳跃列表实现，然后进行相同的测试，最后进行性能比较
[edit | edit source]以下是跳跃列表在 Python 中的实现。首先实现一个单链表，将下一个节点始终视为当前节点，然后实现跳跃列表，尽量减少对前者的修改，比较有助于澄清实现。
#copyright SJT 2014, GNU
#start by implementing a one lookahead single-linked list :
#the head node has a next pointer to the start of the list, and the current node examined is the next node.
#This is much easier than having the head node one of the storage nodes.
class LN:
"a list node, so don't have to use dict objects as nodes"
def __init__(self):
self.k=None
self.v = None
self.next = None
class single_list2:
def __init__(self):
self.h = LN()
def insert(self, k, v):
prev = self.h
while not prev.next is None and k < prev.next.k :
prev = prev.next
n = LN()
n.k, n.v = k, v
n.next = prev.next
prev.next = n
def show(self):
prev = self.h
while not prev.next is None:
prev = prev.next
print prev.k, prev.v, ' '
def find (self,k):
prev = self.h
while not prev.next is None and k < prev.next.k:
prev = prev.next
if prev.next is None:
return None
return prev.next.k
#then after testing the single-linked list, model SkipList after it.
# The main conditions to remember when trying to transform single-linked code to skiplist code:
# * multi-level nodes are being inserted
# * the head node must be as tall as the node being inserted
# * walk backwards down levels from highest to lowest when inserting or searching,
# since this is the basis for algorithm efficiency, as taller nodes are less frequently and widely dispersed.
import random
class SkipList3:
def __init__(self):
self.h = LN()
self.h.next = [None]
def insert( self, k , v):
ht = 1
while random.randint(0,10) < 5:
ht +=1
if ht > len(self.h.next) :
self.h.next.extend( [None] * (ht - len(self.h.next) ) )
prev = self.h
prev_list = [self.h] * len(self.h.next)
# instead of just prev.next in the single linked list, each level i has a prev.next
for i in xrange( len(self.h.next)-1, -1, -1):
while not prev.next[i] is None and prev.next[i].k > k:
prev = prev.next[i]
#record the previous pointer for each level
prev_list[i] = prev
n = LN()
n.k,n.v = k,v
# create the next pointers to the height of the node for the current node.
n.next = [None] * ht
#print "prev list is ", prev_list
# instead of just linking in one node in the single-linked list , ie. n.next = prev.next, prev.next =n
# do it for each level of n.next using n.next[i] and prev_list[i].next[i]
# there may be a different prev node for each level, but the same level must be linked,
# therefore the [i] index occurs twice in prev_list[i].next[i].
for i in xrange(0, ht):
n.next[i] = prev_list[i].next[i]
prev_list[i].next[i] = n
#print "self.h ", self.h
def show(self):
#print self.h
prev = self.h
while not prev.next[0] is None:
print prev.next[0].k, prev.next[0].v
prev = prev.next[0]
def find(self, k):
prev = self.h
h = len(self.h.next)
#print "height ", h
for i in xrange( h-1, -1, -1):
while not prev.next[i] is None and prev.next[i].k > k:
prev = prev.next[i]
#if prev.next[i] <> None:
#print "i, k, prev.next[i].k and .v", i, k, prev.next[i].k, prev.next[i].v
if prev.next[i] <> None and prev.next[i].k == k:
return prev.next[i].v
if pref.next[i] is None:
return None
return prev.next[i].k
def clear(self):
self.h= LN()
self.h.next = [None]
#driver
if __name__ == "__main__":
#l = single_list2()
l = SkipList3()
test_dat = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
pairs = enumerate(test_dat)
m = [ (x,y) for x,y in pairs ]
while len(m) > 0:
i = random.randint(0,len(m)-1)
print "inserting ", m[i]
l.insert(m[i][0], m[i][1])
del m[i]
# l.insert( 3, 'C')
# l.insert(2, 'B')
# l.insert(4, 'D')
# l.insert(1, 'A')
l.show()
n = int(raw_input("How many elements to test?") )
if n <0: n = -n
l.clear()
import time
l2 = [ x for x in xrange(0, n)]
random.shuffle(l2)
for x in l2:
l.insert(x , x)
l.show()
print
print "finding.."
f = 0
t1 = time.time()
nf = []
for x in l2:
if l.find(x) == x:
f += 1
else:
nf.append(x)
t2 = time.time()
print "time", t2 - t1
td1 = t2 - t1
print "found ", f
print "didn't find", nf
dnf = []
for x in nf:
tu = (x,l.find(x))
dnf.append(tu)
print "find again ", dnf
sl = single_list2()
for x in l2:
sl.insert(x,x)
print "finding.."
f = 0
t1 = time.time()
for x in l2:
if sl.find(x) == x:
f += 1
t2 = time.time()
print "time", t2 - t1
print "found ", f
td2 = t2 - t1
print "factor difference time", td2/td1
随机性的作用
[edit | edit source]使更高节点的几何随机频率降低的想法意味着，比较的级别越高，需要比较的键就越少，并且由于这些键是随机选择的，因此这应该可以消除导致树算法需要进行树平衡的退化输入问题。由于更高级别的列表具有间隔更大的元素，但搜索算法在每次搜索在某个级别终止后都会向下移动一个级别，因此更高级别有助于“跳过”在较低级别上搜索较早元素的需要。由于存在多个跳跃级别，因此不太可能在更高级别上跳跃过少而无法在较低级别上通过更好的跳跃来弥补，并且 Pugh 声称总体性能为 O(logN)。
从概念上来说，它比平衡树更容易理解，因此更容易实现吗？从二叉树、平衡二叉树、2-3 树、红黑树和 B 树发展而来的思想形成了一个更强大的概念网络，但发展是渐进的，因此可以说，一旦理解了红黑树，它们就具有更多有助于记忆或刷新记忆的概念背景。
并发访问应用程序
[edit | edit source]除了使用随机化来增强链表的基本内存结构之外，跳跃列表还可以扩展为在多处理器应用程序中使用的全局数据结构。请参阅本章末尾的补充主题。
练习的想法
[edit | edit source]将 Linux 完全公平调度程序的红黑树实现替换为跳跃列表，看看重新编译后你的 Linux 版本运行情况如何。
树堆
[edit | edit source]树堆是一种双键二叉树，它使用第二个随机生成的键和前面讨论过的树操作（父节点-子节点旋转）来随机旋转树，以便总体上生成一个平衡树。回想一下，二叉树的工作原理是将所有左子树中的节点都小于给定节点，并将所有右子树中的节点都大于给定节点。还要记住，节点旋转不会破坏此顺序（有些人称之为不变式），但会改变父节点和子节点的关系，因此，如果父节点小于右子节点，则父节点会变成以前右子节点的左子节点。树堆或树堆的想法是，在父节点和子节点之间保持二叉堆关系，即父节点的优先级高于其子节点，这与二叉树中键的左右顺序不同，因此，最近插入的二叉树叶节点恰好具有很高的随机优先级，可以被旋转，使其在树中相对较高，没有优先级较低的父节点。
树堆是红黑树和跳跃列表的替代方案，是一种自平衡排序存储结构。
Java 树堆实现示例
[edit | edit source]// Treap example: 2014 SJT, copyleft GNU .
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Random;
public class Treap1<K extends Comparable<K>, V> {
public Treap1(boolean test) {
this.test = test;
}
public Treap1() {}
boolean test = false;
static Random random = new Random(System.currentTimeMillis());
class TreapNode {
int priority = 0;
K k;
V val;
TreapNode left, right;
public TreapNode() {
if (!test) {
priority = random.nextInt();
}
}
}
TreapNode root = null;
void insert(K k, V val) {
root = insert(k, val, root);
}
TreapNode insert(K k, V val, TreapNode node) {
TreapNode node2 = new TreapNode();
node2.k = k;
node2.val = val;
if (node == null) {
node = node2;
} else if (k.compareTo(node.k) < 0) {
node.left = insert(k, val, node.left);
} else {
node.right = insert(k, val, node.right);
}
if (node.left != null && node.left.priority > node.priority) {
// right rotate (rotate left node up, current node becomes right child )
TreapNode tmp = node.left;
node.left = node.left.right;
tmp.right = node;
node = tmp;
} else if (node.right != null && node.right.priority > node.priority) {
// left rotate (rotate right node up , current node becomes left child)
TreapNode tmp = node.right;
node.right = node.right.left;
tmp.left = node;
node = tmp;
}
return node;
}
V find(K k) {
return findNode(k, root);
}
private V findNode(K k, Treap1<K, V>.TreapNode node) {
// TODO Auto-generated method stub
if (node == null)
return null;
if (k.compareTo(node.k) < 0) {
return findNode(k, node.left);
} else if (k.compareTo(node.k) > 0) {
return findNode(k, node.right);
} else {
return node.val;
}
}
public static void main(String[] args) {
LinkedList<Integer> dat = new LinkedList<Integer>();
for (int i = 0; i < 15000; ++i) {
dat.add(i);
}
testNumbers(dat, true); // no random priority balancing
testNumbers(dat, false);
}
private static void testNumbers(LinkedList<Integer> dat,
boolean test) {
Treap1<Integer, Integer> tree= new Treap1<>(test);
for (Integer integer : dat) {
tree.insert(integer, integer);
}
long t1 = System.currentTimeMillis();
Iterator<Integer> iter = dat.iterator();
int found = 0;
while (iter.hasNext()) {
Integer j = desc.next();
Integer i = tree.find(j);
if (j.equals(i)) {
++found;
}
}
long t2 = System.currentTimeMillis();
System.out.println("found = " + found + " in " + (t2 - t1));
}
}
树堆与伸展树的对比
[edit | edit source]伸展树与树堆类似，它们都使用旋转将高优先级节点带到顶部，而不会改变主键顺序，只是它们不使用随机键来确定优先级，而是将最后访问的节点旋转到树的根部，以便更频繁访问的节点将位于顶部附近。这意味着在树堆中，插入的节点只会旋转到其随机优先级键所确定的优先级，而在伸展树中，插入的节点会被旋转到根部，并且伸展树中的每次搜索都会导致重新平衡，但在树堆中并非如此。
去随机化
[edit | edit source][待办事项：存在针对快速排序的确定性算法，其性能与快速排序在平均情况下一样好，并且保证在所有情况下至少达到这种性能。最棒的是，不需要随机化。讨论中还应该包含一些关于使用随机化的观点：一些随机化算法为您提供的置信概率比实际硬件本身还要高！（例如，太阳黑子会随机翻转硬件中的位，导致故障，这是我们经常承担的风险）]
[主要思想：查看所有包含 5 个元素的块，并选择中位数（O(1) 选择），将所有中位数放入数组中（O(n)），递归地选择该数组的中位数，重复此操作，直到数组中少于 5 个元素。这种对每五个元素进行递归中位数构造需要时间 T(n)=T(n/5) + O(n)，根据主定理，这等于 O(n)。因此，可以在 O(n) 时间内找到正确的枢轴。需要证明此枢轴足够好，以便无论输入是什么，我们仍然是 O(n log n)。这种快速排序版本不需要 rand，而且它永远不会表现不佳。仍然需要证明选出的元素是足够好的枢轴。]
练习
[edit | edit source]- 编写一个find-min函数，并在几个不同的输入上运行它，以演示其正确性。
多处理器硬件提供 CAS（比较并设置）或 CMPEXCHG（比较并交换）（英特尔手册 253666.pdf，第 3-188 页）原子操作，其中将预期值加载到累加器寄存器中，与目标内存位置的内容进行比较，如果相同，则将源内存位置的内容加载到目标内存的内容中，并设置零标志，否则，如果不同，则将目标内存的内容返回到累加器中，并取消设置零标志，例如，表示锁争用。在英特尔架构中，在 CMPEXCHG 之前发出 LOCK 指令，如果内存位置正在被缓存，则锁定缓存以防止并发访问，否则，如果不在缓存中，则锁定共享内存位置，以用于下一条指令。
CMPEXCHG 可用于实现锁定，其中自旋锁（例如，直到设置零标志为止一直重试）在设计上是最简单的。
无锁设计通过避免自旋等待锁来提高效率。
Java 标准库有一个非阻塞并发跳跃表的实现，基于一篇名为“非阻塞单链表的实用实现”的论文。
跳跃表实现是对无锁单链表的扩展，下面对其进行描述：-
**插入** 操作为：X -> Y 插入 N，N -> Y，X -> N；预期结果为 X -> N -> Y。
如果 M 在 X 和 Y 之间插入，并且 M 先完成，然后 N 完成，那么情况是 X -> N -> Y <- M，则存在竞争条件。
M 不在列表中。CAS 操作避免了这种情况，因为它在更新 X -> 之前检查了 -> Y 的副本，与 X -> 的当前值进行比较。
如果 N 先更新 X ->，那么当 M 尝试更新 X -> 时，它在执行 M -> Y 之前获得的 X -> Y 副本与 X -> N 不匹配，因此 CAS 返回非零标志设置（回想一下，CAS 要求用户将累加器加载为预期值、目标位置的当前值，然后如果目标位置仍然包含累加器的值，则原子地将目标位置更新为源位置）。尝试插入 M 的进程然后可以在 X 之后重试插入，但现在 CAS 检查 -> N 是 X 的下一个指针，所以重试后，X->M->N->Y，并且两个插入都没有丢失。
如果 M 先更新 X->，N 的 X->Y 副本与 X -> M 不匹配，因此 CAS 在这里也会失败，并且上面重试插入 N 的进程将具有 X ->N -> M -> Y 的序列化结果。
**删除** 操作依赖于在“物理”删除之前进行单独的“逻辑”删除步骤。
“逻辑”删除涉及将下一个指针更改为“标记”指针的 CAS。Java 实现用原子地将代理标记节点插入到下一个节点来代替。
这可以防止未来的插入在具有标记下一个指针的节点之后插入，使后一个节点“逻辑地”删除。
**插入** 操作依赖于另一个函数，*search*，返回在调用时为2个**未标记**的节点指针：第一个指向节点，其下一个指针等于第二个。
第一个节点是插入点之前的节点。
*insert* CAS 操作检查第一个节点的当前下一个指针是否与第二个的未标记引用相对应，因此如果第一个节点的 *next* 指针在调用上面的 *search* 函数后变为标记，则“逻辑上”会失败，因为第一个节点已并发地逻辑地删除。
这满足了防止在节点删除后并发地进行插入的目标。
如果插入操作失败，则前一个节点的下一个指针的 CAS，则从**整个列表的开头**重新开始搜索插入点，因为需要找到一个新的未标记的前一个节点，并且由于列表节点是单链表，因此没有前一个节点指针。
上面概述的**删除** 操作也依赖于 *search* 操作返回两个 *未标记* 的节点，以及删除中的两个 CAS 操作，一个用于逻辑删除或标记第二个指针的下一个指针，另一个用于通过使第一个节点的下一个指针指向第二个节点的未标记的下一个指针来进行物理删除。
删除的第一个 CAS 仅在检查第二个节点原始下一个指针的副本未被标记之后才会发生，并确保只有读取第二个节点的当前下一个指针为未标记的并发删除成功。
第二个 CAS 检查前一个节点是否已被逻辑地删除，因为它的下一个指针与由 search 函数返回的当前第二个节点的未标记指针不同，因此仅更新活动的前一个节点的下一个指针为正在删除的节点的原始未标记下一个指针的副本（其下一个指针已由第一个 CAS 标记）。
如果第二个 CAS 失败，那么前一个节点已被逻辑地删除，并且它的下一个指针被标记，当前节点的下一个指针也是如此。再次调用 *search* 函数会整理好事情，因为它试图找到当前节点的键并返回相邻的未标记的前一个和当前指针，并且在这样做的过程中，它截断了一系列逻辑删除的节点。
饥饿可能是可能的，因为失败的插入必须从列表的开头重新开始。无等待性是一个概念，在这个概念中，算法的所有线程都免受饥饿的困扰。
存在 ABA 问题，其中垃圾收集器回收指针 A，但地址被加载为不同的地址，并且在另一个线程读取 A 并执行 CAS 检查 A 未更改时，指针被重新添加到一个点：地址相同并且未标记，但 A 的内容已更改。