March 20, 2012, 10:24 am
Some quick Javascript which plots random walks from a point…
View it here.
<html>
<head>
<script type="text/javascript">
var ittr=8;
var delta=-0.005;
function draw_frame() {
var canvas = document.getElementById("m_canvas");
if(canvas.getContext) {
var ctx = canvas.getContext("2d");
ctx.lineWidth = 0;
ctx.fillStyle = "rgb(0,0,0)";
var x=250;
var y=250;
for(var n=0;n<200;n++) {
var r=Math.floor(Math.random()*4);
if(r==0) { x+=1; y+=0; }
if(r==1) { x+=0; y+=1; }
if(r==2) { x-=1; y+=0; }
if(r==3) { x-=0; y-=1; }
ctx.fillRect(x*1,y*1,1,1);
}
ctx.fillStyle = "rgb(0,200,200)";
ctx.fillRect(250,250,3,3);
}
}
</script>
</head>
<body onload="setInterval(draw_frame,10);" >
<canvas id="m_canvas" width="500" height="500">You need a Javascipt</canvas>
</body>
</html>
March 18, 2012, 2:55 pm
Another quick and dirty algorithm implementation in C++. This time a Binary search tree (no balancing):
#include <iostream>
#include <vector>
using namespace std;
class Node {
public:
int value;
Node *less;
Node *more;
};
class BinarySearchTree {
public:
BinarySearchTree() : root(NULL) {}
void find_node(int value,Node **findnode,Node **parent) {
*findnode = NULL;
*parent = NULL;
if(root == NULL) {
return;
}
Node *current = root;
for(;;) {
if(current->value == value) {*findnode = current; return;}
if(value < current->value) {
if(current->less != NULL) {*parent = current; current = current->less;}
else {
return;
}
} else {
if(current->more != NULL) {*parent = current; current = current->more;}
else {
return;
}
}
}
}
Node *getr(Node *c,Node **parent) {
*parent = c;
for(;c->more != NULL;) {
*parent = c;
c = c->more;
}
return c;
}
void remove(int value) {
Node *delnode;
Node *parent;
find_node(value,&delnode,&parent);
if(delnode == NULL) return;
// leaf
if((delnode->less == NULL) && (delnode->more == NULL)) {
if(parent->less == delnode) {parent->less = NULL;}
if(parent->more == delnode) {parent->more = NULL;}
delete delnode;
return;
}
// only one child
if((delnode->less == NULL) || (delnode->more == NULL)) {
if(delnode->less != NULL) {
if(parent->less == delnode) {parent->less = delnode->less;}
if(parent->more == delnode) {parent->more = delnode->less;}
delete delnode;
return;
}
if(delnode->more != NULL) {
if(parent->less == delnode) {parent->less = delnode->more;}
if(parent->more == delnode) {parent->more = delnode->more;}
delete delnode;
return;
}
}
// two children
Node *i = getr(delnode->less,&parent);
delnode->value = i->value;
if(parent == i) { delnode->less = NULL;}
if(parent->less == i) { parent->less = NULL; }
else { parent->more = NULL; }
delete i;
}
void insert(int value) {
if(root == NULL) {
Node *n = new Node();
n->value = value;
n->less = NULL;
n->more = NULL;
root = n;
return;
}
Node *current = root;
for(;;) {
if(value < current->value) {
if(current->less != NULL) current = current->less;
else {
Node *n = new Node();
n->value = value;
n->less = NULL;
n->more = NULL;
current->less = n;
break;
}
} else {
if(current->more != NULL) current = current->more;
else {
Node *n = new Node();
n->value = value;
n->less = NULL;
n->more = NULL;
current->more = n;
break;
}
}
}
}
bool exists(int value) {
if(root == NULL) {
return false;
}
Node *current = root;
for(;;) {
if(current->value == value) return true;
if(value < current->value) {
if(current->less != NULL) current = current->less;
else {
return false;
}
} else {
if(current->more != NULL) current = current->more;
else {
return false;
}
}
}
}
Node *root;
};
int main() {
BinarySearchTree s;
vector<int> testdata;
for(size_t n=0;n<10;n++) { testdata.push_back(rand()%20); }
for(size_t n=0;n<10;n++) { s.insert(testdata[n]); }
cout << "testdata: " << endl;
for(size_t n=0;n<10;n++) { cout << testdata[n] << endl; }
cout << "existance check: " << endl;
for(size_t n=0;n<10;n++) { if(s.exists(testdata[n])) cout << "existance: " << testdata[n] << " true" << endl; else cout << "existance: " << testdata[n] << " false" << endl;}
for(size_t n=0;n<10;n++) { if(s.exists(testdata[n]+20)) cout << "existance: " << testdata[n]+20 << " true" << endl; else cout << "existance: " << testdata[n]+20 << " false" << endl;}
cout << "remove: " << testdata[5] << endl;
s.remove(testdata[5]);
if(s.exists(testdata[5])) cout << testdata[5] << " still exists" << endl; else cout << testdata[5] << " no longer exists" << endl;
cout << "remove: " << testdata[3] << endl;
s.remove(testdata[3]);
if(s.exists(testdata[3])) cout << testdata[3] << " still exists" << endl; else cout << testdata[3] << " no longer exists" << endl;
cout << "remove: " << testdata[0] << endl;
s.remove(testdata[0]);
if(s.exists(testdata[0])) cout << testdata[0] << " still exists" << endl; else cout << testdata[0] << " no longer exists" << endl;
}
March 17, 2012, 2:50 pm
I had this problem last week. The /var filesystem was full, but contained few files. This in term seemed to kill cifs and the web interface, though nfs was fine.
Long story short, it’s probably snmpd, there’s a bug in a version of the isilon os (possibly fixed now).
You can use fstat to find abnormally large open files (unfortunately lsof isn’t present, so I couldn’t see a way to locate unlinked files) and the process that has them open. You can then kill -9 snmpd. After that you can restart services as follows:
isi services apache2 disable
Isi services apache2 enable
isi services cifs disable
isi services cifs enable
You may also need to kill off webui/smbd (killall -9 isi_webui_d).
March 17, 2012, 12:05 am
A simple, rough and ready, maxheap implementation. It uses an vector as an implicit complete binary tree:
#include <iostream>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <limits.h>
using namespace std;
class Heap {
public:
Heap() {
store.push_back(0);
}
int l_child(int idx) {
return idx*2;
}
int r_child(int idx) {
return (idx*2)+1;
}
int get_parent(int idx) {
return (idx/2);
}
void insert(int val) {
store.push_back(val);
int idx = store.size()-1;
if(idx == 1) return;
// bubble up
for(;store[get_parent(idx)] < store[idx];) {
int t = store[get_parent(idx)];
store[get_parent(idx)] = val;
store[idx] = t;
idx = get_parent(idx);
if(get_parent(idx) == 0) break;
}
}
void dump() {
cout << "DUMPSTART" << endl;
for(size_t n=0;n<store.size();n++) {
cout << store[n] << endl;
}
cout << "DUMPEND" << endl;
}
int pop() {
int r = store[1];
store[1] = store[store.size()-1];
store.pop_back();
bool min=true;
int idx = 1;
for(;min==true;) {
min=false;
int lidx = l_child(idx);
int ridx = r_child(idx);
int lval;
int rval;
if(lidx < store.size()) lval = store[lidx]; else lval = INT_MIN;
if(ridx < store.size()) rval = store[ridx]; else rval = INT_MIN;
if(store[idx] < lval) { min=true; }
if(store[idx] < rval) { min=true; }
if(!min) break;
int t = store[idx];
if(lval > rval) {
store[idx] = store[l_child(idx)];
store[l_child(idx)] = t;
idx = l_child(idx);
} else {
store[idx] = store[r_child(idx)];
store[r_child(idx)] = t;
idx = r_child(idx);
}
}
return r;
}
vector<int> store;
};
int main() {
vector<int> testdata;
for(size_t n=0;n<10;n++) testdata.push_back(rand()%20);
Heap myheap;
for(size_t n=0;n<testdata.size();n++) myheap.insert(testdata[n]);
cout << "popping heap:" << endl;
for(size_t n=0;n<testdata.size();n++) cout << myheap.pop() << endl;
cout << "sorted testdata:" << endl;
sort(testdata.rbegin(),testdata.rend());
for(size_t n=0;n<testdata.size();n++) cout << testdata[n] << endl;
cout << "second test: " << endl;
Heap myheap2;
for(size_t n=0;n<testdata.size();n++) myheap2.insert(testdata[n]);
for(size_t n=0;n<(testdata.size()/2);n++) cout << myheap2.pop() << endl;
myheap2.insert(100);
myheap2.insert(7);
for(size_t n=0;n<(testdata.size()/2)+2;n++) cout << myheap2.pop() << endl;
}
RSS