Read it here basically Microsoft can’t be trusted to follow up on there promises of openness so we should stop using there technology. That being said I have nothing that uses FAT and would have to wonder at how widespread it really is?
Posted in Software | Comments (0)
Went back and looked at the radix sort and found that it when sorting say 10,000,000 3 digit numbers it can use almost a gig and a half of ram. To try and fix this I changed the ArrayLists to Queues so that an item is only moved to another queue not copied to another queue, I also stopped copying the items to sort into a new variable at the start of the function it was a waste. The old Radix sort used a gig to a gig and a half of ram on average the new version uses 600mb to 800mb on average. Both run in linear time with similar performance.
Not really any point to this yet just seeing if I could make it better. There’s still probably a million improvements to make but this is what I got so far.
Provided in c#/mono once again.
using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;
namespace RadixSort
{
class Program
{
static void Main(string[] args)
{
System.Random rand = new Random(System.DateTime.Now.Millisecond);
int items = Convert.ToInt32(args[0]);
Queue Items = new Queue();
int c = 0;
while (c <= items)
{
Items.Enqueue(rand.Next(0, 999));
c++;
}
System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
sw.Start();
Items = RadixSort(Items, 3);
sw.Stop();
Console.WriteLine("Sorted in :: " + sw.Elapsed.ToString());
}
static Queue RadixSort(Queue Items, int Digits)
{
int Digit = Digits - 1;
while (Digit >= 0)
{
Queue Zero = new Queue();
Queue One = new Queue();
Queue Two = new Queue();
Queue Three = new Queue();
Queue Four = new Queue();
Queue Five = new Queue();
Queue Six = new Queue();
Queue Seven = new Queue();
Queue Eight = new Queue();
Queue Nine = new Queue();
int UpperLimit = Items.Count;
int counter = 1;
while (counter < UpperLimit)
{
int i = Convert.ToInt32(Items.Dequeue());
counter++;
if (i.ToString().PadLeft(Digits, '0')[Digit] == '0')
{
Zero.Enqueue(i);
continue;
}
if (i.ToString().PadLeft(Digits, '0')[Digit] == '1')
{
One.Enqueue(i);
continue;
}
if (i.ToString().PadLeft(Digits, '0')[Digit] == '2')
{
Two.Enqueue(i);
continue;
}
if (i.ToString().PadLeft(Digits, '0')[Digit] == '3')
{
Three.Enqueue(i);
continue;
}
if (i.ToString().PadLeft(Digits, '0')[Digit] == '4')
{
Four.Enqueue(i);
continue;
}
if (i.ToString().PadLeft(Digits, '0')[Digit] == '5')
{
Five.Enqueue(i);
continue;
}
if (i.ToString().PadLeft(Digits, '0')[Digit] == '6')
{
Six.Enqueue(i);
continue;
}
if (i.ToString().PadLeft(Digits, '0')[Digit] == '7')
{
Seven.Enqueue(i);
continue;
}
if (i.ToString().PadLeft(Digits, '0')[Digit] == '8')
{
Eight.Enqueue(i);
continue;
}
if (i.ToString().PadLeft(Digits, '0')[Digit] == '9')
{
Nine.Enqueue(i);
continue;
}
}
Items = new Queue();
foreach (int i in Zero)
{
Items.Enqueue(i);
}
foreach (int i in One)
{
Items.Enqueue(i);
}
foreach (int i in Two)
{
Items.Enqueue(i);
}
foreach (int i in Three)
{
Items.Enqueue(i);
}
foreach (int i in Four)
{
Items.Enqueue(i);
}
foreach (int i in Five)
{
Items.Enqueue(i);
}
foreach (int i in Six)
{
Items.Enqueue(i);
}
foreach (int i in Seven)
{
Items.Enqueue(i);
}
foreach (int i in Eight)
{
Items.Enqueue(i);
}
foreach (int i in Nine)
{
Items.Enqueue(i);
}
Digit--;
}
return Items;
}
}
}Posted in Software | Comments (0)
While browsing Wikipedia I came across the wiki entry for computational sorting methods and one thing on the page struck me as odd. They had a whole list of non-comparison sorting methods that sort things without ever checking them against the other items in the list (hence the name 
) so I thought I’d see if I could come up with a quick Radix sort and see if I can get linear performance out of it (Which the Wikipedia article says its capable of).
This is what I came up with 114 lines not tweaked too much. And yes this code provides a linear search time (e.g. the number of items doubles so does the time needed to sort). On my machine I tested it from 10,000 to 5,120,000 items (by doubling the ammount of items each time 10 test with 4 runs each test to average the time) and it took on average 0.008954888 milliseconds per item regardless of how many there were.
So here’s the code in C#/mono. There’s probably a million ways to optimize it put I was just interested in see how the Radix sort worked in general I might try to make it faster in the future but this is it for now.
NOTE: this program is meant to be run from the command line with the following syntax -> c:\PATH-TO-PROGRAM\Program.exe
using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;
namespace RadixSort
{
class Program
{
static void Main(string[] args)
{
System.Random rand = new Random(System.DateTime.Now.Millisecond);
int items = Convert.ToInt32(args[0]);
ArrayList Items = new ArrayList();
int c = 0;
while (c <= items)
{
Items.Add(rand.Next(0,999));
c++;
}
System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
sw.Start();
ArrayList sorted = RadixSort(Items,3);
sw.Stop();
Console.WriteLine("Sorted in :: "+sw.Elapsed.Seconds.ToString() +
" Seconds and "+sw.Elapsed.Milliseconds.ToString()+" milliseconds");
}
static ArrayList RadixSort (ArrayList Items, int Digits)
{
ArrayList RetValue = new ArrayList();
RetValue = Items;
int Digit = Digits - 1;
while (Digit >= 0)
{
ArrayList Zero = new ArrayList();
ArrayList One = new ArrayList();
ArrayList Two = new ArrayList();
ArrayList Three = new ArrayList();
ArrayList Four = new ArrayList();
ArrayList Five = new ArrayList();
ArrayList Six = new ArrayList();
ArrayList Seven = new ArrayList();
ArrayList Eight = new ArrayList();
ArrayList Nine = new ArrayList();
foreach (int i in RetValue)
{
if (i.ToString().PadLeft(Digits,'0')[Digit] == '0')
{
Zero.Add(i);
continue;
}
if (i.ToString().PadLeft(Digits,'0')[Digit] == '1')
{
One.Add(i);
continue;
}
if (i.ToString().PadLeft(Digits,'0')[Digit] == '2')
{
Two.Add(i);
continue;
}
if (i.ToString().PadLeft(Digits,'0')[Digit] == '3')
{
Three.Add(i);
continue;
}
if (i.ToString().PadLeft(Digits,'0')[Digit] == '4')
{
Four.Add(i);
continue;
}
if (i.ToString().PadLeft(Digits,'0')[Digit] == '5')
{
Five.Add(i);
continue;
}
if (i.ToString().PadLeft(Digits,'0')[Digit] == '6')
{
Six.Add(i);
continue;
}
if (i.ToString().PadLeft(Digits,'0')[Digit] == '7')
{
Seven.Add(i);
continue;
}
if (i.ToString().PadLeft(Digits,'0')[Digit] == '8')
{
Eight.Add(i);
continue;
}
if (i.ToString().PadLeft(Digits,'0')[Digit] == '9')
{
Nine.Add(i);
continue;
}
}
RetValue = new ArrayList();
foreach (int i in Zero)
{
RetValue.Add(i);
}
foreach (int i in One)
{
RetValue.Add(i);
}
foreach (int i in Two)
{
RetValue.Add(i);
}
foreach (int i in Three)
{
RetValue.Add(i);
}
foreach (int i in Four)
{
RetValue.Add(i);
}
foreach (int i in Five)
{
RetValue.Add(i);
}
foreach (int i in Six)
{
RetValue.Add(i);
}
foreach (int i in Seven)
{
RetValue.Add(i);
}
foreach (int i in Eight)
{
RetValue.Add(i);
}
foreach (int i in Nine)
{
RetValue.Add(i);
}
Digit--;
}
return RetValue;
}
}
}Posted in Software | Comments (0)
I made a little program that times how long it take you to solve a Triangle problem like project euler’s problem 18. Randomly generates the triangle and solves them in milliseconds as to not affect the users time. You can change how many rows the triangle has by editing the box in the bottom left corner (there’s no cap on the input so if you really want to try to solve a 100 row triangle by yourself you can). Written in c# requires .net 2.0 or higher.
Download it here TriangleGame (68)
NOTE: its not zipped and some anti-virus programs have problems with people downloading .exe’s
Posted in Software | Comments (0)
Based off of a simpler bot by other people found on the web. Wrote it to be able to allow irc users to add themselves to a Apache blacklist. Some of the features are os dependant ( needs to be run on linux).
Just fill out the sections for server, server password, nickserv password, port, and channel.
#!/usr/bin/python
"""
ircbot.py - An IRC Bot Basis in Python
License:
W3C Open Source License; share and enjoy!
http://www.w3.org/Consortium/Legal/copyright-software-19980720
Original:
http://dev.w3.org/cvsweb/2000/scribe-bot/ircAsync.py
Dan Connolly and Tim Berners-Lee
Copyright (c) 2001 W3C (MIT, INRIA, Keio)
Augmentations' Author:
Sean B. Palmer, inamidst.com
This version updated by: Serinox
Features added:
network oper abilities
actions
kill users
kick users
ip to domain lookup
whois lookup
nickserv signin
works with a modified apache ip whitelist
other random quirks.
"""
import sys, os, re, socket, asyncore, asynchat, re, commands
protect = True
filename = "irc.log"
FILE = open(filename,"a")
proxyacl = "/usr/local/proxy/conf/access.conf"
PACL = open(filename,"a")
class Origin(object):
def __init__(self, origin):
self.origin = origin
self.split(origin)
def __str__(self):
return self.origin
def split(self, origin):
if origin and '!' in origin:
self.nick, userHost = origin.split('!', 1)
if '@' in userHost:
self.user, self.host = userHost.split('@', 1)
else: self.user, self.host = userHost, None
else: self.nick, self.user, self.host = origin, None, None
def replyTo(self, nickname, args):
if (not args) or (len(args) < 2): return
target = args[1]
if target == nickname:
self.sender = self.nick
else: self.sender = target
def ctcp(s): return '\x01%s\x01' % s
def me(s): return ctcp('ACTION %s' % s)
class Bot(asynchat.async_chat):
def __init__(self, nick=None, userid=None, name=None, channels=None):
asynchat.async_chat.__init__(self)
self.bufIn = ''
self.set_terminator('\r\n')
self.nick = nick or 'Ted'
self.userid = userid or 'Ted'
self.name = name or 'Ted'
self.documentation = {}
self.info = {}
self.dispatch = []
self.msgstack = []
self.channels = channels or ['#test']
self.rule(self.welcome, 'welcome', cmd='001')
self.rule(self.help, 'help', '%s[:,] help (\w+)\??' % self.nick)
def run(self, host, port):
port = port or 6667
self.create_socket(socket.AF_INET, socket.SOCK_STREAM)
debug("connecting to...", host, port)
self.connect((host, port))
self.bufIn = ''
asyncore.loop()
def welcome(self, m, origin, args, text):
for chan in self.channels:
self.todo(['JOIN', chan])
self.msg("nickserv","identify NICKSERV PASSWORD")
self.todo(['OPER',"Phil Poper123!"])
def help(self, m, origin, args, text):
command = m.group(1)
if self.documentation.has_key(command):
doc = self.documentation[command]
self.msg(origin.sender, '%s: %s' % (command, doc))
else: self.msg(origin.sender, 'No help available for %s.' % command)
def todo(self, args, *text):
command = ' '.join(args)
if text: command = command + ' :' + ' '.join(text)
self.push(command + '\r\n')
debug("sent/pushed command:", command)
def handle_connect(self):
debug("connected")
self.todo(['PASS',"IRC SERVER PASSWORD"])
self.todo(['NICK', self.nick])
self.todo(['USER', self.userid, "+iw", self.nick], self.name)
def collect_incoming_data(self, bytes):
self.bufIn = self.bufIn + bytes
FILE = open(filename,"a")
FILE.writelines(self.bufIn+"\n")
FILE.close()
def found_terminator(self):
line = self.bufIn
self.bufIn = ''
if line.startswith(':'):
origin, line = line[1:].split(' ', 1)
origin = Origin(origin)
else: origin = None
try: args, text = line.split(' :', 1)
except ValueError:
args, text = line, ''
args = args.split()
if origin: origin.replyTo(self.nick, args)
debug("from::", origin, "|message::", args, "|text::", text)
self.rxdMsg(args, text, origin)
def rule(self, func, name, regexp=None, doc=None, cmd=None):
if isinstance(regexp, basestring):
regexp = re.compile(regexp)
if self.documentation.has_key(name):
raise "DispatchError", "Function %s already added" % name
doc = doc or func.__doc__
if doc and doc.strip():
self.documentation[name] = doc
self.dispatch.append((cmd or 'PRIVMSG', regexp, func))
def bind(self, func, cmd, regexp):
self.dispatch.append((cmd, re.compile(regexp), func))
def rxdMsg(self, args, text, origin):
if args[0] == 'PING':
self.todo(['PONG', text])
for cmd, pat, thunk in self.dispatch:
if args[0] == cmd:
if pat:
m = pat.search(text)
if not m: continue
else: m = None
if protect:
try: thunk(m, origin, args, text)
except Exception, e:
try: self.msg(origin.sender, "%s: %s" % (e.__class__, e))
except: print >> sys.stderr, "%s: %s" % (e.__class__, e)
else: thunk(m, origin, args, text)
def pushMsg(self, msg):
self.msgstack = self.msgstack[-9:]
self.msgstack.append(msg)
def msg(self, dest, text):
# Flood protection
if self.msgstack.count(text) >= 50:
text = '...'
if self.msgstack.count('...') >= 20:
if text == '...': return
if len(''.join(self.msgstack[:-3])) > 200:
import time
time.sleep(2)
self.pushMsg(text)
self.todo(['PRIVMSG', dest], text)
def kick(self, dest, text):
self.todo(['KICK', dest], text)
#def join(self, chan):
# self.todo(['JOIN', chan])
def safeMsg(self, channel, lines):
import time
for line in lines:
if line: self.msg(channel, line)
time.sleep(1)
if len(line) > 50: time.sleep(0.7)
def notice(self, dest, text):
self.todo(['NOTICE', dest], text)
def debug(*args):
sys.stderr.write("DEBUG: ")
for a in args:
sys.stderr.write(str(a))
sys.stderr.write("\n")
def doubleFork():
# http://swhack.com/logs/2004-05-12#T10-20-11
# http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/66012
try:
pid = os.fork()
if pid > 0: sys.exit(0)
except OSError, e:
print >> sys.stderr, "fork #1 failed: %d (%s)" % (e.errno, e.strerror)
sys.exit(1)
os.chdir("/")
os.setsid()
os.umask(0)
try:
pid = os.fork()
if pid > 0:
print "Daemon PID %d" % pid
sys.exit(0)
except OSError, e:
print >> sys.stderr, "fork #2 failed: %d (%s)" % (e.errno, e.strerror)
sys.exit(1)
def test(host, port, channels):
bot = Bot(nick='Ted', channels=channels)
def hi(m, origin, args, text, bot=bot):
bot.msg(origin.sender, "hi %s" % origin.nick)
bot.rule(hi, 'hi', r'hi %s' % bot.nick)
def trout(m, origin, args, text, bot=bot):
bot.kick(origin.sender, origin.nick)
bot.rule(trout, 'trout', p)
def action(m,origin,args,text,bot=bot):
cmd = text.split()
chan = cmd[1]
cmd[0] = ""
cmd[1] = ""
cmd.remove("")
cmd = " ".join(cmd)
bot.msg(chan,"ACTION "+cmd+"")
bot.rule(action,'action',r'!action')
# def up(m,origin,args,text,bot=bot):
# bot.todo(['OPER',"OperName Operpass"])
# bot.rule(up,'up',r'up')
def kill(m,origin,args,text,bot=bot):
cmd = text.split()
cmd = "%s killed_you_dead" % cmd[1]
bot.todo(['KILL',cmd])
bot.rule(kill,'kill',r'!!!kill')
def ip(m, origin, args, text, bot=bot):
bot.msg(origin.sender, "Getting IP informantion")
cmd = text.split()
cmd = "nslookup %s" % cmd[1]
result = commands.getoutput(cmd)
print cmd
fixed = result.splitlines()
found = 0
for i in fixed:
if (i.find(r"Address:") != -1 and i.find(r"#") == -1):
bot.msg(origin.sender, i)
found = 1;
if found <> 1:
bot.msg(origin.sender, "Not Found")
bot.rule(ip, 'ip', r'!ip')
def whois(m, origin, args, text, bot=bot):
bot.msg(origin.sender, "Getting WhoIs informantion")
cmd = text.split()
cmd = "whois %s" % cmd[1]
result = commands.getoutput(cmd)
print cmd
fixed = result.splitlines()
found = 0
for i in fixed:
if i.find(r"Name Server:") != -1:
bot.msg(origin.sender, i)
found = 1;
if found <> 1:
bot.msg(origin.sender, "Not Found")
bot.rule(whois, 'whois', r'!whois')
# def access(m, origin, args, text, bot=bot):
# PACL = open(proxyacl,"r")
# text = PACL.readlines()
# PACL.close()
# for i in range(len(text)):
# bot.msg(origin.nick,text[i])
# bot.rule(access, 'access', r'!access')
# def terminate(m, origin, args, text, bot=bot):
# bot.msg(origin.nick,"terminating!")
# text = text.lower()
# cmd = text.split()
# if (len(cmd) == 2):
# PACL = open(proxyacl,"r")
# text = PACL.readlines()
# PACL.close()
# print text
# remove = cmd[1]
# print "Terminating %s" % cmd[1]
# removed = -1
# for i in range(len(text)):
# l = text[i]
# if (l.find(str(remove)) <> -1):
# removed = i
# if (l.find(str(remove)) <> -1):
# break
# print remove
# if (removed <> -1):
# del text[removed]
# print "\n\n\n\n\n\n\n\n"
# print text
# PACL = open(proxyacl,"w")
# for i in range(len(text)):
# PACL.write(text[i])
# PACL.close()
# bot.msg(origin.sender,"You have terminated " + cmd[1])
# bot.rule(terminate, 'terminate', r'!terminate')
## def proxy(m, origin, args, text, bot=bot):
## text = text.lower()
## cmd = text.split()
## if (len(cmd) == 3):
## errTest = cmd[2]
## errName = cmd[1]
## err = 0
## if (errName.count("#") <> 0):
## bot.msg(origin.sender,"INVALID NAME TRY AGAIN")
## err = 1
## if (errTest.count("#") <> 0):
## bot.msg(origin.sender,"INVALID IP TRY IT AGAIN")
## err = 1
## if (errTest.find("169.254") <> -1):
## bot.msg(origin.sender,"INVALID IP GO BACK AND TRY AGAIN ")
## if (errTest.find("169.254") <> -1):
## err = 1
## if (errTest.find("192.168") <>-1):
## bot.msg(origin.sender,"INVALID IP GO BACK AND TRY AGAIN")
## if (errTest.find("192.168") <>-1):
## err = 1
## if (errTest.count(".") <> 3):
## bot.msg(origin.sender,"INVALID IP GO BACK AND TRY AGAIN")
## if (errTest.count(".") <> 3):
## err = 1
## if (err <> 1):
## PACL = open(proxyacl,"r")
## text = PACL.readlines()
## PACL.close()
## checked = 1
## for i in range(len(text)):
## l = text[i]
## print "IP::::" + errTest
## print "LINE::"+l
## if (str(l.find(str(errTest))) <> '-1'):
## checked = 0
##
## if (checked == 1):
## PACL = open(proxyacl,"r")
## text = PACL.readlines()
## PACL.close()
## print text
## remove = cmd[1]
## print "you are looking for"
## removed = -1
## for i in range(len(text)):
## l = text[i]
## if (l.find(str(remove)) <> -1):
## removed = i
## if (l.find(str(remove)) <> -1):
## break
## print remove
## if (removed <> -1):
## del text[removed]
## print "\n\n\n\n\n\n\n\n"
## print text
## PACL = open(proxyacl,"w")
## for i in range(len(text)):
## PACL.write(text[i])
## PACL.close()
## cmd = "allow from %s #%s" % (cmd[2],cmd[1])
## bot.msg(origin.sender, cmd)
## PACL = open(proxyacl,"a")
## PACL.writelines(cmd+"\n")
## PACL.close()
## bot.msg(origin.sender,"your ip has been added, if the proxy does not work for you check your ip and try again.")
## else:
## bot.msg(origin.sender,"your IP is already in this list")
## else:
## bot.msg(origin.sender,"Your command was not formatted correctly the correct format is '!proxy <name> <ipaddress>' please try again")
## result = commands.getoutput("/usr/local/proxy/bin/apachectl stop")
## print result
## result = commands.getoutput("/usr/local/proxy/bin/apachectl start")
## print result
## bot.rule(proxy, 'proxy', r'!proxy')
## def hmm(m, origin, (cmd, chan), text, bot=bot):
## """.test - Do some crazy test thing."""
## raise Exception, "blargh"
## bot.msg(origin.sender, 'Test')
## bot.rule(hmm, 'test', r'^\.test$')
bot.run(host, port)
if __name__=='__main__':
test('SERVERIP', PORTNUMBER, ['#CHANNEL'])
Posted in General, Software | Comments (1)