In [1]:
%pylab inline
Populating the interactive namespace from numpy and matplotlib
In [2]:
import pandas as pd
In [3]:
bench = pd.concat([
pd.read_table("CompactBitVector.tsv"),
pd.read_table("SucVector.tsv"),
pd.read_table("RRR.tsv"),
pd.read_table("LargeRRR.tsv")
])
In [4]:
# remove package name
bench.type = map(lambda s: s.split(".")[1], bench.type)
In [5]:
figsize(12, 8)
In [6]:
def plot_bench(name, r, logy=True):
bench[bench.r == r]\
.pivot(index="length", columns="type", values="bench_" + name)\
.plot(style="o-")
title("{} (r = {})".format(name, r))
xscale("log", basex=2)
ylabel("sec / op")
if logy:
yscale("log")
else:
ticklabel_format(style="scientific", axis="y", scilimits=(0,0))
grid()
savefig("{}_{}.png".format(name, r))
The result shows operation time (second per operation) of getindex
, rank1
, and select1
.
In [7]:
plot_bench("getindex", 0.5)
In [8]:
plot_bench("rank1", 0.5)
In [9]:
plot_bench("select1", 0.5)
In [10]:
plot_bench("getindex", 0.1)
In [11]:
plot_bench("rank1", 0.1)
In [12]:
plot_bench("select1", 0.1)
In [13]:
plot_bench("getindex", 0.01)
In [14]:
plot_bench("rank1", 0.01)
In [15]:
plot_bench("select1", 0.01)
In [16]:
pd.options.display.max_rows = 1000
In [17]:
bench
Out[17]:
type
length
r
bench_getindex
bench_rank1
bench_select1
0
CompactBitVector
1024
0.01
1.345151e-09
1.089107e-09
1.387914e-08
1
CompactBitVector
4096
0.01
1.086814e-09
5.505452e-10
1.190852e-08
2
CompactBitVector
16384
0.01
1.055945e-09
5.673192e-10
1.051917e-08
3
CompactBitVector
65536
0.01
1.250713e-09
7.280791e-10
1.174915e-08
4
CompactBitVector
262144
0.01
9.965591e-10
5.151887e-10
1.255847e-08
5
CompactBitVector
1048576
0.01
1.264959e-09
4.969864e-10
1.437504e-08
6
CompactBitVector
4194304
0.01
1.048179e-09
5.761096e-10
1.277089e-08
7
CompactBitVector
16777216
0.01
1.092204e-09
4.839556e-10
1.327523e-08
8
CompactBitVector
67108864
0.01
1.212893e-09
7.043719e-10
1.542759e-08
9
CompactBitVector
268435456
0.01
1.027694e-09
4.840958e-10
1.350173e-08
10
CompactBitVector
1073741824
0.01
1.072107e-09
4.881632e-10
1.434298e-08
11
CompactBitVector
1024
0.10
1.137992e-09
6.940799e-10
1.754343e-08
12
CompactBitVector
4096
0.10
1.015003e-09
5.883138e-10
1.889744e-08
13
CompactBitVector
16384
0.10
9.892070e-10
5.147293e-10
2.632452e-08
14
CompactBitVector
65536
0.10
1.064315e-09
4.987495e-10
3.174713e-08
15
CompactBitVector
262144
0.10
9.748447e-10
5.069270e-10
3.505566e-08
16
CompactBitVector
1048576
0.10
9.685864e-10
5.709505e-10
3.186957e-08
17
CompactBitVector
4194304
0.10
9.672930e-10
4.921985e-10
3.298815e-08
18
CompactBitVector
16777216
0.10
9.982483e-10
4.966464e-10
3.508962e-08
19
CompactBitVector
67108864
0.10
9.747987e-10
4.839420e-10
3.897124e-08
20
CompactBitVector
268435456
0.10
9.688348e-10
4.871001e-10
4.081599e-08
21
CompactBitVector
1073741824
0.10
1.059967e-09
4.878574e-10
5.522714e-08
22
CompactBitVector
1024
0.50
1.132616e-09
7.027550e-10
4.825072e-08
23
CompactBitVector
4096
0.50
1.134642e-09
5.463512e-10
7.696368e-08
24
CompactBitVector
16384
0.50
9.743023e-10
5.206652e-10
9.500369e-08
25
CompactBitVector
65536
0.50
1.016924e-09
4.931512e-10
1.018655e-07
26
CompactBitVector
262144
0.50
1.005617e-09
5.896056e-10
1.097038e-07
27
CompactBitVector
1048576
0.50
9.829810e-10
5.425515e-10
1.136305e-07
28
CompactBitVector
4194304
0.50
9.707210e-10
5.001440e-10
1.253409e-07
29
CompactBitVector
16777216
0.50
9.597192e-10
4.946260e-10
1.415620e-07
30
CompactBitVector
67108864
0.50
9.847541e-10
4.915171e-10
1.474177e-07
31
CompactBitVector
268435456
0.50
1.169112e-09
4.844056e-10
1.515289e-07
32
CompactBitVector
1073741824
0.50
1.061399e-09
4.878827e-10
2.373968e-07
0
SucVector
1024
0.01
9.296966e-10
7.024148e-10
1.377899e-08
1
SucVector
4096
0.01
5.476806e-10
8.188248e-10
1.340988e-08
2
SucVector
16384
0.01
5.553980e-10
5.220163e-10
1.582036e-08
3
SucVector
65536
0.01
5.222585e-10
4.958749e-10
1.425094e-08
4
SucVector
262144
0.01
7.701297e-10
5.780656e-10
1.400882e-08
5
SucVector
1048576
0.01
4.946909e-10
4.913583e-10
1.502046e-08
6
SucVector
4194304
0.01
6.564791e-10
5.636210e-10
1.488853e-08
7
SucVector
16777216
0.01
4.839499e-10
5.652239e-10
1.596462e-08
8
SucVector
67108864
0.01
5.040133e-10
4.839354e-10
1.574822e-08
9
SucVector
268435456
0.01
5.129973e-10
5.069458e-10
1.599031e-08
10
SucVector
1073741824
0.01
5.304270e-10
5.372372e-10
1.738206e-08
11
SucVector
1024
0.10
1.118354e-09
7.129514e-10
2.208915e-08
12
SucVector
4096
0.10
5.548525e-10
5.478623e-10
2.378241e-08
13
SucVector
16384
0.10
5.048091e-10
5.800121e-10
3.164378e-08
14
SucVector
65536
0.10
9.626167e-10
5.153158e-10
3.450101e-08
15
SucVector
262144
0.10
4.919088e-10
5.780592e-10
3.983448e-08
16
SucVector
1048576
0.10
5.075872e-10
4.879177e-10
3.971256e-08
17
SucVector
4194304
0.10
4.910557e-10
5.166223e-10
4.174172e-08
18
SucVector
16777216
0.10
4.884722e-10
4.886682e-10
4.365922e-08
19
SucVector
67108864
0.10
4.845481e-10
5.259576e-10
4.962912e-08
20
SucVector
268435456
0.10
4.841522e-10
4.881558e-10
4.703194e-08
21
SucVector
1073741824
0.10
5.808690e-10
5.379685e-10
5.266313e-08
22
SucVector
1024
0.50
9.548991e-10
7.073236e-10
6.379537e-08
23
SucVector
4096
0.50
5.487809e-10
6.375170e-10
9.996026e-08
24
SucVector
16384
0.50
5.857460e-10
5.486987e-10
1.198403e-07
25
SucVector
65536
0.50
7.734530e-10
5.370657e-10
1.344881e-07
26
SucVector
262144
0.50
4.976175e-10
8.046229e-10
1.345314e-07
27
SucVector
1048576
0.50
4.971538e-10
5.166597e-10
1.513672e-07
28
SucVector
4194304
0.50
4.967237e-10
5.659256e-10
1.604264e-07
29
SucVector
16777216
0.50
4.869080e-10
5.770164e-10
1.659357e-07
30
SucVector
67108864
0.50
4.844873e-10
4.874899e-10
1.776878e-07
31
SucVector
268435456
0.50
4.889215e-10
5.166654e-10
1.905493e-07
32
SucVector
1073741824
0.50
4.942066e-10
4.901402e-10
2.055738e-07
0
RRR
1024
0.01
3.441781e-08
3.490671e-08
3.885704e-08
1
RRR
4096
0.01
3.579069e-08
3.697433e-08
3.431738e-08
2
RRR
16384
0.01
3.483607e-08
3.550530e-08
3.779558e-08
3
RRR
65536
0.01
3.794330e-08
3.655816e-08
3.746658e-08
4
RRR
262144
0.01
3.754601e-08
3.806678e-08
4.229694e-08
5
RRR
1048576
0.01
3.682849e-08
3.880979e-08
4.004179e-08
6
RRR
4194304
0.01
3.655731e-08
3.823807e-08
4.822628e-08
7
RRR
16777216
0.01
3.666237e-08
3.491394e-08
4.131398e-08
8
RRR
67108864
0.01
3.906775e-08
3.607488e-08
4.689900e-08
9
RRR
268435456
0.01
3.668992e-08
3.607852e-08
4.049754e-08
10
RRR
1073741824
0.01
3.735148e-08
3.680100e-08
4.640783e-08
11
RRR
1024
0.10
4.024846e-08
3.796337e-08
8.043339e-08
12
RRR
4096
0.10
3.864635e-08
4.020459e-08
8.827926e-08
13
RRR
16384
0.10
3.883256e-08
3.913251e-08
9.672428e-08
14
RRR
65536
0.10
3.900821e-08
4.087748e-08
1.065240e-07
15
RRR
262144
0.10
3.874913e-08
3.756109e-08
1.179822e-07
16
RRR
1048576
0.10
4.023338e-08
4.109999e-08
1.210701e-07
17
RRR
4194304
0.10
3.967288e-08
3.832332e-08
1.474409e-07
18
RRR
16777216
0.10
4.010929e-08
3.894474e-08
1.443287e-07
19
RRR
67108864
0.10
3.957294e-08
3.928270e-08
1.533886e-07
20
RRR
268435456
0.10
3.987384e-08
4.204407e-08
1.556958e-07
21
RRR
1073741824
0.10
4.246645e-08
4.081548e-08
1.681173e-07
22
RRR
1024
0.50
3.802303e-08
3.971923e-08
2.537505e-07
23
RRR
4096
0.50
4.232418e-08
4.108492e-08
3.257695e-07
24
RRR
16384
0.50
3.812072e-08
4.213742e-08
3.741268e-07
25
RRR
65536
0.50
4.023949e-08
3.966833e-08
4.068046e-07
26
RRR
262144
0.50
3.773928e-08
4.131214e-08
4.356947e-07
27
RRR
1048576
0.50
3.846935e-08
4.103451e-08
4.827074e-07
28
RRR
4194304
0.50
3.849704e-08
4.046939e-08
5.208089e-07
29
RRR
16777216
0.50
4.023410e-08
4.082892e-08
5.766204e-07
30
RRR
67108864
0.50
4.039431e-08
4.484450e-08
6.047385e-07
31
RRR
268435456
0.50
4.026568e-08
4.307281e-08
6.663900e-07
32
RRR
1073741824
0.50
4.013457e-08
4.119111e-08
7.154228e-07
0
LargeRRR
1024
0.01
8.023082e-08
7.955678e-08
4.834036e-08
1
LargeRRR
4096
0.01
7.695358e-08
7.746356e-08
5.045836e-08
2
LargeRRR
16384
0.01
8.587621e-08
8.838561e-08
6.387574e-08
3
LargeRRR
65536
0.01
8.963918e-08
8.679650e-08
4.943700e-08
4
LargeRRR
262144
0.01
9.150199e-08
8.568312e-08
5.621138e-08
5
LargeRRR
1048576
0.01
8.850931e-08
9.124375e-08
7.233315e-08
6
LargeRRR
4194304
0.01
8.848737e-08
9.355794e-08
6.593454e-08
7
LargeRRR
16777216
0.01
9.156619e-08
9.158794e-08
6.454996e-08
8
LargeRRR
67108864
0.01
8.692829e-08
8.701026e-08
7.301309e-08
9
LargeRRR
268435456
0.01
8.731957e-08
8.931782e-08
7.369421e-08
10
LargeRRR
1073741824
0.01
8.756829e-08
8.889485e-08
6.619541e-08
11
LargeRRR
1024
0.10
1.188172e-07
1.298908e-07
1.947715e-07
12
LargeRRR
4096
0.10
1.391386e-07
1.441132e-07
2.300217e-07
13
LargeRRR
16384
0.10
1.662537e-07
1.666976e-07
2.658073e-07
14
LargeRRR
65536
0.10
1.636808e-07
1.623765e-07
2.857835e-07
15
LargeRRR
262144
0.10
1.649009e-07
1.614463e-07
3.147488e-07
16
LargeRRR
1048576
0.10
1.660001e-07
1.642531e-07
3.531855e-07
17
LargeRRR
4194304
0.10
1.622596e-07
1.629909e-07
3.740972e-07
18
LargeRRR
16777216
0.10
1.646761e-07
1.633312e-07
3.837388e-07
19
LargeRRR
67108864
0.10
1.672727e-07
1.711756e-07
4.350000e-07
20
LargeRRR
268435456
0.10
1.651876e-07
1.644834e-07
4.697184e-07
21
LargeRRR
1073741824
0.10
1.631401e-07
1.665021e-07
4.755405e-07
22
LargeRRR
1024
0.50
1.456902e-07
1.427457e-07
8.467216e-07
23
LargeRRR
4096
0.50
2.373085e-07
2.374130e-07
1.123976e-06
24
LargeRRR
16384
0.50
2.661128e-07
2.688997e-07
1.311119e-06
25
LargeRRR
65536
0.50
2.537201e-07
2.673846e-07
1.523427e-06
26
LargeRRR
262144
0.50
2.624446e-07
2.609150e-07
1.634996e-06
27
LargeRRR
1048576
0.50
2.607045e-07
2.777768e-07
1.832050e-06
28
LargeRRR
4194304
0.50
2.593048e-07
2.560381e-07
2.074716e-06
29
LargeRRR
16777216
0.50
2.775988e-07
2.644293e-07
2.179542e-06
30
LargeRRR
67108864
0.50
2.666140e-07
2.651907e-07
2.443488e-06
31
LargeRRR
268435456
0.50
2.649453e-07
2.666639e-07
2.648206e-06
32
LargeRRR
1073741824
0.50
2.639318e-07
2.621970e-07
2.806736e-06
Content source: bicycle1885/IndexableBitVectors.jl
Similar notebooks: