 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Insert-sort is an O(N^2) algorithm. It takes O(N) time to work out where
the next item needs to go, and it takes O(N) time to move all the data
down one slot in order to make room to insert the new item. And you have
to do this sequence of operations exactly N times. Hence, O(N^2).
An obvious optimisation is to do a binary search over the array. Then
you can find the correct insert-point in O(log N) time. But still it'll
take you O(N) operations to shift everything down one slot to make room.
Now, suppose I built a machine containing special RAM chips, where
there's a special signal I can send that copies the contents of every
memory register in a specified range into the next register along.
Assuming all these shifts happen concurrently, I just made shifting an
O(1) operation. (!!)
Depending on how wide your array slots are, you might need to perform
several hardware-level shifts. But since the slot size is by definition
fixed, that's still O(1).
With this hoopy trick, insert-sort suddenly becomes an O(N log N)
algorithm. (!) It takes O(log N) operations to find the insert-point,
O(1) operations to move stuff, and O(1) to actually insert the item. We
need to do this N times. O(N log N) time complexity.
Better yet, this whole shifting operation doesn't need to go through the
CPU's cache hierachy. We are completely avoiding the von Neuman
bottleneck here, and getting performance in a different complexity class
as the result.
It would of course be somewhat tricky to design a system where we can
affect a subset of the memory registers and have the time taken to do
this be independent of the size of that subrange.
The most obvious thing to do would be to specify two memory addresses
and affect everything between them. Have the address decoder send
signals to each endpoint register, and have those signals propogate in
opposite directions until they meet. But the time required to do that
would be proportional to the size of the subrange.
A better idea is for the signals to propogate to several neighboring
registers: one 1 unit away, one 2 units away, one 4 units away, and so
forth. Given that the chips have a finite capacity, you could make it
constant-time (and fast).
Of course, I don't seriously expect anybody to rush out and implement
this cool new optimisation. Why make insert-sort faster when you can
just use a better algorithm? It's just interesting that you can change
the number of operations something requires simply by redefining what
counts as an "operation".
Trouble is, this would require adding lots and lots of new circuitry to
the RAM chips, which would sit there doing nothing 99.9% of the time,
until somebody asks it to do an insert-sort. (I can't think of many
other potential uses for it.)
Still, while there seem to be rather stern limits on the bandwidth you
can have *between* chips, inside a single chip there's in principle very
much more bandwidth available. You could potentially move data between
millions of registers simultaneously.
(The tricky part is the fact that RAM almost always consists of more
than one discrete chip. But still, even if the CPU has to finish off the
transfer between the chip edges, we're still talking about a
breathtaking speedup.)
Now I'm wondering what other functions you could hypothetically get your
RAM chips to perform in parallel...
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible wrote:
> Now I'm wondering what other functions you could hypothetically get your
> RAM chips to perform in parallel...
Try taking a class about SIMD algorithm design. There's all kinds of funky
hardware interconnects you can actually do.
--
Darren New, San Diego CA, USA (PST)
C# - a language whose greatest drawback
is that its best implementation comes
from a company that doesn't hate Microsoft.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible <voi### [at] dev null> wrote:
> Insert-sort is an O(N^2) algorithm. It takes O(N) time to work out where
> the next item needs to go, and it takes O(N) time to move all the data
> down one slot in order to make room to insert the new item.
Don't you mean that it moves the data one slot *up* (iow. towards the
end of the array)? (Or is this a question of different ways of visualizing
an array? To me "up" is towards the end of the array and "down" is towards
the beginning, perhaps because "up" means "higher", in other words, higher
memory addresses.)
(And of course you could start the insertion sort from the end of the
array instead of from the beginning, in which case you would move elements
"down", ie. towards the beginning of the array...)
> And you have
> to do this sequence of operations exactly N times. Hence, O(N^2).
At least the worst case (and average) scenarios. The best-case scenario
for insertion sort is O(N).
> An obvious optimisation is to do a binary search over the array. Then
> you can find the correct insert-point in O(log N) time. But still it'll
> take you O(N) operations to shift everything down one slot to make room.
If you remove the requirement that the sorting must happen in-place and
that no extra memory (as a function of the size of the array) cannot be
used, then there's an easy way of making insertion sort O(N log N).
Curiously, this algorithm happens to be very easily expressable in C++
(by using its standard library). Suppose you have a std::vector<T> named
'v' which contains the elements to sort. You can do an "insertion sort"
like this:
std::multiset<T> tmp(v.begin(), v.end());
v.assign(tmp.begin(), tmp.end());
The first line copies all the elements in 'v' into a balanced binary
tree, and the second line copies them back to 'v'. Now they are sorted,
and in O(N log N) time.
The first line performs, technically speaking, an insertion sort in
O(N log N) (the idea is exactly the same as in insertion sort, but the
insertion of an element can be done in O(log N) time because it's a tree
and not an array).
Of course this is quite inefficient compared to more traditional
in-place O(N log N) sorting algorithms, which is why this method is not
very practical.
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Warp wrote:
> Don't you mean that it moves the data one slot *up*
Wet ink smears. Hence, people write from the top of the page towards the
bottom. Hence, lower numbers in a list are higher on the page than higher
numbers on a list.
I knew a guy who would write his assembly code with the first instructions
at the bottom of the page and work upwards for just this reason. Drove
everyone else batty.
--
Darren New, San Diego CA, USA (PST)
C# - a language whose greatest drawback
is that its best implementation comes
from a company that doesn't hate Microsoft.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Darren New <dne### [at] sanrrcom> wrote:
> Warp wrote:
> > Don't you mean that it moves the data one slot *up*
> Wet ink smears. Hence, people write from the top of the page towards the
> bottom. Hence, lower numbers in a list are higher on the page than higher
> numbers on a list.
It really becomes irritatingly confusing when people use the terms
"upcasting" and "downcasting" assuming that all the readers agree on what
they mean.
Heck, even *I* can't figure out which is which. In UML derived classes
are typically drawn *below* the base class, so "upcasting" would mean
casting from derived class to base class (I have seen this usage). On the
other hand, an inheritance hierarchy can be seen as a tree where the base
class is at the root (hence the name "base"). In this case "upcasting" would
be casting from the base class to the derived class (I have seen this usage
as well).
When I see someone using the terms, I just can't assume anything (unless
it can be unambiguously deduced from the context).
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Warp wrote:
> When I see someone using the terms, I just can't assume anything (unless
> it can be unambiguously deduced from the context).
Yep. I've been working on trying to make measurements unambiguous in my
everyday speech and my written docs. For example, your clock is not "ahead"
of my clock. It's either "showing earlier" or "showing later" than my clock.
Your colors aren't "brighter" than mine, they're either "more saturated" or
"lighter hued" or something like that.
(The one that killed me all the f'ing time was when we were selling tickets,
and the boss refused to distinguish between SKUs and individual tickets. SO
you never knew if he was talking about (for example) all the tickets to
Batman need to be able to be refunded, or the individual ticket that Fred
bought needs to be able to be refunded. Over and over I tried to get him to
distinguish between the event you're talking about and the individual piece
of paper that let you into that event, to no avail.)
I've found it's worth the effort, at least when talking to other technical
people, to be precise and consistent about such things. :-)
--
Darren New, San Diego CA, USA (PST)
C# - a language whose greatest drawback
is that its best implementation comes
from a company that doesn't hate Microsoft.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Darren New <dne### [at] sanrrcom> wrote:
> I've found it's worth the effort, at least when talking to other technical
> people, to be precise and consistent about such things. :-)
At least "big-endian" and "little-endian" are unambiguous in that
everybody uses them with the same meaning, even though the names are
completely backwards compared to what they mean (probably causing
confusion to people learning them for the first time).
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Warp wrote:
> Darren New <dne### [at] sanrrcom> wrote:
>> I've found it's worth the effort, at least when talking to other technical
>> people, to be precise and consistent about such things. :-)
>
> At least "big-endian" and "little-endian" are unambiguous in that
> everybody uses them with the same meaning, even though the names are
> completely backwards compared to what they mean (probably causing
> confusion to people learning them for the first time).
Yeah. It's the same basic problem, tho. We write the small numbers first,
and larger addresses come later on the screen.
I saw someone once arguing that a hex dump should be like this:
..... F E C D B A 9 8 7 6 5 4 3 2 1 0 | 0123456789ABCDEF
0100: 0A 41 42 43 44 45 46 47 48 49 40 20 20 20 20 20| @IHGFEDCBA\r
0110: ...
0120:
0130:
So, basically, the numbers are addressed right to left, while the text is
addressed left to right. Then little-endian is just as readable as
big-endian. While making bit zero be the LSB[1] of a byte or a register at
least has some mathematical backing, the endian-ness never seemed to really
make much difference as long as it was treated consistently, in my experience.
[1] And bit zero was the MSB on the mainframe I worked with. And, honestly,
I don't remember the endian-ness of it, because it never came up, because
the address pointing to a character was a different size than the address
pointing to a word or a double-word or whatever. If I had to guess, I'd
guess it was big-endian, but I'd have to look it up to be sure.
--
Darren New, San Diego CA, USA (PST)
C# - a language whose greatest drawback
is that its best implementation comes
from a company that doesn't hate Microsoft.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Am 02.08.2010 21:16, schrieb Darren New:
>> At least "big-endian" and "little-endian" are unambiguous in that
>> everybody uses them with the same meaning, even though the names are
>> completely backwards compared to what they mean (probably causing
>> confusion to people learning them for the first time).
>
> Yeah. It's the same basic problem, tho. We write the small numbers
> first, and larger addresses come later on the screen.
Actually the terms "big-endian" and "little-endian" are only confusing
as long as you don't know about their etymology. If you do, it's
actually pretty easy to remember that "big-endian" is, of course, the
byte ordering that /starts/ with the "big end".
Aside from that, the knowledge also helps to lean back and grin a deep
grin about the unintended hidden irony in rants like "little-endian byte
order clearly gets it all wrong, big-endian is the only sane thing!" -
or just vice versa. Yeah, sure, eggheads :-)
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 02/08/2010 10:27 PM, clipka wrote:
>
> Actually the terms "big-endian" and "little-endian" are only confusing
> as long as you don't know about their etymology. If you do, it's
> actually pretty easy to remember that "big-endian" is, of course, the
> byte ordering that /starts/ with the "big end".
I thought it was all about which way you opened your boiled egg.
--
Best Regards,
Stephen
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Am 02.08.2010 23:44, schrieb Stephen:
> On 02/08/2010 10:27 PM, clipka wrote:
>>
>> Actually the terms "big-endian" and "little-endian" are only confusing
>> as long as you don't know about their etymology. If you do, it's
>> actually pretty easy to remember that "big-endian" is, of course, the
>> byte ordering that /starts/ with the "big end".
>
> I thought it was all about which way you opened your boiled egg.
Exactly. With the people being named according to the end where they
opened it and, hence, /started eating/ it. I.e., "big-endians" /started/
at the egg's big end.
(I must confess I probably wouldn't have learned which is which to this
day, if it wasn't for this background knowledge.)
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 02/08/2010 11:30 PM, clipka wrote:
> (I must confess I probably wouldn't have learned which is which to this
> day, if it wasn't for this background knowledge.)
I read the book.
--
Best Regards,
Stephen
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
clipka wrote:
> byte ordering that /starts/ with the "big end".
But that's my point. "Starts" and "ends" is meaningless. The MSB is either
at the lowest address space or it's at the highest address space. The only
reason we think of "starts" and "ends" that was is we write from left to
right. I suspect "big endian" and "little endian" would be confusing to
those speaking hebrew, arabic, or whatever version of chinese goes from top
to bottom.
I mean, if the terms were in chinese, they'd be "highendian" and
"lowendian", and you'd have a heck of a time guessing what that's supposed
to mean.
> or just vice versa. Yeah, sure, eggheads :-)
Well, there's arguments for both that make sense. But it's really quite
arbitrary exactly because there *are* arguments for both.
--
Darren New, San Diego CA, USA (PST)
C# - a language whose greatest drawback
is that its best implementation comes
from a company that doesn't hate Microsoft.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Am 03.08.2010 02:20, schrieb Darren New:
> clipka wrote:
>> byte ordering that /starts/ with the "big end".
>
> But that's my point. "Starts" and "ends" is meaningless. The MSB is
> either at the lowest address space or it's at the highest address space.
> The only reason we think of "starts" and "ends" that was is we write
> from left to right. I suspect "big endian" and "little endian" would be
> confusing to those speaking hebrew, arabic, or whatever version of
> chinese goes from top to bottom.
Huh?
Processors /do/ have a "native" ordering of the memory words: The
typical direction of program flow. While this may theoretically differ
between processors just like the writing direction does between
languages (though I've never seen a processor so far that would
decrement its program counter, but maybe some might use gray code
addresses), it still defines a unique logical "start" and "end" - just
like there is a unique logical "start" and "end" in each written text
(though in some writing systems you may have to guess that start and end
from the content or context, and of course you'll have the occasional
sample where start and end are intentionally ambiguous for artistic
reasons).
It is "top" and "bottom", "left" and "right" that are meaningless in the
context of memory layout, but "start" and "end" are absolutely not: They
might be different between processors, too, but they're always
unambiguous and meaningful.
> I mean, if the terms were in chinese, they'd be "highendian" and
> "lowendian", and you'd have a heck of a time guessing what that's
> supposed to mean.
Not really - note that we don't call them "left-endian" or
"right-endian" either.
They're called "big-endian" and "little-endian" not because a particular
byte is on the "biggest" (or "smallest") address, but because the
"biggest" byte (=MSB, or "smallest" byte =LSB) comes first in memory.
/And/ these particular terms are used because they had already been used
in different context and... well, let's put it this way: It wasn't the
byte ordering zealots that suggested them. Abso-bloody-lutely not. I
guess they were rather pissed off when the terms first came up in this
use. Well, those that knew the story behind it, that is.
>> or just vice versa. Yeah, sure, eggheads :-)
>
> Well, there's arguments for both that make sense. But it's really quite
> arbitrary exactly because there *are* arguments for both.
... which, as a matter of fact, is exactly why the terms "big-endian"
and "little-endian" so beautifully hit home.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
clipka wrote:
> It is "top" and "bottom", "left" and "right" that are meaningless in the
> context of memory layout, but "start" and "end" are absolutely not:
If you have a machine whose instructions are all 32-bits long, asking the
order of bytes within a machine word might not make much sense.
But OK, I'll grant you that "low address" chronologically comes before "high
address" for at least some instructions, generally speaking.
> They're called "big-endian" and "little-endian" not because a particular
> byte is on the "biggest" (or "smallest") address, but because the
> "biggest" byte (=MSB, or "smallest" byte =LSB) comes first in memory.
I know that. I was arguing about "first" in memory, not "biggest" address.
Indeed, I'd say "bigger address" makes more sense / is less ambiguous than
"first address". But all the memory is there all the time. To call one
memory address "before" another, you have to have some chronological
ordering of memory addresses. Which you pointed out is the auto-increment
types of instructions, including the implicit auto-increment of the PC.
> ... which, as a matter of fact, is exactly why the terms "big-endian"
> and "little-endian" so beautifully hit home.
Yep.
--
Darren New, San Diego CA, USA (PST)
C# - a language whose greatest drawback
is that its best implementation comes
from a company that doesn't hate Microsoft.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Le 02/08/2010 17:46, Invisible a écrit :
> Insert-sort is an O(N^2) algorithm. It takes O(N) time to work out where
> the next item needs to go, and it takes O(N) time to move all the data
> down one slot in order to make room to insert the new item. And you have
> to do this sequence of operations exactly N times. Hence, O(N^2).
> Now, suppose I built a machine containing special RAM chips, where
> there's a special signal I can send that copies the contents of every
> memory register in a specified range into the next register along.
> Assuming all these shifts happen concurrently, I just made shifting an
> O(1) operation. (!!)
Congratulations,
that the difference between a linked list to store your data, and an
indexed array.
>
> Depending on how wide your array slots are, you might need to perform
> several hardware-level shifts. But since the slot size is by definition
> fixed, that's still O(1).
If instead of a single value, the cells of your array contains also a
pointer to the next value in the list, you could sort it without moving
the value, and only updating the "next" index field.
That approach is trading memory (an additional explicit next-index value
for each cell) for better performance.
Notice: the size of the values to sort might be bigger than the value of
the next-index field, which only need to be able to store about the size
of the array in term of cells.
--
A: Because it messes up the order in which people normally read text.<br/>
Q: Why is it such a bad thing?<br/>
A: Top-posting.<br/>
Q: What is the most annoying thing on usenet and in e-mail?
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Le_Forgeron <lef### [at] freefr> wrote:
> If instead of a single value, the cells of your array contains also a
> pointer to the next value in the list, you could sort it without moving
> the value, and only updating the "next" index field.
How would you find the proper place for the value faster than O(n)?
Performing insertion sort on a linked list is still O(n^2) even though
the insertion itself can be done in constant-time. That's because finding
the point of insertion takes O(n) time.
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
|
|
