arraymodifyHomework

#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;

typedef struct Row {
    int a;
    int b;
} Row;

void lazyprint(const Row* row) {
    cout << "one row=" << row->a << "," << row->b << endl;
}

void task1(const Row* rows, int nrows) {
    // 基于以下 C 程序框架, 我们希望你实现 task1() 这个函数, 它把 rows 中所有满⾜ b >= 10 && b < 50 并且 a == 1000 || a == 2000 || a == 3000 的⾏的内容都打印到终端.
    // TBD: 为了利用cpu cache locality， 所以一定要顺序读
    cout << "task1" << endl;
    const Row* base = rows;
    for (int i = 0; i < nrows; i++) {
        rows = base + i;
        // cout << "addr=" << rows  << "; sizeof" << sizeof(Row) << "; content=" << rows->a << rows->b << endl;
        if ((rows->a == 1000 || rows->a == 2000 || rows->a == 3000) && 
            (rows->b >= 10 && rows->b < 50)) {
            // cout << "one row:" << rows->a << rows->b << endl;
            lazyprint(rows);
        }
    }
}

inline bool filter_imp1(int a) {
    if (a % 1000 == 0 && (a / 1000) > 0 && (a / 1000) < 4) {
        return true;
    }
    return false;
}

void task2(const Row* rows, int nrows) {
    // 在任务 1 的基础上, 如果输⼊的参数 rows 已经按照 (a,b) 进⾏过排序, 请实现 task2() , 对 task1() 的执⾏性能进⾏优化. ⽰例输⼊ (再次提醒, 实际输⼊为海量数据)
    // TBD: 主要是利用相邻数据的有序和重复做分支预测
    cout << "task2" << endl;
    const Row* base = rows;
    bool a_match = false;
    int last_a = base->a;
    if (filter_imp1(last_a)) {
        a_match = true;
    }
    for (int i = 0; i < nrows; i++) {
        rows = base + i;
        if (rows->a == last_a) {
            // fast check, cpu branch prediction
        } else {
            last_a = rows->a;
            if (filter_imp1(last_a)) {
                a_match = true;
            } else {
                a_match = false;
            }
        }
        if (!a_match) {
            // fast check, cpu branch prediction
            continue;
        }
        if (rows->b >= 10 && rows->b < 50) {
            lazyprint(rows);
        }
    }
}

class lazyprintbuf {
    public:
    vector<Row> buckets[40];
    void lazyprint2_into(const Row* rows) {
        int idx = rows->b - 10;
        buckets[idx].push_back(*rows);
    }

    void lazyprint2_realprint() {
        for (int i = 0; i < 40; i++) {
            for (auto x : buckets[i]) {
                cout << "one row=" << x.a << "," << x.b << endl;
            }
        }
    }
};

void task3(const Row* rows, int nrows) {
    // 在任务 2 的基础上, 我们期望你打印出的匹配⾏是按照 b 列进⾏排序的, 请实现 task3() .
    // TBD: 因为B的range有限，而且是海量数据，所以用bucket sort 很好
    cout << "task3" << endl;
    const Row* base = rows;
    bool a_match = false;
    int last_a = base->a;
    if (filter_imp1(last_a)) {
        a_match = true;
    }
    lazyprintbuf printbuf;
    for (int i = 0; i < nrows; i++) {
        rows = base + i;
        if (rows->a == last_a) {
            // fast check, cpu branch prediction
        } else {
            last_a = rows->a;
            if (filter_imp1(last_a)) {
                a_match = true;
            } else {
                a_match = false;
            }
        }
        if (!a_match) {
            // fast check, cpu branch prediction
            continue;
        }
        if (rows->b >= 10 && rows->b < 50) {
            printbuf.lazyprint2_into(rows);
        }
    }
    printbuf.lazyprint2_realprint();
}

class filterholder{
    public:
    unordered_set<int> myset;
    filterholder() {
        for (int i = 1; i < 100; i++) {
            myset.insert(1000*i);
        }
    }
    bool filter_imp2(int a) {
        return myset.find(a) != myset.end();
    }
};

void task4(const Row* rows, int nrows) {
    // 在任务 3 的基础上, 如果 a 列上的匹配条件不只是 1000,2000,3000 , ⽽是扩充成 1000,2000,3000,...,98000,99000 , 你在任务 3 中进⾏的实现是否⾜够优化? 请针对这⼀场 景实现 task4() , 再次提醒, 程序要能⾼效处理海量数据
    // TBD: 我假设匹配条件不一定是整数串吧, 所以需要优化下filter, 这里可以用hash+bloomfilter, 
    // 不然的话仅用把filter_imp1的4改成100就可以了
    // 因为是纯内存的数据结构，所以好像用bloomfilter没有必要
    cout << "task4" << endl;
    const Row* base = rows;
    bool a_match = false;
    int last_a = base->a;
    filterholder myfilter;
    if (myfilter.filter_imp2(last_a)) {
        a_match = true;
    }
    lazyprintbuf printbuf;
    for (int i = 0; i < nrows; i++) {
        rows = base + i;
        if (rows->a == last_a) {
            // fast check, cpu branch prediction
        } else {
            last_a = rows->a;
            if (myfilter.filter_imp2(last_a)) {
                a_match = true;
            } else {
                a_match = false;
            }
        }
        if (!a_match) {
            // fast check, cpu branch prediction
            continue;
        }
        if (rows->b >= 10 && rows->b < 50) {
            printbuf.lazyprint2_into(rows);
        }
    }
    printbuf.lazyprint2_realprint();
}

int main() {
/*
    ⾼效处理海量数据 : 假设Rows有GB级别
    cpu cache locality

    1. plain for if
    2. range check, fast check, branch prediction
    3. bucket sort
    4. check with hash
*/

    Row testdata[15] = {
        {1000, 2}, 
        {1000, 4},
        {1000, 13},
        {1000, 24},
        {1100, 24},
        {2000, 4},
        {2100, 14},
        {2110, 14},
        {2111, 14},
        {2000, 15},
        {2000, 34},
        {3000, 4},
        {3000, 34},
        {3000, 34},
    };
    task1(testdata, 15);
    task2(testdata, 15);
    task3(testdata, 15);
    task4(testdata, 15);

    cout << "end of main" << endl;
}