SWIG 磨人

每次用新工具, 我都要觉得这东西不够灵活.

SWIG 自1995 年开始, 至今也算稳定了. 只是稳定到一个不够 versatile 的状态.

SWIG的Typemap很方便, 只可惜, 找不到将多参数一起解析, 或者解析时引用前面参数的方法. 文档里倒是明确提到 numinputs 须为0或1, 像是不支持这个.

文档里找不到, 邮件列表里没人解答, 虽然还没到最后一步看实现, 估计我也放弃了. 有新资源申请依赖参数时, 手写Python扩展也比这个框架下写接口来得快.

``SWIG垃圾, 支持多语言的自然做不好.''

``框架!''

虽然, 倒是从 numpy.i 里找出一些代码, 包装数组挺方便的.

纯属测试: 中共匪然海外的都与敏感词相关么.

几种简单的排序算法比较次数比较

几种简单的排序算法比较次数比较

1 说明

几种排序算法, 有一些是简单实现, 另有 glibc 的 qsort 和 GNU C++ 库的 std::sort. 下面的时间是排序 long 型数组的时间. 其实, 是一个 C 里 Sequence, 但此 Sequence 占用的时间和时间的误差相近, 在 10% 左右.

比较程序使用 random 生成数组, 在数组比较小时, 排序并打乱数组多次, 取时 间平均值, 最后几个, 因时间比较大, 只比较一次. 所以, 在所有的时间里, 有 打乱数组的时间开销, 大致为 O(size * time(random)). 本文只关心相对比较明 显的差异, 故不细分这些.

各排序算法如其名. 其中 quicksort_nr 是快速排序的非递归版, cqsort 是调 C 标准库函数 qsort. std::sort(iterator) 中的 get/set 不能区分, 统一计在 get 下.

C 的 qsort 由于必须有函数指针, 比较是相对较大开销, 所以在数组较小, 且内 存足够时采用需要额外内存但比较次数最少的归并排序. C++ 采用的是 quicksort 和 heapsort 的杂交 introsort, 比较次数相对归并排序多一点, 但 对整数而言, 比较仅是减法, 受限于内存访问的时间, 估可以次要考虑.

2 sort comparisons table


Algo.Sizetime# comparisons/size# gets/size# sets/size
introsort2^52.29932e-065.274929.386234.00063
heapsort2^52.70095e-065.1821813.22918.45347
mergesort2^52.37965e-063.796959.296956
quicksort2^52.19414e-065.560798.3592.83799
quicksort_nr2^52.15747e-065.369258.235582.85841
cqsort2^52.98512e-063.79623NANA
combsort2^52.41381e-068.8018417.61233.36478
std::sort(iterator)324.68653e-065.9521813.9444NA
std::sort321.65281e-065.94951NANA
introsort2^64.42774e-066.5157111.08174.47673
heapsort2^65.82915e-066.2620715.3059.46844
mergesort2^64.97256e-064.7661510.26626
quicksort2^64.87501e-066.7783410.05663.35011
quicksort_nr2^64.76849e-066.602369.942053.3574
cqsort2^66.40913e-064.76535NANA
combsort2^65.18118e-0611.609423.22344.28761
std::sort(iterator)643.99712e-067.1153315.4967NA
std::sort643.62354e-067.12488NANA
introsort2^71.00313e-057.7648812.82934.99319
heapsort2^71.28292e-057.3085817.346110.4755
mergesort2^71.94854e-055.7494213.24948
quicksort2^71.06718e-057.9855111.7373.83951
quicksort_nr2^71.05284e-057.8048811.6143.8471
cqsort2^71.41386e-055.74657NANA
combsort2^71.22646e-0514.512629.02745.30448
std::sort(iterator)1288.65036e-068.3236917.1383NA
std::sort1287.87806e-068.31551NANA
introsort2^82.16346e-058.9674514.52865.49551
heapsort2^82.79746e-058.3332119.368211.4748
mergesort2^82.38339e-056.7419714.2428
quicksort2^82.26148e-059.2145413.43754.31297
quicksort_nr2^82.29063e-059.0021713.29554.34143
cqsort2^83.07402e-056.74541NANA
combsort2^82.71602e-0517.38334.76726.34737
std::sort(iterator)2561.99121e-059.5476518.8368NA
std::sort2561.73477e-059.57421NANA
introsort2^94.58946e-0510.155616.22476.01352
heapsort2^96.01988e-059.3549621.392212.4821
mergesort2^95.17732e-057.7391117.23911NA
quicksort2^94.92418e-0510.361815.06154.8
quicksort_nr2^94.81522e-0510.183314.95124.81563
cqsort2^96.54729e-057.74022NANA
combsort2^95.884e-0520.352140.70477.38508
std::sort(iterator)5124.32935e-0510.795420.6048NA
std::sort5123.68822e-0510.7974NANA
introsort2^100.00010043811.358217.93566.51449
heapsort2^100.00012830510.36123.397413.4805
mergesort2^100.0001068048.7383318.238310
quicksort2^100.00010464911.575716.74615.26775
quicksort_nr2^100.00010298411.430216.65645.27142
cqsort2^100.0001853988.73907NANA
combsort2^100.00014446923.950847.90198.49806
std::sort(iterator)10248.9258e-0511.954622.1866NA
std::sort10247.89147e-0512.0618NANA
introsort2^110.00023065512.532219.69557.09028
heapsort2^110.00028826711.366225.402514.4817
mergesort2^110.0002396899.736421.236412
quicksort2^110.0002410312.732318.37895.75391
quicksort_nr2^110.00021754612.538318.26075.76871
cqsort2^110.0003054819.737NANA
combsort2^110.00028974927.091954.1849.64027
std::sort(iterator)20480.00019089113.173523.8782NA
std::sort20480.0001666413.1915NANA
introsort2^120.00046250213.841621.60967.6772
heapsort2^120.00057006612.3727.40515.4825
mergesort2^120.00051040910.736522.236512
quicksort2^120.00046962513.945920.08336.24193
quicksort_nr2^120.0004639113.70619.90276.24634
cqsort2^120.00064265710.7388NANA
combsort2^120.00063899930.262260.524510.6047
std::sort(iterator)40960.00040534114.465525.6454NA
std::sort40960.00035872314.6613NANA
introsort2^130.00094431614.980323.25488.18111
heapsort2^130.001234513.372829.409616.483
mergesort2^130.0011129411.736625.236614
quicksort2^130.0010070715.123421.73036.71223
quicksort_nr2^130.00099806514.859921.5356.73174
cqsort2^130.0013335511.7354NANA
combsort2^130.0014358233.842267.684511.7082
std::sort(iterator)81920.00086368615.767427.4121NA
std::sort81920.0007462515.6189NANA
introsort2^140.0021051216.12624.96778.75029
heapsort2^140.0026205214.369431.403517.4816
mergesort2^140.0023129912.738226.238214
quicksort2^140.0024223616.135823.23437.2082
quicksort_nr2^140.0023941416.129923.26887.187
cqsort2^140.0029565112.7369NANA
combsort2^140.0031642637.091274.182512.864
std::sort(iterator)163840.0018147517.111929.2536NA
std::sort163840.0016003817.1486NANA
introsort2^150.0050492317.369626.83739.35675
heapsort2^150.0056817515.364833.398918.474
mergesort2^150.0054972813.733129.233116
quicksort2^150.0046777717.763325.28967.6303
quicksort_nr2^150.0050014917.266224.89327.67592
cqsort2^150.0065320113.7351NANA
combsort2^150.007007340.216780.433413.9531
std::sort(iterator)327680.0038477818.333830.9398NA
std::sort327680.0033502617.9507NANA
introsort2^160.0096925518.517228.58199.94678
heapsort2^160.011969116.361935.397519.4703
mergesort2^160.010597514.732930.232916
quicksort2^160.0094070418.323526.40238.18502
quicksort_nr2^160.0095629718.106626.24758.1935
cqsort2^160.012993514.7351NANA
combsort2^160.014304543.214286.428415.0652
std::sort(iterator)655360.008198519.551932.6143NA
std::sort655360.007059119.4078NANA
introsort2^170.019830919.252129.675810.3184
heapsort2^170.02646817.355437.389520.462
mergesort2^170.024387815.734633.234618
quicksort2^170.02496719.918428.44278.62446
quicksort_nr2^170.020683119.672828.28098.6527
cqsort2^170.02870815.7364NANA
combsort2^170.03145146.213292.426316.2224
std::sort(iterator)1310720.01720620.735934.2805NA
std::sort1310720.014752920.7001NANA
introsort2^180.042837120.776331.991711.08
heapsort2^180.06022518.35439.387821.461
mergesort2^180.05420416.735434.235418
quicksort2^180.044906120.932329.95069.11972
quicksort_nr2^180.044407120.791129.85849.11888
cqsort2^180.061237116.7355NANA
combsort2^180.070429149.212798.425317.2837
std::sort(iterator)2621440.036987121.805635.8416NA
std::sort2621440.033554121.7911NANA
introsort2^190.1053122.116633.975611.7039
heapsort2^190.16923119.35441.387622.4603
mergesort2^190.12893617.736237.236220
quicksort2^190.10564522.126731.60429.58018
quicksort_nr2^190.10500522.23431.77779.59514
cqsort2^190.15018217.7361NANA
combsort2^190.18412852.2115104.42318.3483
std::sort(iterator)5242880.094221123.330637.815NA
std::sort5242880.085955124.1802NANA
introsort2^200.24776423.447536.075412.4453
heapsort2^200.44266320.354543.388723.4609
mergesort2^200.29055618.73638.23620
quicksort2^200.25062623.241233.207410.0712
quicksort_nr2^200.25393123.307133.318110.0623
cqsort2^200.34422118.736NANA
combsort2^200.4308656.2095112.41919.3904
std::sort(iterator)10485760.23045923.955438.9847NA
std::sort10485760.2057224.3193NANA
introsort2^210.55471224.174837.159812.82
heapsort2^211.0754921.354445.388924.4613
mergesort2^210.65845219.736141.236122
quicksort2^210.56490924.339434.798310.5612
quicksort_nr2^210.55677324.050934.580810.582
cqsort2^210.75741919.7364NANA
combsort2^210.97694859.2084118.41720.509
std::sort(iterator)20971520.50442225.502140.9916NA
std::sort20971520.47248925.5631NANA
introsort2^221.2034625.508839.172713.4783
heapsort2^222.4821322.354247.388525.4608
mergesort2^221.3851220.735742.235722
quicksort2^221.208825.605936.527511.0243
quicksort_nr2^221.1937125.868336.81310.995
cqsort2^221.563720.7359NANA
combsort2^222.0283262.2124124.42521.6898
std::sort(iterator)41943041.0736826.534242.514NA
std::sort41943040.97738226.8222NANA
introsort2^232.4810726.994841.425114.2166
heapsort2^235.7018423.353949.388126.4607
mergesort2^232.9349221.735745.235724
quicksort2^232.5393726.489637.922611.5348
quicksort_nr2^232.5229828.030939.391311.4106
cqsort2^233.2848121.7354NANA
combsort2^234.399466.2117132.42322.7599
std::sort(iterator)83886082.2389927.888244.3053NA
std::sort83886082.0583327.8466NANA
introsort2^245.2841128.792744.279615.2239
heapsort2^2412.959524.354151.388327.4607
mergesort2^245.9699422.735746.235724
quicksort2^245.1942527.937639.818211.9814
quicksort_nr2^245.2373527.937639.857311.9697
cqsort2^246.7785722.7356NANA
combsort2^248.8429169.2087138.41723.8582
std::sort(iterator)167772164.7065928.79545.7217NA
std::sort167772164.2997529.2741NANA