perl-Set-SegmentTree - Immutable segment trees with flatbuffers in perl

Property Value
Distribution ALT Linux Sisyphus
Repository Autoimports noarch
Package name perl-Set-SegmentTree
Package version 0.06
Package release alt1
Package architecture noarch
Package type rpm
Installed size 56.79 KB
Download size 56.79 KB
Official Mirror
wat? Segment Tree
A Segment tree is an immutable tree structure used to efficiently
resolve a value to the set of segments which encompass it.
You have a large set of value intervals (like time segments!) and
need to match them against a single value (like a time) efficiently.
This solution is suitable for problems where the set of intervals is
known in advance of the queries, and the tree needs to be loaded and
queried efficiently many orders of magnitude more often than the set
of intervals is updated.
Data structure:
A segment is like this:
[ Segment Label, Start Value , End Value ]
Start Value and End Values Must be numeric.
Start Value Must be less than End Value
Segment Identity Must occur exactly once
The speed of Set::SegmentTree depends on not being concerned
with additional segment relevant data, so it is expected one would
use the identity to refer into whatever persistence retains
additional information about the segment.
Use walkthrough
my @segments = (['A',1,5],['B',2,3],['C',3,8],['D',10,15]);
This defines four intervals which both do and don't overlap
- A - 1 to 5
- B - 2 to 3
- C - 3 to 8
- D - 10 to 15
Doing a find within the resulting tree
my $tree = Set::SegmentTree::Builder->new(@segments)->build
Would make these tests pass
is_deeply [$tree->find(0)], [];
is_deeply [$tree->find(1)], [qw/A/];
is_deeply [$tree->find(2)], [qw/A B/];
is_deeply [$tree->find(3)], [qw/A B C/];
is_deeply [$tree->find(4)], [qw/A C/];
is_deeply [$tree->find(6)], [qw/C/];
is_deeply [$tree->find(9)], [];
is_deeply [$tree->find(12)], [qw/D/];
And although this structure is relatively expensive to build,
it can be saved efficiently,
my $builder = Set::SegmentTree::Builder->new(@segments);
and then loaded and queried extremely quickly, making this
pass in only milliseconds.
my $tree = Set::SegmentTree->from_file('filename');
is_deeply [$tree->find(3)], [qw/A B C/];
This structure is useful in the use case where...
1) value segment inter...


Package Version Architecture Repository
perl-Set-SegmentTree - - -


Name Value
/usr/share/perl5 -
perl(File/ >= 0.640
perl(IO/ >= 1.160
perl(List/ >= 1.460
perl( >= 2.050
perl(Time/ >= 1.972.600
perl-base >= 1:5.10.0
rpmlib(PayloadIsLzma) -


Name Value
perl(Set/ = 0.060
perl(Set/SegmentTree/ = 0.060
perl(Set/SegmentTree/ = 0.060
perl(Set/SegmentTree/ = 0.060
perl-Set-SegmentTree = 0.06-alt1


Type URL
Binary Package perl-Set-SegmentTree-0.06-alt1.noarch.rpm
Source Package perl-Set-SegmentTree-0.06-alt1.src.rpm

Install Howto

  1. Add the following line to /etc/apt/sources.list:
    rpm [Sisyphus] noarch autoimports
    rpm [Sisyphus] noarch autoimports
  2. Update the package index:
    # sudo apt-get update
  3. Install perl-Set-SegmentTree rpm package:
    # sudo apt-get install perl-Set-SegmentTree



See Also

Package Description
perl-Set-Similarity-0.026-alt1.noarch.rpm similarity measures for sets
perl-Set-Similarity-BV-0.06-alt1.noarch.rpm similarity measures for sets using fast bit vectors (BV)
perl-Set-Similarity-CosinePDL-0.013-alt1.noarch.rpm Cosine similarity for sets PDL implementation
perl-Set-Similarity-CosinePP-0.015-alt1.noarch.rpm Cosine similarity for sets pure Perl vector implementation
perl-Set-SortedArray-0.02-alt1.noarch.rpm sets stored as sorted arrays
perl-Set-String-0.03-alt1.noarch.rpm perl module Set-String
perl-Set-Toolkit-0.11-alt1.noarch.rpm searchable, orderable, flexible sets of (almost) anything
perl-Set-Window-1.01-alt1.noarch.rpm perl module Set-Window
perl-Setup-1.0.5-alt1.noarch.rpm Specification for setup module
perl-Setup-Project-0.01-alt1.noarch.rpm setup project tool
perl-Setup-Project-scripts-0.01-alt1.noarch.rpm Setup-Project scripts
perl-Sew-Color-1.05-alt1.noarch.rpm Perl Module for giving rgb values for colours of varous manufactures embroidery thread
perl-Sex-0.69-alt2_8.noarch.rpm Perl teaches the birds and the bees
perl-Shannon-Entropy-1.101011-alt1.noarch.rpm Calculate the Shannon entropy H of a given input string
perl-Shape-RegularPolygon-0.01-alt1.noarch.rpm Object that treats the shape of the regular polygon