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
|