| Bonita Montero <Bonita.Montero@gmail.com>: Nov 28 11:00AM +0100 Imagine you sort a list of pointers to a list of items to prevent 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 ? |
| Melzzzzz <Melzzzzz@zzzzz.com>: Nov 28 10:49AM > 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 ? In my experience sorting list by pointer is much slower then swaps and rearagning access order, makes slow traversal afterwards. -- current job title: senior software engineer skills: c++,c,rust,go,nim,haskell... press any key to continue or any other to quit... U ničemu ja ne uživam kao u svom statusu INVALIDA -- Zli Zec Svi smo svedoci - oko 3 godine intenzivne propagande je dovoljno da jedan narod poludi -- Zli Zec Na divljem zapadu i nije bilo tako puno nasilja, upravo zato jer su svi bili naoruzani. -- Mladen Gogala |
| Bonita Montero <Bonita.Montero@gmail.com>: Nov 28 12:12PM +0100 > In my experience sorting list by pointer is much slower then swaps > and rearagning access order, makes slow traversal afterwards. No, that depends on the size of the items you have. I had items that were so "heavy" (20 bytes) that sorting the pointers was faster and with light items of 8 bytes sorting the items was faster. |
| "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com>: Nov 28 05:34PM +0100 On 28.11.2020 11:00, Bonita Montero wrote: > 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 ? Better drop the in-place requirement. And then it's trivial. But do consider that this adds an O(n) copying, and that sorting is just O(n log n) in the first place. - Alf |
| Bonita Montero <Bonita.Montero@gmail.com>: Nov 28 05:38PM +0100 > Better drop the in-place requirement. And then it's trivial. ... It's not because I need a certain solution but I'm just curious about if there's an in-place solution without external memory. |
| Richard Damon <Richard@Damon-Family.org>: Nov 28 01:03PM -0500 On 11/28/20 11:38 AM, Bonita Montero wrote: >> Better drop the in-place requirement. And then it's trivial. ... > It's not because I need a certain solution but I'm just curious > 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. |
| Kaz Kylheku <563-365-8930@kylheku.com>: Nov 28 06:08PM > 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 ? Are the items scattered in dynamic memory, and of the same size? Or can they be in a single, contiguous block of memory, and of variable size? E.g. [B ][C ][A] -> [A][B ][C ] Firstly, literally without any external memory whatsoever, we cannot even swap two items. Even the XOR trick for swapping objects bitwise still requires external memory, such as a machine register. I think you have to assume that you have enough external memory to exchange two objects. Are all items treated as unique, or can the solution potentially take advantage of situations when pairs of items happen to be bit-for-bit equivalent, not requiring a swap even if they appear out of order through the pointer list? All in all, this is essentially a miminal edit distance problem, (in which only transpositions are allowed, no substitutions, deletions or insertions): https://en.wikipedia.org/wiki/Edit_distance |
| Tim Woodall <news001@woodall.me.uk>: Nov 28 06:13PM > 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 ? I'm not exactly sure what you're asking! But: N items in array. ptr is sorted. for(i=0; i<N; i++) { swap(array[i], *ptr[i]); for(y=i; y<N; y++) if(ptr[y] == &array[i]) { swap(ptr[y], ptr[i]); break; } } Completely untested. There's an O(N**2) search of the ptr array but O(N) swaps. I'm assuming than each item is very big and the number of items is quite small otherwise why the no external memory when you've already used extra memory with the ptr array. |
| olcott <NoOne@NoWhere.com>: Nov 27 09:53PM -0600 On 11/27/2020 9:02 PM, Ben Bacarisse wrote: >>> A halt decider is a function F such that F(P, I) is true iff P(I) is a >>> finite computation and false otherwise. >>> Do you agree? I never answer yes or no questions with a yes or no answer. I always answer yes or no questions with a complete explanation that derives a yes or no answer. I answered the above question this way in my next answer. >> that is not halting behavior. > Again an evasion, and for the same reason. You gave (a) so you can't > retract it, and you know (b) is also a fact. It is not an evasion it is a step-by-step proof that I am correct and you always skip these steps and leap to the conclusion that I am incorrect. > A computation that would not halt if its simulation were not > halted is indeed a non-halting computation. But a computation that > would not halt and one that is halted are different computations. Yes, that is the exact dichotomy required by the actual halting problem. void H_Hat(u32 P) { u32 Input_Halts = Halts(P, P); if (!Input_Halts) HALT else HERE: goto HERE; } Halts(H_Hat, H_Hat) does correctly decide that its input would not halt unless Halts stopped simulating it, then Halts(H_Hat, H_Hat) itself halts. > Confound_Halts(Confound_Halts) is a computation that does halt. It's > just a word game to say that it only halts because it's simulation had > to be halted in the course of determining the return value from Halts. Not so much. In this case H_Hat never gets any return value from Halts so it can't possibly do the opposite of whatever Halts decides and Halts does have to stop simulating H_Hat or H_Hat would have never halted. >> stopped simulating it. > Halts(Confound_Halts, Confound_Halts) returns false, according to you, > making Confound_Halts(Confound_Halts) a finite computation. No not at all. Halts is a finite computation. The input to Halts is only finite because Halts forced it to be finite, otherwise it is infinite. > How this > determination is made by Halts makes no difference. The determination The input to Halts is only finite because Halts forced it to be finite, otherwise it is infinite. > it if readers took the fact that Halts has a particular /reason/ for > returning false, namely that the execution would not otherwise > terminate, as excusing the fact that false is the wrong answer. The input to Halts is only finite because Halts forced it to be finite, otherwise it is infinite. >>> Therefore Halts is not a halt decider. Which of the these do you >>> disagree with? > No answer? What a surprise! I just proved that Halts does decide (H_Hat, H_Hat) correctly because the input to Halts is only finite because Halts forced it to be finite, otherwise it is infinite. >>> other hand, duck and dive, evade and distract. Maybe you will change >>> and ANSWER THE QUESTIONS ABOVE. > Not a single one of my questions answered. I answer yes or no questions with a complete explanation. If you can have the discipline to very very carefully analyze my answers as if there was a real chance that I am correct then it should be quite easy to verify in your own mind that I am actually correct. This is the key to understanding that I am correct. On 11/27/2020 9:02 PM, Ben Bacarisse wrote: > A computation that would not halt if its simulation were not > halted is indeed a non-halting computation. When the simulator stops simulating H_Hat before H_Hat ever gets any return value from Halts this makes it impossible for H_Hat to do the opposite of whatever Halts decides, thus making all the conventional HP proofs lose their entire basis. -- Copyright 2020 Pete Olcott "Great spirits have always encountered violent opposition from mediocre minds." Einstein |
| You received this digest because you're subscribed to updates for this group. You can change your settings on the group membership page. To unsubscribe from this group and stop receiving emails from it send an email to comp.lang.c+++unsubscribe@googlegroups.com. |
No comments:
Post a Comment