fork download 
  1. #!/usr/bin/perl
  2. # Compares node distances in memory for different layouts of the following
  3. # binary tree:
  4. #                      A
  5. #                  /       \
  6. #              B               C
  7. #            /   \           /   \
  8. #          D       E       F       G
  9. #         / \     / \     / \     / \
  10. #        H   I   J   K   L   M   N   O
  11. #       / \ / \ / \ / \ / \ / \ / \ / \
  12. #       P Q R S T U V W X Y Z 0 1 2 3 4
  13.  
  14. # Calculates the real node distance.
  15. sub dist($$)
  16. {
  17.   my ($i, $j) = @_;
  18.   return 0 if ($i == $j);
  19.   ($j,$i) = ($i,$j) if ($i > $j);
  20.   # $i<$j. Go one up from the larger node.
  21.   return 1 + dist($i, ($j-1)>>1);
  22. }
  23.  
  24. # Determines the average memory distance for nodes as a function of tree distance.
  25. sub get_dists($$)
  26. {
  27.   my $tree = shift;     # Original tree ordering
  28.   my $locality = shift; # Locality-based ordering
  29.  
  30.   my %dists = ();
  31.   my %counts = ();
  32.  
  33.   for (my $i=0; $i<length($tree); $i++)
  34.   {
  35.     for (my $j=$i; $j<length($tree); $j++)
  36.     {
  37.       # Find location of $i and $j in the locality-based ordering.
  38.       my $ni = substr($tree, $i, 1);
  39.       my $nj = substr($tree, $j, 1);
  40.       my $it = index($locality, $ni);
  41.       my $jt = index($locality, $nj);
  42.       my $d = (($i <= $j) ? ($j-$i) : ($i-$j));
  43.       my $dt = (($it <= $jt) ? ($jt-$it) : ($it-$jt));
  44.       my $treedist = dist($i, $j);
  45.       $dists{$treedist} += $dt;
  46.       $counts{$treedist}++;
  47.     }
  48.   }
  49.   foreach my $k (sort keys %counts)
  50.   {
  51.     $dists{$k} /= $counts{$k};
  52.   }
  53.   return %dists;
  54. }
  55.  
  56. my $tree = "ABCDEFGHIJKLMNOPQRSTUVWXYZ01234";    # original (breadth-first prefix) ordering
  57. my $prefix = "ABDHPQIRSEJTUKVWCFLXYMZ0GN12O34";  # depth-first prefix ordering
  58. my $infix = "PHQDRISBTJUEVKWAXLYFZM0C1N2G3O4";   # infix ordering
  59. my $veb = "ABCDHPQIRSEJTUKVMFLXYMZ0GN12O34";     # V.E.B. layout (hope I got it right)
  60.  
  61. my %original_dists = get_dists($tree, $tree);
  62. my %prefix_dists = get_dists($tree, $prefix);
  63. my %infix_dists = get_dists($tree, $infix);
  64. my %veb_dists = get_dists($tree, $veb);
  65.  
  66. print "set key top left;\n";
  67. print "set title 'Locality ratios';\n";
  68. print "set xlabel 'tree distance';\n";
  69. print "set ylabel 'avg. memory distance';\n";
  70.  
  71. print "plot '-' w lp title 'original', '-' w lp title 'prefix ordering', '-' w lp title 'infix ordering', '-' w lp title 'van-Emde-Boas layout';\n";
  72.  
  73. foreach my $k (sort keys %original_dists)
  74. {
  75.   print "$k $original_dists{$k}\n";
  76. }
  77. print "e\n";
  78. foreach my $k (sort keys %prefix_dists)
  79. {
  80.   print "$k $prefix_dists{$k}\n";
  81. }
  82. print "e\n";
  83. foreach my $k (sort keys %infix_dists)
  84. {
  85.   print "$k $infix_dists{$k}\n";
  86. }
  87. print "e\n";
  88. foreach my $k (sort keys %veb_dists)
  89. {
  90.   print "$k $veb_dists{$k}\n";
  91. }
  92. print "e\n";
  93.  
  94.  
Success #stdin #stdout 0.01s 6000KB
comments (?)
stdin 
Standard input is empty
stdout 
set key top left;
set title 'Locality ratios';
set xlabel 'tree distance';
set ylabel 'avg. memory distance';
plot '-' w lp title 'original', '-' w lp title 'prefix ordering', '-' w lp title 'infix ordering', '-' w lp title 'van-Emde-Boas layout';
0 0
1 8.5
2 9.13953488372093
3 12.9230769230769
4 11.4117647058824
5 12.75
6 9.6
7 12
8 8
e
0 0
1 2.63333333333333
2 5.13953488372093
3 8.15384615384615
4 9.82352941176471
5 11
6 11.8
7 15
8 15
e
0 0
1 2.13333333333333
2 3.72093023255814
3 6.15384615384615
4 8.47058823529412
5 12
6 12.8
7 16
8 16
e
0 0
1 3.83333333333333
2 6.58139534883721
3 10.2692307692308
4 9.83823529411765
5 10.859375
6 11.325
7 14.4375
8 16.125
e
https://ideone.com/6UX9KR
language:
Perl (perl 5.28.1)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!