 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
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
|
|
| |
| |
|
|
|
|
| |
|
|
