Skip to content

Instantly share code, notes, and snippets.

@masrab
Last active October 10, 2021 01:55
Show Gist options
  • Save masrab/f65c2fe3e4dbf0502626 to your computer and use it in GitHub Desktop.
Save masrab/f65c2fe3e4dbf0502626 to your computer and use it in GitHub Desktop.
Visual data structure selector
Name Indexing (Average) Search (Average) Insertion (Average) Deletion (Worst) Indexing (Worst) Search (Worst) Insertion (Worst) Deletion (Worst) Space
Basic Array O(1) O(n) Undefined Undefined O(1) O(n) Undefined Undefined O(n)
Dynamic Array O(1) O(n) O(n) O(n) O(1) O(n) O(n) O(n) O(n)
Singly-Linked List O(n) O(n) O(1) O(1) O(n) O(n) O(1) O(1) O(n)
Doubly-Linked List O(n) O(n) O(1) O(1) O(n) O(n) O(1) O(1) O(n)
Skip List O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n) O(n) O(n) O(n) O(n log(n))
Hash Table Undefined O(1) O(1) O(1) Undefined O(n) O(n) O(n) O(n)
Binary Search Tree O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n) O(n) O(n) O(n) O(n)
Cartresian Tree Undefined O(log(n)) O(log(n)) O(log(n)) Undefined O(n) O(n) O(n) O(n)
B-Tree O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n)
Red-Black Tree O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n)
Splay Tree Undefined O(log(n)) O(log(n)) O(log(n)) Undefined O(log(n)) O(log(n)) O(log(n)) O(n)
AVL Tree O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n)
var margin = {top: 30, right: 10, bottom: 10, left: 10},
width = 1000 - margin.left - margin.right,
height = 300 - margin.top - margin.bottom;
var svg = d3.select(".chart").append("svg")
.attr("width", width + margin.left + margin.right)
.attr("height", height + margin.top + margin.bottom)
.append("g")
.attr("transform", "translate(" + margin.left + "," + margin.top + ")");
var x = d3.scale.ordinal().rangePoints([0, width], 1),
y = {};
var line = d3.svg.line(),
axis = d3.svg.axis().orient("left"),
foreground;
var source_select = d3.select("#source_select");
// first time
// load data and render the page
d3.csv(source_select.property("value"), function(err, dataset) {
render_page(dataset);
});
// on source change
source_select.on("change", function(){
// clean up svg canvas
svg.selectAll('*').remove();
// load data and render the page
d3.csv(source_select.property("value"), function(err, dataset) {
render_page(dataset);
});
});
// functions
function obj_ascending (obj1, obj2) {
return d3.ascending(d3.values(obj1), d3.values(obj2));
}
function obj_descending (obj1, obj2) {
return d3.descending(d3.values(obj1), d3.values(obj2));
}
function render_page(dataset){
// extract colnames
var dimensions = d3.keys(dataset[0]).filter(function(d) {
return d != "Name"});
draw(dataset, dimensions);
// create sliders
create_sliders(dimensions);
var n = get_size();
scores = score(dataset, n);
render_ranking(scores);
highlight_best(scores);
d3.selectAll(".controls input")
.on("input", function() {
var n = get_size();
var scores = score(dataset, n);
render_ranking(scores);
highlight_best(scores);
});
};
function highlight_best(scores){
name_best = d3.keys(scores.sort(obj_descending)[0])[0];
d3.selectAll('.foreground path')
.filter(function(d) { return d.Name === name_best; })
.call(highlight);
}
function render_ranking (scores) {
d3.select("div#ranking").selectAll("ol").remove();
d3.select("div#ranking")
.append("ol")
.selectAll("li")
.data(scores)
.enter()
.append("li")
.sort(obj_descending)
.text(function(d) {return d3.keys(d)+": "+ d3.values(d).map(d3.format(".4f"));})
}
function print_debug(names, weight, row_scores, row_costs){
var score_div = d3.select("div.debug");
score_div.html(null);
score_div.append('h2').text('Weights: ');
score_div.append('p').text(weight.map(d3.format("%")));
score_div.append('h2').text('row_scores: ');
score_div.append("div")
.selectAll("p")
.data(row_scores)
.enter()
.append("p")
.text(function(d,i) { return names[i]+ ': '+ d.map(d3.format(".3f")).join(' , '); });
score_div.append('h2').text('row_costs: ');
score_div.append("div")
.selectAll("p")
.data(row_costs)
.enter()
.append("p")
.text(function(d,i) { return names[i]+ ': '+ d.map(d3.format(".3f")).join(' , '); });
console.log(weight);
console.log('row_costs: ', row_costs);
console.log('row_scores: ', row_scores);
}
function score(dataset, n) {
// n: problem size
var values = get_slider_values(),
slider_sum = d3.sum(values),
weight = values.map(function(x) { return x/slider_sum;});
//calc cost for each row
var row_costs = dataset.map(function(d) {return row_cost(d, n);} );
var row_scores = row_costs.map(function(cost) { return row_score(weight, cost)});
var scores = row_scores.map(function(rs) {return d3.sum(rs);});
var names = dataset.map(function(d){ return d.Name;});
// print_debug(names, weight, row_scores, row_costs);
var scores_obj = [];
for (i in names) {
tmp = {};
tmp[names[i]] = scores[i];
scores_obj.push(tmp);
};
return scores_obj;
}
// calculate score for given cost and weight vectors
function row_score(weight, cost){
// weight: vector of weights (length = # dimensions)
// cost: vector of cost calculated from equations (length = # dimensions)
var score = [];
for (i in cost){
score[i] = weight[i] * (1/cost[i]);
};
return score;
};
// calculate cost vector for a single row
function row_cost(d, n) {
// d: object representing one row of data
// n: problem size
var d = d3.map(d);
d.remove('Name');
var dimensions = d.keys();
var cost = [];
var cost = dimensions.map(function(dim) {
return equations[d.get(dim)](n);
});
return cost;
};
var equations=
{
'O(n!)': function(x) {
var rval=1;
for (var i = 2; i <= x; i++) {
rval = rval * i;
}
return rval;
},
'O(n^2)': function(x) {
return x * x;
},
'O(n log(n))': function(x) {
return x * Math.log(x);
},
'O(log(n))': function(x) {
return Math.log(x);
},
'O(n)': function(x) {
return x;
},
'O(m+n)': function(x) {
return x;
},
'O(1)': function(x) {
return 1;
},
'Undefined': function(x) {
// return 1e15;
return Infinity;
}
};
function get_size(){
return +d3.select("div#size input").property('value');
}
function get_slider_values() {
var slider_values =
d3.selectAll('div#sliders input')[0]
.map(function(slider) {return +slider.value;});
return slider_values;
};
// dynamically create sliders for each input dimension
function create_sliders(dimensions) {
d3.select('#sliders')
.selectAll('div')
.remove();
d3.select('#sliders')
.selectAll('div')
.data(dimensions)
.enter()
.append('div')
.attr('id', function(d,i) { return 'slider'+i; })
.append('label')
.text(function(d) { return d; })
.append('input')
.property({'type':'range', 'min':0, 'max':100, 'step':25});
}
function draw(dataset, dimensions) {
x.domain(dimensions);
// create an array of scales. one for each column
dimensions.forEach(function(d){
y[d] = d3.scale.ordinal()
.domain(d3.set(dataset.map(function(row) { return row[d];})).values().sort()) // extract column
.rangePoints([0,height-20])
});
var foreground = svg.append('g')
.attr('class', 'foreground')
.selectAll('path')
.data(dataset)
.enter()
.append('path')
.attr('d', function(d) { return path(d,dimensions); } );
// Add a group element for each dimension.
var g = svg.selectAll(".dimension")
.data(dimensions)
.enter().append("g")
.attr("class", "dimension")
.attr("transform", function(d) { return "translate(" + x(d) + ")"; });
g.append("g")
.attr("class", "axis")
.each(function(d) { d3.select(this).call(axis.scale(y[d])); });
var labels = g.append("text")
.style("text-anchor", "middle")
.attr("y", -15)
.attr('class', 'label')
.text(function(d) { return d; });
// highlight the first path
d3.select('.foreground path').call(highlight);
// hover effect
foreground
.on('mouseover', function(d) {
d3.select(this).call(highlight);
});
}
// Returns the path for a given data point.
function path(d, dimensions) {
return line(dimensions.map(function(p) { return [x(p), y[p](d[p])]; }));
}
function tbl_row(obj) {
var obj = d3.map(obj);
obj.remove('Name');
var header = obj.keys().map(function(v) { return '<th>'+v+'</th>'});
var row = obj.values().map(function(v) { return '<td>'+v+'</td>'});
return '<tr>' + header.join('') + '</tr>' + '<tr>'+row.join('')+'</tr>';
}
function highlight(selected_path) {
d3.selectAll('.foreground path').style({'stroke': '#ddd', 'stroke-width': '1px'})
selected_path.style({'stroke': 'gold', 'stroke-width': '3px'});
d3.select('#btn-title').text(selected_path.datum().Name).style('display', 'block');
d3.select('#tbl_output').html(tbl_row(selected_path.datum()));
}
Name Heapify Find Max Extract Max Increase Key Insert Delete Merge
Linked List (sorted) Undefined O(1) O(1) O(n) O(n) O(1) O(m+n)
Linked List (unsorted) Undefined O(n) O(n) O(1) O(1) O(1) O(1)
Binary Heap O(n) O(1) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(m+n)
Binomial Heap Undefined O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n))
Fibonacci Heap Undefined O(1) O(log(n)) O(1) O(1) O(log(n)) O(1)
<!DOCTYPE html>
<meta charset="utf-8">
<style>
#container {
width: 1050px;
margin: auto;
margin-top: 20px;
margin-bottom: 20px;
padding: 10px;
border:1px solid black;
/*background-color: ghostwhite;*/
}
svg {
font: 10px sans-serif;
}
.foreground path {
fill: none;
stroke: #ddd;
}
.axis line,
.axis path {
fill: none;
stroke: #000;
stroke-dasharray: 5,5;
shape-rendering: crispEdges;
}
.axis text {
text-shadow: 0 1px 0 #fff, 1px 0 0 #fff, 0 -1px 0 #fff, -1px 0 0 #fff;
}
text.label {
font: 12px Verdana;
fill: darkgray;
}
.label:hover {
fill: gold;
}
.chart {
margin: auto;
/*float: left;*/
}
.output {
width: 70%;
margin: auto;
font: 12px Verdana;
/*float: left;*/
}
#btn-title {
display: none;
}
fieldset.controls {
padding: 5px;
font-weight: normal;
width: 300px;
}
fieldset.controls label {
font-weight: normal;
width: 280px;
}
fieldset.controls input {
display: inline-block;
width: 150px;
vertical-align: middle;
float: right;
}
div#size {
margin-bottom: 5px;
}
div#ranking {
margin-top: 20px;
margin-right: 30px;
/*background-color: ghostwhite;*/
float: right;
padding: 10px;
}
</style>
<head>
<link href="//maxcdn.bootstrapcdn.com/bootstrap/3.3.1/css/bootstrap.min.css" rel="stylesheet">
</head>
<body>
<div id='container'>
<label>Pick one:
<select name="source_select" id="source_select">
<option value="ds.csv" selected>Data Structure</option>
<option value="heap.csv">Heap</option>
</select>
</label> <br>
<div class="chart"></div>
<div class="output">
<div>
<button type="button" class="btn btn-danger" id="btn-title" disabled></button> <br>
</div>
<table class='table table-bordered table-striped' id='tbl_output'></table>
</div>
<div id="ranking"><p>Ranking:</p></div>
<fieldset class='controls'>
<legend>Problem Specification</legend>
<div id="size">
<label>Problem Size<input type="number" min="0" step="1000" value="10000"></label>
</div>
<div id="sliders"></div>
</fieldset>
<div class="debug">
</div>
</div>
<script src="http://d3js.org/d3.v3.min.js"></script>
<script src="ds.js"></script>
</body>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment