python - 在python中快速排序很长的整数列表
问题描述
我有一个包含几亿个 np.uint8 元素的向量。它们的值范围仅从 0 到 255。
我需要对这个列表进行排序,我认为它应该比快速排序更快。我想我可以找到所有值“0”的索引并将它们放在前面,然后将所有值“1”放在最后一次插入之后,然后继续进行直到我完成。它将是唯一的突变后代,并带有一些索引,并且应该很快工作。
有没有一个内置的东西可以很好地、正确地、在像“C”这样快速的东西中做到这一点,而我不必自制它?你能指点我吗?
假设作为我实际问题的“玩具”,我想对 100 兆像素版本的山魈图像的每种颜色 (rgb) 的强度值进行排序,其中每种颜色都已转换为一个非常长的向量uint8 值。如果我要在python中计算排序方法之间的差异,这将是合理的计算?
解决方案
你可能会发现这numpy.bincount
就是你所需要的。它计算数据中每个整数的出现次数。
例如,这里有一些随机的无符号 8 位整数:
In [100]: np.random.seed(8675309)
In [101]: r = np.random.gamma(9, scale=8.5, size=100000).astype(np.uint8)
In [102]: r.min(), r.max()
Out[102]: (11, 242)
使用 计算整数bincount
:
In [103]: b = np.bincount(r, minlength=256)
In [104]: b
Out[104]:
array([ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1, 1, 3, 1, 5, 13, 9, 17, 24, 31, 27,
41, 55, 63, 96, 131, 146, 178, 210, 204, 268, 297,
308, 367, 422, 480, 512, 584, 635, 669, 671, 759, 830,
885, 934, 955, 1025, 1105, 1146, 1145, 1344, 1271, 1353, 1300,
1456, 1419, 1451, 1504, 1499, 1561, 1600, 1509, 1678, 1621, 1643,
1633, 1616, 1574, 1677, 1664, 1682, 1625, 1608, 1581, 1598, 1575,
1583, 1524, 1493, 1381, 1448, 1399, 1422, 1249, 1322, 1225, 1278,
1174, 1246, 1128, 1161, 1077, 999, 1033, 980, 981, 897, 917,
880, 813, 779, 774, 697, 716, 651, 612, 657, 592, 556,
497, 482, 474, 484, 445, 411, 399, 354, 368, 363, 342,
313, 301, 293, 263, 241, 249, 244, 196, 215, 182, 189,
172, 161, 139, 143, 142, 120, 121, 104, 103, 112, 88,
82, 88, 67, 60, 83, 57, 63, 59, 50, 52, 55,
40, 34, 34, 43, 35, 33, 28, 24, 26, 20, 18,
21, 26, 30, 17, 15, 12, 17, 11, 7, 6, 16,
8, 3, 4, 12, 9, 6, 5, 8, 10, 7, 1,
4, 8, 5, 3, 2, 1, 0, 1, 1, 0, 1,
0, 0, 4, 2, 2, 0, 0, 2, 0, 1, 1,
1, 4, 0, 0, 0, 0, 0, 0, 0, 0, 2,
1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0,
0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0,
1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0])
所以 0 出现 0 次r
, 13 出现 3 次,依此类推:
In [105]: b[0], b[13]
Out[105]: (0, 3)
推荐阅读
- graphics - Eliminate skewing effect in combined track and zoom
- php - 表单提交后回显选择选项数据属性值
- python - 如何通过嵌套字典值迭代字典字典
- c# - 从内联 Linq 转换为 Linq 查询?
- c++ - 构造函数被调用的次数
- algorithm - 为什么每次插入左倾红黑树后都需要将根着色为黑色?
- angularjs - AngularJS中的控制器未正确处理日期选择器日期
- visual-studio-2017 - 如何修复损坏的 MSVC 库?
- reactjs - attrTween 打字稿问题
- scala - Spark Dataframe 的 where 子句可以将变量作为参数吗?