Menu Sidebar
Menu

June 2020

TimSort

TimSort其实就是插入排序和合并排序的综合体. 首先切分数组, 然后利用插入排序对小数组的优势, 先sort小数组, 然后再merge几个小数组. code我是直接抄github的

ComboSort

Combosort是一个基于swap的排序, 和冒泡排序一样, 它改良了冒泡排序中只对相邻元素做比较然后swap的特点, 通过使用gap 表示两个数时间的index位置, 然后用gap除以一个经验定值1.3,获得当前比较的两个数的位置. gap从n一直减小到1, 然后完成排序.

Bitonic Sort双调排序

这个排序的名字很好玩, Bi是双的意思 tonic是音乐的元音. 所以叫双调, 就是两个调性(递增 递减). 具体的操作可以看 https://en.wikipedia.org/wiki/Bitonic_sorter 我主要讲讲下面这个例子: [5,2,1,7,3,8,6,4], len = 8 第一步先临近的两个元素比大小, 比如[5,2]变成[2,5], [1,7]变成[7,1], 数组变为 [2,5], [7,1], [3,8], [6,4] 此时序列为[2,5,7,1,3,8,6,4] 这样就是递增, 递减, 递增 递减的两对儿双调.然后就是合并两个双调. 合并的方法是用的wiki中的batcher理论. 显示四个为一组合并, 然后是两个为一组合并. 四个为一组: [2,1,7,5] ([2,5]和[7,1]合并的结果) [6,8,3,4] ([3,8]和[6,4]合并的结果) 此时的序列为[2,1,7,5,6,8,3,4] 此时, 并不是双调序列, 还需要进行两个为一组的合并. [2,1,7,5] 变成 [1,2,5,7] 递增 [6,8,3,4] 变成 [8,6,4,3] 递减, 此时序列为[1,2,5,7,8,6,4,3] 最后要进行八个一组的合并, 然后是四个一组, 然后是两个一组. 八个一组后: [1,2,4,3,8,6,5,7] 四个一组后: [1,2,4,3,5,6,8,7] 两个一组后: […]

BeadSort重力排序

最近在看好玩的算法, 重力排序是一个根据重力(Gravity)原理的自动排序, 这个排序是自然排序的一种, 非人为操作便可实现. 这种排序非常适合给小孩子解释排序的原理和自然需求. 上面这个图就是重力排序, 首先找出最大的数, 上图中是4, 然后设为m, 就是有m个pole(杆子), 这图就是4个杆子. 然后横着看, 每个row就是当前数字有几便有几个球. 比如row 1 (ary[0] = 2) 是2, 就是两个珠子. 然后让数字随着重力下落即可排序, 具体证明和复杂度wiki有. https://en.wikipedia.org/wiki/Bead_sort 可以看出这种排序用机械实现还可以, 用算法实现效率并不好. 上面是一个实现, 具体来说, 最难的地方在于如何实现珠子下落 代码首先计算一个pole上有几个珠子, 然后计算有几个空位, 把空位补上珠子,就是下落后的个数. 最后这个算法的弱点是只能sort正整数, 而且如果数字很离散, 那么效率就太低了

Mediawiki + Elasticsearch

跟着 https://www.mediawiki.org/wiki/Extension:CirrusSearch 装就可以. 注意两个插件都要装好, 然后再装Elasticsearch 装CirrusSearch的时候, 需要用里面的ReadMe文件去装, 每个版本对应的Mediawiki的改动的都不一样, 要注意去看. 这里需要注意的是用https://hub.docker.com/r/wikibase/elasticsearch 这个image, 否则肯定会出错. 装完后建议用update.php更新一下

如何迁移MediaWiki

我们的目标: 将现有的Mediawiki从一个域名迁移到另一个域名. 或者一个空间到另一个空间. 迁移不改变数据库内容, wiki中的内部和外部链接, wiki的用户权限. 此方法也适用于升级Mediawiki, 但仅限于将wiki升到非测试版. 步骤: 备份数据库, 备份wiki, 备份LocalSettings.php 具体方法有很多种, 这里随意. 在新的域名/空间, 配置一个新的mediawiki和数据库. 把新的LocalSettings.php下载到本地, 然后和现有的LocalSettings.php, 把现有的LocalSettings.php中的数据库连接, wiki名字, 版本等信息, 替换. 把替换好的LocalSettings.php放到新的空间里, 然后执行maintenance/update.php. 这时会自动建立数据库. php rebuildtextindex.php 执行每一个extension下面的update.php, 确保新数据库完整. 把旧数据库导入新数据库. 完成. 其他: 如果使用了parsoid server (visual editor), 需要改parsoid的api文件, 改域名和wiki的api位置. 我尝试了直接转移数据库, 但是没有成功. 我曾经没有完全更新extension后就转移数据库, 结果网站挂掉了, 失败.

Older Posts

书脊

这青苔碧瓦堆, 俺曾睡风流觉, 将五十年兴亡看饱.