After thinking about the "philosophy" question it occured to me that here is an ideal problem which will illustrate the Lisp way of doing things.
You are input a list made up exclusively of structs ( or classes, your choice ) of type foo. foo contains at least five members, strings of length 20. Because of this, copying of foos should be kept to a minimum.
The list will contain at least 10,000 elements and at most 1,000,000 elements.
One thing that will be required is that you maintain lists of elements sorted with different members as key ( you would prefer to maintain references of the elements rather than copies for two reasons: 1) You want to be able to insert modifications to elements and have it reflect in all the lists. 2) You want to minimize used memory and so not copy anything large. 3) You want to make it fast, so try not to copy anthing large.
The operations allowed are: 1) Adding a list ( call it a key list ), this list is sorted by taking a specified member. 2) Remove a key list. 3) Find an element or elements by a specified set of members. 3) Add an element ( and update all key lists ). 4) Delete a key element ( and update all key lists ). 5) Modify a specific element.
The program needs to be a fast as possible, and it needs to use as little memory as is possible.
> After thinking about the "philosophy" question it occured to me > that here is an ideal problem which will illustrate the Lisp way of > doing things.
> You are input a list made up exclusively of > structs ( or classes, your choice ) of type foo. > foo contains at least five members, strings of length 20. > Because of this, copying of foos should be kept to a minimum.
> The list will contain at least 10,000 elements and at most 1,000,000 > elements.
> One thing that will be required is that you maintain lists of elements > sorted with different members as key ( you would prefer to maintain > references of the elements rather than copies for two reasons: > 1) You want to be able to insert modifications to elements and have it > reflect in all the lists. > 2) You want to minimize used memory and so not copy anything large. > 3) You want to make it fast, so try not to copy anthing large.
> The operations allowed are: > 1) Adding a list ( call it a key list ), this list is sorted by taking > a specified member. > 2) Remove a key list. > 3) Find an element or elements by a specified set of members. > 3) Add an element ( and update all key lists ). > 4) Delete a key element ( and update all key lists ). > 5) Modify a specific element.
> The program needs to be a fast as possible, and it needs to use as > little memory as is possible.
Maybe someone will in fact write this for you. I happen not to be that person.
I'd bet you'll do better to write the program and offer it for critique.
>olc...@interaccess.com (Thaddeus L Olczyk) writes:
>> After thinking about the "philosophy" question it occured to me >> that here is an ideal problem which will illustrate the Lisp way of >> doing things.
>> You are input a list made up exclusively of >> structs ( or classes, your choice ) of type foo. >> foo contains at least five members, strings of length 20. >> Because of this, copying of foos should be kept to a minimum.
>> The list will contain at least 10,000 elements and at most 1,000,000 >> elements.
>> One thing that will be required is that you maintain lists of elements >> sorted with different members as key ( you would prefer to maintain >> references of the elements rather than copies for two reasons: >> 1) You want to be able to insert modifications to elements and have it >> reflect in all the lists. >> 2) You want to minimize used memory and so not copy anything large. >> 3) You want to make it fast, so try not to copy anthing large.
>> The operations allowed are: >> 1) Adding a list ( call it a key list ), this list is sorted by taking >> a specified member. >> 2) Remove a key list. >> 3) Find an element or elements by a specified set of members. >> 3) Add an element ( and update all key lists ). >> 4) Delete a key element ( and update all key lists ). >> 5) Modify a specific element.
>> The program needs to be a fast as possible, and it needs to use as >> little memory as is possible.
>Maybe someone will in fact write this for you. I happen not to be that >person.
>I'd bet you'll do better to write the program and offer it for critique.
If it was C++ I could write it in about two hours, but I couldn't write it in Lisp both efficiently and stingy on memory. That's the point. This problem has all the elements that styme me. So instead of worrying about being productive, I keep worrying about how to be more efficient.
On Mon, 18 Mar 2002, Thaddeus L. Olczyk wrote: > After thinking about the "philosophy" question it occured to me > that here is an ideal problem which will illustrate the Lisp way of > doing things.
It doesn't illustrate anything about the "Lisp" way of doing things. It is a reasonable test to see if someone has a very basic understanding of data structuring, though.
> You are input a list made up exclusively of > structs ( or classes, your choice ) of type foo. > foo contains at least five members, strings of length 20. > Because of this, copying of foos should be kept to a minimum.
This is the point at which I would object to the test, because the data structure is broken by design. :)
Each foo should contain five or more keys, each of which is a reference to the relevant string in an associative container (probably a hash) somewhere.
Each foo should be identified by a key, so that each foo is stored in an associative container.
> The list will contain at least 10,000 elements and at most 1,000,000 > elements.
> One thing that will be required is that you maintain lists of elements > sorted with different members as key ( you would prefer to maintain > references of the elements rather than copies for two reasons:
...so, you are manipulating lists of keys, each of which can be turned into a foo...
> 1) You want to be able to insert modifications to elements and have it > reflect in all the lists. > 2) You want to minimize used memory and so not copy anything large. > 3) You want to make it fast, so try not to copy anthing large.
...and these are all easy to achieve. It's a simple matter of programming. Just don't forget to write the custom find/insert code for your lists. A balanced tree would probably be reasonable, so long as the rebalancing time wasn't too high for you.
[...]
> The program needs to be a fast as possible, and it needs to use as > little memory as is possible.
Build from the sane data structure I describe and, no matter what the language, you are going to manage this. Use arrays, not lists, as well, since they can be constructed with zero-byte overhead per element. :)
Daniel
-- Remember that under the skin you fondle lie the bones, waiting to reveal themselves. -- Ikkyu
> >> The program needs to be a fast as possible, and it needs to use as > >> little memory as is possible.
> >Maybe someone will in fact write this for you. I happen not to be that > >person.
> >I'd bet you'll do better to write the program and offer it for critique. > If it was C++ I could write it in about two hours, but I couldn't > write it in Lisp both efficiently and stingy on memory. That's the > point. This problem has all the elements that styme me. So instead of > worrying about being productive, I keep worrying about how to be more > efficient.
You would be better off worrying about how to be more productive, so you can spend your time working on efficient algorithms. If I understand you're not particularly well specified problem, it hardly seems a challenge, since it can be trivially implemented in practically any language efficiently.
Thaddeus L Olczyk wrote: > >I'd bet you'll do better to write the program and offer it for critique. > If it was C++ I could write it in about two hours, but I couldn't > write it in Lisp both efficiently and stingy on memory. That's the > point. This problem has all the elements that styme me. So instead of > worrying about being productive, I keep worrying about how to be more > efficient.
First, don't worry about being efficient, unless it becomes necessary.
In this case, efficiency was emphasized pretty heavily in the problem statement, so "worrying about how to be more efficient" seems to be exactly what is called for :-)
Keep in mind that C++ has been paying my bills for over a decade now. That said...
> After thinking about the "philosophy" question it occured to me > that here is an ideal problem which will illustrate the Lisp way of > doing things.
Well, the problem statement is much more in the spirit of C or C++ than Lisp, which is really going to color the implementation.
> You are input a list made up exclusively of > structs ( or classes, your choice ) of type foo.
Some implementations do better (memory wise) with one or the other. There doesn't seem to be any consistency between implementations here...
> foo contains at least five members, strings of length 20. > Because of this, copying of foos should be kept to a minimum.
Since the strings will typically be stored by reference, copying foos isn't a big deal... But I'd still avoid it if I really want to be efficient. But short-lived allocations aren't as expensive in most Lisps as they are in C.
> The list will contain at least 10,000 elements and at most 1,000,000 > elements.
m'kay. Personally I'd keep the "master list" in a vector. Usually better space efficiency than a list, and better locality.
> One thing that will be required is that you maintain lists of elements > sorted with different members as key ( you would prefer to maintain > references of the elements rather than copies for two reasons:
Again, since references are the default in Lisp, this will tend to just happen...
> 1) You want to be able to insert modifications to elements and have it > reflect in all the lists. > 2) You want to minimize used memory and so not copy anything large. > 3) You want to make it fast, so try not to copy anthing large.
Having a garbage collector *really* reduces the need to copy things, but you can't program in a functional style. Imperative style is perfectly compatible with the CL way. I tend to mix and match the two pretty freely, with some CLOS sprinkled in for spice.
> The operations allowed are: > 1) Adding a list ( call it a key list ), this list is sorted by taking > a specified member. > 2) Remove a key list. > 3) Find an element or elements by a specified set of members. > 3) Add an element ( and update all key lists ). > 4) Delete a key element ( and update all key lists ). > 5) Modify a specific element.
> The program needs to be a fast as possible, and it needs to use as > little memory as is possible.
Well, you don't mention which of these is to be preferred should they come into conflict. If I'm gonna be dealing with wads of data, I generally prefer to keep it in an array (whether I'm writing Lisp or C). Modern processors are much better at dealing with arrays than linked structures, plus linked structures tend to have poor predictability which causes pipeline stalls, and poor locality which increases cache miss rate and page-fault rate. The upshot of these considerations is that an efficient lisp implementation would likely look a lot like an efficient C implementation.
Do the "lists" really need to be lists? Can they be vectors? If so, then vectors (a) use less space than lists (b) sort quicker (c) can be binary-searched more easily (d) are more pipeline/cache/ paging-friendly. Insertion is the same big-O as linked lists, but those constant factors for a list (pipeline stalls, increased cache misses, page faults) can eat your lunch. You can leave holes in the vector when you delete, which makes deletion O(1) per list, and you can take advantage of these to help reduce insertion overhead to O(n)/#holes which is the same big-O time, but will improve locality and reduce your paging rate -- again, those constant factors can easily swamp the theoretical considerations. You can keep track of the #holes and compact when things get too sparse.
Can the "lists" be b+trees? More memory overhead, more complicated implementation, but improved insertion/deletion time over a vector implementation. How much improved depends. For C++ you could maybe use the red-black tree implementation, but that imposes a fairly high per-element memory overhead.
If they've gotta be lists, then both C++ (STL) and CL have good list implementations. And CL offers destructive versions of most of its list operations. You can use resources to reduce consing further, which *really* makes the Lisp code look like C :-)
As for the list-of-lists, I'd just make that a list. It's not likely to be enough to worry about.
* Thaddeus L Olczyk | If it was C++ I could write it in about two hours, but I couldn't write | it in Lisp both efficiently and stingy on memory. That's the point. This | problem has all the elements that styme me. So instead of worrying about | being productive, I keep worrying about how to be more efficient.
How far along your learning path are you? Please remember that efficiency is encountered very early on the C++ learning path, and very late on the Common Lisp learning path. If you think "by now, I should have learned how to be efficient", you are effectively still walking on the C++ learning path. How come that path is the correct one? Would you have worried so much about efficiency if you had not known C++ before Common Lisp?
/// -- In a fight against something, the fight has value, victory has none. In a fight for something, the fight is a loss, victory merely relief.
> If it was C++ I could write it in about two hours, but I couldn't > write it in Lisp both efficiently and stingy on memory. That's the > point. This problem has all the elements that styme me. So instead of > worrying about being productive, I keep worrying about how to be more > efficient.
I don't know if it's out of scope for this forum but maybe you could code one in C++ and we, as a group, could run through the exercise of converting portions of it to Lisp (or even the whole thing).
I don't know if it would be of interest to anyone else but I'd like to see a Lisp version take shape with all the grey matter we have in this group.
It could easily turn into a flame war though -- I can see it already.
>> If it was C++ I could write it in about two hours, but I couldn't >> write it in Lisp both efficiently and stingy on memory. That's the >> point. This problem has all the elements that styme me. So instead of >> worrying about being productive, I keep worrying about how to be more >> efficient.
> I don't know if it's out of scope for this forum but maybe you could > code one in C++ and we, as a group, could run through the exercise of > converting portions of it to Lisp (or even the whole thing).
Perhaps this is something that we newbies could undertake...?
> I don't know if it would be of interest to anyone else but I'd like to > see a Lisp version take shape with all the grey matter we have in this > group.
I know that I could benefit from getting feedback from the gurus here on coding issues...
> It could easily turn into a flame war though -- I can see it already.
Even /more/ reason to do it... :-)
-jon -- ------------------ Jon Allen Boone ipmon...@delamancha.org
> Perhaps this is something that we newbies could undertake...?
Great idea. And if the OP does not come through, maybe the newbies could first do it in their preferred language (if they are not total programming newbies) and share those.
Keep track of the time required as well.
I'm no newbie, but I learn a lot when the real heavyweights start slinging code.
> > It could easily turn into a flame war though -- I can see it already.
Oh, as long you use IF* I do not think there will be any trouble.
--
kenny tilton clinisys, inc --------------------------------------------------------------- "Well, I've wrestled with reality for thirty-five years, Doctor, and I'm happy to state I finally won out over it." Elwood P. Dowd
On Mon, 18 Mar 2002 08:07:00 -0500, Thaddeus L Olczyk wrote: > After thinking about the "philosophy" question it occured to me that > here is an ideal problem which will illustrate the Lisp way of doing > things. [...] > The operations allowed are:
[...] Nope, you've already violated "the Lisp way of doing things".
> On Mon, 18 Mar 2002, Thaddeus L. Olczyk wrote: > > After thinking about the "philosophy" question it occured to me > > that here is an ideal problem which will illustrate the Lisp way of > > doing things.
Trying to solve this problem won't illustrate the lisp way of doing things. It's a well defined (or could be well defined problem). Isn't the advantage of lisp is that it's well suited to solving problems which are not well specified, and whose specification in fact would be a computer program.So maybe a better problem to illustrate the strengths of lisp over C++ would be to write a program that understands written commands in some limited domain of discourse. Here the problem at the outset is not how to do things efficiently but just how to do it at all. Or write a program that simulates human behavior like the sim people game.
larrye2...@hotmail.com (larry) wrote in message <news:7b8f89d6.0203201056.38646979@posting.google.com>... > It's a well defined (or could be well defined problem). Isn't the > advantage of lisp is that it's well suited to solving problems which > are not well specified, and whose specification in fact would be a > computer program.So maybe a better problem to illustrate the strengths > of lisp over C++ would be to write a program that understands written > commands in some limited domain of discourse. Here the problem at the > outset is not how to do things efficiently but just how to do it at > all. Or write a program that simulates human behavior like the sim > people game.
In my short career (12 years) I've seen many problems/applications which were "not well specified."
Are you talking about problems which are *hard* to specify or are we talking about systems with just a *poor* definition?
* Damond Walker | In my short career (12 years) I've seen many problems/applications | which were "not well specified." | | Are you talking about problems which are *hard* to specify or are we | talking about systems with just a *poor* definition?
In my experience, the most interesting problems are very different before and after they have a solution. If you implement the problem as it was understood before it had a real solution, you have one more problem. If you try to understand the problem as you keep trying to solve it, you may end up with a lot fewer problems than you solved. I find it extremely hard to do this in languages that require (1) an enormous amount of typing to get anything useful done, and (2) an enormous amount of thinking to get anything useful typed.
Now, since problems to which we already have one correct solution are hardly _problems_ any longer, I consider only the problems that have no solution to be worth solving, and quite frequently, the solution to such a problem is to discover that it really is a different problem. This is what understand "not well specified" to mean in a Common Lisp context. In a C++ context, such a problem would just be dumb to give to a coder.
/// -- In a fight against something, the fight has value, victory has none. In a fight for something, the fight is a loss, victory merely relief.
> Now, since problems to which we already have one correct solution are > hardly _problems_ any longer, I consider only the problems that have no > solution to be worth solving, and quite frequently, the solution to such > a problem is to discover that it really is a different problem. This is > what understand "not well specified" to mean in a Common Lisp context. > In a C++ context, such a problem would just be dumb to give to a coder.
Agree with the C++ reference. I'd figure that 60% to 90% of a C++ coders experience with a problem "worth solving" would be spent slinging infrastructure. Odds are if the problem definition changes then much of that infrastructure, if tied to closely to the original problem, would be thrown out.
As an aside: A correct solution is not always the optimal one. Would you consider sub-optimal solutions to still be in the class of problems "worth solving?" I'd say yes though I'd qualify it with a "it depends."
* dwal...@syncreticsoft.com (Damond Walker) | Agree with the C++ reference. I'd figure that 60% to 90% of a C++ | coders experience with a problem "worth solving" would be spent | slinging infrastructure. Odds are if the problem definition changes | then much of that infrastructure, if tied to closely to the original | problem, would be thrown out.
Precisely, and the personal attachment that mere mortals feel towards what they have written is such a strong barrier to throwing things out that it is even a stronger motivator to keep going than all the waste of time that went into what is thrown away. However, anyone who has ever successfully been published (even in academia), will know that in order to get an idea across, you need to be able to phrase it as least half a dozen different ways and be able to expand on each of them. Successful writing is much harder than chess or go in terms of thinking ahead and setting up for future moves. Writing good software is even harder, and that is why setting up the proper abstractions is so amazingly hard and why both library and language design requires so much forethought and experience. The problem with C++ is basically that it was not thrown out in time, that Bjarne accepted almost every suggestion he received.
The more experience you have writing, the less attached you become to what you have written. This does not appear to be true for programmers, maybe because the function the copy-editor and editor has in a publishing company is performed by the compiler, so everything that passes the compiler is effectively "published".
| As an aside: A correct solution is not always the optimal one. Would you | consider sub-optimal solutions to still be in the class of problems | "worth solving?" I'd say yes though I'd qualify it with a "it depends."
Whether a problem has been solved sufficiently or not is usually an engineering decision, not an academic exercise in perfection, but if there is a satisfaactory general solution, the engineering decisions change dramatically in nature.
/// -- In a fight against something, the fight has value, victory has none. In a fight for something, the fight is a loss, victory merely relief.
> On Mon, 18 Mar 2002 17:54:10 GMT, Kent M Pitman <pit...@world.std.com> > wrote:
> >olc...@interaccess.com (Thaddeus L Olczyk) writes:
> >> After thinking about the "philosophy" question it occured to me > >> that here is an ideal problem which will illustrate the Lisp way of > >> doing things.
> >> You are input a list made up exclusively of > >> structs ( or classes, your choice ) of type foo. > >> foo contains at least five members, strings of length 20. > >> Because of this, copying of foos should be kept to a minimum.
> >> The list will contain at least 10,000 elements and at most 1,000,000 > >> elements.
> >> One thing that will be required is that you maintain lists of elements > >> sorted with different members as key ( you would prefer to maintain > >> references of the elements rather than copies for two reasons: > >> 1) You want to be able to insert modifications to elements and have it > >> reflect in all the lists. > >> 2) You want to minimize used memory and so not copy anything large. > >> 3) You want to make it fast, so try not to copy anthing large.
> >> The operations allowed are: > >> 1) Adding a list ( call it a key list ), this list is sorted by taking > >> a specified member. > >> 2) Remove a key list. > >> 3) Find an element or elements by a specified set of members. > >> 3) Add an element ( and update all key lists ). > >> 4) Delete a key element ( and update all key lists ). > >> 5) Modify a specific element.
> >> The program needs to be a fast as possible, and it needs to use as > >> little memory as is possible.
> >Maybe someone will in fact write this for you. I happen not to be that > >person.
> >I'd bet you'll do better to write the program and offer it for critique. > If it was C++ I could write it in about two hours, but I couldn't > write it in Lisp both efficiently and stingy on memory. That's the > point. This problem has all the elements that styme me. So instead of > worrying about being productive, I keep worrying about how to be more > efficient.
It might help, then, if you'd show us the C++ version. * It'd inspire the "anything C++ can do Lisp can do better" crowd.:-| * It'd help supplement your specification. E.g. by reading it we could guess ** Is it acceptable in this application to write your own specialized memory manager which ties up at all times as much memory as it needs for peak usage in this task? ** What is to be done with duplicate elements? In particular, if they're not to be discarded, does your "avoid copies" mean that the system should optimize performance in this case by keeping a count of duplicates, instead of multiple copies? * It'd also give a better idea of what level of microoptimization cruft you want, thus giving people a better idea of whether it's their kind of challenge. * It'd soothe possible anxieties that you're going to do the debating fallacy/trick/whatever of criticizing a proposal for not being perfect, while ignoring any shortcomings of your explicit or implicit alternative. * It'd soothe possible anxieties that you might expect people to work harder on what is, after all, your problem than you're willing to work yourself.
> Precisely, and the personal attachment that mere mortals feel towards > what they have written is such a strong barrier to throwing things out > that it is even a stronger motivator to keep going than all the waste of > time that went into what is thrown away. However, anyone who has ever > successfully been published (even in academia), will know that in order > to get an idea across, you need to be able to phrase it as least half a > dozen different ways and be able to expand on each of them. Successful > writing is much harder than chess or go in terms of thinking ahead and > setting up for future moves. Writing good software is even harder, and > that is why setting up the proper abstractions is so amazingly hard and > why both library and language design requires so much forethought and > experience. The problem with C++ is basically that it was not thrown out > in time, that Bjarne accepted almost every suggestion he received.
The "One Right Way", as defined by one person -- and pushed by industry, becomes the anchor that holds successive programmers back.
Coding doesn't have to be painful. C++ just makes it that way. I keep searching for someone who has a Really Good Time(tm) writing C++ code.
Ignoring various implementation issues I havn't talked to one person who really *enjoys* the C++ coding experience.
> The more experience you have writing, the less attached you become to > what you have written. This does not appear to be true for programmers, > maybe because the function the copy-editor and editor has in a publishing > company is performed by the compiler, so everything that passes the > compiler is effectively "published".
Code reviews are a terribly humbling experience. I havn't had to endure one for years -- but they do force you to justify what you did (assuming you have a good reviewer) -- much like the editor(s) looking over a paper/article.
As a variant on the "Take a C++ program and show me the Lisp Way" how about we take a Lisp program and "show me the C++ way?"
We would need a good, short (say under 5k to 10k of Lisp source -- excluding comments), example of how one solves a less-than-easy problem in Common Lisp.
Would that be easier? It would allow the original poster to get the code, run it through the interpreter, ask all the questions in the world, and then implement a C++ solution.
I think the end result (learning) would be nearly the same.
Damond Walker wrote: > As a variant on the "Take a C++ program and show me the Lisp Way" how > about we take a Lisp program and "show me the C++ way?"
> We would need a good, short (say under 5k to 10k of Lisp source -- > excluding comments), example of how one solves a less-than-easy > problem in Common Lisp.
> Would that be easier? It would allow the original poster to get the > code, run it through the interpreter, ask all the questions in the > world, and then implement a C++ solution.
> I think the end result (learning) would be nearly the same.
there is a little bit of Lisp. 146 lines, 5283 bytes, including a very few comments; 117 non-blank, non-comment lines, of which 10 could be omitted with no loss of functionality or speed.
It was prompted by reading that "Oysters oysters oysters split split split" is a meaningful (albeit useless) English sentence. The same is true "for arbitrary values of 3".
The interesting (i.e., "interesting if you find this sort of weirdness interesting") functions are:
PARSE-SENTENCE
takes a list, each of whose elements is one of the two symbols OYSTERS and SPLIT. Returns a list of possible parses of that sequence of words as a sentence. (I hope it returns a list of *all* possible parses.)
TRY-ALL
takes a length, and an optional threshold. Constructs all sequences of the given length built out of OYSTERS and SPLIT, and tells you about all the ones that make sentences. Reports on multiple parses. If the threshold is given, it reports only sequences that have at least that many different parses.
TRY-ALL-2
same semantics as TRY-ALL, but uses less memory.
For example, doing (TRY-ALL 7 2) reveals that there are exactly two sequences with more than one parse. One of them follows:
On my machine (Athlon, 1GHz, 256Mb, FreeBSD), running CMU CL 18c, (TRY-ALL-2 12 5) takes just under 2 seconds of real time to find the five sequences of length 12 that have 5 parses each, and describe all those parses. TRY-ALL takes about the same time but conses much more.
I'd be very interested to see how well this can be translated into C++. It probably wouldn't be as grim as some non-C++-ers expect (the standard library has a fairly decent selection of data structures), but I think combining decent performance and decent brevity could be tricky.
-- Gareth McCaughan Gareth.McCaug...@pobox.com .sig under construc
