| Tim Woodall <news001@woodall.me.uk>: Nov 28 11:40PM >> about if there's an in-place solution without external memory. > It will need at least 1 temporary location to save to, but that is > enough. Depends on exactly how you define 'temporary location' but: void paws(unsigned char* a, unsigned char* b) { if((*a & 0x80) != (*b & 0x80)) { *a ^= 0x80; *b ^= 0x80; } if((*a & 0x40) != (*b & 0x40)) { *a ^= 0x40; *b ^= 0x40; } if((*a & 0x20) != (*b & 0x20)) { *a ^= 0x20; *b ^= 0x20; } if((*a & 0x10) != (*b & 0x10)) { *a ^= 0x10; *b ^= 0x10; } if((*a & 0x08) != (*b & 0x08)) { *a ^= 0x08; *b ^= 0x08; } if((*a & 0x04) != (*b & 0x04)) { *a ^= 0x04; *b ^= 0x04; } if((*a & 0x02) != (*b & 0x02)) { *a ^= 0x02; *b ^= 0x02; } if((*a & 0x01) != (*b & 0x01)) { *a ^= 0x01; *b ^= 0x01; } } on x86 I think the above could be implemented using bts/btc, but you can argue that the flag is an external bit of memory. A hypothetical processor that can "test and jump" (aka Turing Machine) has no external memory needed at all to do a swap. |
| Siri Cruise <chine.bleu@yahoo.com>: Nov 28 05:16PM -0800 In article <rpt731$i20$2@dont-email.me>, > expensive swaps of the items at the first place. How could you > rearrange the items according to the pointer-list in place with > the fewest steps without any external memory ? This is my code int stringcompare ( /*String comparison for qsort.*/ const ptr a, const ptr b ) { char **A = a, **B = b; return strcmp(*A, *B); } int unsignedcompare ( /*Unsigned number comparison.*/ const ptr a, const ptr b ) { unsigned *A = a, *B = b; return *A<*B ? -1 : *A>*B ? 1 : 0; } unsigned *stringorder ( /*Sort an array of strings. Rather than return the strings, the order of sorted strings is returned.*/ Nat n, /*Array length.*/ char **list /*Array of strings.*/ ) { typedef struct {char *s; unsigned i;} Item1; Item1 item1[n]; for (int i=0; i<n; i++) { item1[i].s = list[i]; item1[i].i = i; } qsort(item1, n, sizeof(Item1), stringcompare); typedef struct {unsigned i; unsigned o;} Item2; Item2 item2[n]; for (int i=0; i<n; i++) { item2[i].i = item1[i].i; item2[i].o = i; } qsort(item2, n, sizeof(Item2), unsignedcompare); unsigned *N = malloc(n*sizeof(unsigned)); for (int i=0; i<n; i++) N[i] = item2[i].o; return N; } -- :-<> Siri Seal of Disavowal #000-001. Disavowed. Denied. Deleted. @ 'I desire mercy, not sacrifice.' /|\ Discordia: not just a religion but also a parody. This post / \ I am an Andrea Doria sockpuppet. insults Islam. Mohammed |
| Juha Nieminen <nospam@thanks.invalid>: Nov 29 09:41AM > char **A = a, **B = b; > return strcmp(*A, *B); > } Ah, I love how in C you just implicitly cast from const void* to non-const char** without a worry in the world, happily ignoring the compiler warnings, because what does the compiler know anyway? It's just a dumb program. Also love how the comparator function is non-static, throwing it in the global namespace. Better not have any other function with that name anywhere else. But how likely is that? After all, "stringcompare" is such a unique name. The chances that anybody will ever use that same name anywhere are astronomically minuscule. |
| Siri Cruise <chine.bleu@yahoo.com>: Nov 29 02:16AM -0800 In article <rpvqc3$1cc$1@gioia.aioe.org>, > Ah, I love how in C you just implicitly cast from const void* to I love how in C++ you have a billion names of cast. Even for a strong coercion. > Also love how the comparator function is non-static, throwing it in the > global namespace. Better not have any other function with that name Yeah, because it's impossible to decorate the code if you use it. > anywhere else. But how likely is that? After all, "stringcompare" is > such a unique name. The chances that anybody will ever use that same > name anywhere are astronomically minuscule. Yeah, because it's not like the original names are different, part of collection of qsort utilities, only changed here for didactism. Fuck off, child. -- :-<> Siri Seal of Disavowal #000-001. Disavowed. Denied. Deleted. @ 'I desire mercy, not sacrifice.' /|\ Discordia: not just a religion but also a parody. This post / \ I am an Andrea Doria sockpuppet. insults Islam. Mohammed |
| Bonita Montero <Bonita.Montero@gmail.com>: Nov 29 01:52PM +0100 I wanted an in-place alortihm. |
| Kaz Kylheku <563-365-8930@kylheku.com>: Nov 29 06:28PM > non-const char** without a worry in the world, happily ignoring > the compiler warnings, because what does the compiler know anyway? > It's just a dumb program. Arguably, you can do this in Your Compiler's C, not in ISO C. The diagnostic is required by ISO C, which requires no such implicit cast to be performed. The program is not required to successfully translate at all. > anywhere else. But how likely is that? After all, "stringcompare" is > such a unique name. The chances that anybody will ever use that same > name anywhere are astronomically minuscule. In fact, stringcompare intrudes into a namespace reserved by ISO C. Programs which introduce external names beginning with "str" invoke undefined behavior. This is given in the "Future library directions" section. "Function names that begin with str, mem, or wcs and a lowercase letter may be added to the declarations in the <string.h> header." In practice, this doesn't happen just in the future; implementors add their own functions, like strdup (POSIX), strcasecmp (various?), memchr (GNU) ... If <string.h> is included, there are additional considerations in the use of those names, because <string.h> can introduce macros beginning with str. So this is required: #include <string.h> #undef stringcompare static int stringcompare(...) { ... } -- TXR Programming Language: http://nongnu.org/txr Music DIY Mailing List: http://www.kylheku.com/diy ADA MP-1 Mailing List: http://www.kylheku.com/mp1 |
| Kaz Kylheku <563-365-8930@kylheku.com>: Nov 29 06:32PM >> Ah, I love how in C you just implicitly cast from const void* to > I love how in C++ you have a billion names of cast. Even for a > strong coercion. I love how you can wrap the C++ casts behind macros, and then take advantage of them in code that compiles as C or C++: #ifdef __cplusplus #define strip_qual(TYPE, EXPR) (const_cast<TYPE>(EXPR)) #define convert(TYPE, EXPR) (static_cast<TYPE>(EXPR)) #define coerce(TYPE, EXPR) (reinterpret_cast<TYPE>(EXPR)) #else #define strip_qual(TYPE, EXPR) ((TYPE) (EXPR)) #define convert(TYPE, EXPR) ((TYPE) (EXPR)) #define coerce(TYPE, EXPR) ((TYPE) (EXPR)) 
Subscribe to:
Post Comments (Atom)
|
No comments:
Post a Comment