Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  newsreader  groups  login

Message-ID:  

Outside of a dog, a book is man's best friend. Inside of a dog, it is too dark to read.


computers / comp.ai.philosophy / Re: Implementing a two-way Turing Machine tape as an improvement to std::deque

SubjectAuthor
* Re: Implementing a two-way Turing Machine tape as an improvement toolcott
`* Re: Implementing a two-way Turing Machine tape as an improvement toMr Flibble
 `- Re: Implementing a two-way Turing Machine tape as an improvement toChris M. Thomasson

1
Re: Implementing a two-way Turing Machine tape as an improvement to std::deque

<zdmdnV7tirvcHeP_nZ2dnUU7_8xQAAAA@giganews.com>

 copy mid

https://www.novabbs.com/computers/article-flat.php?id=8740&group=comp.ai.philosophy#8740

 copy link   Newsgroups: comp.theory comp.ai.philosophy comp.lang.c comp.lang.c++
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!buffer2.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Fri, 13 May 2022 10:58:56 -0500
Date: Fri, 13 May 2022 10:58:56 -0500
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.9.0
Subject: Re: Implementing a two-way Turing Machine tape as an improvement to
std::deque
Content-Language: en-US
Newsgroups: comp.theory,comp.ai.philosophy,comp.lang.c,comp.lang.c++
References: <cNWdnXqV1cXzEuD_nZ2dnUU7_8zNnZ2d@giganews.com>
<20220512235610.00004914@reddwarf.jmc>
<Vf2dnR9fAewpDuD_nZ2dnUU7_8xh4p2d@giganews.com>
<20220513002218.00003fa0@reddwarf.jmc>
<-s-dncjVifoXB-D_nZ2dnUU7_83NnZ2d@giganews.com>
<20220513004049.00000d64@reddwarf.jmc>
<HYudneQqVdKFAOD_nZ2dnUU7_83NnZ2d@giganews.com>
<20220513005340.00001694@reddwarf.jmc>
<Bo-dnemL1eT6P-D_nZ2dnUU7_81g4p2d@giganews.com>
<20220513015816.00006f57@reddwarf.jmc>
<D7WdnSjo4swvKOD_nZ2dnUU7_81g4p2d@giganews.com>
<20220513080247.000077d7@reddwarf.jmc>
From: NoO...@NoWhere.com (olcott)
In-Reply-To: <20220513080247.000077d7@reddwarf.jmc>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <zdmdnV7tirvcHeP_nZ2dnUU7_8xQAAAA@giganews.com>
Lines: 211
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-ofSLRgWJvnbYo7bdrrwvPPx3uTaUhL6ta0Dk+Qm+/xOlD0m8IJpD9TyinvE7lgUoOEU6AY8LhiwLsSL!+htfqZCySP1ho8PyaRtDcKRbm80mlq3YxnbDF3mXU2L1J0Wcj9TPvzNFbEdb2iwVZ4F6+I3Al9A=
X-Complaints-To: abuse@giganews.com
X-DMCA-Notifications: http://www.giganews.com/info/dmca.html
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
X-Original-Bytes: 9882
 by: olcott - Fri, 13 May 2022 15:58 UTC

On 5/13/2022 2:02 AM, Mr Flibble wrote:
> On Thu, 12 May 2022 20:34:41 -0500
> olcott <NoOne@NoWhere.com> wrote:
>
>> On 5/12/2022 7:58 PM, Mr Flibble wrote:
>>> On Thu, 12 May 2022 19:12:22 -0500
>>> olcott <NoOne@NoWhere.com> wrote:
>>>
>>>> On 5/12/2022 6:53 PM, Mr Flibble wrote:
>>>>> On Thu, 12 May 2022 18:49:43 -0500
>>>>> olcott <NoOne@NoWhere.com> wrote:
>>>>>
>>>>>> On 5/12/2022 6:40 PM, Mr Flibble wrote:
>>>>>>> On Thu, 12 May 2022 18:38:49 -0500
>>>>>>> olcott <NoOne@NoWhere.com> wrote:
>>>>>>>
>>>>>>>> On 5/12/2022 6:22 PM, Mr Flibble wrote:
>>>>>>>>> On Thu, 12 May 2022 18:09:39 -0500
>>>>>>>>> olcott <NoOne@NoWhere.com> wrote:
>>>>>>>>>
>>>>>>>>>> On 5/12/2022 5:56 PM, Mr Flibble wrote:
>>>>>>>>>>> On Thu, 12 May 2022 17:51:25 -0500
>>>>>>>>>>> olcott <NoOne@NoWhere.com> wrote:
>>>>>>>>>>>
>>>>>>>>>>>> C/C++ people please critique this as the basis for an
>>>>>>>>>>>> improvement to std::deque. It seems to have the key
>>>>>>>>>>>> functionality of std::deque and does it much more simply
>>>>>>>>>>>> while saving time and space.
>>>>>>>>>>>> https://www.cplusplus.com/reference/deque/deque/
>>>>>>>>>>>>
>>>>>>>>>>>> #define tape_element unsigned char
>>>>>>>>>>>>
>>>>>>>>>>>> class Tape_Type
>>>>>>>>>>>> {
>>>>>>>>>>>> private:
>>>>>>>>>>>> int Tape_Head = 0; // Can be negative
>>>>>>>>>>>> std::vector<tape_element> Left; // Stores left
>>>>>>>>>>>> expansion std::vector<tape_element> Right; // Stores right
>>>>>>>>>>>> expansion tape_element & operator[](int index);
>>>>>>>>>>>>
>>>>>>>>>>>> public:
>>>>>>>>>>>> void move_left(); // Tape_Head--;
>>>>>>>>>>>> Left.push_back(0); as needed void move_right(); //
>>>>>>>>>>>> Tape_Head++; Left.push_back(0); as needed void
>>>>>>>>>>>> Write(tape_element Y){ this->operator[](Tape_Head) = Y; };
>>>>>>>>>>>> tape_element Read() { return
>>>>>>>>>>>> this->operator[](Tape_Head); }; Tape_Type(){
>>>>>>>>>>>> Right.push_back('_'); } // constructor void Output(); };
>>>>>>>>>>>>
>>>>>>>>>>>> tape_element& Tape_Type::operator[](int index)
>>>>>>>>>>>> {
>>>>>>>>>>>> if (index > 0)
>>>>>>>>>>>> return Right[index];
>>>>>>>>>>>> int Left_Index = ((index * -1) -1);
>>>>>>>>>>>> return Left[Left_Index];
>>>>>>>>>>>> }
>>>>>>>>>>>>
>>>>>>>>>>>> void Tape_Type::Output()
>>>>>>>>>>>> {
>>>>>>>>>>>> printf("Tape_Type::Output()\n");
>>>>>>>>>>>>
>>>>>>>>>>>> if (Left.size())
>>>>>>>>>>>> {
>>>>>>>>>>>> int Last_One = Left.size() - 1;
>>>>>>>>>>>> for (int N = Last_One; N >= 0; N--)
>>>>>>>>>>>> {
>>>>>>>>>>>> int TH = (N + 1) * -1; // determine Tape_Head
>>>>>>>>>>>> from N printf("[%04d]:%c Left[%02d]\n", TH, Left[N], N);
>>>>>>>>>>>> }
>>>>>>>>>>>> }
>>>>>>>>>>>> if (Right.size())
>>>>>>>>>>>> for (int N = 0; N < Right.size(); N++)
>>>>>>>>>>>> printf("[%04d]:%c Right[%02d]\n", N, Right[N],
>>>>>>>>>>>> N); }
>>>>>>>>>>>>
>>>>>>>>>>>> void Tape_Type::move_left()
>>>>>>>>>>>> {
>>>>>>>>>>>> Tape_Head--;
>>>>>>>>>>>> int Left_Index = ((Tape_Head * -1) -1);
>>>>>>>>>>>> if (Left_Index == Left.size())
>>>>>>>>>>>> Left.push_back('_');
>>>>>>>>>>>> }
>>>>>>>>>>>>
>>>>>>>>>>>> void Tape_Type::move_right()
>>>>>>>>>>>> {
>>>>>>>>>>>> Tape_Head++;
>>>>>>>>>>>> if (Tape_Head == Right.size())
>>>>>>>>>>>> Right.push_back('_');
>>>>>>>>>>>> }
>>>>>>>>>>>
>>>>>>>>>>> It might be a more appropriate solution than std::deque for
>>>>>>>>>>> your specific use-case however it is NOT an improvement to
>>>>>>>>>>> std::deque for the general case -- see my reply in the other
>>>>>>>>>>> thread for why.
>>>>>>>>>>>
>>>>>>>>>>> /Flibble
>>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> I didn't see any reason why it would not make a better
>>>>>>>>>> std::deque.
>>>>>>>>>
>>>>>>>>> Because it doesn't meet the complexity and referential
>>>>>>>>> integrity requirements of std::deque.
>>>>>>>>>
>>>>>>>>> /Flibble
>>>>>>>>>
>>>>>>>>
>>>>>>>> It is faster then std::deque.
>>>>>>>> I couldn't find what you mean by referential integrity it has
>>>>>>>> too many different meanings. invalidating iterators seemed to
>>>>>>>> be what you mean otherwise I have no idea.
>>>>>>>
>>>>>>> I see you are choosing to ignore my reply in the other thread.
>>>>>>> OK, I will repost why you are wrong here:
>>>>>>>
>>>>>>> * referential integrity and iterator invalidation are
>>>>>>> different things: when you add or remove elements to either end
>>>>>>> of a std::deque iterators are indeed invalidated however
>>>>>>> references to existing elements remain valid
>>>>>>
>>>>>> Mine words the same way and has the added benefit of contiguous
>>>>>> storage.
>>>>>>
>>>>>>> * If you do 1000 push_fronts followed by 1000 push_backs
>>>>>>> followed by 1000 pop_fronts all is good however your next
>>>>>>> pop_front will have linear complexity, O(n), as it will
>>>>>>> necessitate removal of the first element of the right
>>>>>>> std::vector.
>>>>>>
>>>>>> I don't think that this applies to the way that I implemented it.
>>>>>> pop_front pops from the end of Left. pop_back pops from the end
>>>>>> of Right. This is the key aspect that I used from David's
>>>>>> two-stack approach.
>>>>>
>>>>> Then it is totally different to what std::deque offers: std::deque
>>>>> allows ALL elements to be either popped from the front or back.
>>>>> Try reading AND UNDERSTANDING what I wrote again.
>>>>>
>>>>> /Flibble
>>>>>
>>>>
>>>> I could allow all elements to be popped from the front or the back
>>>> too. Mine is much faster when you need far less than all elements.
>>>>
>>>
>>> What you have does not offer what std::deque offers so is not
>>
>> All these things can be added and we end up with a simple, faster,
>> std:deque that has most the conventional overhead and complexity
>> abolished.
>>
>>> equivalent to std::deque so can't be considered better than
>>> std::deque for the general case (I don't care about your specific
>>> use-case).
>>>
>>> /Flibble
>>>
>>
>> It just a matter of defining more member functions.
>
> You cannot implement all of std::deque's member functions meeting
> std::deque requirements using your chosen data structure of two
> std::vectors.
>
> /Flibble
>


Click here to read the complete article
Re: Implementing a two-way Turing Machine tape as an improvement to std::deque

<20220513170239.0000273b@reddwarf.jmc>

 copy mid

https://www.novabbs.com/computers/article-flat.php?id=8741&group=comp.ai.philosophy#8741

 copy link   Newsgroups: comp.theory comp.ai.philosophy comp.lang.c comp.lang.c++
Path: i2pn2.org!i2pn.org!aioe.org!news.uzoreto.com!feeder1.feed.usenet.farm!feed.usenet.farm!peer01.ams4!peer.am4.highwinds-media.com!news.highwinds-media.com!fx14.ams4.POSTED!not-for-mail
From: flib...@reddwarf.jmc (Mr Flibble)
Newsgroups: comp.theory,comp.ai.philosophy,comp.lang.c,comp.lang.c++
Subject: Re: Implementing a two-way Turing Machine tape as an improvement to
std::deque
Message-ID: <20220513170239.0000273b@reddwarf.jmc>
References: <cNWdnXqV1cXzEuD_nZ2dnUU7_8zNnZ2d@giganews.com>
<20220512235610.00004914@reddwarf.jmc>
<Vf2dnR9fAewpDuD_nZ2dnUU7_8xh4p2d@giganews.com>
<20220513002218.00003fa0@reddwarf.jmc>
<-s-dncjVifoXB-D_nZ2dnUU7_83NnZ2d@giganews.com>
<20220513004049.00000d64@reddwarf.jmc>
<HYudneQqVdKFAOD_nZ2dnUU7_83NnZ2d@giganews.com>
<20220513005340.00001694@reddwarf.jmc>
<Bo-dnemL1eT6P-D_nZ2dnUU7_81g4p2d@giganews.com>
<20220513015816.00006f57@reddwarf.jmc>
<D7WdnSjo4swvKOD_nZ2dnUU7_81g4p2d@giganews.com>
<20220513080247.000077d7@reddwarf.jmc>
<zdmdnV7tirvcHeP_nZ2dnUU7_8xQAAAA@giganews.com>
Organization: Jupiter Mining Corp
X-Newsreader: Claws Mail 3.17.8 (GTK+ 2.24.33; x86_64-w64-mingw32)
MIME-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
Lines: 211
X-Complaints-To: abuse@eweka.nl
NNTP-Posting-Date: Fri, 13 May 2022 16:02:38 UTC
Date: Fri, 13 May 2022 17:02:39 +0100
X-Received-Bytes: 9809
 by: Mr Flibble - Fri, 13 May 2022 16:02 UTC

On Fri, 13 May 2022 10:58:56 -0500
olcott <NoOne@NoWhere.com> wrote:

> On 5/13/2022 2:02 AM, Mr Flibble wrote:
> > On Thu, 12 May 2022 20:34:41 -0500
> > olcott <NoOne@NoWhere.com> wrote:
> >
> >> On 5/12/2022 7:58 PM, Mr Flibble wrote:
> >>> On Thu, 12 May 2022 19:12:22 -0500
> >>> olcott <NoOne@NoWhere.com> wrote:
> >>>
> >>>> On 5/12/2022 6:53 PM, Mr Flibble wrote:
> >>>>> On Thu, 12 May 2022 18:49:43 -0500
> >>>>> olcott <NoOne@NoWhere.com> wrote:
> >>>>>
> >>>>>> On 5/12/2022 6:40 PM, Mr Flibble wrote:
> >>>>>>> On Thu, 12 May 2022 18:38:49 -0500
> >>>>>>> olcott <NoOne@NoWhere.com> wrote:
> >>>>>>>
> >>>>>>>> On 5/12/2022 6:22 PM, Mr Flibble wrote:
> >>>>>>>>> On Thu, 12 May 2022 18:09:39 -0500
> >>>>>>>>> olcott <NoOne@NoWhere.com> wrote:
> >>>>>>>>>
> >>>>>>>>>> On 5/12/2022 5:56 PM, Mr Flibble wrote:
> >>>>>>>>>>> On Thu, 12 May 2022 17:51:25 -0500
> >>>>>>>>>>> olcott <NoOne@NoWhere.com> wrote:
> >>>>>>>>>>>
> >>>>>>>>>>>> C/C++ people please critique this as the basis for an
> >>>>>>>>>>>> improvement to std::deque. It seems to have the key
> >>>>>>>>>>>> functionality of std::deque and does it much more simply
> >>>>>>>>>>>> while saving time and space.
> >>>>>>>>>>>> https://www.cplusplus.com/reference/deque/deque/
> >>>>>>>>>>>>
> >>>>>>>>>>>> #define tape_element unsigned char
> >>>>>>>>>>>>
> >>>>>>>>>>>> class Tape_Type
> >>>>>>>>>>>> {
> >>>>>>>>>>>> private:
> >>>>>>>>>>>> int Tape_Head = 0; // Can be
> >>>>>>>>>>>> negative std::vector<tape_element> Left; // Stores left
> >>>>>>>>>>>> expansion std::vector<tape_element> Right; // Stores
> >>>>>>>>>>>> right expansion tape_element & operator[](int index);
> >>>>>>>>>>>>
> >>>>>>>>>>>> public:
> >>>>>>>>>>>> void move_left(); // Tape_Head--;
> >>>>>>>>>>>> Left.push_back(0); as needed void move_right(); //
> >>>>>>>>>>>> Tape_Head++; Left.push_back(0); as needed void
> >>>>>>>>>>>> Write(tape_element Y){ this->operator[](Tape_Head) = Y;
> >>>>>>>>>>>> }; tape_element Read() { return
> >>>>>>>>>>>> this->operator[](Tape_Head); }; Tape_Type(){
> >>>>>>>>>>>> Right.push_back('_'); } // constructor void Output(); };
> >>>>>>>>>>>>
> >>>>>>>>>>>> tape_element& Tape_Type::operator[](int index)
> >>>>>>>>>>>> {
> >>>>>>>>>>>> if (index > 0)
> >>>>>>>>>>>> return Right[index];
> >>>>>>>>>>>> int Left_Index = ((index * -1) -1);
> >>>>>>>>>>>> return Left[Left_Index];
> >>>>>>>>>>>> }
> >>>>>>>>>>>>
> >>>>>>>>>>>> void Tape_Type::Output()
> >>>>>>>>>>>> {
> >>>>>>>>>>>> printf("Tape_Type::Output()\n");
> >>>>>>>>>>>>
> >>>>>>>>>>>> if (Left.size())
> >>>>>>>>>>>> {
> >>>>>>>>>>>> int Last_One = Left.size() - 1;
> >>>>>>>>>>>> for (int N = Last_One; N >= 0; N--)
> >>>>>>>>>>>> {
> >>>>>>>>>>>> int TH = (N + 1) * -1; // determine
> >>>>>>>>>>>> Tape_Head from N printf("[%04d]:%c Left[%02d]\n", TH,
> >>>>>>>>>>>> Left[N], N); }
> >>>>>>>>>>>> }
> >>>>>>>>>>>> if (Right.size())
> >>>>>>>>>>>> for (int N = 0; N < Right.size(); N++)
> >>>>>>>>>>>> printf("[%04d]:%c Right[%02d]\n", N,
> >>>>>>>>>>>> Right[N], N); }
> >>>>>>>>>>>>
> >>>>>>>>>>>> void Tape_Type::move_left()
> >>>>>>>>>>>> {
> >>>>>>>>>>>> Tape_Head--;
> >>>>>>>>>>>> int Left_Index = ((Tape_Head * -1) -1);
> >>>>>>>>>>>> if (Left_Index == Left.size())
> >>>>>>>>>>>> Left.push_back('_');
> >>>>>>>>>>>> }
> >>>>>>>>>>>>
> >>>>>>>>>>>> void Tape_Type::move_right()
> >>>>>>>>>>>> {
> >>>>>>>>>>>> Tape_Head++;
> >>>>>>>>>>>> if (Tape_Head == Right.size())
> >>>>>>>>>>>> Right.push_back('_');
> >>>>>>>>>>>> }
> >>>>>>>>>>>
> >>>>>>>>>>> It might be a more appropriate solution than std::deque
> >>>>>>>>>>> for your specific use-case however it is NOT an
> >>>>>>>>>>> improvement to std::deque for the general case -- see my
> >>>>>>>>>>> reply in the other thread for why.
> >>>>>>>>>>>
> >>>>>>>>>>> /Flibble
> >>>>>>>>>>>
> >>>>>>>>>>
> >>>>>>>>>> I didn't see any reason why it would not make a better
> >>>>>>>>>> std::deque.
> >>>>>>>>>
> >>>>>>>>> Because it doesn't meet the complexity and referential
> >>>>>>>>> integrity requirements of std::deque.
> >>>>>>>>>
> >>>>>>>>> /Flibble
> >>>>>>>>>
> >>>>>>>>
> >>>>>>>> It is faster then std::deque.
> >>>>>>>> I couldn't find what you mean by referential integrity it has
> >>>>>>>> too many different meanings. invalidating iterators seemed to
> >>>>>>>> be what you mean otherwise I have no idea.
> >>>>>>>
> >>>>>>> I see you are choosing to ignore my reply in the other thread.
> >>>>>>> OK, I will repost why you are wrong here:
> >>>>>>>
> >>>>>>> * referential integrity and iterator invalidation are
> >>>>>>> different things: when you add or remove elements to either
> >>>>>>> end of a std::deque iterators are indeed invalidated however
> >>>>>>> references to existing elements remain valid
> >>>>>>
> >>>>>> Mine words the same way and has the added benefit of contiguous
> >>>>>> storage.
> >>>>>>
> >>>>>>> * If you do 1000 push_fronts followed by 1000 push_backs
> >>>>>>> followed by 1000 pop_fronts all is good however your next
> >>>>>>> pop_front will have linear complexity, O(n), as it will
> >>>>>>> necessitate removal of the first element of the right
> >>>>>>> std::vector.
> >>>>>>
> >>>>>> I don't think that this applies to the way that I implemented
> >>>>>> it. pop_front pops from the end of Left. pop_back pops from
> >>>>>> the end of Right. This is the key aspect that I used from
> >>>>>> David's two-stack approach.
> >>>>>
> >>>>> Then it is totally different to what std::deque offers:
> >>>>> std::deque allows ALL elements to be either popped from the
> >>>>> front or back. Try reading AND UNDERSTANDING what I wrote again.
> >>>>>
> >>>>> /Flibble
> >>>>>
> >>>>
> >>>> I could allow all elements to be popped from the front or the
> >>>> back too. Mine is much faster when you need far less than all
> >>>> elements.
> >>>
> >>> What you have does not offer what std::deque offers so is not
> >>
> >> All these things can be added and we end up with a simple, faster,
> >> std:deque that has most the conventional overhead and complexity
> >> abolished.
> >>
> >>> equivalent to std::deque so can't be considered better than
> >>> std::deque for the general case (I don't care about your specific
> >>> use-case).
> >>>
> >>> /Flibble
> >>>
> >>
> >> It just a matter of defining more member functions.
> >
> > You cannot implement all of std::deque's member functions meeting
> > std::deque requirements using your chosen data structure of two
> > std::vectors.
> >
> > /Flibble
> >
>
> // Tape_Type implements a two-way Turing machine tape.
> // Right contains Tape_Head >= 0 values (right expansion)
> // Left contains Tape_Head < 0 values (left expansion)
> //
> // Grows with Right.push_back() as Tape_Head increases above 0.
> // Grows with Left.push_back() as Tape_Head decreases below 0.
> //
> // Tape_Type has functionality very similar to std::deque
> // yet implements this functionality much more simply.
> // This saves time and space.
> //
> class Tape_Type
> {
> public:
> typedef unsigned char tape_element;
>
> private:
> int Tape_Head = 0; // Can be negative
> std::vector<tape_element> Left; // Stores left expansion
> std::vector<tape_element> Right; // Stores right expansion
>
> tape_element& operator[](int index)
> {
> return index >= 0 ? Right[index] : Left[-index - 1];
> }
>
> public:
> tape_element& front( ) { return Left.back(); }
> tape_element& back() { return Right.back(); }
> void pop_front() { Left.pop_back(); }
> void pop_back() { Right.pop_back(); }
> void push_front(tape_element& E) { Left.push_back(E); }
> void push_back(tape_element& E) { Right.push_back(E); }
> void reserve(unsigned int N)
> { Left.reserve(N); Right.reserve(N); }


Click here to read the complete article
Re: Implementing a two-way Turing Machine tape as an improvement to std::deque

<t5mce6$ij6$1@dont-email.me>

 copy mid

https://www.novabbs.com/computers/article-flat.php?id=8753&group=comp.ai.philosophy#8753

 copy link   Newsgroups: comp.theory comp.ai.philosophy comp.lang.c comp.lang.c++
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: chris.m....@gmail.com (Chris M. Thomasson)
Newsgroups: comp.theory,comp.ai.philosophy,comp.lang.c,comp.lang.c++
Subject: Re: Implementing a two-way Turing Machine tape as an improvement to
std::deque
Date: Fri, 13 May 2022 12:44:05 -0700
Organization: A noiseless patient Spider
Lines: 237
Message-ID: <t5mce6$ij6$1@dont-email.me>
References: <cNWdnXqV1cXzEuD_nZ2dnUU7_8zNnZ2d@giganews.com>
<20220512235610.00004914@reddwarf.jmc>
<Vf2dnR9fAewpDuD_nZ2dnUU7_8xh4p2d@giganews.com>
<20220513002218.00003fa0@reddwarf.jmc>
<-s-dncjVifoXB-D_nZ2dnUU7_83NnZ2d@giganews.com>
<20220513004049.00000d64@reddwarf.jmc>
<HYudneQqVdKFAOD_nZ2dnUU7_83NnZ2d@giganews.com>
<20220513005340.00001694@reddwarf.jmc>
<Bo-dnemL1eT6P-D_nZ2dnUU7_81g4p2d@giganews.com>
<20220513015816.00006f57@reddwarf.jmc>
<D7WdnSjo4swvKOD_nZ2dnUU7_81g4p2d@giganews.com>
<20220513080247.000077d7@reddwarf.jmc>
<zdmdnV7tirvcHeP_nZ2dnUU7_8xQAAAA@giganews.com>
<20220513170239.0000273b@reddwarf.jmc>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Fri, 13 May 2022 19:44:06 -0000 (UTC)
Injection-Info: reader02.eternal-september.org; posting-host="9e0404c658f08f4bf7ea56fefb5cef5d";
logging-data="19046"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19T/UmUQKCOniMNDOz1tYwL5hsQ6c/jQwM="
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.9.0
Cancel-Lock: sha1:8UOLRFmg89b6HySbb96cNw28VdA=
In-Reply-To: <20220513170239.0000273b@reddwarf.jmc>
Content-Language: en-US
 by: Chris M. Thomasson - Fri, 13 May 2022 19:44 UTC

On 5/13/2022 9:02 AM, Mr Flibble wrote:
> On Fri, 13 May 2022 10:58:56 -0500
> olcott <NoOne@NoWhere.com> wrote:
>
>> On 5/13/2022 2:02 AM, Mr Flibble wrote:
>>> On Thu, 12 May 2022 20:34:41 -0500
>>> olcott <NoOne@NoWhere.com> wrote:
>>>
>>>> On 5/12/2022 7:58 PM, Mr Flibble wrote:
>>>>> On Thu, 12 May 2022 19:12:22 -0500
>>>>> olcott <NoOne@NoWhere.com> wrote:
>>>>>
>>>>>> On 5/12/2022 6:53 PM, Mr Flibble wrote:
>>>>>>> On Thu, 12 May 2022 18:49:43 -0500
>>>>>>> olcott <NoOne@NoWhere.com> wrote:
>>>>>>>
>>>>>>>> On 5/12/2022 6:40 PM, Mr Flibble wrote:
>>>>>>>>> On Thu, 12 May 2022 18:38:49 -0500
>>>>>>>>> olcott <NoOne@NoWhere.com> wrote:
>>>>>>>>>
>>>>>>>>>> On 5/12/2022 6:22 PM, Mr Flibble wrote:
>>>>>>>>>>> On Thu, 12 May 2022 18:09:39 -0500
>>>>>>>>>>> olcott <NoOne@NoWhere.com> wrote:
>>>>>>>>>>>
>>>>>>>>>>>> On 5/12/2022 5:56 PM, Mr Flibble wrote:
>>>>>>>>>>>>> On Thu, 12 May 2022 17:51:25 -0500
>>>>>>>>>>>>> olcott <NoOne@NoWhere.com> wrote:
>>>>>>>>>>>>>
>>>>>>>>>>>>>> C/C++ people please critique this as the basis for an
>>>>>>>>>>>>>> improvement to std::deque. It seems to have the key
>>>>>>>>>>>>>> functionality of std::deque and does it much more simply
>>>>>>>>>>>>>> while saving time and space.
>>>>>>>>>>>>>> https://www.cplusplus.com/reference/deque/deque/
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> #define tape_element unsigned char
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> class Tape_Type
>>>>>>>>>>>>>> {
>>>>>>>>>>>>>> private:
>>>>>>>>>>>>>> int Tape_Head = 0; // Can be
>>>>>>>>>>>>>> negative std::vector<tape_element> Left; // Stores left
>>>>>>>>>>>>>> expansion std::vector<tape_element> Right; // Stores
>>>>>>>>>>>>>> right expansion tape_element & operator[](int index);
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> public:
>>>>>>>>>>>>>> void move_left(); // Tape_Head--;
>>>>>>>>>>>>>> Left.push_back(0); as needed void move_right(); //
>>>>>>>>>>>>>> Tape_Head++; Left.push_back(0); as needed void
>>>>>>>>>>>>>> Write(tape_element Y){ this->operator[](Tape_Head) = Y;
>>>>>>>>>>>>>> }; tape_element Read() { return
>>>>>>>>>>>>>> this->operator[](Tape_Head); }; Tape_Type(){
>>>>>>>>>>>>>> Right.push_back('_'); } // constructor void Output(); };
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> tape_element& Tape_Type::operator[](int index)
>>>>>>>>>>>>>> {
>>>>>>>>>>>>>> if (index > 0)
>>>>>>>>>>>>>> return Right[index];
>>>>>>>>>>>>>> int Left_Index = ((index * -1) -1);
>>>>>>>>>>>>>> return Left[Left_Index];
>>>>>>>>>>>>>> }
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> void Tape_Type::Output()
>>>>>>>>>>>>>> {
>>>>>>>>>>>>>> printf("Tape_Type::Output()\n");
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> if (Left.size())
>>>>>>>>>>>>>> {
>>>>>>>>>>>>>> int Last_One = Left.size() - 1;
>>>>>>>>>>>>>> for (int N = Last_One; N >= 0; N--)
>>>>>>>>>>>>>> {
>>>>>>>>>>>>>> int TH = (N + 1) * -1; // determine
>>>>>>>>>>>>>> Tape_Head from N printf("[%04d]:%c Left[%02d]\n", TH,
>>>>>>>>>>>>>> Left[N], N); }
>>>>>>>>>>>>>> }
>>>>>>>>>>>>>> if (Right.size())
>>>>>>>>>>>>>> for (int N = 0; N < Right.size(); N++)
>>>>>>>>>>>>>> printf("[%04d]:%c Right[%02d]\n", N,
>>>>>>>>>>>>>> Right[N], N); }
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> void Tape_Type::move_left()
>>>>>>>>>>>>>> {
>>>>>>>>>>>>>> Tape_Head--;
>>>>>>>>>>>>>> int Left_Index = ((Tape_Head * -1) -1);
>>>>>>>>>>>>>> if (Left_Index == Left.size())
>>>>>>>>>>>>>> Left.push_back('_');
>>>>>>>>>>>>>> }
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> void Tape_Type::move_right()
>>>>>>>>>>>>>> {
>>>>>>>>>>>>>> Tape_Head++;
>>>>>>>>>>>>>> if (Tape_Head == Right.size())
>>>>>>>>>>>>>> Right.push_back('_');
>>>>>>>>>>>>>> }
>>>>>>>>>>>>>
>>>>>>>>>>>>> It might be a more appropriate solution than std::deque
>>>>>>>>>>>>> for your specific use-case however it is NOT an
>>>>>>>>>>>>> improvement to std::deque for the general case -- see my
>>>>>>>>>>>>> reply in the other thread for why.
>>>>>>>>>>>>>
>>>>>>>>>>>>> /Flibble
>>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>> I didn't see any reason why it would not make a better
>>>>>>>>>>>> std::deque.
>>>>>>>>>>>
>>>>>>>>>>> Because it doesn't meet the complexity and referential
>>>>>>>>>>> integrity requirements of std::deque.
>>>>>>>>>>>
>>>>>>>>>>> /Flibble
>>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> It is faster then std::deque.
>>>>>>>>>> I couldn't find what you mean by referential integrity it has
>>>>>>>>>> too many different meanings. invalidating iterators seemed to
>>>>>>>>>> be what you mean otherwise I have no idea.
>>>>>>>>>
>>>>>>>>> I see you are choosing to ignore my reply in the other thread.
>>>>>>>>> OK, I will repost why you are wrong here:
>>>>>>>>>
>>>>>>>>> * referential integrity and iterator invalidation are
>>>>>>>>> different things: when you add or remove elements to either
>>>>>>>>> end of a std::deque iterators are indeed invalidated however
>>>>>>>>> references to existing elements remain valid
>>>>>>>>
>>>>>>>> Mine words the same way and has the added benefit of contiguous
>>>>>>>> storage.
>>>>>>>>
>>>>>>>>> * If you do 1000 push_fronts followed by 1000 push_backs
>>>>>>>>> followed by 1000 pop_fronts all is good however your next
>>>>>>>>> pop_front will have linear complexity, O(n), as it will
>>>>>>>>> necessitate removal of the first element of the right
>>>>>>>>> std::vector.
>>>>>>>>
>>>>>>>> I don't think that this applies to the way that I implemented
>>>>>>>> it. pop_front pops from the end of Left. pop_back pops from
>>>>>>>> the end of Right. This is the key aspect that I used from
>>>>>>>> David's two-stack approach.
>>>>>>>
>>>>>>> Then it is totally different to what std::deque offers:
>>>>>>> std::deque allows ALL elements to be either popped from the
>>>>>>> front or back. Try reading AND UNDERSTANDING what I wrote again.
>>>>>>>
>>>>>>> /Flibble
>>>>>>>
>>>>>>
>>>>>> I could allow all elements to be popped from the front or the
>>>>>> back too. Mine is much faster when you need far less than all
>>>>>> elements.
>>>>>
>>>>> What you have does not offer what std::deque offers so is not
>>>>
>>>> All these things can be added and we end up with a simple, faster,
>>>> std:deque that has most the conventional overhead and complexity
>>>> abolished.
>>>>
>>>>> equivalent to std::deque so can't be considered better than
>>>>> std::deque for the general case (I don't care about your specific
>>>>> use-case).
>>>>>
>>>>> /Flibble
>>>>>
>>>>
>>>> It just a matter of defining more member functions.
>>>
>>> You cannot implement all of std::deque's member functions meeting
>>> std::deque requirements using your chosen data structure of two
>>> std::vectors.
>>>
>>> /Flibble
>>>
>>
>> // Tape_Type implements a two-way Turing machine tape.
>> // Right contains Tape_Head >= 0 values (right expansion)
>> // Left contains Tape_Head < 0 values (left expansion)
>> //
>> // Grows with Right.push_back() as Tape_Head increases above 0.
>> // Grows with Left.push_back() as Tape_Head decreases below 0.
>> //
>> // Tape_Type has functionality very similar to std::deque
>> // yet implements this functionality much more simply.
>> // This saves time and space.
>> //
>> class Tape_Type
>> {
>> public:
>> typedef unsigned char tape_element;
>>
>> private:
>> int Tape_Head = 0; // Can be negative
>> std::vector<tape_element> Left; // Stores left expansion
>> std::vector<tape_element> Right; // Stores right expansion
>>
>> tape_element& operator[](int index)
>> {
>> return index >= 0 ? Right[index] : Left[-index - 1];
>> }
>>
>> public:
>> tape_element& front( ) { return Left.back(); }
>> tape_element& back() { return Right.back(); }
>> void pop_front() { Left.pop_back(); }
>> void pop_back() { Right.pop_back(); }
>> void push_front(tape_element& E) { Left.push_back(E); }
>> void push_back(tape_element& E) { Right.push_back(E); }
>> void reserve(unsigned int N)
>> { Left.reserve(N); Right.reserve(N); }
>
> And what happens if Left is empty, Right is non-empty and you call
> pop_front()?


Click here to read the complete article
1
server_pubkey.txt

rocksolid light 0.9.7
clearnet tor