点击量:8

定义

在给定线性序集中n个元素和一个整数k,要求找出n个元素中第k小的数。

方法一

线性时间选择,可以使用堆排序,这样就可以在$O(n+klog_n)=O(n)_的时间内找到的k小的元素。

方法二

使用快速排序中的分块算法,对所需要选择的数组分块,分完以后再在剩余的部分中,寻找(k – 减去分块的大小)

代码如下:

template <class Type>
int Partition(Type a[], int p, int r)
{
    int i = p;
        j = r+1;
    Type x = a[p];
    while(1)
    {
        while(a[++i] < x);
        while(a[--j] > x);
        if(i >= j) break;
        swap(a[i], a[j]);
    }
    a[p] = a[j];
    a[j] = x;
    return j;
}
template <class Type>
int RandomPartition(Type a[], int p, int r)
{
    int i = Random(p, r);
    swap(a[i], a[p]);
    return Partition(a, p, r);
}
template <class Type>
Type RandomizedSelect(Type a[], int p, int r, int k)
{
    if(p == r) return a[p];
    int i = RandomPartition(a, p, r);
    j = i - p + 1; // 分块的大小
    if(k <= j) return RandomizedSelect(a, p, i, k);
    else return RandomizedSelect(a, i+1, r, k-j);
}

但是此方法在最差的情况下需要$n^2$的时间,比如在寻找最小元素时,总是在最大的元素划分。

尽管如此,平均效率还是不错的。

方法三

我还是比较喜欢直接看代码= =

template <class Type>
Type Select(Type a[], int p, int r, int k)
{
    if (r - p < 75)
    {
        sort(&a[p], &a[r]);
        return a[p+k-1];
    }
    for(int i = 0; i <= (r-p-4)/5; i++)
        Type x = Select(a, p, p+(r-p-4)/5, (r-p-4)/10);
    int i = Partition(a, p, r, x);
    j = i - p + 1;
    if(k <= j) return Select(a, p, i, k);
    else return Select(a, i+1, r, k-j)
}

点击量:10

这篇文章一直没有写,因为并行计算的报告写的比较潦草。此外,没有实现fork。

文件的源代码贴在 https://github.com/Svtter/workspace/tree/master/parallel/enum_sort

实现了Java, MPI, openmp, pthread, win32, MFC, .NET 的并行枚举排序,测试机是双核四线程的ThinkpadE430.

MPI的环境是archlinux . openmpi

贴一个MPI的源代码, 运行结果都在源代码对应的文件夹中保存,这里就不贴了。

/*=============================================================================
#
# Author: svtter - svtter@qq.com
#
# QQ : 57180160
#
# Last modified: 2014-11-02 17:08
#
# Filename: enum_sort_MPI.cpp
#
# Description: 
#
=============================================================================*/
#include "mpi.h"
#include <stdio.h>
#include <math.h>
#include <sys/time.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <iostream>
using namespace std;
#define MAXN 10000
#define PMAX 1000
void build(int a[], int b[])
{
    srand(time(NULL));
    for(int i = 1; i <= MAXN; i++)
        a[i] = b[i] = random()%PMAX;
}
//serial enum sort
double serial_enum_sort(int a[], int at[])
{
    double t1, t2;
    t1 = MPI_Wtime();
    int k, i, j;
    for(i = 1; i <= MAXN; i++)
    {
        k = 1;
        for(j = 1; j <= MAXN; j++)
            if(a[i] > a[j] || (a[i] == a[j] && i > j))
                k++;
        at[k] = a[i];
    }
    t2 = MPI_Wtime();
    return (t2 - t1);
}
// 用于调试数组
void debug(int a[], int len)
{
    for(int i = 1; i <= len; i++)
    {
        fprintf(stderr, "%5d", a[i]);
    }
    fprintf(stderr, "\n");
}
int a[MAXN+10], b[MAXN+10], at[MAXN+10], bt[MAXN+10];
void ensort(int rank[], int &myid, int &numprocs)
{
    int i, j, k;
    for(i = myid; i <= MAXN; i+=numprocs)
    {
        k = 1;
        for(j = 1; j <= MAXN; j++)
        {
            if(b[i] > b[j] || (b[i] == b[j] && (i > j)))
                k++;
        }
        rank[i] = k;
    }
}
int main(int argc, char *argv[])
{
    int myid, numprocs;
    int namelen;
    char processor_name[MPI_MAX_PROCESSOR_NAME];
    double c1 = 0, c2;
    double start, end;
    int i;
    MPI_Init(&argc, &argv);
    MPI_Comm_rank(MPI_COMM_WORLD, &myid);
    MPI_Comm_size(MPI_COMM_WORLD, &numprocs);
    MPI_Get_processor_name(processor_name, &namelen);
    // fprintf(stderr, "Hello world! Processor %d of %d on %s\n", myid, numprocs, processor_name);
    //serial
    if(myid == 0)
    {
        build(a, b);
        c1 = serial_enum_sort(a, at);
        cout << "original array is: " << endl;
        debug(a, 100);
        cout << endl;
        cout << "serial sorted array is: " << endl;
        debug(at, 100);
        cout << endl;
        cout << "serial cost time is: " << c1 << endl;
        cout << endl;
    }
    int con[numprocs][MAXN+10];
    int pt[MAXN+10];
    memset(con ,0, sizeof(con));
    memset(pt,0, sizeof(pt));
    // int **con = new int*[numprocs];
    // for(int i = 0; i < numprocs; i++)
        // con[i] = new int[MAXN+10];
    start = MPI_Wtime();
    // P0 send b to ALL
    MPI_Bcast(b, MAXN+10, MPI_INT, 0, MPI_COMM_WORLD);
    ensort(pt, myid, numprocs);
    // Gather
    MPI_Gather(pt, MAXN+10, MPI_INT, con[myid], MAXN+10, MPI_INT, 0, MPI_COMM_WORLD);
    // if(myid == 0)
    // {
        // fprintf(stderr, "myid: %d\n", myid);
        // fprintf(stderr, "con: %d\n", myid);
        // debug(con[1], 100);
        // fprintf(stderr, "pt: %d\n", myid);
        // debug(pt, 100);
        // fprintf(stderr, "\n");
    // }
    if(myid == 0)
    {
        int j;
        // for(i = 0; i < numprocs; i++)
        // {
            // printf("i: %d\n", i);
            // for(j = 1; j <= MAXN; j++)
                // printf("%5d", con[i][j]);
            // puts("");
        // }
        // rank[k] = i
        for(i = 0; i < numprocs; i++)
            for(j = 1; j <= MAXN; j++)
                bt[con[i][j]] = b[j];
        // fprintf(stderr, "bt: \n");
        cout << "parallel sorted array is: " << endl;
        debug(bt, 100);
        cout << endl;
        end = MPI_Wtime();
        c2 = end - start;
        fprintf(stderr, "parallel cost time is: %lf\n", c2);
        fprintf(stderr, "加速比为: %lf\n", c1 / c2);
    }
    // for(i = 0; i < numprocs; i++)
        // delete con[i];
    // delete con;
    MPI_Finalize();
    return 0;
}

并行计算非常有趣,有时间肯定会再在这条道路上探寻…

点击量:7

拾遗

  1. 使用q:查看历史命令
  2. @*执行寄存器命令

高亮特定文件

" for ROS:
augroup filetypedetect
    au BufRead,BufNewFile *.launch set filetype=xml
augroup END

点击量:7

在php中

使用preg_match("/<title>(.*)<title>/isU")

  • /****/表示中间的部分匹配。
  • (.*)表示匹配的部分。
  • i表示忽略大小写
  • s使点号能匹配所有字符包括换行符
  • U最短匹配。注意U一定要大写才有效果

继续阅读

点击量:14

搭建BLOG的心得 + 2014年10月份的总结


胡言乱语的blog心得

要不是登录到sinaapp上看看我都忘记了自己还有一个用typecho搭建的blog,但是凡事一旦牵扯到git之类的东西,总会觉得高大上一点。

然后伤心的觉得,似乎我辛辛苦苦搭建的hexo, 似乎没个鸟用。心塞。

主要问题在于:

  1. 这家伙对于之前的写的文章,修改起来不够方便,还要回去慢慢找,不如直接用点击来的快捷。
  2. 但是从另一个角度上说,如果是命令行玩家,grep几次自然也就完全没有问题了。
  3. 当然,也有好处,最大的好处就是方便,推送,不用花钱等。
  4. 还有各种玩头,就不一一说明了。。反正大家仁者见仁,智者见智。

相比之下typecho就会轻松很多(因为发现也是不支持一些东西,我又懒得弄),__JustWriting__嘛。。不想再用了,虽然说也是很爽,但是用了php搞得和静态页面的一个项目似的,总是感觉怪怪的。

之前给__Justwriting__写了一点点称不上脚本的脚本(仅LINUX下好用, 毕竟bash用的挺XX,python也没时间学。),但是事情一多,自然也是有点想要放弃git pull request的意思了。

再想想,__JustWriting__最大的优点在于,可以把我们的代码备份上去,不像hexo,今天下午手残的我 + 神经短路的我一个不小心弄丢了所有的代码,真心是哭了。。。

另外,也是需要各种grep的阿。

其实本来想吐槽关于找不到文章的问题,不过在写着写着的过程中想到了可以使用搜索这种东西。。倒是我自己有些不动脑了。

写一个对自己来讲简单的比较:

如果有问题,就当我说错了,最好是指出来= =

项目 JustWriting hexo typecho(wordpress)
命令行推送 AC AC
直接界面编辑 AC
代码部署 简单 更简单 一般
是否使用googleapi YES
想起来我再加上

外观上都难说,typecho我没有做过什么优化,JustWriting因为用的是不稳定(也不知道也没有稳定版本,^_^)版本,所以删掉了。有兴趣倒是可以看看hexo

当然我也知道基本上转到cnblogs这边估计也就没人看了。。。本身也上不了主页,哈。

另说句没什么关系的话,googleapi的相关东西态坑了。

我这么写blogs会不会呼我熊脸阿= =blogs老套的博客模板。。唉。


10月份的总结

9:30倒是不适合闲扯了= =

关于记录表

看看自己的记录表吧。11月的记录表依然是空的(因为会写一些私人的东西,所以就不喜欢开源了。。)。最近也是没有改过每日计划(也是大致按照那么进行的)

本来想要把自己的计划python化的,但是时间上实在是腾不出来——今天去健身了,也是没有复习考研数学,英语(本来写个回宿舍看看,想想倒也不现实)。

10月份的记录表__高数__一栏全是空的(= =)就没复习过!那天和学长一起讨论关于考研的问题才发现自己走偏了方向(blog的方面也是有些走偏)。

想要深造所以不太想太早的工作,但是技术的世界丰富多彩而有趣(喜欢写代码的我注定屌丝一生= =)。

有今天记录情况不全,后面的备注表我也没有写什么,大概是比较忙,之后也没有补充上吧。现在看起来倒是想不通了。。。

写了完成情况的部分也因为转换了位置,看起来不怎么方便(还是需要改善阿),需要把记录表放在记录表里面,然后查看的时候再做相关处理。

看看记录表,因为系统不稳定的问题着实花费了不少时间(10.02),另外10.03买的奶是9.23产的- -。 10.06就想看操作系统Linux的源码,结果到了现在也没有看。

SG函数倒是明白了,不过对应的题目没有做多少= =。最近大部分的时间都在搞并行计算(呼呼的写代码感觉比较爽), 并行计算的作业也是只剩下文档了,算是搞定了把。

日记还是写的那些东西,不过效率不太行阿。。。以后的备注倒是可以自由一点。

出现的问题:
1. 英语空出好几天没有背。
2. 高数没复习
3. 锻炼有好好坚持。
4. 早睡没有好好坚持。

关于这个月

也没什么别的东西了,主要就是谨记学长的教诲,转移对于一些对于我最终目标无意义的事情的注意力,主要放在数学,英语上面。晚自习的内容以后放在这个上面。晚上回去以后可以写日记,

或者补充一下或者使得库更加简单等。白天的时间主要用于学习其他的科目,抓紧时间。以后每天都要好好的写日记。

就这样吧!

努力努力!