n*2
2 楼
qsort [] = []
qsort (x:xs) = qsort (filter (<= x) xs) ++ [x] ++ qsort (filter (> x) xs)
qsort (x:xs) = qsort (filter (<= x) xs) ++ [x] ++ qsort (filter (> x) xs)
b*n
3 楼
求文献，谢谢啦！
http://jjap.jsap.jp/link?JJAPS/32S2/517
Jpn. J. Appl. Phys. 32 (1993) Supplement 32-2 pp. 517-522
Proc. 7th Int. Conf. X-ray Absorption Fine Structure, Kobe, 1992
http://jjap.jsap.jp/link?JJAPS/32S2/517
Jpn. J. Appl. Phys. 32 (1993) Supplement 32-2 pp. 517-522
Proc. 7th Int. Conf. X-ray Absorption Fine Structure, Kobe, 1992
n*w
4 楼
F#:
let rec qsort = function
| [] -> []
| x::xs -> let smaller,larger = List.partition (fun y -> y<=x) xs
qsort smaller @ [x] @ qsort larger
let rec qsort = function
| [] -> []
| x::xs -> let smaller,larger = List.partition (fun y -> y<=x) xs
qsort smaller @ [x] @ qsort larger
b*t
6 楼
好写好懂，
但pivot选的真心别扭
这比java估计慢二十倍以上
你写个性能好的haskell qsort绝壁比java难懂二十倍
语法糖没意思，haskell玩玩还可以，但绝壁不是industrial grade语言
但pivot选的真心别扭
这比java估计慢二十倍以上
你写个性能好的haskell qsort绝壁比java难懂二十倍
语法糖没意思，haskell玩玩还可以，但绝壁不是industrial grade语言
n*w
7 楼
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));
}
public static IEnumerable
{
if (items.Count() <= 1) return items;
var pivot = items.First();
return QSLinq(item.Where(i=>i
.Concat(QSLinq(item.Where(i=>i>pivot));
}
n*2
8 楼
qsort [] = []
qsort (x:xs) = qsort (filter (<= x) xs) ++ [x] ++ qsort (filter (> x) xs)
qsort (x:xs) = qsort (filter (<= x) xs) ++ [x] ++ qsort (filter (> x) xs)
n*w
9 楼
F#:
let rec qsort = function
| [] -> []
| x::xs -> let smaller,larger = List.partition (fun y -> y<=x) xs
qsort smaller @ [x] @ qsort larger
let rec qsort = function
| [] -> []
| x::xs -> let smaller,larger = List.partition (fun y -> y<=x) xs
qsort smaller @ [x] @ qsort larger
b*t
10 楼
好写好懂，
但pivot选的真心别扭
这比java估计慢二十倍以上
你写个性能好的haskell qsort绝壁比java难懂二十倍
语法糖没意思，haskell玩玩还可以，但绝壁不是industrial grade语言
但pivot选的真心别扭
这比java估计慢二十倍以上
你写个性能好的haskell qsort绝壁比java难懂二十倍
语法糖没意思，haskell玩玩还可以，但绝壁不是industrial grade语言
n*w
11 楼
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));
}
public static IEnumerable
{
if (items.Count() <= 1) return items;
var pivot = items.First();
return QSLinq(item.Where(i=>i
.Concat(QSLinq(item.Where(i=>i>pivot));
}
s*i
12 楼
Quick sort 的精华部分还包括inplace的空间利用。
上述实现都忽略了
[发表自未名空间手机版 - m.mitbbs.com]
上述实现都忽略了
[发表自未名空间手机版 - m.mitbbs.com]
A*e
13 楼
连基本的复杂度概念都没有。你那个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)
快排的精髓在那个in-place move。完整的快排算法是两部分:partition，sort。你大
笔一挥把partition给省了，这叫作弊。
【在 n**********2 的大作中提到】
: qsort [] = []
: qsort (x:xs) = qsort (filter (<= x) xs) ++ [x] ++ qsort (filter (> x) xs)
A*e
14 楼
+1
就是用伪代码写了个快排主程序而已，还沾沾自喜。
【在 s*i 的大作中提到】
: Quick sort 的精华部分还包括inplace的空间利用。
: 上述实现都忽略了
: [发表自未名空间手机版 - m.mitbbs.com]
就是用伪代码写了个快排主程序而已，还沾沾自喜。
【在 s*i 的大作中提到】
: Quick sort 的精华部分还包括inplace的空间利用。
: 上述实现都忽略了
: [发表自未名空间手机版 - m.mitbbs.com]
g*e
15 楼
Jvm乘务员的脑子里根本没有“空间”这个概念，他们写程序就是不停的new new new
d*i
16 楼
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
sep=", ";
}
printf("};n");
return 0;
}
#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
sep=", ";
}
printf("};n");
return 0;
}
t*r
17 楼
quicksort :: (Ord a) => [a] -> [a]
quicksort [] = []
quicksort (x:xs) =
let smallerOrEqual = [a | a larger = [a | a x]
in quicksort smallerOrEqual ++ [x] ++ larger
main = do
let a = [ 5, 1, 9, 4, 6, 7, 3]
print $ quicksort a
quicksort [] = []
quicksort (x:xs) =
let smallerOrEqual = [a | a larger = [a | a x]
in quicksort smallerOrEqual ++ [x] ++ larger
main = do
let a = [ 5, 1, 9, 4, 6, 7, 3]
print $ quicksort a
t*r
18 楼
你这是scala?
【在 n**********2 的大作中提到】
: qsort [] = []
: qsort (x:xs) = qsort (filter (<= x) xs) ++ [x] ++ qsort (filter (> x) xs)
【在 n**********2 的大作中提到】
: qsort [] = []
: qsort (x:xs) = qsort (filter (<= x) xs) ++ [x] ++ qsort (filter (> x) xs)
a*e
19 楼
求教一下，这个 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 的大作中提到】
: 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
20 楼
我很久以前写的，看看是否难懂 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 > 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 > let split' i j = if j == right then (swap i right v) >> return i else do
> b > 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 > writeArray arr i b
> writeArray arr j a
【在 b*****t 的大作中提到】
: 好写好懂，
: 但pivot选的真心别扭
: 这比java估计慢二十倍以上
: 你写个性能好的haskell qsort绝壁比java难懂二十倍
: 语法糖没意思，haskell玩玩还可以，但绝壁不是industrial grade语言
请自动忽略里面的 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 > 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 > let split' i j = if j == right then (swap i right v) >> return i else do
> b > 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 > writeArray arr i b
> writeArray arr j a
【在 b*****t 的大作中提到】
: 好写好懂，
: 但pivot选的真心别扭
: 这比java估计慢二十倍以上
: 你写个性能好的haskell qsort绝壁比java难懂二十倍
: 语法糖没意思，haskell玩玩还可以，但绝壁不是industrial grade语言
n*2
21 楼
void*, C 里面的generic type, 哈哈
【在 a*****e 的大作中提到】
: 求教一下，这个 C 程序非要用 void* 是个什么道理？会更快还是...？还从来没见过
: 这样写的快排
【在 a*****e 的大作中提到】
: 求教一下，这个 C 程序非要用 void* 是个什么道理？会更快还是...？还从来没见过
: 这样写的快排
a*e
22 楼
你和楼主是大水冲了龙王庙吗？LOL
【在 t**r 的大作中提到】
: 你这是scala?
【在 t**r 的大作中提到】
: 你这是scala?
a*e
23 楼
就算是没有 C++ 里面的 template，也可以用 macro 定义一个 T 类型来做啊，不能理
解用 void* 和 size_t 这种做法。
【在 n**********2 的大作中提到】
: void*, C 里面的generic type, 哈哈
解用 void* 和 size_t 这种做法。
【在 n**********2 的大作中提到】
: void*, C 里面的generic type, 哈哈
b*t
24 楼
你觉得呢？
这还不够反人类？
【在 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 : > if j - i > 10000 then (fork $ aux (i, k - 1)) >> return ()
这还不够反人类？
【在 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 : > if j - i > 10000 then (fork $ aux (i, k - 1)) >> return ()
g*y
25 楼
还是 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 的大作中提到】
: 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
26 楼
C里面的void *指针就相当于泛型，这样传入swap函数的可以是任何primitive或者
struct的类型，当然要给定字节长度。用宏来做的话当然也可以，但是不推荐，宏没有
类型检查，容易出错。
【在 a*****e 的大作中提到】
: 就算是没有 C++ 里面的 template，也可以用 macro 定义一个 T 类型来做啊，不能理
: 解用 void* 和 size_t 这种做法。
struct的类型，当然要给定字节长度。用宏来做的话当然也可以，但是不推荐，宏没有
类型检查，容易出错。
【在 a*****e 的大作中提到】
: 就算是没有 C++ 里面的 template，也可以用 macro 定义一个 T 类型来做啊，不能理
: 解用 void* 和 size_t 这种做法。
z*e
27 楼
只能说明你还只是一个初级java程序员
连中级都说不上，spring等框架都统一管理内存
高级程序员会用jmx监控memory的使用情况
new
【在 g*********e 的大作中提到】
: Jvm乘务员的脑子里根本没有“空间”这个概念，他们写程序就是不停的new new new
连中级都说不上，spring等框架都统一管理内存
高级程序员会用jmx监控memory的使用情况
new
【在 g*********e 的大作中提到】
: Jvm乘务员的脑子里根本没有“空间”这个概念，他们写程序就是不停的new new new
i*p
28 楼
请问面试20分钟写一个quicksort对于毕业10年的工业界程序员reasonable吗?
【在 z****e 的大作中提到】
: 只能说明你还只是一个初级java程序员
: 连中级都说不上，spring等框架都统一管理内存
: 高级程序员会用jmx监控memory的使用情况
:
: new
【在 z****e 的大作中提到】
: 只能说明你还只是一个初级java程序员
: 连中级都说不上，spring等框架都统一管理内存
: 高级程序员会用jmx监控memory的使用情况
:
: new
h*y
29 楼
可以问问基本sort算法在各种应用场景下可以作哪些优化。什么情况下sort会成为性能
瓶颈。做过大数据看过一点terasort的人一般能说出个大概吧。然后就可以接着问问
hadoop eco. 光考个quick sort对被面试的人是非常不负责任的。毕竟人家大老远请假
跑来面试也不容易吧。
【在 i**p 的大作中提到】
: 请问面试20分钟写一个quicksort对于毕业10年的工业界程序员reasonable吗?
瓶颈。做过大数据看过一点terasort的人一般能说出个大概吧。然后就可以接着问问
hadoop eco. 光考个quick sort对被面试的人是非常不负责任的。毕竟人家大老远请假
跑来面试也不容易吧。
【在 i**p 的大作中提到】
: 请问面试20分钟写一个quicksort对于毕业10年的工业界程序员reasonable吗?
g*e
30 楼
hehe jvm程序员可写不出spring框架 他们只会用
【在 z****e 的大作中提到】
: 只能说明你还只是一个初级java程序员
: 连中级都说不上，spring等框架都统一管理内存
: 高级程序员会用jmx监控memory的使用情况
:
: new
i*p
31 楼
不是光考quick sort. quick sort for first 20 minutes.
【在 h*****y 的大作中提到】
: 可以问问基本sort算法在各种应用场景下可以作哪些优化。什么情况下sort会成为性能
: 瓶颈。做过大数据看过一点terasort的人一般能说出个大概吧。然后就可以接着问问
: hadoop eco. 光考个quick sort对被面试的人是非常不负责任的。毕竟人家大老远请假
: 跑来面试也不容易吧。
【在 h*****y 的大作中提到】
: 可以问问基本sort算法在各种应用场景下可以作哪些优化。什么情况下sort会成为性能
: 瓶颈。做过大数据看过一点terasort的人一般能说出个大概吧。然后就可以接着问问
: hadoop eco. 光考个quick sort对被面试的人是非常不负责任的。毕竟人家大老远请假
: 跑来面试也不容易吧。
b*t
32 楼
写不出来qsort不一定是什么问题，这里有区别
工业经验长的反而不一定记得qsort的算法过程，是有可能的，没有大问题，看一下
spec能写出就行
但是如果知道大概的算法，但无能力转化成code，那就不要滥竽充数了，太差
数学所用的思维和programming至少有些部分是mutually exclusive
不少数学系的很牛人，写个matlab都费劲，手把手教了这个，换个algo又趴下了，就是
没有那个代码表达能力，见得太多了
【在 i**p 的大作中提到】
: 请问面试20分钟写一个quicksort对于毕业10年的工业界程序员reasonable吗?
工业经验长的反而不一定记得qsort的算法过程，是有可能的，没有大问题，看一下
spec能写出就行
但是如果知道大概的算法，但无能力转化成code，那就不要滥竽充数了，太差
数学所用的思维和programming至少有些部分是mutually exclusive
不少数学系的很牛人，写个matlab都费劲，手把手教了这个，换个algo又趴下了，就是
没有那个代码表达能力，见得太多了
【在 i**p 的大作中提到】
: 请问面试20分钟写一个quicksort对于毕业10年的工业界程序员reasonable吗?
i*p
33 楼
那好, 20分钟内读qsort spec, 写出正确的代码, 对工业经验长的合适吗?
【在 b*****t 的大作中提到】
: 写不出来qsort不一定是什么问题，这里有区别
: 工业经验长的反而不一定记得qsort的算法过程，是有可能的，没有大问题，看一下
: spec能写出就行
: 但是如果知道大概的算法，但无能力转化成code，那就不要滥竽充数了，太差
: 数学所用的思维和programming至少有些部分是mutually exclusive
: 不少数学系的很牛人，写个matlab都费劲，手把手教了这个，换个algo又趴下了，就是
: 没有那个代码表达能力，见得太多了
【在 b*****t 的大作中提到】
: 写不出来qsort不一定是什么问题，这里有区别
: 工业经验长的反而不一定记得qsort的算法过程，是有可能的，没有大问题，看一下
: spec能写出就行
: 但是如果知道大概的算法，但无能力转化成code，那就不要滥竽充数了，太差
: 数学所用的思维和programming至少有些部分是mutually exclusive
: 不少数学系的很牛人，写个matlab都费劲，手把手教了这个，换个algo又趴下了，就是
: 没有那个代码表达能力，见得太多了
b*t
34 楼
20分钟写qsort是worst case scenario，
写得出不证明合适，
写不出一定不合适
【在 i**p 的大作中提到】
: 那好, 20分钟内读qsort spec, 写出正确的代码, 对工业经验长的合适吗?
写得出不证明合适，
写不出一定不合适
【在 i**p 的大作中提到】
: 那好, 20分钟内读qsort spec, 写出正确的代码, 对工业经验长的合适吗?
z*e
35 楼
spring的本质就是reflection
which在1.4时代经常拿来面试的东西
【在 g*********e 的大作中提到】
:
: hehe jvm程序员可写不出spring框架 他们只会用
which在1.4时代经常拿来面试的东西
【在 g*********e 的大作中提到】
:
: hehe jvm程序员可写不出spring框架 他们只会用
z*e
36 楼
我反正用hadoop的过程中还没遇到过用快排的地方
现在基本上都不sort了，要sort的话，建index的cache就好了
不需要等到用的时候再sort，那多慢呀，而且又吃内存
多sort几下，整个系统就别干其他事了，光忙着sort了
而且快排能并行么？我好像是不太记得怎么做快排的并行
所以感觉做hadoop什么不合适，terasort第一步就是并行化处理
不过说到这里我突然想起来，terasort跟quicksort倒是有些共通之处
可以按照terasort的方式做，但是那样就是terasort而非qs了
【在 h*****y 的大作中提到】
: 可以问问基本sort算法在各种应用场景下可以作哪些优化。什么情况下sort会成为性能
: 瓶颈。做过大数据看过一点terasort的人一般能说出个大概吧。然后就可以接着问问
: hadoop eco. 光考个quick sort对被面试的人是非常不负责任的。毕竟人家大老远请假
: 跑来面试也不容易吧。
现在基本上都不sort了，要sort的话，建index的cache就好了
不需要等到用的时候再sort，那多慢呀，而且又吃内存
多sort几下，整个系统就别干其他事了，光忙着sort了
而且快排能并行么？我好像是不太记得怎么做快排的并行
所以感觉做hadoop什么不合适，terasort第一步就是并行化处理
不过说到这里我突然想起来，terasort跟quicksort倒是有些共通之处
可以按照terasort的方式做，但是那样就是terasort而非qs了
【在 h*****y 的大作中提到】
: 可以问问基本sort算法在各种应用场景下可以作哪些优化。什么情况下sort会成为性能
: 瓶颈。做过大数据看过一点terasort的人一般能说出个大概吧。然后就可以接着问问
: hadoop eco. 光考个quick sort对被面试的人是非常不负责任的。毕竟人家大老远请假
: 跑来面试也不容易吧。
相关阅读
今天Hacker News上关于Pubup.org的讨论国内进高校的年龄要求，求解答(got)paper help. (baozi)大家帮我提提意见和建议吧 (转载)国内土博找工作，工作经验问题求助最近为什么不见枫树姓窦的都喜欢做金属有机？而且做得都很出色关于博士后offer的问题苦逼的化学狗问问未来。。【化学】中国高校近三年发表的化学顶级杂志论文统计(2009-2012)EB1A DIY PP 十天获批化学没前途《文汇报》头版：该吃的苦，总是要吃的Ing Direct checking account免费送50刀， 赶紧申请有人在ACS Chemistry/Polymer Division信用分数知多少？Poor or Excellent？免费查询，尽快提高到700分这个版，对化学充满了绝望啊求翻译千老们赶紧起来自救了。。。生物就会哭穷哪有我们化学苦逼啊？