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对被面试的人是非常不负责任的。毕竟人家大老远请假
: 跑来面试也不容易吧。
相关阅读
Paper help thanks!!Paper help湾区公司招research scientist (转载)paper help. THANKS!paper help! Thanks天空如此蓝，还在通风橱做实验？圣诞快到了，大家去哪里玩？new journals金属氢重复出来了吗？Paper help, Thanks!1 baozi, if you get this paper for me. Thanks!Paper help, Thanks!Paper help, Thanks!Request Paper Review转行成为临床实验室科学家及实验室主任机会：特拉华临床实验室博士后Carbon Nanotubes Principal Scientist/Engineer文献求助，很偏的一个杂志 （已经求到，谢谢）化学系的学生惹不起，杀人于无形小心！这款会“冒烟”的网红冰淇凌可能隐藏你不知道的危险！Paper help, Thank you!