mirror of https://github.com/copenhas/ropex.git
You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
Sean Copenhaver
16d3b8caa8
|
11 years ago | |
|---|---|---|
| css | 11 years ago | |
| images | 11 years ago | |
| js | 11 years ago | |
| Binary.Chars.Rope.html | 11 years ago | |
| Enumerable.Rope.html | 11 years ago | |
| Inspect.Rope.html | 11 years ago | |
| README.html | 11 years ago | |
| Rope.html | 11 years ago | |
| index.html | 11 years ago | |
| modules_list.html | 11 years ago | |
| protocols_list.html | 11 years ago | |
| records_list.html | 11 years ago | |
README.html
<!DOCTYPE html>
<html>
<head>
<title>README</title>
<meta charset="utf-8">
<link rel="stylesheet" href="css/style.css" type="text/css" media="screen" charset="utf-8" />
<script type="text/javascript" charset="utf-8">
relpath = '';
if (relpath != '') relpath += '/';
</script>
<script type="text/javascript" charset="utf-8" src="js/jquery.js"></script>
<script type="text/javascript" charset="utf-8" src="js/app.js"></script>
</head>
<body>
<script type="text/javascript" charset="utf-8">
if (window.top.frames.main) document.body.className = 'frames';
</script>
<div id="content">
<h1>Rope</h1>
<p>Implemention of a rope data structure in Elixir. It provides faster index based operations, especially at scale,
then plain binary based strings. One of the basic building block of this is the <code>slice/3</code> operation which is roughly 3x
faster at 2kb of text and up to 50x faster at 880kb of text. The other is <code>concat/2</code> operation which runs in constant time
but as it stands so does the BEAM (how about that). <code>concat/2</code> does suffer roughly double the overhead of the <code><></code> operator
on plain binary based strings. The combination of <code>slice/3</code> and <code>concat/2</code> allows efficient <code>insert_at/3</code> and <code>remove_at/3</code>.</p>
<h2>So what does this look like?</h2>
<p>The following images where genereated with <a href="http://graphviz.org">GraphViz</a>. The green oval represent the variables who point
to a rope. The squares represent the internal record data structure for the rope. 'concat' nodes are purely for connecting
the leaves together, while the leaves actually contain the text.</p>
<p>Straight concatenation with an auto-rebalance triggered part way:</p>
<p><img src="http://copenhas.github.io/ropex/images/bulldozer.dot.png" alt="Worst case" title="worst case"></p>
<p>The same rope explicitly rebalanced for better slice based operations:</p>
<p><img src="http://copenhas.github.io/ropex/images/bulldozerrebalanced.dot.png" alt="Worst case rebalanced" title="worst case rebalanced"></p>
<p>Also existing leafs should be reused in new ropes. The operations performed where creating a new rope (original),
inserting 'hello world' (insert), a subrope sliced out (slice), then concatenated back in (concat), then finally
a series of concatenations (multiconcat).</p>
<p><img src="http://copenhas.github.io/ropex/images/manipulations.dot.png" alt="Rope with manipulations" title="Rope with manipulation"></p>
<p>That same rope rebalanced:</p>
<p><img src="http://copenhas.github.io/ropex/images/manipulationsbalanced.dot.png" alt="Rope with manipulations rebalanced" title="Rope with manipulation rebalanced"></p>
</div>
</body>
</html>