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))
.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))
.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]
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 printf("%s%d",sep,num_list[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
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语言
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 ()
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对被面试的人是非常不负责任的。毕竟人家大老远请假
: 跑来面试也不容易吧。
相关阅读
你们没绿卡的化学人为啥不移民澳大利亚那?能推荐几个做chemical biology的大牛吗? (转载)Papers Help, ThanksPaper help, Thanks! {Cellulose}paper helpI140递交整2个月了,没pp。 (转载)Chase Credit Card Offer信用卡开户送350刀 限时真的很ft实验室Chase信用卡开户送350刀 Discover $75+$60 限时求篇文章Paper HelpPaper help!Paper help JHC 1994,31,1473跪求电子书_The Casa Cookbook: Recipes for XPS Data Processi (转载)GC-MS 和 LC-MS 哪个就业范围广?欢迎加入x1980的俱乐部,欢迎大家Discover 信用卡送$75+$60 限时 Chase信用卡送350刀paper help, thanks!paper help, thanks!有人知道indiana University化学的milos Novotny吗?