ARST打卡第212周[212/521]

发表于 分类于 阅读次数：
lc1093_大样本统计 【TED演讲】可以改变你职业生涯的习惯 带你全面了解compaction的13个问题 RocksDB中sst_dump的编译使用

Algorithm

lc1093_大样本统计

思考:
可以一次遍历获得最大最小值，平均数(sum/size)，众数(hash_set记录)，

但是中位数就好像需要排序，那么就会把时间复杂度拉高到O(nlog(n))，用大小堆维护也会导致插入O(nlog(n)).

所以好像免不了把时间复杂度拉到O(nlog(n))？

看看题解有没有办法控制时间复杂度。

看了题解恍然大悟，原来自己没有充分利用题意的内容，因为数字采样就在0到255，所以有了sum值之后就能通过count计数知道中位数的位置…

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
class Solution {
public:    
    vector<double> sampleStats(vector<int>& count) {
        int n = count.size();
        int total = accumulate(count.begin(), count.end(), 0);
        double mean = 0.0;
        double median = 0.0;
        int minnum = 256;
        int maxnum = 0;
        int mode = 0;

        int left = (total + 1) / 2;
        int right = (total + 2) / 2;
        int cnt = 0;
        int maxfreq = 0;
        long long sum = 0;
        for (int i = 0; i < n; i++) {
            sum += (long long)count[i] * i;
            if (count[i] > maxfreq) {
                maxfreq = count[i];
                mode = i;
            }
            if (count[i] > 0) {
                if (minnum == 256) {
                    minnum = i;
                }
                maxnum = i;
            }
            // 这里的范围判断很灵性
            if (cnt < right && cnt + count[i] >= right) {
                median += i;
            }
            if (cnt < left && cnt + count[i] >= left) {
                median += i;
            }
            cnt += count[i];
        }
        mean = (double) sum / total;
        median = median / 2.0;
        return {(double)minnum, (double)maxnum, mean, median, (double)mode};
    }
};

Review

【TED演讲】可以改变你职业生涯的习惯

每天反思，不断迭代自己的bug，然后fix bug，让自己成为一个更好的自己，这相比盲目前进有用得多

Tips

带你全面了解compaction的13个问题

Share-RocksDB中sst_dump的编译使用

编译

有可能要先编译rocksdb

1
2
3
4
5
6
7
8
9
10
11
12
 ✘ ⚡ 05/23|19:48:09  rocksdb   6.29.fb ●  make sst_dump
$DEBUG_LEVEL is 1
Makefile:170: Warning: Compiling in debug mode. Don't use the resulting binary in production
  CC       tools/sst_dump.o
  CC       tools/io_tracer_parser_tool.o
  CC       tools/ldb_cmd.o
  CC       tools/ldb_tool.o
  CC       tools/sst_dump_tool.o
  CC       utilities/blob_db/blob_dump_tool.o
  AR       librocksdb_tools_debug.a
/usr/bin/ar: creating librocksdb_tools_debug.a
  CCLD     sst_dump

cmake编译会在 tool 目录下生成，直接 make sst_dump 则是生成在 rocksdb 根目录

使用

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
 ⚡ 05/24|10:13:22  rocksdb   6.29.fb  ./sst_dump --file=/tmp/rocksdb_tmp --command=raw
options.env is 0x559da26cea00
Process /tmp/rocksdb_tmp/000013.sst
Sst file format: block-based
raw dump written to file /tmp/rocksdb_tmp/000013_dump.txt
Process /tmp/rocksdb_tmp/000007.sst
Sst file format: block-based
raw dump written to file /tmp/rocksdb_tmp/000007_dump.txt
Process /tmp/rocksdb_tmp/000019.sst
Sst file format: block-based
raw dump written to file /tmp/rocksdb_tmp/000019_dump.txt
Process /tmp/rocksdb_tmp/000004.sst
Sst file format: block-based
raw dump written to file /tmp/rocksdb_tmp/000004_dump.txt

 ⚡ 05/24|10:49:58  rocksdb   6.29.fb  cat /tmp/rocksdb_tmp/000019_dump.txt
Footer Details:
--------------------------------------
  metaindex handle: E40620
  index handle: 1E0F
  table_magic_number: 9863518390377041911
  format version: 5

Metaindex Details:
--------------------------------------
  Properties block handle: 32AD06

Table Properties:
--------------------------------------
  # data blocks: 1
  # entries: 1
  # deletions: 0
  # merge operands: 0
  # range deletions: 0
  raw key size: 11
  raw average key size: 11.000000
  raw value size: 3
  raw average value size: 3.000000
  data block size: 30
  index block size (user-key? 1, delta-value? 1): 20
  filter block size: 0
  # entries for filter: 0
  (estimated) table size: 50
  filter policy name: N/A
  prefix extractor name: nullptr
  column family ID: 0
  column family name: default
  comparator name: leveldb.BytewiseComparator
  merge operator name: nullptr
  property collectors names: []
  SST file compression algo: Snappy
  SST file compression options: window_bits=-14; level=32767; strategy=0; max_dict_bytes=0; zstd_max_train_bytes=0; enabled=0; max_dict_buffer_bytes=0;
  creation time: 1681356505
  time stamp of earliest key: 0
  file creation time: 0
  slow compression estimated data size: 0
  fast compression estimated data size: 0
  DB identity: 86751c5f-624e-4582-a4aa-a7078979ab79
  DB session identity: ZRB0TF2BT6GWRTCMNZD4
  DB host id: YF-72166391D1
  original file number: 19
  unique ID: 80345056726F72BF-D677A376A5E0D45C-A2CFA81888233438

Index Details:
--------------------------------------
  Block key hex dump: Data block handle
  Block key ascii

  HEX    666F6F: 0019
  ASCII  f o o
  ------

Data Block # 1 @ 0019
--------------------------------------
  HEX    666F6F: 626172
  ASCII  f o o : b a r
  ------

Data Block Summary:
--------------------------------------
  # data blocks: 1
  min data block size: 25
  max data block size: 25
  avg data block size: 25.000000