Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

Khaos

Algorithms that would make your mother proud

This topic is 5195 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

    I propose a thread that contains a round-table discussion of common algorithms and data structures, their implementation, and their performance. The idea is quite simple, and only contains one caveat: any code you post should be in C#, unless it is pseudocode. The reason being, C# is clean and pretty looking, and in general, would be easily understood in most cases. Not only that, but C++ and plain-old C have many books and papers and websites devoted to this topic. C# being new, has less documentation in this regard. Basically, it would be nice to provide code in a language that has fewer examples to choose from. I, and I am sure many others, have looked far and wide for algorithms in C# and don''t find a whole lot of great examples. Anyways, that''s not the point...     The point is that it would be nice to have everyone contribute code to build a simple linked list, or a binary search tree, or a string tokenizer, or something of the like (random tricks and neat tips, optimizations... all welcome). We could then, if necessary, comment and improve on each other''s work. Uninformed folk will learn a great deal, and mastery folk might learn a few new tricks as well.     Basically, let''s create a tutorial thread containing common algorithms and data structures in C#, to help people learn, and to help people improve.     I thank anyone who can contribute. I''m sure many will appreciate it. I will start... this is a string reverse function I made. I am quite aware I could call the string.Reverse() method, but that would be lame, and I would have learned nothing from doing it. Please, feel free to comment. Add something interesting of your own as well.
public static char[] RevStr(string x)
	{
		int xPerm = x.Length;
		int xSize = xPerm;
		char[] x_copy = new char[xSize];
		int idx = 0;
		
		while(idx < xPerm)
		{
			--xSize;
			x_copy[idx] = x[xSize];
			++idx;
		}
		
		return x_copy;
	}

Share this post


Link to post
Share on other sites
Advertisement
I''ll be the first rule breaker, my code is in Scheme (mainly because it was easier than in C#, and it wouldn''t have made my mommy proud).

I wrote two functions. The first one is called filter. It takes two parameters: a predicate and a list. The function returns a new list containing every element of the original list which met the predicate. The second function removes all duplicates items in a list (keeping the original order).

Both functions are written in a purely functional way. They have not been optimised to use tail-recursion for example, so don''t use that in production code (though I doubt there''s much Scheme "production" code nowadays )


(define (filter pred lst)
(if (null? lst)
()
(if (pred (car lst))
(cons (car lst) (filter pred (cdr lst)))
(filter pred (cdr lst)))))

(define (uniq lst)
(if (null? lst)
()
(if (member (car lst) (cdr lst))
(cons (car lst) (uniq (filter (lambda (e) (not (equal? e (car lst)))) (cdr lst))))
(cons (car lst) (uniq (cdr lst))))))

Share this post


Link to post
Share on other sites
Guest Anonymous Poster

char *reverse(const char *s)
{
char *sp = 0;
if (s) {
size_t l = ::strlen(s);
char c;
sp = new char[l+1];
sp += l;
*sp = ''\0'';
while (c = *s++) *(--sp) = c;
}
return sp;
}


So I don''t know C#. Sue me. If anyone knows how to do this without the variable c, post the solution. I couldn''t get rid of it because the null winds up on the other side of the string if you simply do *(--sp) = *s++. I suppose I could make an extra byte in front of the reversed string and write nulls on both ends of the string, but that''s tacky.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Here''s an alternate version filter that''s tail-recursive.


(define (filter pred lst k)
(if (null? lst)
(k ())
(if (pred (car lst))
(filter pred (cdr lst) (lambda (c) (k (cons (car lst) c))))
(filter pred (cdr lst) k))))

Share this post


Link to post
Share on other sites
quote:
Original post by Khaos
The reason being, C# is clean and pretty looking, and in general, would be easily understood in most cases.


Share this post


Link to post
Share on other sites
Way to ruin a good thing by limitting it to a Microsoft language that actually in reality isn't that clean and doesn't look that good.

EDIT: I'll post some assembly language (x86, intel style) or some Lisp later.

[edited by - Puzzler183 on May 31, 2004 9:23:38 AM]

Share this post


Link to post
Share on other sites
This doesn''t have to start a flame war, that''s simply ridiculous. The point was, C++ and C and every other language like that has dozens of websites and books on algorithm implementation and such. C#, does not . Thus, it would be nice if you could post in C#, since most examples could be easily converted to C++, or possibly to C. However, C and C++ often use lots of pointers, and I wanted to avoid that if possible. If you don''t like C#, I''m sorry, I certainly don''t want to stand in the way of progress.

Anyways, keep it going if you can. In any language that suits your fancy if it needs to be that way.

Share this post


Link to post
Share on other sites
quote:
Original post by Puzzler183
[...]limitting it to a Microsoft language[...]


It may have been invented by Microsoft, but it was standardized by the ISO, just like C++ or C was. And therefore, it is an open language for people like the Mono Foundation to freely recreate. C# is no longer limited to Microsoft platforms, so that statement is unnecessarily harmful.

I appreciate people posting in any language (even in Scheme, I found that interesting), but the point of the thread was to be a reference to basic algorithm and data structures. I don't think many novice programmers are going to rush over to a Common Lisp implementation of a binary search tree. However, if they saw C# code, I think they might understand it to an extent, if not only to port it to another language. I'm sure you can understand what I mean, lest we turn this into a stupid discussion of meaningless terms.

C# is first choice.
...Java too.
C++ or C with minimal pointers/memory management issues.
BASIC type language.
Pseudocode of sorts.
Lisp-ish languages.
Cobol and FORTRAN.
Piet.
D.

Edit: Added Java...

[edited by - khaos on May 31, 2004 9:56:50 AM]

Share this post


Link to post
Share on other sites
I''m using pseudocode... much easier than anything else...

Breadth-first search in a graph : finding if there is a path from a to b.



procedure BFS( a : node, b : node )

s : node queue (FIFO)
v : node list

push a onto s
while s is not empty do
pop n from s
if n = b then return true
for all children c of n do
if c is not in v then
add c to v
push c onto s
return false


And why not a classic? Insertion sort :


procedure ISORT( a : array of size N )

if N <= 1 then do nothing
ISORT( a[2..N] )
t <-- a[1]
for i = 1 to N-1 do
if t > a[i+1] then
a[i] <-- a[i+1]
a[i+1] <-- t


There you go...

Share this post


Link to post
Share on other sites

This topic is 5195 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Guest
This topic is now closed to further replies.

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!