n**********2
发帖数: 648 | 1 qsort [] = []
qsort (x:xs) = qsort (filter (<= x) xs) ++ [x] ++ qsort (filter (> x) xs) |
n*w
发帖数: 3393 | 2 F#:
let rec qsort = function
| [] -> []
| x::xs -> let smaller,larger = List.partition (fun y -> y<=x) xs
qsort smaller @ [x] @ qsort larger |
b*****t
发帖数: 840 | 3 好写好懂，
但pivot选的真心别扭
这比java估计慢二十倍以上
你写个性能好的haskell qsort绝壁比java难懂二十倍
语法糖没意思，haskell玩玩还可以，但绝壁不是industrial grade语言 |
n*w
发帖数: 3393 | 4 C#:
public static IEnumerable QSLinq(IEnumerable items)
{
if (items.Count() <= 1) return items;
var pivot = items.First();
return QSLinq(item.Where(i=>i
.Concat(QSLinq(item.Where(i=>i==pivot))
.Concat(QSLinq(item.Where(i=>i>pivot));
} |
n**********2
发帖数: 648 | 5 qsort [] = []
qsort (x:xs) = qsort (filter (<= x) xs) ++ [x] ++ qsort (filter (> x) xs) |
n*w
发帖数: 3393 | 6 F#:
let rec qsort = function
| [] -> []
| x::xs -> let smaller,larger = List.partition (fun y -> y<=x) xs
qsort smaller @ [x] @ qsort larger |
b*****t
发帖数: 840 | 7 好写好懂，
但pivot选的真心别扭
这比java估计慢二十倍以上
你写个性能好的haskell qsort绝壁比java难懂二十倍
语法糖没意思，haskell玩玩还可以，但绝壁不是industrial grade语言 |
n*w
发帖数: 3393 | 8 C#:
public static IEnumerable QSLinq(IEnumerable items)
{
if (items.Count() <= 1) return items;
var pivot = items.First();
return QSLinq(item.Where(i=>i
.Concat(QSLinq(item.Where(i=>i==pivot))
.Concat(QSLinq(item.Where(i=>i>pivot));
} |
s*i
发帖数: 5025 | 9 Quick sort 的精华部分还包括inplace的空间利用。
上述实现都忽略了
[发表自未名空间手机版 - m.mitbbs.com] |
A*******e
发帖数: 2419 | 10 连基本的复杂度概念都没有。你那个filter能做到in-place move，且平均线性？
快排的精髓在那个in-place move。完整的快排算法是两部分:partition，sort。你大
笔一挥把partition给省了，这叫作弊。
【在 n**********2 的大作中提到】
: qsort [] = []
: qsort (x:xs) = qsort (filter (<= x) xs) ++ [x] ++ qsort (filter (> x) xs)
|
|
|
A*******e
发帖数: 2419 | 11 +1
就是用伪代码写了个快排主程序而已，还沾沾自喜。
【在 s*i 的大作中提到】
: Quick sort 的精华部分还包括inplace的空间利用。
: 上述实现都忽略了
: [发表自未名空间手机版 - m.mitbbs.com]
|
g*********e
发帖数: 14401 | 12 Jvm乘务员的脑子里根本没有“空间”这个概念，他们写程序就是不停的new new new |
d****i
发帖数: 4809 | 13 Plain old vanilla pure C code. Disclaimer: copied from online
#include
#include
static void swap(void *x, void *y, size_t l) {
char *a = x, *b = y, c;
while(l--) {
c = *a;
*a++ = *b;
*b++ = c;
}
}
static void sort(char *array, size_t size, int (*cmp)(void*,void*), int
begin, int end) {
if (end > begin) {
void *pivot = array + begin;
int l = begin + size;
int r = end;
while(l < r) {
if (cmp(array+l,pivot) <= 0) {
l += size;
} else if ( cmp(array+r, pivot) > 0 ) {
r -= size;
} else if ( l < r ) {
swap(array+l, array+r, size);
}
}
l -= size;
swap(array+begin, array+l, size);
sort(array, size, cmp, begin, l);
sort(array, size, cmp, r, end);
}
}
void qsort(void *array, size_t nitems, size_t size, int (*cmp)(void*,void*))
{
sort(array, size, cmp, 0, nitems*size);
}
typedef int type;
int type_cmp(void *a, void *b){ return (*(type*)a)-(*(type*)b); }
int main(void)
{ /* simple test case for type=int */
int num_list[]={5,4,3,2,1};
int len=sizeof(num_list)/sizeof(type);
char *sep="";
int i;
qsort(num_list,len,sizeof(type),type_cmp);
printf("sorted_num_list={");
for(i=0; i
printf("%s%d",sep,num_list[i]);
sep=", ";
}
printf("};n");
return 0;
} |
t**r
发帖数: 3428 | 14 quicksort :: (Ord a) => [a] -> [a]
quicksort [] = []
quicksort (x:xs) =
let smallerOrEqual = [a | a <- xs, a <= x]
larger = [a | a <- xs, a > x]
in quicksort smallerOrEqual ++ [x] ++ larger
main = do
let a = [ 5, 1, 9, 4, 6, 7, 3]
print $ quicksort a |
t**r
发帖数: 3428 | 15 你这是scala?
【在 n**********2 的大作中提到】
: qsort [] = []
: qsort (x:xs) = qsort (filter (<= x) xs) ++ [x] ++ qsort (filter (> x) xs)
|
a*****e
发帖数: 1700 | 16 求教一下，这个 C 程序非要用 void* 是个什么道理？会更快还是...？还从来没见过
这样写的快排
【在 d****i 的大作中提到】
: Plain old vanilla pure C code. Disclaimer: copied from online
: #include
: #include
: static void swap(void *x, void *y, size_t l) {
: char *a = x, *b = y, c;
: while(l--) {
: c = *a;
: *a++ = *b;
: *b++ = c;
: }
|
a*****e
发帖数: 1700 | 17 我很久以前写的，看看是否难懂 20 倍？
请自动忽略里面的 fork，当时是做了个 lightweight thread scheduler 拿快排做测
试。
> qsortM = qsort (i j a -> sysio $ qsplit i j a) fork
> qsort split fork (i, j) arr = aux (i, j)
> where
> aux (i, j) =
> if j <= i then return () else do
> k <- split i j arr
> if j - i > 10000 then (fork $ aux (i, k - 1)) >> return ()
> else aux (i, k - 1)
> aux (k + 1, j)
> qsplit left right arr = do
> v <- readArray arr right
> let split' i j = if j == right then (swap i right v) >> return i else do
> b <- readArray arr j
> if b <= v
> then (swap i j b) >> split' (i + 1) (j + 1)
> else split' i (j + 1)
> split' left left
> where
> swap i j b = do
> a <- readArray arr i
> writeArray arr i b
> writeArray arr j a
【在 b*****t 的大作中提到】
: 好写好懂，
: 但pivot选的真心别扭
: 这比java估计慢二十倍以上
: 你写个性能好的haskell qsort绝壁比java难懂二十倍
: 语法糖没意思，haskell玩玩还可以，但绝壁不是industrial grade语言
|
n**********2
发帖数: 648 | 18 void*, C 里面的generic type, 哈哈
【在 a*****e 的大作中提到】
: 求教一下，这个 C 程序非要用 void* 是个什么道理？会更快还是...？还从来没见过
: 这样写的快排
|
a*****e
发帖数: 1700 | 19 你和楼主是大水冲了龙王庙吗？LOL
【在 t**r 的大作中提到】
: 你这是scala?
|
a*****e
发帖数: 1700 | 20 就算是没有 C++ 里面的 template，也可以用 macro 定义一个 T 类型来做啊，不能理
解用 void* 和 size_t 这种做法。
【在 n**********2 的大作中提到】
: void*, C 里面的generic type, 哈哈
|
|
|
b*****t
发帖数: 840 | 21 你觉得呢？
这还不够反人类？
【在 a*****e 的大作中提到】
: 我很久以前写的，看看是否难懂 20 倍？
: 请自动忽略里面的 fork，当时是做了个 lightweight thread scheduler 拿快排做测
: 试。
: > qsortM = qsort (i j a -> sysio $ qsplit i j a) fork
: > qsort split fork (i, j) arr = aux (i, j)
: > where
: > aux (i, j) =
: > if j <= i then return () else do
: > k <- split i j arr
: > if j - i > 10000 then (fork $ aux (i, k - 1)) >> return ()
|
g*****y
发帖数: 7271 | 22 还是 C 看着亲切，void* 就更亲切了，哈哈
【在 d****i 的大作中提到】
: Plain old vanilla pure C code. Disclaimer: copied from online
: #include
: #include
: static void swap(void *x, void *y, size_t l) {
: char *a = x, *b = y, c;
: while(l--) {
: c = *a;
: *a++ = *b;
: *b++ = c;
: }
|
d****i
发帖数: 4809 | 23 C里面的void *指针就相当于泛型，这样传入swap函数的可以是任何primitive或者
struct的类型，当然要给定字节长度。用宏来做的话当然也可以，但是不推荐，宏没有
类型检查，容易出错。
【在 a*****e 的大作中提到】
: 就算是没有 C++ 里面的 template，也可以用 macro 定义一个 T 类型来做啊，不能理
: 解用 void* 和 size_t 这种做法。
|
z****e
发帖数: 54598 | 24 只能说明你还只是一个初级java程序员
连中级都说不上，spring等框架都统一管理内存
高级程序员会用jmx监控memory的使用情况
new
【在 g*********e 的大作中提到】
: Jvm乘务员的脑子里根本没有“空间”这个概念，他们写程序就是不停的new new new
|
i**p
发帖数: 902 | 25 请问面试20分钟写一个quicksort对于毕业10年的工业界程序员reasonable吗?
【在 z****e 的大作中提到】
: 只能说明你还只是一个初级java程序员
: 连中级都说不上，spring等框架都统一管理内存
: 高级程序员会用jmx监控memory的使用情况
:
: new
|
h*****y
发帖数: 298 | 26 可以问问基本sort算法在各种应用场景下可以作哪些优化。什么情况下sort会成为性能
瓶颈。做过大数据看过一点terasort的人一般能说出个大概吧。然后就可以接着问问
hadoop eco. 光考个quick sort对被面试的人是非常不负责任的。毕竟人家大老远请假
跑来面试也不容易吧。
【在 i**p 的大作中提到】
: 请问面试20分钟写一个quicksort对于毕业10年的工业界程序员reasonable吗?
|
g*********e
发帖数: 14401 | 27
hehe jvm程序员可写不出spring框架 他们只会用
【在 z****e 的大作中提到】
: 只能说明你还只是一个初级java程序员
: 连中级都说不上，spring等框架都统一管理内存
: 高级程序员会用jmx监控memory的使用情况
:
: new
|
i**p
发帖数: 902 | 28 不是光考quick sort. quick sort for first 20 minutes.
【在 h*****y 的大作中提到】
: 可以问问基本sort算法在各种应用场景下可以作哪些优化。什么情况下sort会成为性能
: 瓶颈。做过大数据看过一点terasort的人一般能说出个大概吧。然后就可以接着问问
: hadoop eco. 光考个quick sort对被面试的人是非常不负责任的。毕竟人家大老远请假
: 跑来面试也不容易吧。
|
b*****t
发帖数: 840 | 29 写不出来qsort不一定是什么问题，这里有区别
工业经验长的反而不一定记得qsort的算法过程，是有可能的，没有大问题，看一下
spec能写出就行
但是如果知道大概的算法，但无能力转化成code，那就不要滥竽充数了，太差
数学所用的思维和programming至少有些部分是mutually exclusive
不少数学系的很牛人，写个matlab都费劲，手把手教了这个，换个algo又趴下了，就是
没有那个代码表达能力，见得太多了
【在 i**p 的大作中提到】
: 请问面试20分钟写一个quicksort对于毕业10年的工业界程序员reasonable吗?
|
i**p
发帖数: 902 | 30 那好, 20分钟内读qsort spec, 写出正确的代码, 对工业经验长的合适吗?
【在 b*****t 的大作中提到】
: 写不出来qsort不一定是什么问题，这里有区别
: 工业经验长的反而不一定记得qsort的算法过程，是有可能的，没有大问题，看一下
: spec能写出就行
: 但是如果知道大概的算法，但无能力转化成code，那就不要滥竽充数了，太差
: 数学所用的思维和programming至少有些部分是mutually exclusive
: 不少数学系的很牛人，写个matlab都费劲，手把手教了这个，换个algo又趴下了，就是
: 没有那个代码表达能力，见得太多了
|
|
|
b*****t
发帖数: 840 | 31 20分钟写qsort是worst case scenario，
写得出不证明合适，
写不出一定不合适
【在 i**p 的大作中提到】
: 那好, 20分钟内读qsort spec, 写出正确的代码, 对工业经验长的合适吗?
|
z****e
发帖数: 54598 | 32 spring的本质就是reflection
which在1.4时代经常拿来面试的东西
【在 g*********e 的大作中提到】
:
: hehe jvm程序员可写不出spring框架 他们只会用
|
z****e
发帖数: 54598 | 33 我反正用hadoop的过程中还没遇到过用快排的地方
现在基本上都不sort了，要sort的话，建index的cache就好了
不需要等到用的时候再sort，那多慢呀，而且又吃内存
多sort几下，整个系统就别干其他事了，光忙着sort了
而且快排能并行么？我好像是不太记得怎么做快排的并行
所以感觉做hadoop什么不合适，terasort第一步就是并行化处理
不过说到这里我突然想起来，terasort跟quicksort倒是有些共通之处
可以按照terasort的方式做，但是那样就是terasort而非qs了
【在 h*****y 的大作中提到】
: 可以问问基本sort算法在各种应用场景下可以作哪些优化。什么情况下sort会成为性能
: 瓶颈。做过大数据看过一点terasort的人一般能说出个大概吧。然后就可以接着问问
: hadoop eco. 光考个quick sort对被面试的人是非常不负责任的。毕竟人家大老远请假
: 跑来面试也不容易吧。
|
