hello !
First of all, I'm French so sorry for my English ! ;-)
I want implement a B-tree in Lisp. The main operation I have to achieve is
the insertion of an element in this B-tree.
Which is, according to you, the best data structur to do it (most simply) ?
Thank a lot.
Mathieu
--
=== Ma citation du mois ===
C'est l'incertitude qui nous charme. Tout devient merveilleux dans la brume.
Oscar Wilde - Extrait de "Le portrait de Dorian Gray"
P.S. This citation does not have importance. Should I translate it all the
same? ;-)
"Mathieu" <·········@hotmail.com> writes:
> hello !
Hello.
> First of all, I'm French so sorry for my English ! ;-)
Your English seems fine.
> I want implement a B-tree in Lisp. The main operation I have to achieve is
> the insertion of an element in this B-tree.
> Which is, according to you, the best data structur to do it (most simply) ?
This sounds suspiciously like homework. If so, you MUST say so, if you
don't want people to think you are simply trying to cheat.
If it IS homework, you should also show what you have tried so far.
People here don't mind helping in the case of a legitimate block,
but this is not the place to just have someone do your work for you.
It's homework !
But I'm not so stupid to request the solution without to have searched
before !
I'm not a child !!!!
I believed find good consultings here. And I wished learn too !
Mathieu, disappointed
--
=== Ma citation du mois ===
C'est l'incertitude qui nous charme. Tout devient merveilleux dans la brume.
Oscar Wilde - Extrait de "Le portrait de Dorian Gray"
"Kent M Pitman" <······@world.std.com> a �crit dans le message de news:
···············@shell01.TheWorld.com...
> "Mathieu" <·········@hotmail.com> writes:
>
> > hello !
>
> Hello.
>
> > First of all, I'm French so sorry for my English ! ;-)
>
> Your English seems fine.
>
> > I want implement a B-tree in Lisp. The main operation I have to achieve
is
> > the insertion of an element in this B-tree.
> > Which is, according to you, the best data structur to do it (most
simply) ?
>
> This sounds suspiciously like homework. If so, you MUST say so, if you
> don't want people to think you are simply trying to cheat.
>
> If it IS homework, you should also show what you have tried so far.
> People here don't mind helping in the case of a legitimate block,
> but this is not the place to just have someone do your work for you.
"Mathieu" <·········@hotmail.com> writes:
> It's homework !
> But I'm not so stupid to request the solution without to have searched
> before !
> I'm not a child !!!!
>
> I believed find good consultings here. And I wished learn too !
>
> Mathieu, disappointed
> "Kent M Pitman" <······@world.std.com> a �crit dans le message de news:
>
> > If it IS homework, you should also show what you have tried so far.
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
> > People here don't mind helping in the case of a legitimate block,
> > but this is not the place to just have someone do your work for you.
Show what you've tried, where you are, what code you have, etc. Then,
people can give you advice from there. Anything else would be doing
your homework for you.
--
/|_ .-----------------------.
,' .\ / | No to Imperialist war |
,--' _,' | Wage class war! |
/ / `-----------------------'
( -. |
| ) |
(`-. '--.)
`. )----'
"Thomas F. Burdick" <···@conquest.OCF.Berkeley.EDU> wrote in message
····················@conquest.OCF.Berkeley.EDU...
> "Mathieu" <·········@hotmail.com> writes:
>
> > It's homework !
> > But I'm not so stupid to request the solution without to have searched
> > before !
> > I'm not a child !!!!
> >
> > I believed find good consultings here. And I wished learn too !
> >
> > Mathieu, disappointed
>
> > "Kent M Pitman" <······@world.std.com> a �crit dans le message de news:
> >
> > > If it IS homework, you should also show what you have tried so far.
> ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
> > > People here don't mind helping in the case of a legitimate block,
> > > but this is not the place to just have someone do your work for you.
>
> Show what you've tried, where you are, what code you have, etc. Then,
> people can give you advice from there. Anything else would be doing
> your homework for you.
>
In the OP's defense, his question "I want implement a B-tree in Lisp[...]Which
is[..]the best data structur to do it (most simply) ?" is really a design
question so it is not so unreasonable to ask this before writing anything....
I have not implemented a B-tree in lisp, but I might suggest off the top of my
head using a b-tree-node defstruct. If you do not want it to be general but
rather specific to whatever order your assignment or you wish, you can just
have a slot for each key and a a slot for each child b-tree-node. Otherwise
you might want to use a single list of keys slot and a list of child node slots
along with a order-n slot of 2 or 3 or whatever and use that to know if your
node is full or not. I guess you would have to have a slot for the parent node
too. The alternatives are a class - this has the advantage of specializing
methods on it and all the other wonders of CLOS or a simple nested list which
has the advantage of simplicity though it may be harder to look at and harder
to debug.
Other than that, you should probably take the other advice you got, implement
as much as you can, and then you can come back with specific questions. Don't
worry, people are very happy to help with homework, they just don't want to
feel used.
--
Coby
(remove #\space "coby . beck @ opentechgroup . com")
Coby Beck wrote:
> The alternatives are a class - this has the advantage of
> specializing methods on it and all the other wonders of CLOS or a simple
> nested list which has the advantage of simplicity though it may be harder
> to look at and harder to debug.
You can create methods that specialize on a struct.
ciao,
Jochen
--
http://www.dataheaven.de
"Jochen Schmidt" <···@dataheaven.de> wrote in message
·················@rznews2.rrze.uni-erlangen.de...
> Coby Beck wrote:
> > The alternatives are a class - this has the advantage of
> > specializing methods on it and all the other wonders of CLOS or a simple
> > nested list which has the advantage of simplicity though it may be harder
> > to look at and harder to debug.
>
> You can create methods that specialize on a struct.
>
True. Thanks for the reminder...now I can't think of the reason I often end up
changing defstruct to defclass as the code developes, I thought that was it....
--
Coby
(remove #\space "coby . beck @ opentechgroup . com")
"Coby Beck" <·····@mercury.bc.ca> writes:
> "Jochen Schmidt" <···@dataheaven.de> wrote in message
> ·················@rznews2.rrze.uni-erlangen.de...
> > Coby Beck wrote:
> > > The alternatives are a class - this has the advantage of
> > > specializing methods on it and all the other wonders of CLOS or a simple
> > > nested list which has the advantage of simplicity though it may be harder
> > > to look at and harder to debug.
> >
> > You can create methods that specialize on a struct.
>
> True. Thanks for the reminder...now I can't think of the reason I
> often end up changing defstruct to defclass as the code developes, I
> thought that was it....
Perhaps the first time you have to REdefine a struct, adding or removing
a slot, the answer will come back to you. Then again, you might have to
wait until you first want multiple inheritance. But I'm sure eventually
something will jog your memory.
"Kent M Pitman" <······@world.std.com> wrote in message
····················@shell01.TheWorld.com...
> "Coby Beck" <·····@mercury.bc.ca> writes:
>
> > "Jochen Schmidt" <···@dataheaven.de> wrote in message
> > ·················@rznews2.rrze.uni-erlangen.de...
> > > Coby Beck wrote:
> > > > The alternatives are a class - this has the advantage of
> > > > specializing methods on it and all the other wonders of CLOS or a
simple
> > > > nested list which has the advantage of simplicity though it may be
harder
> > > > to look at and harder to debug.
> > >
> > > You can create methods that specialize on a struct.
> >
> > True. Thanks for the reminder...now I can't think of the reason I
> > often end up changing defstruct to defclass as the code developes, I
> > thought that was it....
>
> Perhaps the first time you have to REdefine a struct, adding or removing
> a slot, the answer will come back to you. Then again, you might have to
> wait until you first want multiple inheritance. But I'm sure eventually
> something will jog your memory.
>
Yes, there are a few reasons to regret thinking "I'll just use a struct, it's
faster and I don't need anything fancy"
I did just remember my most recent reason: slot accessors are not generic
functions.
--
Coby
(remove #\space "coby . beck @ opentechgroup . com")
"Coby Beck" <·····@mercury.bc.ca> writes:
> The alternatives are a class - this has the advantage of specializing
> methods on it
You can specialize methods on structs and other types too.
(Accessors made with defstruct aren't generic functions, though.)
hello !
I'm happy because your advices have permitted me to learn the notion of
class in Lisp (thank to web sites). This to silence persons who believed I
cheet.
It's a notion that we not learned. So I think my teacher don't want an
implementation that used classes. Perhaps she would be impress ;-)
So, I rather searched a struct using only the lists. It is possible?
Mathieu
"Coby Beck" <·····@mercury.bc.ca> a �crit dans le message de news:
·························@typhoon.tampabay.rr.com...
>
> "Thomas F. Burdick" <···@conquest.OCF.Berkeley.EDU> wrote in message
> ····················@conquest.OCF.Berkeley.EDU...
> > "Mathieu" <·········@hotmail.com> writes:
> >
> > > It's homework !
> > > But I'm not so stupid to request the solution without to have searched
> > > before !
> > > I'm not a child !!!!
> > >
> > > I believed find good consultings here. And I wished learn too !
> > >
> > > Mathieu, disappointed
> >
> > > "Kent M Pitman" <······@world.std.com> a �crit dans le message de
news:
> > >
> > > > If it IS homework, you should also show what you have tried so far.
> > ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
> > > > People here don't mind helping in the case of a legitimate block,
> > > > but this is not the place to just have someone do your work for you.
> >
> > Show what you've tried, where you are, what code you have, etc. Then,
> > people can give you advice from there. Anything else would be doing
> > your homework for you.
> >
>
> In the OP's defense, his question "I want implement a B-tree in
Lisp[...]Which
> is[..]the best data structur to do it (most simply) ?" is really a design
> question so it is not so unreasonable to ask this before writing
anything....
>
> I have not implemented a B-tree in lisp, but I might suggest off the top
of my
> head using a b-tree-node defstruct. If you do not want it to be general
but
> rather specific to whatever order your assignment or you wish, you can
just
> have a slot for each key and a a slot for each child b-tree-node.
Otherwise
> you might want to use a single list of keys slot and a list of child node
slots
> along with a order-n slot of 2 or 3 or whatever and use that to know if
your
> node is full or not. I guess you would have to have a slot for the parent
node
> too. The alternatives are a class - this has the advantage of
specializing
> methods on it and all the other wonders of CLOS or a simple nested list
which
> has the advantage of simplicity though it may be harder to look at and
harder
> to debug.
>
> Other than that, you should probably take the other advice you got,
implement
> as much as you can, and then you can come back with specific questions.
Don't
> worry, people are very happy to help with homework, they just don't want
to
> feel used.
>
> --
> Coby
> (remove #\space "coby . beck @ opentechgroup . com")
>
>
>
"Mathieu" <·········@hotmail.com> writes:
> I'm happy because your advices have permitted me to learn the notion
> of class in Lisp (thank to web sites). This to silence persons who
> believed I cheet.
> It's a notion that we not learned. So I think my teacher don't want
> an implementation that used classes. Perhaps she would be impress
> ;-)
> So, I rather searched a struct using only the lists. It is possible?
Certainly it's _possible_ to do it solely using lists.
It's only going to be particularly "useful" for doing toy homework
problems, because in "real world" applications, it makes vastly more
sense to use either a DEFSTRUCT or a CLASS.
Either approach will _certainly_ be faster, more robust, and more
maintainable than just using lists.
--
(reverse (concatenate 'string ····················@" "454aa"))
http://www3.sympatico.ca/cbbrowne/internet.html
If the cops arrest a mime, do they tell him he has the right to remain
silent?
hello!
Thank you for your answer.
First question: what is the main difference between a DEFSTRUCT and a
CLASS. I read some web sites about it but the difference don't seem me
obvious.
Beaucause of not knowing the notion of classes, can you give me an
exemple of class definition. For example, a class that contain two
lists... or any other example. Just to give me an idea!
After, I try to write the first method that I should effectuate. If I'll
have any problem, I would contact you. If you are agree with that, of
course!
Mathieu
P.S. Don't hesitate to correct my English. That will be useful for me...
(I remember I'm French)
Christopher Browne a �crit :
>
> "Mathieu" <·········@hotmail.com> writes:
> > I'm happy because your advices have permitted me to learn the notion
> > of class in Lisp (thank to web sites). This to silence persons who
> > believed I cheet.
>
> > It's a notion that we not learned. So I think my teacher don't want
> > an implementation that used classes. Perhaps she would be impress
> > ;-)
>
> > So, I rather searched a struct using only the lists. It is possible?
>
> Certainly it's _possible_ to do it solely using lists.
>
> It's only going to be particularly "useful" for doing toy homework
> problems, because in "real world" applications, it makes vastly more
> sense to use either a DEFSTRUCT or a CLASS.
>
> Either approach will _certainly_ be faster, more robust, and more
> maintainable than just using lists.
> --
> (reverse (concatenate 'string ····················@" "454aa"))
> http://www3.sympatico.ca/cbbrowne/internet.html
> If the cops arrest a mime, do they tell him he has the right to remain
> silent?
--
Mathieu <········@info.univ-angers.fr> writes:
> hello!
>
> Thank you for your answer.
>
> First question: what is the main difference between a DEFSTRUCT and a
> CLASS. I read some web sites about it but the difference don't seem me
> obvious.
Flexibility, multiple inheritance, easer extensibility, Meta Information
>
> Beaucause of not knowing the notion of classes, can you give me an
> exemple of class definition. For example, a class that contain two
> lists... or any other example. Just to give me an idea!
Well I think a decent Common Lisp book should give you an
idea. However a class may look like this
(defclass foo ()
((l1 :accessor l1 :initarg :l1 :type list)
(l2 :accessor l2 :initarg :l2 :type list)))
That's a class definition with to list-slots.
Regards
Friedrich
Coby Beck a �crit :
> I have not implemented a B-tree in lisp, but I might suggest off the top of my
> head using a b-tree-node defstruct. If you do not want it to be general but
> rather specific to whatever order your assignment or you wish, you can just
> have a slot for each key and a a slot for each child b-tree-node. Otherwise
> you might want to use a single list of keys slot and a list of child node slots
> along with a order-n slot of 2 or 3 or whatever and use that to know if your
> node is full or not. I guess you would have to have a slot for the parent node
> too.
I'm french and I'm not sure to have all understand. Nevertheless, the
Coby's idea seems me interesant.
Can someone explain me, with other words, this idea?
for example, the sentence : "a single list of keys slot and a list of
child node slots
along with a order-n slot of 2 or 3 or whatever" is complex for me ;-)
And my limited knowledge about class and struct in Lisp dont't help me
;-)
Mathieu
--
\\\|///
\ ~ ~ /
(\ @ @ /)
#########---o000--(_)--000o---#########
# #
# Mathieu BROSSAIS #
# #
# UFR Sciences Angers #
# Licence Informatique #
# #
# oo0 #
#####---( )--0oo---##################
\ ( ( )
\_) ) /
(_)
Mathieu wrote:
> It's homework !
Thank you for saying so.
As you did not ask for code, but only what data structure would be most
appropriate, I will attempt to answer this question.
The main structural choice in a B-tree is which ordered sequence one should
use to hold the children nodes of a given node in the B-tree. Common Lisp
gives you the choice of either a list or an array. If you are transcribing
code from an algorithm book describing the operation using a standard
procedural language (Pascal, C), the array might give you slightly simpler
transliteration.
However, since simply transcribing the code will not teach you much, I'd
recommend understanding the algorithm and how the data structure is used
within it. That would allow you to code the algorithm without knowledge of
the basic data structure and let you check the performance and ease of
coding using any data structure that supported the abstract base
operations. You'd learn a lot more.
Think about the algorithm in terms of a node, what a node contains and what
you have to do to it to perform operations on the tree. Think about
splitting, merging, rebalancing, etc. and how they relate to insertion and
deletion. As for base operations think about removing a child node, adding
a child node, setting and retrieving the element on a node`, etc.
The operative word is "think". It should go along with "work" and "try out
things".
faa
"Mathieu" <·········@hotmail.com> writes:
> It's homework ! [...]
> Mathieu, disappointed
Be disappointed all you want. But in the midst of it, tell us what part
you have done and where you are stuck.
Mathieu wrote:
> It's homework !
> But I'm not so stupid to request the solution without to have searched
> before !
> I'm not a child !!!!
Then don't act like one. Your temper !!!! tantrum!!!! is unlikely to
motivate others to help you.
>
> I believed find good consultings here. And I wished learn too !
>
> Mathieu, disappointed
>
Perhaps after a bit of mature reflection you will realize that you are
asking for help--not demanding it.
> I want implement a B-tree in Lisp. The main operation I have to achieve is
Maybe this will help:
http://www-2.cs.cmu.edu/afs/cs/project/ai-repository/ai/lang/lisp/code/ext/trees/0.html