he array. But then you need
>>> > array elements to contain the indices for the children explicitely.
>>> And why is this a problem?
>DA> Oh, I'm sorry -- I see what you are saying now. You're saying you can
>DA> just implement a normal binary search tree
Douglas Alan writes:
> I can't see that a binary search tree would typically have
> particularly good cache-friendliness, so I can't see why a flat-array
> representation, such as is done for a binary heap, would have
> particularly worse cache-reference.
That is a good p
licitely.
> And why is this a problem?
Oh, I'm sorry -- I see what you are saying now. You're saying you can
just implement a normal binary search tree, but store the tree nodes
in an array, as if it were a chunk of memory, and use array indices as
pointers, rather than using memor
flat array efficiently (n log
n time overall), but it never even seems to bring up the subject as to
whether a binary search tree or a treap can also be efficiently
maintained in a flat array.
Though it may be the case that these questions are left as exercises
for the student, and therefore bu
On Jul 14, 8:10 am, Piet van Oostrum wrote:
> Of course you can take any BST algorithm and replace pointers by indices
> in the array and allocate new elements in the array. But then you need
> array elements to contain the indices for the children explicitely.
And why is this a problem? This is
On Jul 14, 7:38 am, Florian Brucker wrote:
> Douglas Alan wrote:
> > Thank you. My question wasn't intended to be Python specific, though.
> > I am just curious for purely academic reasons about whether there is
> > such an algorithm. All the sources I've skimmed only seem to the
> > answer the
Piet van Oostrum wrote:
Douglas Alan (DA) wrote:
DA> On Jul 13, 3:57 pm, a...@pythoncraft.com (Aahz) wrote:
Still, unless your list is large (more than thousands of elements),
that's the way you should go. See the bisect module. Thing is, the
speed difference between C and Python means the
> Douglas Alan (DA) wrote:
>DA> On Jul 13, 3:57 pm, a...@pythoncraft.com (Aahz) wrote:
>>> Still, unless your list is large (more than thousands of elements),
>>> that's the way you should go. See the bisect module. Thing is, the
>>> speed difference between C and Python means the constant
Douglas Alan wrote:
> Thank you. My question wasn't intended to be Python specific, though.
> I am just curious for purely academic reasons about whether there is
> such an algorithm. All the sources I've skimmed only seem to the
> answer the question via omission. Which is kind of strange, since i
On Jul 13, 3:57 pm, a...@pythoncraft.com (Aahz) wrote:
> Still, unless your list is large (more than thousands of elements),
> that's the way you should go. See the bisect module. Thing is, the
> speed difference between C and Python means the constant for insertion
> and deletion is very very s
In article ,
Douglas Alan wrote:
>
>I couldn't find a good algorithms forum on the Internet, so I guess
>I'll ask this question here instead: Is it possible to efficiently
>maintain a binary search tree in a flat array (i.e., without using
>pointers), as is typical
Douglas Alan writes:
> It would also clearly be
> possible to store a balanced binary tree in a flat array, storing the
> children of the node at index i at indices 2*i and 2*i + 1, just as
> one does for a binary heap. But if you do that, I don't know if you
> could then do insertions and deletio
I couldn't find a good algorithms forum on the Internet, so I guess
I'll ask this question here instead: Is it possible to efficiently
maintain a binary search tree in a flat array (i.e., without using
pointers), as is typically done for a binary heap?
It *is* possible, of course,
On Jun 17, 1:01 am, "Gabriel Genellina" <[EMAIL PROTECTED]>
wrote:
> En Mon, 16 Jun 2008 07:34:06 -0300, Bart Kastermans <[EMAIL PROTECTED]>
> escribió:
>
> > Summary: can't verify big O claim, how to properly time this?
>
> > This is interesting. I had never attempted to verify a big O
> > state
En Mon, 16 Jun 2008 07:34:06 -0300, Bart Kastermans <[EMAIL PROTECTED]>
escribió:
> Summary: can't verify big O claim, how to properly time this?
>
> This is interesting. I had never attempted to verify a big O
> statement
> before, and decided that it would be worth trying. So I wrote some
> c
On Mon, Jun 16, 2008 at 12:07 PM, Alex Elder <[EMAIL PROTECTED]> wrote:
> I found this article useful when dealing with strings in Python:
>
>http://www.skymind.com/~ocrow/python_string/
>
> It may help squeeze some more time out of your code. 8-)
Things seem to have changed since then. I
On Mon, 16 Jun 2008 11:30:19 -0600, Ian Kelly <[EMAIL PROTECTED]> wrote:
On Mon, Jun 16, 2008 at 11:09 AM, Jean-Paul Calderone
<[EMAIL PROTECTED]> wrote:
It will depend what version of Python you're using and the *exact* details
of the code in question. An optimization was introduced where, if
I found this article useful when dealing with strings in Python:
http://www.skymind.com/~ocrow/python_string/
It may help squeeze some more time out of your code. 8-)
Alex.
--
http://mail.python.org/mailman/listinfo/python-list
On Mon, Jun 16, 2008 at 11:09 AM, Jean-Paul Calderone
<[EMAIL PROTECTED]> wrote:
> It will depend what version of Python you're using and the *exact* details
> of the code in question. An optimization was introduced where, if the
> string being concatenated to is not referred to anywhere else, it
On Mon, 16 Jun 2008 10:41:05 -0600, Ian Kelly <[EMAIL PROTECTED]> wrote:
On Mon, Jun 16, 2008 at 4:34 AM, Bart Kastermans <[EMAIL PROTECTED]> wrote:
This is interesting. I had never attempted to verify a big O
statement
before, and decided that it would be worth trying. So I wrote some
code to
On Mon, Jun 16, 2008 at 4:34 AM, Bart Kastermans <[EMAIL PROTECTED]> wrote:
> This is interesting. I had never attempted to verify a big O
> statement
> before, and decided that it would be worth trying. So I wrote some
> code to
> collect data, and I can't find that it goes quadratic. I have th
Summary: can't verify big O claim, how to properly time this?
On Jun 15, 2:34 pm, "Terry Reedy" <[EMAIL PROTECTED]> wrote:
> "Bart Kastermans" <[EMAIL PROTECTED]> wrote in message
>
> news:[EMAIL PROTECTED]
> |I wrote a binary search tree in pytho
"Bart Kastermans" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]
|I wrote a binary search tree in python, explaining as I was doing it
| how and why I did it. I am very interested in receiving comments on
| the code, process, and anything else that will impr
I wrote a binary search tree in python, explaining as I was doing it
how and why I did it. I am very interested in receiving comments on
the code, process, and anything else that will improve my coding or
writing.
I wrote this all up in my blog at:
http://kasterma.wordpress.com/2008/06/15
On 11/13/07, Terry Reedy ([EMAIL PROTECTED]) wrote:
>"Scott SA" <[EMAIL PROTECTED]> wrote in message
>news:[EMAIL PROTECTED]
>| On 11/12/07, Scott SA ([EMAIL PROTECTED]) wrote:
>| I decided to test the speeds of the four methods:
>|
>|set_example
>|s = set()
>|for url in urls
En Mon, 12 Nov 2007 16:21:36 -0300, Scott SA <[EMAIL PROTECTED]> escribió:
> I decided to test the speeds of the four methods:
(but one should always check for correctness before checking speed)
> def dict_example(urls):
> d = {}
> for url in urls:
> if url in d:
> d[
"Scott SA" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]
| On 11/12/07, Scott SA ([EMAIL PROTECTED]) wrote:
| I decided to test the speeds of the four methods:
|
|set_example
|s = set()
|for url in urls:
|if not url in s:
|s.add(url)
On 11/12/07, Scott SA ([EMAIL PROTECTED]) wrote:
Uhm sorry, there is a slightly cleaner way of running the second option I
presented (sorry for the second post).
>If you would find an index and count useful, you could do something like this:
>
>for idx in range(len(urls)):
>uniqu
>> > more than one time(can't be more than twice).
>>
>> > I thought to put them into binary search tree, this way they'll be
>> > sorted and I'll be able to check if the URL already exist.
>>
>> What about a set ?
>>
>> s = set()
&
> Now, I can see that this method has some superfluous data (the `1`
> that is assigned to the dict). So I suppose this is less memory
> efficient. But is this slower then? As both implementations use hashes
> of the URL to access the data. Just asking out of curiosity ;)
Performance-wise, there i
On Nov 9, 11:45 pm, Bruno Desthuilliers
<[EMAIL PROTECTED]> wrote:
> [EMAIL PROTECTED] a écrit :
>
> > Hi,
>
> > I have to get list of URLs one by one and to find the URLs that I have
> > more than one time(can't be more than twice).
>
> > I though
[EMAIL PROTECTED] a écrit :
> Hi,
>
> I have to get list of URLs one by one and to find the URLs that I have
> more than one time(can't be more than twice).
>
> I thought to put them into binary search tree, this way they'll be
> sorted and I'll be able to c
On Nov 9, 4:06 pm, [EMAIL PROTECTED] wrote:
> Hi,
>
> I have to get list of URLs one by one and to find the URLs that I have
> more than one time(can't be more than twice).
>
> I thought to put them into binary search tree, this way they'll be
> sorted and I'll
> [EMAIL PROTECTED] wrote:
> > Hi,
> >
> > I have to get list of URLs one by one and to find the URLs that I have
> > more than one time(can't be more than twice).
> >
> > I thought to put them into binary search tree, this way they'll be
> > s
On 2007-11-09, Larry Bates <[EMAIL PROTECTED]> wrote:
> [EMAIL PROTECTED] wrote:
>> I have to get list of URLs one by one and to find the URLs
>> that I have more than one time(can't be more than twice).
>>
>> I thought to put them into binary search tree,
[EMAIL PROTECTED] wrote:
> Hi,
>
> I have to get list of URLs one by one and to find the URLs that I have
> more than one time(can't be more than twice).
>
> I thought to put them into binary search tree, this way they'll be
> sorted and I'll be ab
Hi,
I have to get list of URLs one by one and to find the URLs that I have
more than one time(can't be more than twice).
I thought to put them into binary search tree, this way they'll be
sorted and I'll be able to check if the URL already exist.
Couldn't find any python lib
37 matches
Mail list logo
