 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Dan Byers wrote:
> Cool as the graphics were, the storytelling was even better. This is why Pixar
> is still head-and-shoulders above just about everyone else. They don't assume
> their audiences are either complete morons or are all under age six. My two
> cents.
Dreamworks, for pretty much its whole time in the business, has resorted
either to fairly predictable stories, or filling the flick with one gag
after the next. When the gags are good, like they were in Shrek and
Shrek II, the results are good, but when the gags are no longer funny
the film loses its appeal.
Regards,
John
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
John VanSickle <evi### [at] hotmail com> wrote:
> Dreamworks, for pretty much its whole time in the business, has resorted
> either to fairly predictable stories, or filling the flick with one gag
> after the next. When the gags are good, like they were in Shrek and
> Shrek II, the results are good, but when the gags are no longer funny
> the film loses its appeal.
Indeed. Pixar movies are true to the Disney tradition of long play movies with
strong stories. Dreamworks went for the Warner Looney Tunes style of quick
gags, which really just works for short movies.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
nemesis <nam### [at] gmailcom> wrote:
> > And speaking of Pixar, I read recently that Cars was entirely raytraced :)
> Not sure. Renderman is capable of raytracing, but its main pipeline is a kind
> of scanline: REYES. Besides, I think in the DVD they said the reflections on
> the cars were limited to 2 or 3 bounces, not to bog it down indefinitely. And
> all those desert scenaries surely don't require raytracing...
It was one of the major technological points in Cars: They wanted it
raytraced, and they had to use advanced technology for that to be possible,
one example being using volumetric rays (ie. cones instead of line segments).
(The reason to use cones instead of lines when tracing is that many effects,
such as mip-mapping, require knowing not only the location of the intersection
on the texture, but the area of the visible portion of the texture at that
place.)
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
John VanSickle <evi### [at] hotmailcom> wrote:
> the ray-tracing algorithm requires that all of the scene geometry exist
> in memory all at once.
I don't think that's true. You can have bounding boxes for objects loaded
into memory instead of the objects themselves, and test against those boxes.
Only if the box is hit you load the object itself into memory and test the
ray against it. This process can be cached so that least used objects can
be dropped from memory.
Other optimizations can be used as well: For example, if an object is
far enough (looks very small from the point of view of the origin of the
current ray being traced), a billboard graphic can be used instead of the
object itself. (Or, in some cases, the object could be ignored completely.)
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Warp wrote:
> John VanSickle <evi### [at] hotmailcom> wrote:
>> the ray-tracing algorithm requires that all of the scene geometry exist
>> in memory all at once.
>
> I don't think that's true. You can have bounding boxes for objects loaded
> into memory instead of the objects themselves, and test against those boxes.
> Only if the box is hit you load the object itself into memory and test the
> ray against it. This process can be cached so that least used objects can
> be dropped from memory.
They used a combination of this with procedural geometry in Monsters,
Inc, I believe. If I understand their comments correctly, then each of
the children's doors was basically a single flat polygon and a random
seed. If that door needed to be drawn (rays striking it or something),
then the geometry and texturing for that door would be generated from
the seed, used, and then discarded when not needed anymore. It was the
only way they could keep millions of doors in memory at once.
> Other optimizations can be used as well: For example, if an object is
> far enough (looks very small from the point of view of the origin of the
> current ray being traced), a billboard graphic can be used instead of the
> object itself. (Or, in some cases, the object could be ignored completely.)
Progressive LOD - coming soon to a theatre near you! ;)
--
...Ben Chambers
www.pacificwebguy.com
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Warp wrote:
> Very cool graphics, IMO. Fur and water effects, especially.
>
> Also, throughout the movie I noticed that the rendering style resembled
> a lot Gilles Tran's works. That kind of warm smooth (often yellowish)
> lighting which makes everything look realistic, yet not photorealistic.
> Like for example:
>
> http://www.oyonale.com/image.php?code=727&mode=info§ion=2004&lang=en
> http://www.oyonale.com/image.php?code=491&mode=info§ion=1999&lang=en
>
>
My understanding is that it would have been up for the Best Picture
Oscar, except there is a specific category for animated films - Best
Animated Feature Film.
Tom
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> Very cool graphics, IMO. Fur and water effects, especially.
I bought it on Blu-Ray the day it was released (not on purpose, I just
happened to see it at the airport that day and thought "oh i didn't realise
it was out yet").
Yes, the graphics and animation are really impressive, even my non-tech gf
commented on how cool it looked when he was going down the sewer water. The
level of detail is amazing, often you don't notice until you pause the film
then start looking around. As always, numerous references are included to
previous pixar films and shorts, I always enjoy looking for them!
There are several papers on the pixar website that explain the techniques
used in this film.
http://graphics.pixar.com/
(link posted again incase you missed the previous 32423432 times it was
posted here)
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Yes, loved that film. Got it on DVD, might need to watch it again this
week. The CG work was incredible on it - especially, as you say, the
water and the hair effects.
Jim
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On Thu, 20 Mar 2008 16:23:36 -0500, Dan Byers wrote:
> Cool as the graphics were, the storytelling was even better.
100% agreed. They do a good job of not using the technology for the sake
of using the technology, but for telling a story. In some respects,
similar to what Roddenberry did with Star Trek - he used the technology
to tell the story - the story was rarely about the technology, but more
about the characters and the interactions between them.
Jim
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On Thu, 20 Mar 2008 17:27:33 -0500, Warp wrote:
> Btw, there's a short animation in the DVD called "Lifted" which is
> graphically perhaps even more impressive. And funny too.
Yes, loved Lifted. Have you seen the Pixar Shorts DVD?
Jim
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> Btw, there's a short animation in the DVD called "Lifted" which is
>> graphically perhaps even more impressive. And funny too.
>
> Yes, loved Lifted. Have you seen the Pixar Shorts DVD?
Absolutely brilliant, my favourites are For the Birds, Boundin, and the one
with the two street musicians (can't remember the name). The visual quality
is stunning.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On Wed, 26 Mar 2008 14:15:42 +0100, scott wrote:
>>> Btw, there's a short animation in the DVD called "Lifted" which is
>>> graphically perhaps even more impressive. And funny too.
>>
>> Yes, loved Lifted. Have you seen the Pixar Shorts DVD?
>
> Absolutely brilliant, my favourites are For the Birds, Boundin, and the
> one with the two street musicians (can't remember the name). The visual
> quality is stunning.
Yes, I particularly liked the one with the street musicians - that one
was new for us. For the Birds is a blast as well, but my wife is
particularly fond of Luxo Jr. To get the emotions of the two lamps
across the way they did was pure genius.
Jim
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> Yes, I particularly liked the one with the street musicians - that one
> was new for us. For the Birds is a blast as well, but my wife is
> particularly fond of Luxo Jr. To get the emotions of the two lamps
> across the way they did was pure genius.
Indeed, my favourite part is when the big ball comes rolling in, how they
could induce so much emotion from such simple geometry is brilliant.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On Wed, 26 Mar 2008 15:41:01 +0100, scott wrote:
>> Yes, I particularly liked the one with the street musicians - that one
>> was new for us. For the Birds is a blast as well, but my wife is
>> particularly fond of Luxo Jr. To get the emotions of the two lamps
>> across the way they did was pure genius.
>
> Indeed, my favourite part is when the big ball comes rolling in, how
> they could induce so much emotion from such simple geometry is
> brilliant.
Yes - though my favourite bit is when the small ball is punctured - the
sadness conveyed by Jr. is just incredible storytelling - like you said,
from such simple geometry, and with no facial expressions (just movement).
Jim
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
What can I say? The people who make these things are obviously absurdly
talented.
(Sickening, isn't it?)
I sat and watched The Increadibles once. By the end of it, I'd almost
convinced myself that I could do that, given enough time. And then I
watched the "making of" DVD. And, er, no. I couldn't. In a million
years. No way. These guys have more talent in one finger than I have in
my entire body...
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On Wed, 26 Mar 2008 15:07:48 +0000, Orchid XP v7 wrote:
> What can I say? The people who make these things are obviously absurdly
> talented.
They certainly are.
> I sat and watched The Increadibles once. By the end of it, I'd almost
> convinced myself that I could do that, given enough time. And then I
> watched the "making of" DVD. And, er, no. I couldn't. In a million
> years. No way. These guys have more talent in one finger than I have in
> my entire body...
Well, maybe at animation. But it's also a huge server farm and a lot of
people. I'm sure that most of them couldn't program in Haskell, so
you've got one up on them as well.
Jim
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
"Jim Henderson" <nos### [at] nospamcom> a écrit dans le message de news:
47ea7cd6$1@news.povray.org...
> Well, maybe at animation. But it's also a huge server farm and a lot of
> people. I'm sure that most of them couldn't program in Haskell, so
> you've got one up on them as well.
Mark VandeWettering, Pixar's technical director (also software engineer,
optimization artist etc. since Toy Story), has a few things to say about
Haskell ;) http://brainwagon.org/2006/11/27/why-haskell-indeed/
Perhap Andy should send him his resume...
G.
--
**********************
http://www.oyonale.com
**********************
- Graphic experiments
- POV-Ray, Cinema 4D and Poser computer art
- Posters
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> Well, maybe at animation. But it's also a huge server farm and a lot of
>> people. I'm sure that most of them couldn't program in Haskell, so
>> you've got one up on them as well.
Oh *really*? I would think something like Haskell is probably highly
relevant to their area of work, so I'd be seriously surprised if none of
them have even researched into...
> Mark VandeWettering, Pixar's technical director (also software engineer,
> optimization artist etc. since Toy Story), has a few things to say about
> Haskell ;) http://brainwagon.org/2006/11/27/why-haskell-indeed/
...oh, well there we are then. (And yes, I do take his point.)
> Perhap Andy should send him his resume...
Uh... Pixar? Isn't that in America?
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On Wed, 26 Mar 2008 18:00:39 +0100, Gilles Tran wrote:
> "Jim Henderson" <nos### [at] nospamcom> a écrit dans le message de news:
> 47ea7cd6$1@news.povray.org...
>> Well, maybe at animation. But it's also a huge server farm and a lot
>> of people. I'm sure that most of them couldn't program in Haskell, so
>> you've got one up on them as well.
>
> Mark VandeWettering, Pixar's technical director (also software engineer,
> optimization artist etc. since Toy Story), has a few things to say about
> Haskell ;) http://brainwagon.org/2006/11/27/why-haskell-indeed/ Perhap
> Andy should send him his resume...
Now there's an idea (and I didn't know that about Mark <g>)
Jim
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On Wed, 26 Mar 2008 17:22:21 +0000, Orchid XP v7 wrote:
>> Perhap Andy should send him his resume...
>
> Uh... Pixar? Isn't that in America?
Yes. Ever hear of Telecommuting? People do it all the time (I'm doing
it right now, in fact <G>)
But given the cost of living in the US compared to the UK (and the
relative value of the currencies), your Pounds are worth a lot more in
the US at the moment....
Jim
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
"Orchid XP v7" <voi### [at] devnull> a écrit dans le message de news:
47ea863f$1@news.povray.org...
>> Perhap Andy should send him his resume...
>
> Uh... Pixar? Isn't that in America?
Have you seen "Love, actually"? Remember what happens to the lonely English
boy who goes to America?
http://www.youtube.com/watch?v=O4_sSXZuO2c
That could happen to YOU!
G.
--
**********************
http://www.oyonale.com
**********************
- Graphic experiments
- POV-Ray, Cinema 4D and Poser computer art
- Posters
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Gilles Tran wrote:
> Haskell ;) http://brainwagon.org/2006/11/27/why-haskell-indeed/
> Perhap Andy should send him his resume...
Hey, Mark Chu-Carrol. I went to grad school with him, back when he was
Mark Carrol. Actually, I knew his wife Chu also. :-) Funky where you
run across people.
--
Darren New / San Diego, CA, USA (PST)
"That's pretty. Where's that?"
"It's the Age of Channelwood."
"We should go there on vacation some time."
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Darren New wrote:
> Hey, Mark Chu-Carrol. I went to grad school with him, back when he was
> Mark Carrol. Actually, I knew his wife Chu also. :-) Funky where you
> run across people.
Not when you live by yourself in your bedroom...
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Gilles Tran <gitran_nospam_@wanadoo.fr> wrote:
> http://brainwagon.org/2006/11/27/why-haskell-indeed/
I think he has a point. Quicksort is not such a good example because
quicksort is rather easy and short to implement in almost any language
(which is one of the strengths of quicksort: it's so fast because its
inner loop is so small).
What I would like to see is introsort in haskell to see how easy and
fast it is.
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Warp wrote:
> I think he has a point. Quicksort is not such a good example because
> quicksort is rather easy and short to implement in almost any language
> (which is one of the strengths of quicksort: it's so fast because its
> inner loop is so small).
I think he has a point too.
However, as the blog author points out, it's kinda difficult. To see how
good a language "really is", you need a non-trivial example. But if
you're trying to write a tutorial, you need small examples which are
easy to understand - in other words, trivial. Kind of a no-win situation
there...
> What I would like to see is introsort in haskell to see how easy and
> fast it is.
Heh. I once tried to implement something similar to this. It did an
insert sort on lists of less than 50 elements, and a quicksort
otherwise. However, I made a *fatal* mistake: I used the "length"
function to determine the size of the list. At every iteration.
Shall we just say it was "not fast"?
Anyway, assuming you've already got a heapsort function that takes a
list and completely sorts it, and you want to swap from quicksort to
heapsort after exactly 16 iterations, you could do something like this:
introsort = choose 16
choose 0 xs = heapsort xs
choose n (x:xs) =
(choose (n-1) (filter (<x) xs)) ++ [x] ++
(choose (n-1) (filter (>x) xs))
Of course, a good quicksort utterly depends on picking the right pivot.
And for a linked list, it seems hard to do that without wasting too much
time trying to pick a pivot. So I'm not really sure quicksort is a good
algorithm to be using on a linked list in the first place, but hey...
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v7 escribió:
> Of course, a good quicksort utterly depends on picking the right pivot.
> And for a linked list, it seems hard to do that without wasting too much
> time trying to pick a pivot. So I'm not really sure quicksort is a good
> algorithm to be using on a linked list in the first place, but hey...
In Java, if you sort a linked list (or any collection with linear lookup
time), it copies the whole contents into an array, sorts it, and copies
the sorted results back to the structure you were using.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> Of course, a good quicksort utterly depends on picking the right
>> pivot. And for a linked list, it seems hard to do that without wasting
>> too much time trying to pick a pivot. So I'm not really sure quicksort
>> is a good algorithm to be using on a linked list in the first place,
>> but hey...
>
> In Java, if you sort a linked list (or any collection with linear lookup
> time), it copies the whole contents into an array, sorts it, and copies
> the sorted results back to the structure you were using.
Ouch! That's a bit expensive isn't it?
Mind you... maybe not... A quick sort with a decent pivot is going to be
that much faster.
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v7 escribió:
>>> Of course, a good quicksort utterly depends on picking the right
>>> pivot. And for a linked list, it seems hard to do that without
>>> wasting too much time trying to pick a pivot. So I'm not really sure
>>> quicksort is a good algorithm to be using on a linked list in the
>>> first place, but hey...
>>
>> In Java, if you sort a linked list (or any collection with linear
>> lookup time), it copies the whole contents into an array, sorts it,
>> and copies the sorted results back to the structure you were using.
>
> Ouch! That's a bit expensive isn't it?
>
> Mind you... maybe not... A quick sort with a decent pivot is going to be
> that much faster.
I once thought sorting a linked list would be even faster than an array,
since moving elements around is so fast (no copying needed, just
changing the link). Then pretty quickly noticed how stupid that was; you
need to read elements to know *where* to move the elements, and reading
random elements is not fast...
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v7 <voi### [at] devnull> wrote:
> Anyway, assuming you've already got a heapsort function that takes a
> list and completely sorts it, and you want to swap from quicksort to
> heapsort after exactly 16 iterations, you could do something like this:
While introsort probably doesn't "officially" state how the pivot is
chosen, the median-of-3 choosing algorithm is the de-facto standard.
> Of course, a good quicksort utterly depends on picking the right pivot.
> And for a linked list, it seems hard to do that without wasting too much
> time trying to pick a pivot. So I'm not really sure quicksort is a good
> algorithm to be using on a linked list in the first place, but hey...
As I have commented to you before, it is possible to use the median-of-3
pivot choice even with linked lists.
Of course it's much easier to do with a true array, which I think it's
one weak point of Haskell, at least currently?
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Nicolas Alvarez wrote:
> I once thought sorting a linked list would be even faster than an array,
> since moving elements around is so fast (no copying needed, just
> changing the link). Then pretty quickly noticed how stupid that was; you
> need to read elements to know *where* to move the elements, and reading
> random elements is not fast...
Well, if the array elements are quite large, a linked list could
arguably be faster. However, in that case you'd likely use an array of
pointers, and any advantage is gone.
[I believe Warp has done some work on this question though...]
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Nicolas Alvarez <nic### [at] gmailisthebestcom> wrote:
> In Java, if you sort a linked list (or any collection with linear lookup
> time), it copies the whole contents into an array, sorts it, and copies
> the sorted results back to the structure you were using.
Why? C++ supports sorting of its linked list data structure, and it
does so in-place, without the need for additional memory and without
having to copy elements around. And it's very fast.
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Nicolas Alvarez <nic### [at] gmailisthebestcom> wrote:
> I once thought sorting a linked list would be even faster than an array,
It is, if copying one element is slow enough.
> Then pretty quickly noticed how stupid that was; you
> need to read elements to know *where* to move the elements, and reading
> random elements is not fast...
It is perfectly possible to implement merge sort and even quick sort
on a linked list without the need for random access. Merge sort is the
best for linked lists because it's truely O(n log n), has no pathological
cases, and for doubly-linked lists requires no additional memory. (The
array links can be used as the "additional memory" the merge sort algorithm
requires, so no additional memory needs to be allocated just for the
sorting.)
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Warp escribió:
> Nicolas Alvarez <nic### [at] gmailisthebestcom> wrote:
>> In Java, if you sort a linked list (or any collection with linear lookup
>> time), it copies the whole contents into an array, sorts it, and copies
>> the sorted results back to the structure you were using.
>
> Why? C++ supports sorting of its linked list data structure, and it
> does so in-place, without the need for additional memory and without
> having to copy elements around. And it's very fast.
I said how it works, it wasn't my idea :D
http://ln-s.net/1jjA
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Warp wrote:
> As I have commented to you before, it is possible to use the median-of-3
> pivot choice even with linked lists.
Yeah, it just adds an extra traversal. (Interestingly, I don't think
that technically alters the complexity class of the algorithm...)
> Of course it's much easier to do with a true array, which I think it's
> one weak point of Haskell, at least currently?
Merge sort or heap sort is probably a more natural fit for Haskell.
(For a merge sort, you can split a list into the even and odd elements,
sort, and then merge. Heapsort I've demonstrated here before...)
If you did want to do a quick sort, you'd have to decide whether you
want to use immutable or mutable arrays. If I feel sufficiently bored
I'll have a go at implementing them. (I'm curios to see what it would
look like myself...)
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v7 <voi### [at] devnull> wrote:
> Well, if the array elements are quite large, a linked list could
> arguably be faster. However, in that case you'd likely use an array of
> pointers, and any advantage is gone.
If you are using a linked list because of the advantages of linked lists,
then using an array to sort the list is useless overhead because linked
lists can be sorted in-place in O(n log n) time.
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Nicolas Alvarez <nic### [at] gmailisthebestcom> wrote:
> http://ln-s.net/1jjA
"This avoids the n2 log(n) performance that would result from attempting
to sort a linked list in place."
I would have never though I would see such BS from such a big company
(who is not Microsoft).
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v7 <voi### [at] devnull> wrote:
> Warp wrote:
> > As I have commented to you before, it is possible to use the median-of-3
> > pivot choice even with linked lists.
> Yeah, it just adds an extra traversal.
The extra traversal can be used to perform the first partitioning
(using eg. simply the first element as pivot), thus potentially reducing
the overall amount of work.
> (Interestingly, I don't think
> that technically alters the complexity class of the algorithm...)
No, because the "extra traversal" has to be done only once. That adds
only one 'n' to the total time, which does not affect the complexity class.
> > Of course it's much easier to do with a true array, which I think it's
> > one weak point of Haskell, at least currently?
> Merge sort or heap sort is probably a more natural fit for Haskell.
Merge sort is quite efficient for linked lists because it can be done
in-place and without requiring extra memory. On the other hand, it's a bit
complicated to implement for linked lists.
> (For a merge sort, you can split a list into the even and odd elements,
> sort, and then merge.
But does this avoid creating new lists? In other words, can Haskell
optimize it so that the merge sort is done in-place, without requiring
any additional memory?
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> http://ln-s.net/1jjA
>
> "This avoids the n2 log(n) performance that would result from attempting
> to sort a linked list in place."
>
> I would have never though I would see such BS from such a big company
> (who is not Microsoft).
......what...the...hell.....?
Seriously. Wow.
A stand astounded. I can't *begin* to imagine what they were thinking.
The only explanation I can come up with is that the document is
incorrect and the actual implementation does something sane. Just... wow.
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v7 escribió:
> A stand astounded. I can't *begin* to imagine what they were thinking.
> The only explanation I can come up with is that the document is
> incorrect and the actual implementation does something sane. Just... wow.
>
Did you know Java is open-source nowadays?
(this is from Collections.java)
public static <T extends Comparable<? super T>> void sort(List<T> list) {
Object[] a = list.toArray();
Arrays.sort(a);
ListIterator<T> i = list.listIterator();
for (int j=0; j<a.length; j++) {
i.next();
i.set((T)a[j]);
}
}
That's the magic inside. Note it's converted into an array without first
checking what kind of list it is (even an ArrayList would suffer this
unneeded copying!).
Arrays.sort then uses clone() on the array, making yet another copy.
Apparently that's needed for the actual implementation.
(Arrays.java)
public static void sort(Object[] a) {
Object[] aux = (Object[])a.clone();
mergeSort(aux, a, 0, a.length, 0);
}
mergeSort signature is:
private static void mergeSort(Object[] src, Object[] dest,
int low, int high, int off)
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> Yeah, it just adds an extra traversal.
>
> The extra traversal can be used to perform the first partitioning
> (using eg. simply the first element as pivot), thus potentially reducing
> the overall amount of work.
Yeah, true. And that's the kind of trick Haskell's compiler is likely to
pull off too...
>> (For a merge sort, you can split a list into the even and odd elements,
>> sort, and then merge.
>
> But does this avoid creating new lists? In other words, can Haskell
> optimize it so that the merge sort is done in-place, without requiring
> any additional memory?
Well, between garbage collection, lazy evaluation and aggressive
compiler optimisations, that's not a terribly easy question to answer.
Will it do it with absolutely *no* extra memory at all? Will it
literally take a linked list in memory and just rewrite a few pointers
to make it into a sorted list? I can more or less guarantee that's a "no".
Will it eat N log N extra memory? Again, I can more or less promise you
that's a "no".
If the optimiser does what it's supposed to, and you're not holding on
to a pointer to the original, unsorted list, it should allocate new list
cells directly in sorted order, with GC cleaning up the old cells as the
become unused. [I haven't studied the algorithm in detail, but I'm
fairly confident the N log N potential intermediate lists can be elided
by the optimiser.]
Of course, if sorting is just one part of a long pipeline of list
operations, it's possible that the sorting could be partially merged
with other steps in the pipeline too... as you once said, reasoning
about Haskell program performance isn't that easy for the most part.
[The *other* possibility of course is to design your own brand new list
type that supports explicit in-place updates. But if you're that worried
about space efficiency, it'll probably be better to use an array...]
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v7 wrote:
> Yeah, true. And that's the kind of trick Haskell's compiler is likely to
> pull off too...
I thought it was pretty cool that the latest Erlang compilers will see
code like
map(F, [H|T]) -> [F(H)|map(F,T)];
map(F, []) -> [].
and turn it into the same code you'd get with an auxiliary accumulator
and a call to "reverse" at the end.
--
Darren New / San Diego, CA, USA (PST)
"That's pretty. Where's that?"
"It's the Age of Channelwood."
"We should go there on vacation some time."
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Darren New wrote:
> I thought it was pretty cool that the latest Erlang compilers will see
> code like
>
> map(F, [H|T]) -> [F(H)|map(F,T)];
> map(F, []) -> [].
>
> and turn it into the same code you'd get with an auxiliary accumulator
> and a call to "reverse" at the end.
Doesn't reverse require N operations? Wouldn't that mean that map now
takes 2N operations instead of just N?
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v7 wrote:
> Darren New wrote:
>
>> Hey, Mark Chu-Carrol. I went to grad school with him, back when he was
>> Mark Carrol. Actually, I knew his wife Chu also. :-) Funky where you
>> run across people.
>
> Not when you live by yourself in your bedroom...
>
Trying to visualize you running across people in your bedroom...
Weird.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
andrel wrote:
> Trying to visualize you running across people in your bedroom...
>
> Weird.
Not as weird as the picture *I* had in my head when I mis-parsed your
sentence as "running *across* people in your bedroom"... o_O
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v7 wrote:
> andrel wrote:
>
>> Trying to visualize you running across people in your bedroom...
>>
>> Weird.
>
> Not as weird as the picture *I* had in my head when I mis-parsed your
> sentence as "running *across* people in your bedroom"... o_O
>
Where was the mis-parsing in that?
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>>> Trying to visualize you running across people in your bedroom...
>>>
>>> Weird.
>>
>> Not as weird as the picture *I* had in my head when I mis-parsed your
>> sentence as "running *across* people in your bedroom"... o_O
>>
> Where was the mis-parsing in that?
To "run across" somebody is a figure of speach. I took it literally. [As
in, I had visions of people laying on the ground and having me run
across them, sort of like crowd surfing...]
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v7 wrote:
>>>> Trying to visualize you running across people in your bedroom...
>>>>
>>>> Weird.
>>>
>>> Not as weird as the picture *I* had in my head when I mis-parsed your
>>> sentence as "running *across* people in your bedroom"... o_O
>>>
>> Where was the mis-parsing in that?
>
> To "run across" somebody is a figure of speech. I took it literally. [As
> in, I had visions of people laying on the ground and having me run
> across them, sort of like crowd surfing...]
>
Me too. Note that English is not my mother tongue (indeed my mother has
that horrible 1950's Dutch accent when trying to speak English.) so it
is probably more easy for me to take figures of speech literally. It may
also come from reading too much Pratchett.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
andrel wrote:
>
> Me too. Note that English is not my mother tongue (indeed my mother has
> that horrible 1950's Dutch accent when trying to speak English.) <snip>
What's wrong with a Dutch accent? I used to have a Dutch gf and even now
I find English spoken with a pronounced nederlandse accent _really_ sexy.
John
--
I will be brief but not nearly so brief as Salvador Dali, who gave the
world's shortest speech. He said, "I will be so brief I am already
finished," then he sat down.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v7 wrote:
> Darren New wrote:
>
>> I thought it was pretty cool that the latest Erlang compilers will see
>> code like
>>
>> map(F, [H|T]) -> [F(H)|map(F,T)];
>> map(F, []) -> [].
>>
>> and turn it into the same code you'd get with an auxiliary accumulator
>> and a call to "reverse" at the end.
>
> Doesn't reverse require N operations? Wouldn't that mean that map now
> takes 2N operations instead of just N?
Probably. But note that map as I wrote it isn't tail recursive, unless
the compiler can do what I said. Hence, on a list of 10,000 elements,
the code there will take 10,000 stack frames. The compiler is now smart
enough to see what you're doing and generate tail-recursive code from it.
--
Darren New / San Diego, CA, USA (PST)
"That's pretty. Where's that?"
"It's the Age of Channelwood."
"We should go there on vacation some time."
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Doctor John wrote:
> andrel wrote:
>> Me too. Note that English is not my mother tongue (indeed my mother has
>> that horrible 1950's Dutch accent when trying to speak English.) <snip>
> What's wrong with a Dutch accent? I used to have a Dutch gf and even now
> I find English spoken with a pronounced nederlandse accent _really_ sexy.
>
I wasn't talking about a general modern Dutch accent but the older one
that e.g. pronounces one as 'when'. In a slightly milder form it was
also spoken by our former PM ruud lubbers IIRC. To their defense, it was
developed during the period when English lessons consisted of making
translations. No English was spoken during lessons.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
