Rainy2k
0%

Posted on Edited on In

Alluxio

Alluxio在帮助统一跨各种平台用户数据的同时还有助于为用户提升总体 I/O 吞吐量。

Alluxio是通过把存储分为两个不同的类别来实现这一目标的。

  • UFS(底层文件存储，也称为底层存储)
    • 该存储空间代表不受Alluxio管理的空间。 UFS存储可能来自外部文件系统，包括如HDFS或S3。
    • Alluxio可能连接到一个或多个UFS并在一个命名空间中统一呈现这类底层存储。
    • 通常，UFS存储旨在相当长一段时间持久存储大量数据。
  • Alluxio存储
    • Alluxio做为一个分布式缓存来管理Alluxio workers本地存储，包括内存。这个在用户应用程序与各种底层存储之间的快速数据层带来的是显著提高的I/O性能。
    • Alluxio存储主要用于存储热数据，暂态数据，而不是长期持久数据存储。
    • 每个Alluxio节点要管理的存储量和类型由用户配置决定。
    • 即使数据当前不在Alluxio存储中，通过Alluxio连接的UFS中的文件仍然对Alluxio客户可见。当客户端尝试读取仅可从UFS获得的文件时数据将被复制到Alluxio存储中。

Alluxio存储通过将数据存储在计算节点内存中来提高性能。Alluxio存储中的数据可以被复制来形成”热”数据，更易于I/O并行操作和使用。

Alluxio中的数据副本独立于UFS中可能已存在的副本。 Alluxio存储中的数据副本数是由集群活动动态决定的。 由于Alluxio依赖底层文件存储来存储大部分数据， Alluxio不需要保存未使用的数据副本。

Alluxio还支持让系统存储软件可感知的分层存储，使类似L1/L2 CPU缓存一样的数据存储优化成为可能。

🟠所以，Alluxio本质上是一个中间层。

Read more »

Posted on Edited on In

MLPerf

吞吐量、IOPS 和延迟 Q&A

引用自：https://mp.weixin.qq.com/s/Yz2lkYzimfFC-85KBUq_zQ

吞吐量、IOPS 和延迟是三个术语，通常称为存储性能指标。

SNIA 网络存储论坛 （NSF） 通过现场网络研讨会“您想知道的有关存储但太自豪而无法询问的一切”

带回了我们广受欢迎的网络研讨会系列“您想知道的有关吞吐量、IOPS 和延迟但又太自豪而无法询问的一切”。

Read more »

Posted on Edited on

本篇讲一些其他博客没有展开讲的部分。

Q：什么是lowbit函数?

A：lowbit可以取出一个数字的最低位1，如lowbit(10102{1010}_2) = 00102{0010}_2

lowbit(5) = 1,lowbit(6) = 2

Q：为什么树状数组的划分使用lowbit？

树状数组和线段树一样，需要将一个区域[1,n]分成多段

线段树的划分是：二分，需要4倍内存(粗略4倍)

而树状数组的划分是：二进制分解

假设n=2i1+2i2+…+2imn = 2^{i_1}+2^{i_2}+…+2^{i_m}

那么对于[1,n][1,n]的区域，划分的区间为：

[1,2i1][1,2^{i_1}]

[2i1+1,2i1+2i2][2^{i_1}+1,2^{i_1}+2^{i_2}]

……

[2i1+2i2+…+2im−1+1,2i1+2i2+…+2im],[2^{i_1}+2^{i_2}+…+2^{i_{m-1}}+1,2^{i_1}+2^{i_2}+…+2^{i_{m}}],

x=7=20+21+22x = 7 = 2^0+2^1+2^2

1
2
3
4
5
6
7
8
9
10
x = 7;
lowbit(x); // lowbit(x) = 1
x-=lowbit(x); // x = 6
lowbit(x); // lowbit(x) = 2
x-=lowbit(x); // x = 4
lowbit(x); //lowbit(x) = 4
x-=lowbit(x); // x = 0
[1,7]被划分为[1,4],[5,6],[7,7]

树状数组c[x]保存的则是：[x-lowbit(x)+1,x]区间中所有数的和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int ask(int x) {
    int ans = 0;
    while(x) {
        ans+=c[x];
        x-=lowbit(x);
        // x = 7->[7,7] , c[7] = a[7]
        // x = 6->[5,6] , c[6] = a[5]+a[6]
        // x = 4->[1,4] , c[4] = a[1]+a[2]+a[3]+a[4]
        // x = 0->end
        //由此看出，可以保证不重合的划分
        // ans=c[7]+c[6]+c[4]
    }
    return ans;
}

同时，由以上的介绍可以推出，对于c[x]节点，它的父亲结点应该是c[x+lowbit(x)]

那么更新时则为

1
2
3
4
5
6
7
8
void add(int x,int k) {
    while(x<=n) {
        c[x]+=k;
        x+=lowbit(x); 
        // Q: 为什么是x = x+lowbit(x)？
        // A: 因为它需要更新它的父节点，使得包含它的区间得以被更新
    }
}

以上的add(int x,int k)和ask(int x)实现的功能是：单点更新、区间查询

那么如果要实现单点查询和区间更新呢？考虑利用差分的思想，请看代码：

PS:单点查询为query(x)，而不是query(x)-query(x-1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 100;

int n;
int a[maxn];
int c[maxn];


int lowbit(int x) {
    return x & (-x);
}

void add(int i,int k) { // 单点更新
    while(i<=n) {
        c[i] += k;
        i += lowbit(i);
    }
}
int query(int x) { // [1,x] 区间查询
    int ans = 0;
    while(x) {
        ans += c[x];
        x -= lowbit(x);
    }
    return ans;
} 


int main() {
    int m;
    cin >> n >> m;
    for (int i = 1;i<=n;i++) {
        cin >> a[i];
    }
    for (int i = 1;i<=m;i++) {
        char c;
        cin >> c;
        if(c == 'C') {
            int l, r, d;
            cin >> l >> r >> d;
            // 区间更新
            add(l, d);
            add(r + 1, -d);
        } else {
            int x;cin>>x;
            // 单点查询
            cout << a[x] + query(x)<<endl;
        }

    }
}
Read more »

Posted on Edited on In

Bundling

https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ffc7/00000000001d3ff3

题意

将给定的n个字符串划分为大小为k的组,每组的权值为这些字符串的最长公共前缀

∑n≤106,k∣n\sum n \leq 10^6,k|n

思路

构建一棵字典树,每一个节点对应一个前缀,对于每个前缀,如果它出现的次数大于k,那么它对答案有贡献,加上即可

代码: https://xlorpaste.cn/0ve9u4

Read more »

Posted on Edited on

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
char s[maxn << 1] = "##";
int n, hw[maxn << 1];
int l[maxn << 1], r[maxn << 1];
void manacher(char* a) {//字符串a下标从0开始
    int len = strlen(a);
    for (int i = 0; i < len; i++) {
        s[i * 2 + 2] = a[i];
        s[i * 2 + 3] = '#';
    }
    n = len * 2 + 2;
    s[n] = 0;
    int maxr = 0, m = 0;
    for (int i = 1; i < n; i++) {
        if (i < maxr)
            hw[i] = min(hw[m * 2 - i], hw[m] + m - i);
        else
            hw[i] = 1;
        while (s[i + hw[i]] == s[i - hw[i]]) hw[i]++;
        if (hw[i] + i > maxr) {
            m = i;
            maxr = hw[i] + i;
        }
    }
}
Read more »

Posted on Edited on

扩展GCD

给定a,b

求ax=1(mod b)ax=1(mod \ b) 的最小整数解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll x, y;
ll exgcd(ll a, ll b, ll &x, ll &y){
    if(!b){
        x = 1, y = 0;
        return a;
    }
    ll d = exgcd(b, a % b, x, y);
    ll t = x;
    x = y, y = t - y * (a / b);
    return d;
}

int main() {
    ll a,b;
    cin >> a >> b;
    exgcd(a, b, x, y);
    ll ans = (x + b) % b;//最小整数解
    
    cout << ans << endl;
}
1
2
3
4
5
6
7
8
bool liEu(ll a, ll b, ll c, ll &x, ll &y) {
  ll d = exgcd(a, b, x, y);
  if (c % d != 0) return 0;
  ll k = c / d;
  x *= k;
  y *= k;
  return 1;
}
Read more »

Posted on Edited on

模板

查找主串中的子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 100;
int nxt[maxn][26];

char s[maxn], t[maxn];

int main() {
    scanf("%s", s + 1);
    int len = strlen(s + 1);
    for (int i = len; i >= 1; i--) {
        for (int j = 0; j < 26; j++) {
            nxt[i - 1][j] = nxt[i][j];
        }
        nxt[i - 1][s[i] - 'a'] = i;
    }

    int q;
    scanf("%d", &q);
    while(q--) {
        scanf("%s", t);
        int len1 = strlen(t);
        int f = 0;
        for (int i = 0, u = 0; i < len1; i++) {
            int v = t[i] - 'a';
            u = nxt[u][v];
            if(u==0) {
                f = 1;
                break;
            }
        }
        if(f) {
            printf("NO\n");
        }
        else
            printf("YES\n");
    }
}
Read more »

Posted on Edited on

快速幂方法1：
311=31×32×383^{11} = 3^1 \times 3^2 \times 3^8

1
2
3
4
5
6
7
8
9
10
long long qpow(long long x,int n,long long mod) {
    long long res = 1;
    while(n>0) {
        if(n&1) // 二进制最低位为1，则乘上x^(2^i)
            res = res * x % mod;
        x = x * x % mod;
        n >>= 1;
    }
    return res;
}
Read more »

Posted on Edited on

Lucky Draw

https://nanti.jisuanke.com/t/44330

题意

硬币掷到反面则丢掉一条命

现在有n个人,每个人有k条命,每次掷到正面的概率为p

现在问平局的概率为多少?(也就是全输)

思路

两个结局:有一个人胜出或者平局

只要算有一个人赢了的情况,乘n

考虑误差:将回合数设为1000

代码 : https://xlorpaste.cn/g22mb4

Read more »

Posted on Edited on In

1+3+5+...+(2∗n−1)=n21+3+5+...+(2*n-1) = n^2

2+4+6+...+(2∗n)=n∗(n+1)2+4+6+...+(2*n) = n*(n+1)

1+2+3+...+n=n∗(n+1)21+2+3+...+n = \frac{n*(n+1)}{2}

Cnm=Cn−1m−1+Cn−1mC_{n}^{m}= C_{n-1}^{m-1} + C_{n-1}^m

Read more »

Posted on Edited on

模板

http://xlorpaste.cn/y0xia1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
struct Hash() {
    const int mod = 1e9 + 7;
    const int SEED = 13331;
    long long p[maxn], f[maxn], ff[maxn];
    int n;
    void Hash(string s) {
        n = s.size();
        f[0] = s[0] - 'a' + 1;
        p[0] = 1;
        for (int i = 1; i < n; i++) {
            f[i] = (f[i - 1] * SEED % mod + (s[i] - 'a' + 1)) % mod;
            p[i] = p[i - 1] * SEED % mod;
        }
        ff[n - 1] = s[n - 1] - 'a' + 1;
        for (int i = n - 2; i >= 0; i--) {
            ff[i] = (ff[i + 1] * SEED % mod + (s[i] - 'a' + 1)) % mod;
        }
    }
    long long h(int l, int r) {
        if (l == 0)
            return f[r];
        return (f[r] - f[l - 1] * p[r - l + 1] % mod + mod) % mod;
    }
    long long hh(int l, int r)
    {
        if (r == n - 1)
            return ff[l];
        return (ff[l] - ff[r + 1] * p[r - l + 1] % mod + mod) % mod;
    }
};
Read more »

Posted on Edited on

https://leetcode.cn/problems/remove-nth-node-from-end-of-list/

使用快慢指针，让nxt指针先向后移动N次

这样nxt指针和pre指针之间的间隔则为N

然后，nxt和pre同时向后移动，当nxt移动到链表的尾部，pre依然和它间隔为N，那么此时的pre就是链表的倒数第N个节点了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* pre = head;
        ListNode* nxt = head;
        for(int i=0;i<n;i++) {
            nxt = nxt->next;
        }
        if(nxt == nullptr) {
            head = head->next;
            return head;
        }

        while(nxt!=nullptr) {
            nxt = nxt->next;
            if(nxt == nullptr) {
                cout<<pre->val<<endl;
                pre->next = pre->next->next;
                return head;                
            }
            pre = pre->next;
        }  
        return head;
    }
};
Read more »

Posted on Edited on In

dijkstra 基于贪心思想，利用了三角不等式，因为全局最小值不可能再被其他节点更新

dijkstra 用于解决单源最短路问题

disjstra 用于解决非负权图问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 1e6 + 100;
typedef pair<int,int> pii;

struct node {
    int v;
    int w;
};
vector<node> e[maxn];
int dis[maxn];
bool vis[maxn];
int pre[maxn];

void dijkstra(int s) {
    priority_queue<pii, vector<pii>, greater<pii>> q;
    memset(dis, inf, sizeof(dis));
    dis[s] = 0;
    q.push({dis[s], s});
    while(!q.empty()) {
        pii t = q.top();
        q.pop();
        int u = t.second;
        if(vis[u])
            continue;
        vis[u] = true;
        for(node x:e[u]) {
            int v = x.v;
            int w = x.w;
            if(dis[v]>dis[u]+w) {
                dis[v] = dis[u] + w;
                pre[v] = u;
                q.push({dis[v], v});
            }
        }
    }
}

int main() {
    int n, m, s;
    cin >> n >> m >> s;
    for (int i = 0;i<n;i++) {
        pre[i] = -1;
    }
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        e[u].push_back((node){v, w});
        // e[v].push_back((node){u, w});
    }
    dijkstra(s);
    for (int i = 1; i <= n;i++) {
        cout << dis[i] << " ";
    }
    cout << endl;
}
Read more »