 sj |
||
|
||
Tech: Data Structures/Computer Science
|
|
|
Subject: BS: Data Structures/Computer Science From: GUEST,Jon Date: 14 Jan 04 - 06:40 PM This started as a Tech thread about running Harmony under Linux but has drifted quite a way into the realms of computer science... The thread is here. I'll pick up from where I think it will make sense and see what happens from there: Subject: RE: Tech: Windows programs under WINE on Linux? From: GUEST,Jon Date: 13 Jan 04 - 08:20 PM OK now this thread has drifted so far, time for me to ask for a computer lesson. Mark Clark said "Designing good data structures is the key to any successful program". I can see that in some ways, eg. at folkinfo and the Annexe, my databases are by far the most important things to me - I mean weaknesses there can only lead to problems elsewhere - the sites can only ever be as good as the underlying data structure allows. (it's one bit even a hacker like me did plan on pen and paper using ERDs - not saying I get anything as best as it could be or "right" but I do try). Where I wonder is how would data structures apply to say a user interactive game. Jon -------------------------------------------------------------------------------- Post - Top - Forum Home - Printer Friendly - Translate -------------------------------------------------------------------------------- Subject: RE: Tech: Windows programs under WINE on Linux? From: GUEST,pavane Date: 14 Jan 04 - 02:55 AM Funny thing, I am currently working on 'interactive gaming' (Lotto online). JSP is a data-driven program design method, (as distinct from Yourden, which is process-driven) and one cornerstone is that EVERY program has at least one serial data stream, whether a file or a conversation. The interaction of a user with a game is one such serial data stream. This can be demonstrated by programs which can capture the sequence of keypresses, mouse clicks etc, to a file and play them back to the program. What Michael Jackson (No, NOT that one) didn't say is that the structure of one data stream can be validly represented in many different ways, depending on the use you want to make of it! PS does anyone have the article which describes how to shoot yourself in the foot in a variety of different programming languages? -------------------------------------------------------------------------------- Post - Top - Forum Home - Printer Friendly - Translate -------------------------------------------------------------------------------- Subject: RE: Tech: Windows programs under WINE on Linux? From: GUEST Date: 14 Jan 04 - 06:25 AM I don't know about "a variety of of different" languages, but Bjarne Stroustrup (who invented C++) is alleged to have said words to the effect of: "in C++ you're less likely to shoot yourself in the foot than in C, but if you do you're more likely to blow your whole leg off". Anahata -------------------------------------------------------------------------------- Post - Top - Forum Home - Printer Friendly - Translate -------------------------------------------------------------------------------- Subject: RE: Tech: Windows programs under WINE on Linux? From: Mark Clark Date: 14 Jan 04 - 03:51 PM I responded to Jon in a PM at Folkinfo. Mudcat was down I wasn't convinced there is large Mudcat audience for computer science. - Mark -------------------------------------------------------------------------------- Post - Top - Forum Home - Printer Friendly - Translate -------------------------------------------------------------------------------- Subject: RE: Tech: Windows programs under WINE on Linux? From: Ed. Date: 14 Jan 04 - 04:10 PM Not a large Mudcat audience for sure, Mark. I, for one, would however have been interested to read your reply to Jon's question on data structures. Maybe you could post it here, or PM me either here or at folkinfo? Thanks Ed -------------------------------------------------------------------------------- Post - Top - Forum Home - Printer Friendly - Translate -------------------------------------------------------------------------------- Subject: RE: Tech: Windows programs under WINE on Linux? From: Foolestroupe Date: 14 Jan 04 - 06:26 PM The audience may not be very large, but is enthusistic and extremely grateful to be included in the process. Just like audiences for Folk Music. I too would appreciate the info. :-) Robin |
|
Subject: RE: BS: Data Structures/Computer Science From: Mark Clark Date: 14 Jan 04 - 06:46 PM This was my PM to Jon Hi, Jon, - Mark |
|
Subject: RE: BS: Data Structures/Computer Science From: The Fooles Troupe Date: 14 Jan 04 - 06:55 PM I save my ISP usage pages to HD with filenames that include YYYYMMDD info - auto sorts itself in date order! :-) Robin |
|
Subject: RE: BS: Data Structures/Computer Science From: Amos Date: 14 Jan 04 - 06:59 PM Good description, Mark. More and more systems are becoming data-driven, because it is more elegant. The logic gets leaner and the code gets lighter if the data structuring is well done. And it is easier to change things in code as a result, and quicker to tell whether a bug is in data or in programming. As far as I am concerned you can post as much geekery as you want on the Cat as long as you label it Tech. eh?? A |
|
Subject: RE: BS: Data Structures/Computer Science From: The Fooles Troupe Date: 14 Jan 04 - 07:10 PM Jon, since you started this thread, could you please ask Joe to change this thread to a "Tech:" prefix? Robin
We expect to have high-level discussions on both the music and non-music sides of the Forum. -Joe Offer- |
|
Subject: RE: BS: Data Structures/Computer Science From: GUEST,Jon Date: 14 Jan 04 - 07:15 PM I'll put a request in help forum that the prefix/section might be reviewed. |
|
Subject: RE: BS: Data Structures/Computer Science From: GUEST,Jon Date: 14 Jan 04 - 08:49 PM OK have done that. Will wait and see what happens. On the computer level, I find categorising interesting. I certainly do believe in methods of sorting threads, forums, prefix - call them what you like but computers seem to need rules. What I mean there is this thread could perhaps be BS to one person, (within this structure) Tech in the top (as maybe a problem with a browser would be to another), etc. I wonder how a computer could cater for each individual's thoughts, and in some cases I can see no way of defining a right or wrong in rigid terms... Onto Mark's link: The maths and ideas are well above my head but I can get a general drift of how things can be structured to suit the task in hand and that data structures do come into more areas than I'd realised. Back to more basics and areas I do play with... I find the yyddmm type choices and efficiency as outlined be Mark quite interesting and I guess the more you know, the more options you can think of making the idea of settling on one harder.... The Annexe was my base code for both sites and before planning my changes, I had taken someone elses code and db (aspdev.com). Rightly or wrongly I made 2 very fundamental changes to the data structure and storage. The first was that the original code held the post exactly as given and added the things like changing the carriage returns to html line breaks when interpreting the post for display. I can't always return to the original and of course more characters get stored my way but my (right or wrong) judgment was to store as HTML, arguing a post occurs once but a page may be viewed many times. The second was that whatever terms we use, we have a topic and posts to that topic. The original design "argued" that the first post to the topic belonged in the topic table. This is great in that creating a topic is a one step process. The drawback seems to me to be that you need 2 SQL queries per thread and repeat much just to put the thread in a format familiar here. I adopted the "MC" approach where the contents of the first post are part of the post table. The only real differences there is I don't carry a "subject" for each post and make what is in fact a 2 step process (any one who creates a thread here will know that) invisibly into a 1 step process - the creation of the needed "topic" to group threads together and the creation of the first post are both done in the same script. I see many cases where there is no right or wrong but find the different ideas and, witihin my limited understanding, ways people can implement the same things in so many different ways fascinating. Jon |
|
Subject: RE: Tech: Data Structures/Computer Science From: Mark Clark Date: 15 Jan 04 - 02:15 PM Here is a link to a page maintained by the US National Institute of Standards and Technology (NIST) providing a comprehensive Dictionary of Algorithms and Data Structures. The dictionary gives the reader a general description of the structure or algorithm along with links to variants of it and often links to papers and tutorials outside of NIST where the concepts are presented in detail. These are the fundamental building blocks of software and are well worth studying and using.
If you've come to programming through OJT or perhaps just bravely jumping in to the process and messing about, you should really take a "201" level course at university. Unless you're going for a CS degree, don't waste time with the "101" survey classes but take the basic course on data structures and algorithms. There is a strong demonstrated affinity between musical ability and programming aptitude so don't feel cowed by academia. It's just that many of these basic concepts aren't necessarily self evident. Once someone takes you through basic data structures and algorthims, you'll be off and running.
The choice of programming languages can also affect the success of a program. Sometimes this choice merely determines the portability of an application and the number of potential users but often it also affects the performance, usability and maintainability as well. For a trivial example of this, consider a program to calculate n factorial (i.e., n*n-1 … n-l while n-l < 0). This function is described mathematically as n!=n·(n-1)!. This mathematical definition is self defining or recursive; one doesn't even need to know that that ! is the factorial operator to understand the meaning of this elegant definition. In the C programming language, that function may be written as:
- Mark |
|
Subject: RE: Tech: Data Structures/Computer Science From: GUEST,Jon Date: 15 Jan 04 - 03:37 PM Great link! Thinking of Algorithms, at times I have toyed with buying Knuth's "Art of Computer Programming, Volume 1: Fundamental Algorithms". It's quite expensive though and I'm not sure how much I, who is more of a dabbler who would like to learn a little more than someone with thoughts on becoming a serious commercial programmer, would get out of it. Has anyone got any opinions on this book or perhaps suggest alternatives that may be more suitable for me? Jon |
|
Subject: RE: Tech: Data Structures/Computer Science From: The Fooles Troupe Date: 16 Jan 04 - 02:36 AM It's worth reading - try getting it froma library, or just wander into a University Comp-Sci library with a couple of hours - there should usually be a "Reference only" copy (can't be taken out) on the shelf. The "Dragon Book" - (my copy is packed in the shed!) is worth reading, as well as the "Mythical Man Month" - both editions... Robin |
|
Subject: RE: Tech: Data Structures/Computer Science From: DMcG Date: 16 Jan 04 - 03:31 AM Knuth's "Art of Computer Programming, Volume 1: Fundamental Algorithms". ... Has anyone got any opinions on this book? This is one of the few books from college days (three decades ago, now) that I still refer to occasionally. The algorithms are provided in a pseudo-machine code and are not structured in the modern fashion, making it quite difficult to use directly. However, with a little effort they can usually be converted into a more appropriate form and the book gives excellent coverage of the issues involved. One section I've used many times because I can never remember it precisely is how to do garbage collection without needing additional memory (on the grounds the only reason you are doing garbage collection is that you are already short of memory.) Jon: PM me if you would like to borrow it for a few weeks to see how you get on. |
|
Subject: RE: Tech: Data Structures/Computer Science From: GUEST,Jon Date: 16 Jan 04 - 04:25 AM Thanks both for the info. Dave (posting this here in case others wonder the same), do you think there is enough in it for someone who hasn't the slightest clue about assembler or machine code? My own limits are (within reason - I couldn't make sense of anything complicated) reading things like Pascal and C like languages or a "pseudo-representation" of them. Jon |
|
Subject: RE: Tech: Data Structures/Computer Science From: Grab Date: 16 Jan 04 - 09:32 AM These days, "data structures" have evolved into "objects" or "classes". The idea is that not only do they store the data, they also ensure that the data stored is consistent, and provide functions to do useful stuff with that data. The classic CS example is a class which implements complex numbers, such that you can do normal operations like add, subtract, etc with these objects, and also other related stuff like getting rectangular/polar representation. How to do a game. Well, it really depends on the game. If you think in terms of a 3-D game, there would probably be a lowest-level class which took a triangle and displayed it on the screen. There would be a function to set the three corner points (most likely in the XYZ domain) and another function to set the colour. Each person in the game would be another class. The sprite for the person would be drawn from many triangles, so each would store a zillion instances of the triangle class, each instance with its own values for position and colour. The person would move around, so their location changes. The person class would therefore have a single XYZ value for location, and when this is changed, the person class would tweak the XYZ location values for the zillion triangles used to draw the sprite. So the higher level of the game only needs to pass a single XYZ position to the person class. The person class and the triangle class will then take care of putting this sprite in the right place on the screen, without the rest of the game needing to get involved. Obviously this is a very simplistic example, but you get the idea. You try to make each class self-sufficient, so that the levels above it can just use it without worrying about the detail. This minimises the interactions needed between classes, in exactly the same way as you try to minimise linkage around databases. Graham. |
|
Subject: RE: Tech: Data Structures/Computer Science From: Mark Clark Date: 16 Jan 04 - 01:51 PM Graham is exactly right, the study of data structures has largely moved on to objects. This discussion began talking about tools like Visual Basic and COBOL so I figured most people weren't familiar with objects and object-oriented programming (OOP). I was trying to keep things simple. Let's define what we mean when we say object. The term object refers to data structures and the functions or algorithms that normally operate on those structures encapsulated in a closed module with a rigorously defined interface so that the data structures may not be directly accessed from outside the object but must be manipulated using the object interface.Other definitions of object have been promoted by vendors who want their products to seem to be object-oriented in their literature but in fact are not object-oriented at all. The use of objects in a design can reduce the complexity of programs and make maintenance easier because, if the object interface remains unchanged, the scope of change is limited to the object itself. Still, the data within an object is still organized according to the classical concepts of data structures. Knuth is brilliant and I'd highly recommend his books. He proposes an average but mythical computer he calls MIX and an assembly language for it called MIXAL. All code examples and proglems are expressed in MIXAL. You can download a MIXAL intrepreter that runs on Windows if you'd like to play with the examples and problems. My own view is that programmers are vastly more capable if they have a good grasp of what actually happens inside a computer when their programs are running. The example I cited in the predecessor thread about replacing a 600 line COBOL program with 50 lines of assembler was possible because 32 is 2 raised to the 5th power and, in machine code, this only represents a simple register shift, one of the fastest operations any computer can perform. That knowledge coupled with a couple of small lookup tables keyed on the desired collating sequence and I was done. The original COBOL programmer who lacked knowledge of how the machine actually worked was doomed to write 600 lines of spaghetti code and use many hours of machine time in the process. So, by all means, borrow a copy of Knuth and spend some time with it. Knuth has a grand sense of humor if you're paying attention. My copy is from the second printing (1969) so page numbers may have changed but in the index you'll find the reference “MUG: MIX User's Group, 627.” This is aparantly a reference to a ligitimate organization until you notice that the index entry itself is on page 627 and there is no other reference. That's the sort of attitude and detail you don't often find in works of this sort. Jon, Perhaps more immediately accessible is a book—now long out of print I suspect—published by Prentice-Hall in 1981 called Data Structures Using Pascal by Aaron M. Tenenbaum and Mosch J. Augenstein. This might be found on the used book market but if not, and if you think it would be useful, I'd be willing to send you my copy. If you want to find out what objects and OOP are about, the first thing you need to do is download one of the free Smaltalk systems and become thoroughly comfortable with objects in a pure object-oriented environment. Objects is really an entirely different way of thinking. If someone tells you it's not, they haven't understood objects or worked with OOP tools. You may not wind up writing a lot of applications in Smalltalk but the grounding it will give you in objects will prepare you to be productive in Java, C++ or any of the OO languages. You can start at Smalltalk.Org™ or do a Google search for "smalltalk" and you should find everything you need. The Dragon Book that Robin refers to is really called Compilers - Principles, Techniques And Tools. It's a great book but is really for someone wanting to learn how to build a compiler program that translates a high-order language such as C into executable machine instructions. - Mark |
|
Subject: RE: Tech: Data Structures/Computer Science From: The Fooles Troupe Date: 16 Jan 04 - 06:16 PM Thanks, mark, it's been some years since I looked at the book, and I seem to be getting more disynomic in my dotage... :-) While I agree with you about its content, the result of having read it is that one acquires a way of looking at analysis that is transferrable to other projects, not all of them writing code... :-) Thanks for the links. Robin |
|
Subject: RE: Tech: Data Structures/Computer Science From: GUEST,Jon Date: 16 Jan 04 - 08:08 PM Thanks again for info. I think in view of what I've read here and recieved via PM, the best plan for me is to take some time in learning at least the basics of assembler before moving on. Even if I ended up using another book for the algorithms, I'm sure a little experience in assembler won't be wasted. OOP: I did discover that with Turbo Pascal. I had an excellent book (quite possibly a McGraw/Hill publication - I've lost it) on using TP. Although the first couple of chapters were on the use of TP itself, it then went on starting with basics like data types, moving on to concepts like functions, then recursion, the use of pointers and linked lists, ending with a gentle inroduction to the concepts of OOP. Outside knowing of a formal design method, I learned far more from this book than I did in the course I took where Pascal was used. Here is yet another question for the professional developers: Once in a while even I've been asked about where to start with programming. It's been my opinion that one is better off downloading TP (Borland have or had a free copy in thier archives) and going through the process of learning with a language that is very strict and pretty well forces some "good habits" as well as encorages some structure before moving onto something like VB or Delphi where much can be a couple of lines of code attached to a button. I'd be interested to learn the opinions of those with far more experience than I have. Jon |
|
Subject: RE: Tech: Data Structures/Computer Science From: Mark Clark Date: 16 Jan 04 - 10:24 PM Many well known computer scientists have opined that the most important language to learn first is Lisp. It isn't that you'll wind up writing a lot of Lisp programs but learning Lisp and writing a few successful programs using it will teach one how to correctly structure a program and how to think about algorthims. Learning Lisp has another major advantage. The most powerful most extensible editor available at any price is GNU Emacs and since Emacs is written in Lisp, you use Lisp to extend and customize the editor. You can add menu choices to use any compiler tools you choose and create major modes that recognize any file type and set up indentation, color coding, and helper keys any way you want them. Emacs works differently than other editors you may be accustomed to using but it's worth taking the time to learn. You'll become more productive with it. Emacs can be the only environment you use. It can read your email and newsgroups, format your documents with major modes for HTML, XML, LaTeX and countless other document types. Emacs is also available for most computing environments so you don't have to learn a new editor when moving between systems. After Lisp, I'd say the next thing to master is C using the little Kernighan & Ritchie book. Then there is a small reference book by Harbison (sp?) and Steele that is excellent if still available. After those two languages, you'll find it easy to pick up any language you find interesting, and there are many. Perl, PHP and Python are getting a lot of use right now. Eventually, you'll benefit from a formal design methodology. The best of the old methologies have now merged into the Unified Modeling Language (UML). There is a free open source tool called ArgoUML that already handles many of the key diagrams, generates code and even includes some round trip engineering. Another great free tool is NetBeans an integrated Java development environemt that is already being used for some commercial applications. All these recommendations will take a lot of time but the journey will be great fun and you'll be well rewarded. - Mark |
|
Subject: RE: Tech: Data Structures/Computer Science From: The Fooles Troupe Date: 17 Jan 04 - 08:02 PM Yeah man, I struggled with TECO on the old KL10... grab chunks, stuff them into buffers, invert or reverse the buffers etc, wonderful stuff, in some ways not unlike FORTH... Robin |
|
Subject: RE: Tech: Data Structures/Computer Science From: Mark Clark Date: 18 Jan 04 - 02:21 AM I've never had to use TECO but Richard Stallman's Emacs editor was originally written in TECO. TECO code often looked a lot like the old APL code; long strings of strange incomprehensible characters. Oh, and I forgot to answer my earlier question about FORTH. Moore called it FORTH instead of FOURTH because he developed it on an IBM 1130 minicomputer that only supported five character names. So even though it was his FOURTH generation brainchild, he had to call it FORTH. - Mark |
|
Subject: RE: Tech: Data Structures/Computer Science From: GUEST,Jon Date: 18 Jan 04 - 02:53 AM I've just had a look at Lisp. It's quite unlike anything I've ever seen before! I see I can get a free download of Allegro CL 6.2. When I am able (some point this week) to do a 20+Mb download on my 28.8K connection, I'll have a play with it. I may also have another look at Emacs. I din't really understand it last time I looked at it... I had mentioned Turbo Pascal above and have checked. This is still available for free download at < a "href=http://community.borland.com/article/0,1410,20803,00.html">http://community.borland.com/article/0,1410,20803,00.html. Jon |
|
Subject: RE: Tech: Data Structures/Computer Science From: DMcG Date: 18 Jan 04 - 04:02 AM I've just had a look at Lisp. It's quite unlike anything I've ever seen before! Yep, that sounds like LISP. If you want 'languages unlike one you've seen before' I would also suggest APL and SNOBOL. SNOBOL is tricky because it does look, at first, like ones you have seen before, but look at the way branching works ... |
|
Subject: RE: Tech: Data Structures/Computer Science From: Mark Clark Date: 18 Jan 04 - 03:35 PM For some reason, not practical for sure, my 1968 edition of The SNOBOL4 Programming Language by Griswold, Poage & Polonsky is still sitting on my bookshelf. I confess I haven't used SNOBOL for anything since school. As I recall we wrote an assembler program in SNOBOL and had to correctly assemble and run a program the instructor had written. Jon, You might want to consider GNU Common Lisp as well. GNU CLisp will run on most platforms including Windows and Linux so you'll have the same system in each environment. Also, it doesn't expire in 60 days. There is a nice music typesetting system, CMN - Common Music Notation that will run on either CLisp or Allegro CL 6.2 (ACL). - Mark |
|
Subject: RE: Tech: Data Structures/Computer Science From: Fibula Mattock Date: 19 Jan 04 - 03:54 AM Yay! Emacs promoted on Mudcat. I never thought I'd see the day. Next we'll have the fullscale emacs/vi wars. (BTW, I use emacs for everything, but could never be arsed to learn Lisp.) ....Must...resist....geekiness.....! |
|
Subject: RE: Tech: Data Structures/Computer Science From: Amos Date: 19 Jan 04 - 09:45 AM Emacs comes out head and shoulders ahead over vi. How can there be any question? :>) (Just funnin', guys....) A |
|
Subject: RE: Tech: Data Structures/Computer Science From: Mark Clark Date: 19 Jan 04 - 04:42 PM I actually use vi quite a lot under Cygwin. I use it for editing small text files like configuration files, profiles, shell scripts and the like. I even occasionally use sed when I have several regular expression edits to perform. But GNU Emacs offers a compiled version for Windows so Emacs is my editor under XP as well. All my ABC coding is done in Emacs because there is a good major mode for ABC+.- Mark |
|
Subject: RE: Tech: Data Structures/Computer Science From: Fibula Mattock Date: 19 Jan 04 - 05:45 PM Windows? WINDOWS? Call yerself a *real* geek? ;) |
|
Subject: RE: Tech: Data Structures/Computer Science From: The Fooles Troupe Date: 19 Jan 04 - 06:21 PM Well, back to real geekines... Compilers - Principles, Techniques And Tools, teaches one how to look at input driven "black box" programming. When a task is just about taking input, and reacting a in a predetermined fashion to each input... come to think of it, that's what I thought all real programming as was about, not just concentrating on doing fancy twiddles in some arcane data structure called a registry... Come to think of it, just what other sort of computer programming IS there other than "Input Driven 'black box' programming"? :-) Robin |
|
Subject: RE: Tech: Data Structures/Computer Science From: Amos Date: 19 Jan 04 - 09:24 PM Well there is always "processing based on input:" no matter what architecture you're using but that doesn't tell you a lot. For example, there is massively parallel programming which distributes processing issues over a large number of processors. There's real-time programming which has to live up to rigorous mission-critical or even life-or-death standards of reliability. There's a huge array of different architectures and OSes and target platforms all of which depend on why you're doing the programming. A |
| Share Thread: |
