分页： 1 / 2
研究新的矩阵乘法不如研究排序排序的impact打多了
发表于 ： 2022年 10月 5日 20:07
由 fulvshou
码农考试不如也考排序
大部分码农都码不出两种以上排序
Re: 研究新的矩阵乘法不如研究排序排序的impact打多了
发表于 ： 2022年 10月 5日 20:36
由 Rabboni
瓦特法克，我会至少十种排序。
Re: 研究新的矩阵乘法不如研究排序排序的impact打多了
发表于 ： 2022年 10月 5日 20:44
由 fulvshou
Rabboni 写了： 2022年 10月 5日 20:36
瓦特法克，我会至少十种排序。
你会把把两种排序整到一个排序里吗
Re: 研究新的矩阵乘法不如研究排序排序的impact打多了
发表于 ： 2022年 10月 5日 20:54
由 goFan
要是能把有限元算明白了差不多，解决流体力学的大问题
排序算啥，早研究透了
Re: 研究新的矩阵乘法不如研究排序排序的impact打多了
发表于 ： 2022年 10月 5日 21:56
由 Rabboni
goFan 写了： 2022年 10月 5日 20:54
要是能把有限元算明白了差不多，解决流体力学的大问题
排序算啥，早研究透了
瞎几把扯，排序远远没有研究透。现在的排序算法，普遍使用的是快速排序，但快速排序远远不能说是perfect。
相反，有限元倒是没啥搞头了，流体力学大雷诺数，特别是湍流，是稳定性的问题，误差扩散的问题，跟有限元算法本身没几把关系，换无限元也是一个几把德性。
Re: 研究新的矩阵乘法不如研究排序排序的impact打多了
发表于 ： 2022年 10月 5日 22:24
由 tekkamanz
Rabboni 写了： 2022年 10月 5日 21:56
瞎几把扯，排序远远没有研究透。现在的排序算法，普遍使用的是快速排序，但快速排序远远不能说是perfect。
相反，有限元倒是没啥搞头了，流体力学大雷诺数，特别是湍流，是稳定性的问题，误差扩散的问题，跟有限元算法本身没几把关系，换无限元也是一个几把德性。
排序和信号处理很像 必须是有某些已知特性才进一步能优化 否则时间复杂度的极限就是nlogn
Re: 研究新的矩阵乘法不如研究排序排序的impact打多了
发表于 ： 2022年 10月 5日 22:26
由 fulvshou
tekkamanz 写了： 2022年 10月 5日 22:24
排序和信号处理很像 必须是有某些已知特性才进一步能优化 否则时间复杂度的极限就是nlogn
研究的事 worst case upper bound
Re: 研究新的矩阵乘法不如研究排序排序的impact打多了
发表于 ： 2022年 10月 5日 22:59
由 TheMatrix2
tekkamanz 写了： 2022年 10月 5日 22:24
排序和信号处理很像 必须是有某些已知特性才进一步能优化 否则时间复杂度的极限就是nlogn
对。问题空间和算法都可以细分。
Re: 研究新的矩阵乘法不如研究排序排序的impact打多了
发表于 ： 2022年 10月 5日 23:01
由 bce
fulvshou 写了： 2022年 10月 5日 20:44
你会把把两种排序整到一个排序里吗
抢答，
Re: 研究新的矩阵乘法不如研究排序排序的impact打多了
发表于 ： 2022年 10月 6日 01:14
由 Rabboni
bce 写了： 2022年 10月 5日 23:01
抢答，
瞎几把扯，最简单的排序是地精排序，只需要一个循环。只是因为在循环中有倒退，所以实际上还是二重循环。
Re: 研究新的矩阵乘法不如研究排序排序的impact打多了
发表于 ： 2022年 10月 6日 01:27
由 da1gaku
其实矩阵乘法也是研究生算法课里都要讲的内容。divide and conquer的一个案例
简单按数学定义来写程序是最笨的办法。
Re: 研究新的矩阵乘法不如研究排序排序的impact打多了
发表于 ： 2022年 10月 6日 01:30
由 da1gaku
tekkamanz 写了： 2022年 10月 5日 22:24
排序和信号处理很像 必须是有某些已知特性才进一步能优化 否则时间复杂度的极限就是nlogn
随便用个hashing就能实现O(N)啊。一个特例就是bucket sort
Re: 研究新的矩阵乘法不如研究排序排序的impact打多了
发表于 ： 2022年 10月 6日 01:30
由 goFan
矩阵乘法除了矢量并行计算，有别的快速算法吗
Re: 研究新的矩阵乘法不如研究排序排序的impact打多了
发表于 ： 2022年 10月 6日 01:44
由 tekkamanz
da1gaku 写了： 2022年 10月 6日 01:30
随便用个hashing就能实现O(N)啊。一个特例就是bucket sort
你是在搞笑吗？
你说的的这些都是复杂度不稳定的排序
问个简单问题 bucket size怎么确定？如果所有的数都落在一个bucket里面 是不是还要用快排算一遍？
Re: 研究新的矩阵乘法不如研究排序排序的impact打多了
发表于 ： 2022年 10月 6日 02:04
由 da1gaku
tekkamanz 写了： 2022年 10月 6日 01:44
你是在搞笑吗？
你说的的这些都是复杂度不稳定的排序
问个简单问题 bucket size怎么确定？如果所有的数都落在一个bucket里面 是不是还要用快排算一遍？
你说“时间复杂度的极限就是O(N)”，我只是指出一个理论错误。
space complexity和time complexity是可以互相compromise的
考虑都是整数的情况，如果数据量不是特别大（对于当今的系统来说常常是这样），直接弄个大数组，把它们放进index为自身的位置就行了。
当然实际上不会这么操作，因为那太傻。
Re: 研究新的矩阵乘法不如研究排序排序的impact打多了
发表于 ： 2022年 10月 6日 02:12
由 tekkamanz
da1gaku 写了： 2022年 10月 6日 02:04
你说“时间复杂度的极限就是O(N)”，我只是指出一个理论错误。
space complexity和time complexity是可以互相compromise的
考虑都是整数的情况，如果数据量不是特别大（对于当今的系统来说常常是这样），直接弄个大数组，把它们放进index为自身的位置就行了。
当然实际上不会这么操作，因为那太傻。
你是来抬杠的吗？
你好好读读我的第二句话
Re: 研究新的矩阵乘法不如研究排序排序的impact打多了
发表于 ： 2022年 10月 6日 02:15
由 bce
即使数据量不大，你考虑下128位/256位/1024位整数，这个数组怎么建？
da1gaku 写了： 2022年 10月 6日 02:04
你说“时间复杂度的极限就是O(N)”，我只是指出一个理论错误。
space complexity和time complexity是可以互相compromise的
考虑都是整数的情况，如果数据量不是特别大（对于当今的系统来说常常是这样），直接弄个大数组，把它们放进index为自身的位置就行了。
当然实际上不会这么操作，因为那太傻。
Re: 研究新的矩阵乘法不如研究排序排序的impact打多了
发表于 ： 2022年 10月 6日 02:18
由 da1gaku
bce 写了： 2022年 10月 6日 02:15
即使数据量不大，你考虑下128位整数/256位/1024位整数，这个数组怎么建？
那个其实就不是排序本身的问题了。大数字在各种运算中总会有各种麻烦。
具体到这种情况可以先都取log（或者移位），等等。一般这些计算认为是constant复杂度。
实际中bucket sort不常用，就是因为太傻。
Re: 研究新的矩阵乘法不如研究排序排序的impact打多了
发表于 ： 2022年 10月 6日 02:24
由 tekkamanz
da1gaku 写了： 2022年 10月 6日 02:18
那个其实就不是排序本身的问题了。大数字在各种运算中总会有各种麻烦。
具体到这种情况可以先都取log（或者移位），等等。一般这些计算认为是constant复杂度。
实际中bucket sort不常用，就是因为太傻。
哥就问你个简单问题 一列任意的double类型的数组 应该用什么方法排序
扯那么些有的没的 装啥逼啊
Re: 研究新的矩阵乘法不如研究排序排序的impact打多了
发表于 ： 2022年 10月 6日 02:30
由 da1gaku
tekkamanz 写了： 2022年 10月 6日 02:24
哥就问你个简单问题 一列任意的double类型的数组 应该用什么方法排序
扯那么些有的没的 装啥逼啊
这都是本科内容，不存在任何装逼性。
你的“任意”double类型数组是啥。如果啥都不知道，一般用quick sort或类似方法保险。
但做研究的时候不会啥都不知道。