``Part of you is always traveling faster, always traveling ahead. Even when you are moving, it is never fast enough to satisfy that part of you... You have heard of other travelers whose maps are breadcrumbs, whose maps are stones, whose maps are the four winds, whose maps are yellow bricks laid one after the other. You read your map with your foot, and behind you somewhere there must be another traveler whose map is the bloody footprints that you are leaving behind you.
There is a map of fine white scars on the soles of your feet that tells you where you have been.''
-Kelly Link
./neutronstar Sn10Xe20Nd30Dy40 -k 10000 1.05
generates the 10000 most abundant isotope peaks of a
molecule with 10 tin atoms, 20 xenon atoms, 30 neodymium
atoms, and 40 dysprosium atoms. ./neutronstar
Sn10Xe20Nd30Dy40 -p 0.9 1.05
works similarly, but
instead generates enough peaks to cover 90% of the total
abundance of the molecule.
The 1.05 is the rank of the layer-ordered heaps.
Layer-ordered heaps (LOHs) are an innovative way to get
some benefits of sorting without the $$\Omega(n \log(n))$$
runtime. For example, the list [3,6,2,4,7,1,6]
can be sorted to yield [1,2,3,4,6,6,7]
.
With $$\alpha=2,$$ we can create a layer-ordering such
as [1],[3,2],[6,7,6,4]
. That is, the sizes of
each subsequent layer doubles asymptotically and every
element in layer $$L_i$$ has $$L_i\leq L_{i+1};$$ however,
unlike sorting, elements within a layer remain unordered.
An LOH of rank $$\alpha=2$$ can be constructed in $$O(n)$$ time by using linear 1D selection.
Generate the most abundant 1,564,230 isotope peaks in Xe50 in just over a second.
% intensity explained | # peaks | IsoSpec runtime & memory | NeutronStar runtime & memory |
0.1 | 2510 | 0.800s & 30.7MB | 0.00354s & 1.40MiB |
0.3 | 12909 | 0.801s & 30.7MB | 0.0117s & 5.40MB |
0.5 | 35243 | 0.800s & 30.7MB | 0.0298s & 21.6MB |
0.7 | 91046 | 8.39s & 166MB | 0.0708s & 43.3MB |
0.9 | 332449 | 8.38s & 166MB | 0.235s & 86.9MB |
0.99 | 1564230 | 35.9s & 480MB | 1.15s & 352.3MB |