twitter: comp.lang.c - 25 new messages in 16 topics

comp.lang.c
http://groups.google.com/group/comp.lang.c?hl=en

comp.lang.c@googlegroups.com

Today's topics:

==============================================================================
TOPIC: Is it invoking UB ?!
http://groups.google.com/group/comp.lang.c/t/5421e03087caabdd?hl=en
==============================================================================

== 1 of 2 ==
Date: Sun, Oct 4 2009 8:14 am
From: Debanjan

On Oct 4, 5:30 pm, Seebs <usenet-nos...@seebs.net> wrote:
> On 2009-10-04, Debanjan <debanjan4...@gmail.com> wrote:
>
> > But in the code we are no where modifying the value of the array y ..
> > So Why the problem with y ? the result seems working fine.
>
> ANYTHING CAN HAPPEN.
>
> This does not mean "you might get one of two or three behaviors which are
> totally obvious to you".
>
> If you feel that something in y is being modified, one reason might be that
> you modified space outside some other object, which happened to overlap
> with where y was. Another reason might be that, well, anything can happen.
>
> -s
> --
> Copyright 2009, all wrongs reversed. Peter Seebach / usenet-nos...@seebs.nethttp://www.seebs.net/log/<-- lawsuits, religion, and funny pictureshttp://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!

hm,.. this clears my doubt. Thank you :)

== 2 of 2 ==
Date: Sun, Oct 4 2009 10:11 am
From: James Kuyper

Debanjan wrote:
> On Oct 4, 4:06�pm, Seebs <usenet-nos...@seebs.net> wrote:
>> On 2009-10-04, Debanjan <debanjan4...@gmail.com> wrote:
>>
>>> A code snippet looks likes this :
>> Ignoring your decision to use C++ output functions:
>>
>>> � �int x[5]={1,2,3,4,5},y[5]={5,4,3,2,1},result[5]={0,0,0,0,0};
>>> � �int j=0;
>>> � �while(j++<5)
>>> � � � � �result[j]=x[j]-y[j];
>> This does indeed invoke undefined behavior. �You are probably thinking
>> that the "j++", being a postincrement, gives you the "previous" value of j,
>> but by the time the "result=..." thing happens, j is 5, and you're both
>> modifying and accessing things outside the bounds of the arrays.
>>
>
> But in the code we are no where modifying the value of the array y ..
> So Why the problem with y ? the result seems working fine.

How do you know that? The behavior is undefined, which means it's
entirely possible that the array y is being modified.

==============================================================================
TOPIC: "error: invalid preprocessing directive #DEFINE"
http://groups.google.com/group/comp.lang.c/t/45e8c40b7a06745d?hl=en
==============================================================================

== 1 of 5 ==
Date: Sun, Oct 4 2009 8:17 am
From: "Malcolm McLean"

"alien" <anders.refslund@gmail.com> wrote in message
news:f8fc0570-9e1a-4cf0-8dd4-26b9c0c9cdbe@j9g2000vbp.googlegroups.com...
> When i'm trying to compile a program with #DEFINE it says:
> 2:2: error: invalid preprocessing directive #DEFINE
>
> Why, and how do i fix it?
#define

Somehow you must have got a c source file from an oddball system that
doesn't have lower case.

== 2 of 5 ==
Date: Sun, Oct 4 2009 8:20 am
From: Eric Sosman

alien wrote:
> When i'm trying to compile a program with #DEFINE it says:
> 2:2: error: invalid preprocessing directive #DEFINE
>
> Why, and how do i fix it?

Try #define.

(Language lawyers: Was his compiler justified in
rejecting his code, assuming that it did? See 6.10,
fourth production of group-part; the Standard says very
little about this topic.)

--
Eric Sosman
esosman@ieee-dot-org.invalid

== 3 of 5 ==
Date: Sun, Oct 4 2009 8:24 am
From: kr0wie

On Oct 4, 5:17 pm, "Malcolm McLean" <regniz...@btinternet.com> wrote:
> "alien" <anders.refsl...@gmail.com> wrote in message
>
> news:f8fc0570-9e1a-4cf0-8dd4-26b9c0c9cdbe@j9g2000vbp.googlegroups.com...> When i'm trying to compile a program with #DEFINE it says:
> > 2:2: error: invalid preprocessing directive #DEFINE
>
> > Why, and how do i fix it?
>
> #define
>
> Somehow you must have got a c source file from an oddball system that
> doesn't have lower case.

Okay. It works with #define, thanks for the quick answer.

== 4 of 5 ==
Date: Sun, Oct 4 2009 8:28 am
From: Joe Wright

alien wrote:
> When i'm trying to compile a program with #DEFINE it says:
> 2:2: error: invalid preprocessing directive #DEFINE
>
> Why, and how do i fix it?

C is case sensitive. It is #define that you want.

--
Joe Wright
"If you rob Peter to pay Paul you can depend on the support of Paul."

== 5 of 5 ==
Date: Sun, Oct 4 2009 8:51 am
From: Richard Heathfield

In <haaeh1$2bu$1@news.eternal-september.org>, Eric Sosman wrote:

> alien wrote:
>> When i'm trying to compile a program with #DEFINE it says:
>> 2:2: error: invalid preprocessing directive #DEFINE
>>
>> Why, and how do i fix it?
>
> Try #define.
>
> (Language lawyers: Was his compiler justified in
> rejecting his code, assuming that it did? See 6.10,
> fourth production of group-part; the Standard says very
> little about this topic.)

If not, then # becomes a rather odd but perfectly legal line-comment
character, with the added spice that not all comments are legal.

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
"Usenet is a strange place" - dmr 29 July 1999
Sig line vacant - apply within

==============================================================================
TOPIC: why don't y'all shut up already?
http://groups.google.com/group/comp.lang.c/t/df8676ac26ba493a?hl=en
==============================================================================

== 1 of 1 ==
Date: Sun, Oct 4 2009 8:21 am
From: "Tech07"

I am selfish. I know too much. :(

==============================================================================
TOPIC: I am a liar
http://groups.google.com/group/comp.lang.c/t/e5be07eff59aa1e6?hl=en
==============================================================================

== 1 of 1 ==
Date: Sun, Oct 4 2009 8:23 am
From: "Tech07"

in your room.

==============================================================================
TOPIC: You've crippled me
http://groups.google.com/group/comp.lang.c/t/1b5d2aac48a592d8?hl=en
==============================================================================

== 1 of 1 ==
Date: Sun, Oct 4 2009 8:26 am
From: "Tech07"

hmm?

==============================================================================
TOPIC: انثى أختصرت إناث الأرض!!!!!
http://groups.google.com/group/comp.lang.c/t/6331b38d3801cc5c?hl=en
==============================================================================

== 1 of 1 ==
Date: Sun, Oct 4 2009 8:32 am
From: املي

فوائد الرمان
http://www.hmzzh.com/vb/t539.html
برنامج ابتسامات واشكال تموت من الضحك للمسنجر(تحديث
http://www.hmzzh.com/vb/t538.html
نيك نيمات رووووووووعة للمسنجر
http://www.hmzzh.com/vb/t537.html
توبيكات فراق و حب ملونه مع اكوادها
http://www.hmzzh.com/vb/t536.html
طريقة تعطيل الكاميرا في حاسوبك لحمايتك
http://www.hmzzh.com/vb/t535.html
صور ديكور حمامات بصيغة غرف نوم..!
http://www.hmzzh.com/vb/t534.html
فساتين صيفية خطيرة
http://www.hmzzh.com/vb/t533.html
ازياء جميله لاحلى مراهقات بالكون
http://www.hmzzh.com/vb/t532.html
شوية بلوزات دلع
http://www.hmzzh.com/vb/t531.html
لبسة شيك من الوان الخريف الانيقة
http://www.hmzzh.com/vb/t530.html
كولكشن بنآآآآآآت
http://www.hmzzh.com/vb/t529.html
لانجري 2009اشكال رووعة
http://www.hmzzh.com/vb/t528.html
لانجيريهات جديدة بألوان روووووووعة حصرى
http://www.hmzzh.com/vb/t527.html
مجموعة لانجرى تتطير العقل
http://www.hmzzh.com/vb/t526.html
كوني دلوعه حتى و انت ذاهبه الى الفراش
http://www.hmzzh.com/vb/t525.html
ملابس نوم لك و لعريسك
http://www.hmzzh.com/vb/t524.html
بيجامات حرير ودلع؟؟؟!!!
http://www.hmzzh.com/vb/t523.html
لانجيرى الوانه كلها رقه
http://www.hmzzh.com/vb/t522.html
**لانجيرى و ملابس للنوم للقمرات**
http://www.hmzzh.com/vb/t521.html
لانجيرى اخر شقاوة
http://www.hmzzh.com/vb/t520.html
لانجري بالاحمر ل2009
http://www.hmzzh.com/vb/t519.html
تشكيلة لانجري من إختياري
http://www.hmzzh.com/vb/t518.html
اجدد ازياء البيت
http://www.hmzzh.com/vb/t517.html
ترحيب معطرة
http://www.hmzzh.com/vb/t516.html
مكياج لاحلى عرايس ناااااعم
http://www.hmzzh.com/vb/t515.html
مكياج بايدي امارتية..........
http://www.hmzzh.com/vb/t514.html
صور مكياج و تسريحات لحفلات الخطوبة
http://www.hmzzh.com/vb/t513.html
تسريحات جذابة لعروس 2009
http://www.hmzzh.com/vb/t512.html
طريقة مكياجك ياعروس كامل لجميع المناسبات بالصور
http://www.hmzzh.com/vb/t511.html
لكل عروس ادخلي
http://www.hmzzh.com/vb/t510.html
انثى أختصرت إناث الأرض!!!!!
http://www.hmzzh.com/vb/t509.html
تسريحات خطيرة لكم
http://www.hmzzh.com/vb/t508.html
علاج ظاهرة الكذب - عند الاطفال
http://www.hmzzh.com/vb/t507.html
ظاهرة الخـّدامات والمخدومات في الخليج
http://www.hmzzh.com/vb/t506.html
صور سيارات بشعه .. ليش اقول ...... أدخل وشوف بنفسك..!
http://www.hmzzh.com/vb/t505.html
سيارة الوليد بن طلال - وفقراء العالم

http://www.hmzzh.com/vb/t504.html

==============================================================================
TOPIC: this is so wrong
http://groups.google.com/group/comp.lang.c/t/4d481a9a9056f5d5?hl=en
==============================================================================

== 1 of 1 ==
Date: Sun, Oct 4 2009 8:33 am
From: "Tech07"

I'll tell ya later

==============================================================================
TOPIC: adios and vaya con dios
http://groups.google.com/group/comp.lang.c/t/ab828fe7d1479023?hl=en
==============================================================================

== 1 of 1 ==
Date: Sun, Oct 4 2009 8:55 am
From: "Tech07"

I'm just kidding. there'll be time enough for countin...

==============================================================================
TOPIC: typedef usage
http://groups.google.com/group/comp.lang.c/t/5d3b817d095d4c86?hl=en
==============================================================================

== 1 of 2 ==
Date: Sun, Oct 4 2009 8:58 am
From: "BGB / cr88192"

"Joachim Schmitz" <nospam.jojo@schmitz-digital.de> wrote in message
news:haa4pm$6of$1@online.de...
> BGB / cr88192 wrote:
> snip
>> I don't use this style personally (AKA: I use lots of typedefs).
>
> ITYM (I Think You Ment) IOW (In Other Words) rather than AKA (Also Known
> As)
>
> PCMCIA (People Can't Memorize Computer Industries Acronyms)
>

yeah, IOW would have been maybe better...
AKA works I think, since it has the same basic meaning AFAICT.

or such...

> Bye, Jojo

== 2 of 2 ==
Date: Sun, Oct 4 2009 10:07 am
From: James Kuyper

BGB / cr88192 wrote:
> "Joachim Schmitz" <nospam.jojo@schmitz-digital.de> wrote in message
> news:haa4pm$6of$1@online.de...
>> BGB / cr88192 wrote:
>> snip
>>> I don't use this style personally (AKA: I use lots of typedefs).
>> ITYM (I Think You Ment) IOW (In Other Words) rather than AKA (Also Known
>> As)
>>
>> PCMCIA (People Can't Memorize Computer Industries Acronyms)
>>
>
> yeah, IOW would have been maybe better...
> AKA works I think, since it has the same basic meaning AFAICT.

No, it does not. AKA introduces an alternative name for something.
AFAICT indicates a certain low amount of uncertainty about the accuracy
of the following statement. Neither abbreviation fits the above context.

==============================================================================
TOPIC: Call oddities: &Test() vs &Test vs Test
http://groups.google.com/group/comp.lang.c/t/04cf2e4b2fab1615?hl=en
==============================================================================

== 1 of 1 ==
Date: Sun, Oct 4 2009 9:10 am
From: "Skybuck Flying"

Hello,

There are some call oddities in both languages: Delphi and C.

The purpose of a language is to tell the computer what to do... but ofcourse
a language is also for us humans to understand what is written/ment.

Therefore it would be a nobble cause to try and make the language as clearly
as possible.

I now present to you some "cases" where both languages Delphi and C fail in
this regard:

Case 1 (Delphi):

IdentifierA = IdentifierB;

From this single line of code it cannot be said if IdentifierB is a field or
a routine call yet it's still allowed to be written in Delphi. Correct
translation from Delphi to C/C++ without more information, is therefore not
possible.

Case 2 (C):

IdentifierB;

From this single line of code it cannot be said if IdentifierB is a field or
a routine yet it's still allowed to be written in C. If IdentiferB is a
routine then no call will happen, which is inconsistent with Delphi and
could lead to bugs when translating from Delphi to C/C++. Correct
translation from Delphi to C/C++ without more information, is therefore not
possible.

Case 3 (Delphi):

if (Identifier) then

From this single line of code it cannot be said if Identifier is a field or
a routine call yet it's still allowed to be written in Delphi. Correct
translation from Delphi to C/C++ without more information, is therefore not
possible.

The question is can the situation be improved ?

A possible solution could be to make the () for routine calls mandatory.

Also for acquiring a pointer to a routine the () could be mandatory.

Instead of writing:

IdentifierA = &IdentifierB;

It would become:

IdentifierA = &IdentifierB();

Which would return the address of the routine IdentifierB.

IdentifierA = &IdentifierB()();

Would return the address of the second routine which is being called by the
function pointer returned by the first routine.

(Note: Delphi does not have this functionality: Calling a returned function
pointer immediatly).

Currently the situation is reserved to acquire a pointer to a routine in C
the () must not be written:

IdentifierA = &Identifier;

The question is:

Would any functionality in C be lost if this is changed to described as
above:

IdentifierA = &Identifier();

Bye,
Skybuck.

==============================================================================
TOPIC: I'm gonna do all I can
http://groups.google.com/group/comp.lang.c/t/6940aac6472b1eff?hl=en
==============================================================================

== 1 of 1 ==
Date: Sun, Oct 4 2009 9:19 am
From: "Tech07"

...for my Lord.

==============================================================================
TOPIC: I am afraid of you
http://groups.google.com/group/comp.lang.c/t/41acb3d1c0d58fa0?hl=en
==============================================================================

== 1 of 2 ==
Date: Sun, Oct 4 2009 9:25 am
From: "Tech07"

== 2 of 2 ==
Date: Sun, Oct 4 2009 9:28 am
From: "Tech07"

==============================================================================
TOPIC: you wouldn't know a train
http://groups.google.com/group/comp.lang.c/t/e13b5455fc6705ec?hl=en
==============================================================================

== 1 of 1 ==
Date: Sun, Oct 4 2009 9:39 am
From: "Tech07"

if it hit you in the ass.

==============================================================================
TOPIC: information
http://groups.google.com/group/comp.lang.c/t/1e458a236af3b281?hl=en
==============================================================================

== 1 of 1 ==
Date: Sun, Oct 4 2009 10:03 am
From: James Kuyper

Joe Wright wrote:
> Richard Heathfield wrote:
...
>> Since the Standard does say otherwise, and since the Standard is right
>> by definition, I conclude that your point is mistaken. You said that
>> bwk outranks me. Well, so he does - but, by the same token, sure as
>> eggs is eggs the ISO guys outrank you. So if you find your logic
>> compelling, consistency demands that you apply it to your own claim.
>>
> Since the Standard is right by definition,

The standard defines what C is; it can be inconsistent, in can differ
from what the authors intended, it can be badly designed. The one thing
it can't do is incorrectly define C, because there is no more
authoritative definition of what C is, to which it can be compared and
found wanting.

> ... there is no point in my
> disagreeing with anything you think it says.

If you believe that he thinks incorrectly about what it says, there's a
point in presenting the evidence that justifies your belief.

> ... But please consider..
>
> char *buff = malloc(80);
>
> The pointer buff is an lvalue (object) accepting the assignment of the
> address of some memory returned by malloc. Expressing buff in rvalue
> context yields the address value. Do you insist that this value is a
> pointer? (Yes, it does have pointer type.)

Yes, it is a pointer value. No, it is not a pointer object. Yes the
standard says it is a pointer, with the expectation that the reader will
be able to disambiguate that as meaning "pointer value".

==============================================================================
TOPIC: Selection-Sort in C
http://groups.google.com/group/comp.lang.c/t/08ea5572bc2a2f18?hl=en
==============================================================================

== 1 of 3 ==
Date: Sun, Oct 4 2009 10:09 am
From: pete

Tim Rentsch wrote:
> Eric Sosman <esosman@ieee-dot-org.invalid> writes:
>
>
>>arnuld wrote:
>>
>>>>On Tue, 29 Sep 2009 13:04:11 +0200, Edwin van den Oetelaar wrote:
>>>
>>>>If this is your source how can it give this answer. Do you want
>>>>bubble-sort or selection-sort ?
>>>
>>>I really don't have any idea. I just look at the given O(n) notation
>>>and decide.
>>>
>>>
>>>
>>>
>>>>this hurts my head.
>>>
>>>Why ?
>>
>> Maybe because bubble sort is the worst[*][**] sorting
>>algorithm known to Man?
>
>
> Bubble sort has these advantages. It is easy to understand,
> easy to program, easy to get right, and relies solely on
> local operations. It is also stable.
>
> Selection sort is easy to understand, and not too bad to
> program, but it is not stable.
>
> Insertion sort is stable and easy to understand, but
> programming it takes just a little more care than
> bubble sort. The natural desire to improve the
> search for insertion points (by using binary search)
> makes it more complicated.
>
> Quick sort is easy to understand, at least conceptually,
> but programming it takes a certain amount of care,
> especially if an effort is made to minimize the chances
> for N**2 behavior or use of linear stack space. It
> also isn't stable.
>
> Heap sort isn't easy to understand, isn't nearly so easy
> to program, is easy to get wrong, and /always/ is doing
> non-local operations; it also isn't stable. Heap sort
> is a great sorting algorithm. :)
>
> Merge sort is usually dismissed because of needing extra
> space. Yes it's possible to do a stable merge sort on an
> array and use only O(1) extra space, but programming that is
> horrendous.
>
>
>
>> [***] Yes, despite my own ferreting out of an O(N*N*logN)
>>sort in actual production code. The sort algorithm itself was
>>fine, O(N*logN), but the careless programmer had handed it an
>>O(N) comparison function ...
>
>
> Even that's not as bad as the O(N**3) sort algorithm used
> many years ago in a certain operating system's "help"
> command...

--
pete

== 2 of 3 ==
Date: Sun, Oct 4 2009 10:12 am
From: pete

Tim Rentsch wrote:

> Insertion sort is stable and easy to understand, but
> programming it takes just a little more care than
> bubble sort. The natural desire to improve the
> search for insertion points (by using binary search)
> makes it more complicated.

Today for no particular reason,
I wrote a stable, in place, binary insertion sort.

/* BEGIN output from bisort_test.c */

Arrays of (char *),
are being sorted by string length.

Original order of the test array:
zero
one
two
three
four
five
six
seven
eight
nine
ten

Stable binary insertion sort:
one
two
six
ten
zero
four
five
nine
three
seven
eight

/* END output from bisort_test.c */

/* BEGIN bisort_test.c */

#include <stdio.h>
#include <string.h>

#define SORT_FUNCTIONS { \
nosort, "Original order of the test array:", \
bisort, "Stable binary insertion sort:" \
}
#define NUMBERS { \
"zero","one","two","three","four","five", \
"six","seven","eight","nine","ten" \
}
#define NMEMB (sizeof numbers / sizeof *numbers)
#define SORTS (sizeof s_F / sizeof *s_F)

int comp(const void *a, const void *b);
void nosort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *));
void bisort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *));

int main(void)
{
size_t element, sort;
struct sf {
void (*function)(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *));
const char *description;
} s_F[] = SORT_FUNCTIONS;
const char *numbers[] = NUMBERS;
char *array[NMEMB];

puts("\n/* BEGIN output from bisort_test.c */\n\n"
"Arrays of (char *),\n"
"are being sorted by string length.\n");
for (sort = 0; sort != SORTS; ++sort) {
memcpy(array, numbers, sizeof array);
s_F[sort].function(array, NMEMB, sizeof *array, comp);
puts(s_F[sort].description);
for (element = 0; element != NMEMB; ++element) {
puts(array[element]);
}
putchar('\n');
}
puts("/* END output from bisort_test.c */");
return 0;
}

int comp(const void *a, const void *b)
{
const size_t a_len = strlen(*(const char **)a);
const size_t b_len = strlen(*(const char **)b);

return b_len > a_len ? -1 : b_len != a_len;
}

void nosort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *))
{
base, nmemb, size, compar;
}

void bisort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *))
{
size_t bytes = 0;
const size_t odd_size = size ^ size - 1;
unsigned char *key = base;
unsigned char *const array = key;

while (nmemb-- > 1) {
unsigned char *end;
size_t n;
size_t low = 0;
size_t high = bytes + size;

bytes = high;
key += size;
do {
size_t middle = low;

n = high - middle;
middle += (n & odd_size ? n - size : n) >> 1;
if (0 > compar(key, middle + array)) {
high = middle;
} else {
low = middle;
}
} while (n != size);
if ((end = array + high) != key) {
unsigned char *start = key;
unsigned char *const after = start + size;

do {
unsigned char *p1 = start;
unsigned char *p2 = p1;
const unsigned char temp = *p1;

do {
*p1 = *(p2 -= size);
} while ((p1 = p2) != end);
*p1 = temp;
++end;
} while (++start != after);
}
}
}

/* END bisort_test.c */

--
pete

== 3 of 3 ==
Date: Sun, Oct 4 2009 10:25 am
From: cri@tiac.net (Richard Harter)

On Sun, 04 Oct 2009 13:52:48 +0100, Ben Bacarisse
<ben.usenet@bsb.me.uk> wrote:

[snip a lot of stuff - look at the previous postings if you want
background]

>That's another matter altogether. Sorting is a problem not an
>algorithm.

None-the-less it makes sense to speak of order functions for
problems. Given a problem, there will be a wide variety of
algorithms that can be used to solve it. The intrinsic cost of
solving that problem is the cost of the best algorithms. Thus it
makes sense to say that the traveling salesman problem is
exponential. There is an implicit assumption here that the
algorithms run on a Turing machine equivalent.

>Personally, I'd never say that sorting is O(f) for any f
>since I don't know of any results of that kind for this class of
>problem (I am sure there are some, I just don't know any). Whilst I
>agree one can allow some of the things I listed to be unstated for an
>/algorithm/[1], I don't think any can left out when discussing a
>/problem/.

But they can - it's just a matter of abstraction.
>
>BTW, I will be mildly peeved if the big assumption you think I am
>making is to assume that all sorting algorithms are comparison sorts.
>Your posting history suggest to me that you might have something more
>interesting in mind, but I honestly have no idea what is encompassed
>by your notion of "natural".

I'm wasn't but prepare to be disappointed - I expect your
reaction will be "Is that all?". You asked, quite properly, what
does n denote. And the answer is, and I quote, "data sets of
size n". But what how do you measure size? The natural
measurement of the size of a data set is the amount of storage it
occupies. For specialized data sets such as arrays of elements
it is convenient to use the number of elements as a measure of
size, but it the actual number of bits that is primary. (Don't
argue with me on this point; I'm right by definition. :-))

The thing is, sorting algorithms are developed in terms of
operations on elements so it is natural to characterize their
performance in terms of number of elements with an implict
assumption that the cost of operations on elements is O(1). It's
a convenient assumption that works in practice, because real
sorting problems are of bounded size. However the assumption
creates a blind spot - as the number of distinct elements
increases the intrinsic cost of basic operations also increases.
This increase in cost is usually ignored in analysis.

At this point you may be shaking your head and saying, "So what,
why does it matter?" For most of us, I suppose it doesn't - or
at least we think it doesn't. One place where it matters is in
large systems analysis. The issue is: Does sorting scale?
Primary operations (the things that you use for black boxes)
scale it the cost per data unit passing through the box is O(1).
(That's another definition; don't argue. :-)) So, if you are
thinking in terms of counting elements, sorting doesn't scale; if
you are thinking in terms of counting data volume it does -
perhaps.

After all, we need to establish whether sorting actually is
Theta(n) where n is the number of bits in the data set. The
lower bound is clear enough - whatever the algorithm an oracle
can force it to examine every bit. The upper bound is a bit
murkier. The simple argument runs like this:

Let m be the number of elements and n be the total data set size.
Comparison sorts require O(m * log m) operations. However if
there are m distinct elements then the average size of an element
has to be >= log m. Ergo n >= m * log m. Ergo O(n) is an upper
bound.

There are some fiddles you have to go through to account for
duplicate elements but they're trivial. More importantly, naive
comparisons have a cost of n/m >= log m. However there are
various tricks that can be used to tag the bit/byte position.
The upshot is that the comparison cost can be reduced to O(1).

Where things get murky is the question of data movement. In most
sorting algorithms all of the data is potentially moved log m
times for a n*log(m) cost. However one can avoid moving data by
working with data indices. (With the aid of some hair this can
be done in an O(1) per data bit way.) Give a subsidiary
permutation array all of the data can be moved into place as an
O(n) operation - if setting a bit in an arbitrary location is an
O(1) operation. The trouble is that for an arbitrarily large
address space this is problematic. The upshort is that sorting
isn't really O(n) but if we make assumptions that apply within
ordinary computation it is.

By the by, this little insight seems to be harder to arrive at
than I suppose it to be. When my crackpot was posting everybody
told him he was crazy and nobody caught on that he was talking
about apples whereas they were talking about oranges. Using his
n he was right - sort of. He didn't take into all of the costs
for larg n.

Richard Harter, cri@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Kafka wasn't an author;
Kafka was a prophet!

==============================================================================
TOPIC: ANN An ansic90 version of lcc-win
http://groups.google.com/group/comp.lang.c/t/a2324121ef231067?hl=en
==============================================================================

== 1 of 1 ==
Date: Sun, Oct 4 2009 10:31 am
From: Richard

Tim Rentsch <txr@alumni.caltech.edu> writes:

> Richard Heathfield <rjh@see.sig.invalid> writes:
>
>> In <lnbpkqmzj6.fsf@nuthaus.mib.org>, Keith Thompson wrote:
>>
>> <snip>
>>
>>> (Incidentally, I don't find RH's posting style to be particularly
>>> pompous,
>>
>> Neither do I, but I can see why some might think so. My dictionary
>> gives two senses of "pompous", one of which is "inappropriately grand
>> and flowery; pretentious". There is a considerable body of evidence
>> to suggest that there are those who consider a Usenet article with
>> correct spelling, punctuation, and grammar to be inappropriately
>> grand and flowery.
>
> There are plenty of other posters who strive to use
> correct spelling, punctuation, and grammar, but whose
> postings are not accused of being pompous.

There is a difference between the above and being an arrogant arse.

==============================================================================

You received this message because you are subscribed to the Google Groups "comp.lang.c"
group.

To post to this group, visit http://groups.google.com/group/comp.lang.c?hl=en

To unsubscribe from this group, send email to comp.lang.c+unsubscribe@googlegroups.com

To change the way you get mail from this group, visit:
http://groups.google.com/group/comp.lang.c/subscribe?hl=en

To report abuse, send email explaining the problem to abuse@googlegroups.com

==============================================================================
Google Groups: http://groups.google.com/?hl=en

twitter

Sunday, October 4, 2009

comp.lang.c - 25 new messages in 16 topics - digest

0 Comments:

Post a Comment

About Me

Previous Posts