![](/i/fill.gif) |
![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Le_Forgeron <lef### [at] free fr> 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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |