Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  newsreader  groups  login

Message-ID:  

Did you know that for the price of a 280-Z you can buy two Z-80's? -- P. J. Plauger


devel / comp.theory / Re: Implementing a two-way Turing Machine tape as an improvement to std::deque

SubjectAuthor
* Implementing a two-way Turing Machine tape as an improvement toolcott
+* Implementing a two-way Turing Machine tape as an improvement toMr Flibble
|`* Implementing a two-way Turing Machine tape as an improvement toolcott
| `* Implementing a two-way Turing Machine tape as an improvement toMr Flibble
|  `* Implementing a two-way Turing Machine tape as an improvement toolcott
|   `* Implementing a two-way Turing Machine tape as an improvement toMr Flibble
|    `* Implementing a two-way Turing Machine tape as an improvement toolcott
|     `* Implementing a two-way Turing Machine tape as an improvement toMr Flibble
|      `* Implementing a two-way Turing Machine tape as an improvement toolcott
|       `* Implementing a two-way Turing Machine tape as an improvement toMr Flibble
|        `* Implementing a two-way Turing Machine tape as an improvement toolcott
|         `* Implementing a two-way Turing Machine tape as an improvement to std::dequeMr Flibble
|          +- Implementing a two-way Turing Machine tape as an improvement totth
|          `* Implementing a two-way Turing Machine tape as an improvement toolcott
|           `* Implementing a two-way Turing Machine tape as an improvement toMr Flibble
|            `- Implementing a two-way Turing Machine tape as an improvement toChris M. Thomasson
+* Implementing a two-way Turing Machine tape as an improvement to std::dequeRichard Damon
|`- Implementing a two-way Turing Machine tape as an improvement toolcott
`* Implementing a two-way Turing Machine tape as an improvement to std::dequeBen
 `* Implementing a two-way Turing Machine tape as an improvement toolcott
  +* Implementing a two-way Turing Machine tape as an improvement toMr Flibble
  |`* Implementing a two-way Turing Machine tape as an improvement toolcott
  | `* Implementing a two-way Turing Machine tape as an improvement to std::dequeMr Flibble
  |  `* Implementing a two-way Turing Machine tape as an improvement toolcott
  |   `* Implementing a two-way Turing Machine tape as an improvement toMr Flibble
  |    `- Implementing a two-way Turing Machine tape as an improvement toolcott
  `* Implementing a two-way Turing Machine tape as an improvement to std::dequeBen
   `* Implementing a two-way Turing Machine tape as an improvement toolcott
    +- Implementing a two-way Turing Machine tape as an improvement toPython
    `* Implementing a two-way Turing Machine tape as an improvement to std::dequeBen
     `* Implementing a two-way Turing Machine tape as an improvement toolcott
      +- Implementing a two-way Turing Machine tape as an improvement to std::dequeRichard Damon
      `* Implementing a two-way Turing Machine tape as an improvement to std::dequeBen
       `* Implementing a two-way Turing Machine tape as an improvement toolcott
        `* Implementing a two-way Turing Machine tape as an improvement to std::dequeBen
         `- Implementing a two-way Turing Machine tape as an improvement toolcott

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

<XcvfK.18498$L_b6.1933@fx33.iad>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=32281&group=comp.theory#32281

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!aioe.org!feeder1.feed.usenet.farm!feed.usenet.farm!feeder.usenetexpress.com!tr1.eu1.usenetexpress.com!81.171.65.16.MISMATCH!peer03.ams4!peer.am4.highwinds-media.com!peer01.iad!feed-me.highwinds-media.com!news.highwinds-media.com!fx33.iad.POSTED!not-for-mail
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; 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
References: <cNWdnXqV1cXzEuD_nZ2dnUU7_8zNnZ2d@giganews.com> <87wneq1ejm.fsf@bsb.me.uk> <MeOdncpeZacPMeD_nZ2dnUU7_8zNnZ2d@giganews.com> <8735he1abh.fsf@bsb.me.uk> <692dnROYz_PMWeD_nZ2dnUU7_83NnZ2d@giganews.com> <87sfpdzofd.fsf@bsb.me.uk> <-LadnQlxFteO4eP_nZ2dnUU7_8zNnZ2d@giganews.com>
From: Rich...@Damon-Family.org (Richard Damon)
In-Reply-To: <-LadnQlxFteO4eP_nZ2dnUU7_8zNnZ2d@giganews.com>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Lines: 149
Message-ID: <XcvfK.18498$L_b6.1933@fx33.iad>
X-Complaints-To: abuse@easynews.com
Organization: Forte - www.forteinc.com
X-Complaints-Info: Please be sure to forward a copy of ALL headers otherwise we will be unable to process your complaint properly.
Date: Fri, 13 May 2022 11:56:09 -0400
X-Received-Bytes: 7017
 by: Richard Damon - Fri, 13 May 2022 15:56 UTC

On 5/13/22 11:41 AM, olcott wrote:
> On 5/13/2022 6:01 AM, Ben wrote:
>> olcott <NoOne@NoWhere.com> writes:
>>
>>> On 5/12/2022 8:38 PM, Ben wrote:
>>>> olcott <NoOne@NoWhere.com> writes:
>>>>
>>>>> On 5/12/2022 7:06 PM, Ben wrote:
>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>> I've removed the philosophy group and comp.lang.c as this is C++.
>>>>>>
>>>>>>> C/C++ people please critique this as the basis for an improvement to
>>>>>>> std::deque.
>>>>>> You will get critiques of the code on whatever basis people feel
>>>>>> inclined to comment!  You can't limit the comments to some particular
>>>>>> context.
>>>>>>
>>>>>>> It seems to have the key functionality of std::deque and
>>>>>>> does it much more simply while saving time and space.
>>>>>> It does not have any of the functionality of std::deque.
>>>>>
>>>>> That is a ridiculously stupid thing to say. It has the key most
>>>>> important functionality of a std:deque
>>>> Generally, when you think I am saying something absurd, you should
>>>> re-consider.
>>>> A deque has (at least) these operations:
>>>>     front
>>>>     back
>>>>     push_front
>>>>     push_back
>>>>     pop_front
>>>>     pop_back
>>>> Your Tape_Type has none of these.  Even internally it does not maintain
>>>> the right data to be able to provide them.
>>>
>>> I also added a reserve so you could do a pre-allocated speed test.
>>>
>>> It was easy to add these in terms of the current implementation:
>>
>> You have not provided the correct operations, so you have no idea how
>> hard it might be to do that.  This keeps looking more and more like a
>> distraction to put off having to do what you said.
>>
>>> 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); }
>>
>> Not correct.  Test first.
>
>
> They are all correct. I don't see how you can say that they are not when
> you don't know my design.

Except that you just published your "design" above.

Note, pop_front() needs to remove the first item in the queue/on the tape.

If all the contents of the tape are currently in the Right vector, and
none are on the Left, pop_front() needs to remove the first element of
the right vector, but your implementation doesn't do that.

You have made the INCORRECT assumption that the "0" point of the tape
will always exist.

For the Turing Machine, this isn't important because the Turing Machine
never needs to remove an item from the tape, at best it marks an element
as "empty", but for a general deque, that is a needed for a general
deque that meets the full specifications.

>
>>
>>>>> Double ended queue
>>>>> deque (usually pronounced like "deck") is an irregular acronym of
>>>>> double-ended queue. Double-ended queues are sequence containers with
>>>>> dynamic sizes that can be expanded or contracted on both ends (either
>>>>> its front or its back).
>>>>>
>>>>> All of the rest of the functionality of std::deque can be added as
>>>>> needed.
>>>> You mean you could implement a deque using two arrays if you chose to?
>>>> So what?  All I am saying is that you haven't got a deque.
>>>
>>> If I added these things then I would have a much better deque.
>>
>> If you added them correctly and then removed the things that a deque
>> should not have.  In other words, if you implemented a deque.
>>
>
> I mere want to know that the most basic functionality of my deque is
> (a) simpler (b) faster (c) smaller than a std:deque.
> If Tape_Type.reserve() is used it should be your std::string.
>

There is no definition of "most basic" that excludes the "required"
functionality of deque.

Remember, requirements ARE requirements, and when solving a problem, you
don't normally get to change them (Not and say you are still working on
the same problem).

>>>>> Yes I tested so I don't see what you mean.
>>>> Testing should have caught the bug in operator[].
>>>
>>> It is was a new refactoring of existing working code.
>>
>> A software engineer runs all the tests after every edit (or at least
>> before every commit).  (I am not a software engineer.)
>>
>>>> I plugged your tape class into my C++ TM interpreter and it made it
>>>> slightly slower for the "big" BB(5) test compared with my naive tape
>>>> that just uses a single string.
>>>>
>>>
>>> std::string or char * ?
>>
>> std::string.
>>
>>> If char * was pre-allocated that would give it a big speed advantage.
>>
>> Nothing pre-allocated.
>>
>>>> Mind you, I prefer using a string to all the other methods I've tried
>>>> because it's so convenient.  You can set up the TM with an input simply
>>>> by writing
>>>>     tape = input
>>>> and you can debug by printing the tape any time you like.  And I use a
>>>> string_view to get the non-blank "result" out of the TM and the end
>>>> of a
>>>> run.  All easy to get round with a couple of functions, but still,
>>>> since
>>>> it's fast I see no reason t change.
>>>
>>> What about memory allocation?
>>
>> What about it?  std::string does it.
>>
>
> It is probably much slower than my system now that I added reserve.
> I do like the idea of simplicity, it is my primary design goal.
>

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/devel/article-flat.php?id=32283&group=comp.theory#32283

 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

<zdmdnVntirsfHeP_nZ2dnUU7_8zNnZ2d@giganews.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=32284&group=comp.theory#32284

 copy link   Newsgroups: comp.theory comp.lang.c++
Path: i2pn2.org!rocksolid2!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 11:00:02 -0500
Date: Fri, 13 May 2022 11:00:01 -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.lang.c++
References: <cNWdnXqV1cXzEuD_nZ2dnUU7_8zNnZ2d@giganews.com>
<87wneq1ejm.fsf@bsb.me.uk> <MeOdncpeZacPMeD_nZ2dnUU7_8zNnZ2d@giganews.com>
<20220513020134.00003f42@reddwarf.jmc>
<D7WdnSvo4syeK-D_nZ2dnUU7_81g4p2d@giganews.com>
<20220513080435.00002bdc@reddwarf.jmc>
From: NoO...@NoWhere.com (olcott)
In-Reply-To: <20220513080435.00002bdc@reddwarf.jmc>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <zdmdnVntirsfHeP_nZ2dnUU7_8zNnZ2d@giganews.com>
Lines: 59
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-j0GPV2nkiMHiPeEfAZlTw5+8W79Vh+Eh5beUjpecSMtB2+bY3T21tlPVrpwOuPgi20xeHsOs+PY6kEH!vSpnNfzb1YZldfDeYLDavScF9EoTSwsAeNTj/HbWntXxfCb6zZcySTjNVs445l42dZXw6Cge7oA=
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: 3329
 by: olcott - Fri, 13 May 2022 16:00 UTC

On 5/13/2022 2:04 AM, Mr Flibble wrote:
> On Thu, 12 May 2022 20:36:02 -0500
> olcott <NoOne@NoWhere.com> wrote:
>
>> On 5/12/2022 8:01 PM, Mr Flibble wrote:
>>> On Thu, 12 May 2022 19:55:44 -0500
>>> olcott <NoOne@NoWhere.com> wrote:
>>>
>>>> On 5/12/2022 7:06 PM, Ben wrote:
>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>
>>>>> I've removed the philosophy group and comp.lang.c as this is C++.
>>>>>
>>>>>> C/C++ people please critique this as the basis for an improvement
>>>>>> to std::deque.
>>>>>
>>>>> You will get critiques of the code on whatever basis people feel
>>>>> inclined to comment! You can't limit the comments to some
>>>>> particular context.
>>>>>
>>>>>> It seems to have the key functionality of std::deque and
>>>>>> does it much more simply while saving time and space.
>>>>>
>>>>> It does not have any of the functionality of std::deque.
>>>>
>>>> That is a ridiculously stupid thing to say. It has the key most
>>>> important functionality of a std:deque
>>>>
>>>> Double ended queue
>>>> deque (usually pronounced like "deck") is an irregular acronym of
>>>> double-ended queue. Double-ended queues are sequence containers
>>>> with dynamic sizes that can be expanded or contracted on both ends
>>>> (either its front or its back).
>>>>
>>>> All of the rest of the functionality of std::deque can be added as
>>>> needed.
>>>
>>> Not with your chosen data structure of two std::vectors it can't as
>>> it wouldn't meet the complexity
>>
>> It already has the same complexity.
>>
>>> and referential integrity
>>
>> and better referential integrity.
>
> You are a fucking obtuse idiot, mate.
>
> /Flibble
>

Prove that it doesn't.

--
Copyright 2022 Pete Olcott

"Talent hits a target no one else can hit;
Genius hits a target no one else can see."
Arthur Schopenhauer

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

<20220513170239.0000273b@reddwarf.jmc>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=32286&group=comp.theory#32286

 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

<20220513170449.0000502d@reddwarf.jmc>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=32287&group=comp.theory#32287

 copy link   Newsgroups: comp.theory comp.lang.c++
Path: i2pn2.org!i2pn.org!aioe.org!feeder1.feed.usenet.farm!feed.usenet.farm!peer02.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.lang.c++
Subject: Re: Implementing a two-way Turing Machine tape as an improvement to
std::deque
Message-ID: <20220513170449.0000502d@reddwarf.jmc>
References: <cNWdnXqV1cXzEuD_nZ2dnUU7_8zNnZ2d@giganews.com>
<87wneq1ejm.fsf@bsb.me.uk>
<MeOdncpeZacPMeD_nZ2dnUU7_8zNnZ2d@giganews.com>
<20220513020134.00003f42@reddwarf.jmc>
<D7WdnSvo4syeK-D_nZ2dnUU7_81g4p2d@giganews.com>
<20220513080435.00002bdc@reddwarf.jmc>
<zdmdnVntirsfHeP_nZ2dnUU7_8zNnZ2d@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: 62
X-Complaints-To: abuse@eweka.nl
NNTP-Posting-Date: Fri, 13 May 2022 16:04:48 UTC
Date: Fri, 13 May 2022 17:04:49 +0100
X-Received-Bytes: 3073
 by: Mr Flibble - Fri, 13 May 2022 16:04 UTC

On Fri, 13 May 2022 11:00:01 -0500
olcott <NoOne@NoWhere.com> wrote:

> On 5/13/2022 2:04 AM, Mr Flibble wrote:
> > On Thu, 12 May 2022 20:36:02 -0500
> > olcott <NoOne@NoWhere.com> wrote:
> >
> >> On 5/12/2022 8:01 PM, Mr Flibble wrote:
> >>> On Thu, 12 May 2022 19:55:44 -0500
> >>> olcott <NoOne@NoWhere.com> wrote:
> >>>
> >>>> On 5/12/2022 7:06 PM, Ben wrote:
> >>>>> olcott <NoOne@NoWhere.com> writes:
> >>>>>
> >>>>> I've removed the philosophy group and comp.lang.c as this is
> >>>>> C++.
> >>>>>> C/C++ people please critique this as the basis for an
> >>>>>> improvement to std::deque.
> >>>>>
> >>>>> You will get critiques of the code on whatever basis people feel
> >>>>> inclined to comment! You can't limit the comments to some
> >>>>> particular context.
> >>>>>
> >>>>>> It seems to have the key functionality of std::deque and
> >>>>>> does it much more simply while saving time and space.
> >>>>>
> >>>>> It does not have any of the functionality of std::deque.
> >>>>
> >>>> That is a ridiculously stupid thing to say. It has the key most
> >>>> important functionality of a std:deque
> >>>>
> >>>> Double ended queue
> >>>> deque (usually pronounced like "deck") is an irregular acronym of
> >>>> double-ended queue. Double-ended queues are sequence containers
> >>>> with dynamic sizes that can be expanded or contracted on both
> >>>> ends (either its front or its back).
> >>>>
> >>>> All of the rest of the functionality of std::deque can be added
> >>>> as needed.
> >>>
> >>> Not with your chosen data structure of two std::vectors it can't
> >>> as it wouldn't meet the complexity
> >>
> >> It already has the same complexity.
> >>
> >>> and referential integrity
> >>
> >> and better referential integrity.
> >
> > You are a fucking obtuse idiot, mate.
> >
> > /Flibble
> >
>
> Prove that it doesn't.
Prove to me that you are not an idiot by explaining what happens if
vector Left is empty, vector Right is non-empty and you call pop_front?
Hint: as your design currently stands it will crash.

/Flibble

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

<87tu9txued.fsf@bsb.me.uk>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=32296&group=comp.theory#32296

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: ben.use...@bsb.me.uk (Ben)
Newsgroups: comp.theory
Subject: Re: Implementing a two-way Turing Machine tape as an improvement to std::deque
Date: Fri, 13 May 2022 17:35:38 +0100
Organization: A noiseless patient Spider
Lines: 128
Message-ID: <87tu9txued.fsf@bsb.me.uk>
References: <cNWdnXqV1cXzEuD_nZ2dnUU7_8zNnZ2d@giganews.com>
<87wneq1ejm.fsf@bsb.me.uk>
<MeOdncpeZacPMeD_nZ2dnUU7_8zNnZ2d@giganews.com>
<8735he1abh.fsf@bsb.me.uk>
<692dnROYz_PMWeD_nZ2dnUU7_83NnZ2d@giganews.com>
<87sfpdzofd.fsf@bsb.me.uk>
<-LadnQlxFteO4eP_nZ2dnUU7_8zNnZ2d@giganews.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 8bit
Injection-Info: reader02.eternal-september.org; posting-host="9d7070da1378146bf8b2ebf4ad06ac0b";
logging-data="12938"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18G80xmbkvEFeDSrvMHWeTnkIfER1fWiTU="
Cancel-Lock: sha1:0IRBo/kIsrqDfqSHh0gQ5nRRwMw=
sha1:AaMNNa1V0pEDXaIP7F/nOLZ7rLQ=
X-BSB-Auth: 1.acc654fe1ff7618ab1e7.20220513173538BST.87tu9txued.fsf@bsb.me.uk
 by: Ben - Fri, 13 May 2022 16:35 UTC

olcott <NoOne@NoWhere.com> writes:

> On 5/13/2022 6:01 AM, Ben wrote:
>> olcott <NoOne@NoWhere.com> writes:
>>
>>> On 5/12/2022 8:38 PM, Ben wrote:
>>>> olcott <NoOne@NoWhere.com> writes:
>>>>
>>>>> On 5/12/2022 7:06 PM, Ben wrote:
>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>> I've removed the philosophy group and comp.lang.c as this is C++.
>>>>>>
>>>>>>> C/C++ people please critique this as the basis for an improvement to
>>>>>>> std::deque.
>>>>>> You will get critiques of the code on whatever basis people feel
>>>>>> inclined to comment! You can't limit the comments to some particular
>>>>>> context.
>>>>>>
>>>>>>> It seems to have the key functionality of std::deque and
>>>>>>> does it much more simply while saving time and space.
>>>>>> It does not have any of the functionality of std::deque.
>>>>>
>>>>> That is a ridiculously stupid thing to say. It has the key most
>>>>> important functionality of a std:deque
>>>> Generally, when you think I am saying something absurd, you should
>>>> re-consider.
>>>> A deque has (at least) these operations:
>>>> front
>>>> back
>>>> push_front
>>>> push_back
>>>> pop_front
>>>> pop_back
>>>> Your Tape_Type has none of these. Even internally it does not maintain
>>>> the right data to be able to provide them.
>>>
>>> I also added a reserve so you could do a pre-allocated speed test.
>>>
>>> It was easy to add these in terms of the current implementation:
>> You have not provided the correct operations, so you have no idea how
>> hard it might be to do that. This keeps looking more and more like a
>> distraction to put off having to do what you said.
>>
>>> 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); }
>> Not correct. Test first.
>
>
> They are all correct. I don't see how you can say that they are not
> when you don't know my design.

You posted the code. Have you fixed it now? I've not see correct code
for a deque yet.

>>>>> Double ended queue
>>>>> deque (usually pronounced like "deck") is an irregular acronym of
>>>>> double-ended queue. Double-ended queues are sequence containers with
>>>>> dynamic sizes that can be expanded or contracted on both ends (either
>>>>> its front or its back).
>>>>>
>>>>> All of the rest of the functionality of std::deque can be added as
>>>>> needed.
>>>> You mean you could implement a deque using two arrays if you chose to?
>>>> So what? All I am saying is that you haven't got a deque.
>>>
>>> If I added these things then I would have a much better deque.
>>
>> If you added them correctly and then removed the things that a deque
>> should not have. In other words, if you implemented a deque.
>
> I mere want to know that the most basic functionality of my deque is
> (a) simpler (b) faster (c) smaller than a std:deque.

And when you've correctly implemented a deque, when you've studied the
internals of std:deque, adn when you done extensive testing you can say
which of (a), (b) and (c) you have achieved.

> If Tape_Type.reserve() is used it should be your std::string.

Sure. But that's an odd test.

>>>>> Yes I tested so I don't see what you mean.
>>>> Testing should have caught the bug in operator[].
>>>
>>> It is was a new refactoring of existing working code.
>> A software engineer runs all the tests after every edit (or at least
>> before every commit). (I am not a software engineer.)
>>
>>>> I plugged your tape class into my C++ TM interpreter and it made it
>>>> slightly slower for the "big" BB(5) test compared with my naive tape
>>>> that just uses a single string.
>>>>
>>>
>>> std::string or char * ?
>> std::string.
>>
>>> If char * was pre-allocated that would give it a big speed advantage.
>> Nothing pre-allocated.
>>
>>>> Mind you, I prefer using a string to all the other methods I've tried
>>>> because it's so convenient. You can set up the TM with an input simply
>>>> by writing
>>>> tape = input
>>>> and you can debug by printing the tape any time you like. And I use a
>>>> string_view to get the non-blank "result" out of the TM and the end of a
>>>> run. All easy to get round with a couple of functions, but still, since
>>>> it's fast I see no reason t change.
>>>
>>> What about memory allocation?
>> What about it? std::string does it.
>
> It is probably much slower than my system now that I added reserve.
> I do like the idea of simplicity, it is my primary design goal.

Using a std::string for the tape is very simple.

--
Ben.
"le génie humain a des limites, quand la bêtise humaine n’en a pas"
Alexandre Dumas (fils)

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

<44CdnU0P0pZTEuP_nZ2dnUU7_81g4p2d@giganews.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=32300&group=comp.theory#32300

 copy link   Newsgroups: comp.theory 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!buffer1.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Fri, 13 May 2022 12:05:18 -0500
Date: Fri, 13 May 2022 12:05:18 -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.lang.c++
References: <cNWdnXqV1cXzEuD_nZ2dnUU7_8zNnZ2d@giganews.com>
<87wneq1ejm.fsf@bsb.me.uk> <MeOdncpeZacPMeD_nZ2dnUU7_8zNnZ2d@giganews.com>
<20220513020134.00003f42@reddwarf.jmc>
<D7WdnSvo4syeK-D_nZ2dnUU7_81g4p2d@giganews.com>
<20220513080435.00002bdc@reddwarf.jmc>
<zdmdnVntirsfHeP_nZ2dnUU7_8zNnZ2d@giganews.com>
<20220513170449.0000502d@reddwarf.jmc>
From: NoO...@NoWhere.com (olcott)
In-Reply-To: <20220513170449.0000502d@reddwarf.jmc>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <44CdnU0P0pZTEuP_nZ2dnUU7_81g4p2d@giganews.com>
Lines: 73
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-cIAdWTwi8MqYnb9wOamha7Ofjt7kxohUzW+1DsEgkSkCrOk9NslTRrpvKrwMPjzo/u6xA5T/OzsTcWp!V42FDiL0CMDc7QlpdbCkpaFh0BStjvoRT5QLc6hZmO6GjVumFmMZ3TYU1DQlAzjNsH0Lj24NWo0=
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: 3984
 by: olcott - Fri, 13 May 2022 17:05 UTC

On 5/13/2022 11:04 AM, Mr Flibble wrote:
> On Fri, 13 May 2022 11:00:01 -0500
> olcott <NoOne@NoWhere.com> wrote:
>
>> On 5/13/2022 2:04 AM, Mr Flibble wrote:
>>> On Thu, 12 May 2022 20:36:02 -0500
>>> olcott <NoOne@NoWhere.com> wrote:
>>>
>>>> On 5/12/2022 8:01 PM, Mr Flibble wrote:
>>>>> On Thu, 12 May 2022 19:55:44 -0500
>>>>> olcott <NoOne@NoWhere.com> wrote:
>>>>>
>>>>>> On 5/12/2022 7:06 PM, Ben wrote:
>>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>>
>>>>>>> I've removed the philosophy group and comp.lang.c as this is
>>>>>>> C++.
>>>>>>>> C/C++ people please critique this as the basis for an
>>>>>>>> improvement to std::deque.
>>>>>>>
>>>>>>> You will get critiques of the code on whatever basis people feel
>>>>>>> inclined to comment! You can't limit the comments to some
>>>>>>> particular context.
>>>>>>>
>>>>>>>> It seems to have the key functionality of std::deque and
>>>>>>>> does it much more simply while saving time and space.
>>>>>>>
>>>>>>> It does not have any of the functionality of std::deque.
>>>>>>
>>>>>> That is a ridiculously stupid thing to say. It has the key most
>>>>>> important functionality of a std:deque
>>>>>>
>>>>>> Double ended queue
>>>>>> deque (usually pronounced like "deck") is an irregular acronym of
>>>>>> double-ended queue. Double-ended queues are sequence containers
>>>>>> with dynamic sizes that can be expanded or contracted on both
>>>>>> ends (either its front or its back).
>>>>>>
>>>>>> All of the rest of the functionality of std::deque can be added
>>>>>> as needed.
>>>>>
>>>>> Not with your chosen data structure of two std::vectors it can't
>>>>> as it wouldn't meet the complexity
>>>>
>>>> It already has the same complexity.
>>>>
>>>>> and referential integrity
>>>>
>>>> and better referential integrity.
>>>
>>> You are a fucking obtuse idiot, mate.
>>>
>>> /Flibble
>>>
>>
>> Prove that it doesn't.
>
> Prove to me that you are not an idiot by explaining what happens if
> vector Left is empty, vector Right is non-empty and you call pop_front?
> Hint: as your design currently stands it will crash.
>
> /Flibble
>

Simply extend the definition of the member function.
Maybe std::deque performs better at this?

--
Copyright 2022 Pete Olcott

"Talent hits a target no one else can hit;
Genius hits a target no one else can see."
Arthur Schopenhauer

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

<44CdnU4P0pb4DOP_nZ2dnUU7_81g4p2d@giganews.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=32304&group=comp.theory#32304

 copy link   Newsgroups: comp.theory
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!buffer1.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Fri, 13 May 2022 12:12:05 -0500
Date: Fri, 13 May 2022 12:12:04 -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
References: <cNWdnXqV1cXzEuD_nZ2dnUU7_8zNnZ2d@giganews.com>
<87wneq1ejm.fsf@bsb.me.uk> <MeOdncpeZacPMeD_nZ2dnUU7_8zNnZ2d@giganews.com>
<8735he1abh.fsf@bsb.me.uk> <692dnROYz_PMWeD_nZ2dnUU7_83NnZ2d@giganews.com>
<87sfpdzofd.fsf@bsb.me.uk> <-LadnQlxFteO4eP_nZ2dnUU7_8zNnZ2d@giganews.com>
<87tu9txued.fsf@bsb.me.uk>
From: NoO...@NoWhere.com (olcott)
In-Reply-To: <87tu9txued.fsf@bsb.me.uk>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <44CdnU4P0pb4DOP_nZ2dnUU7_81g4p2d@giganews.com>
Lines: 135
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-RusCSgN39FsvsNLART+U4IpLe/GzfQqmBX1lbrr8IEta2Ct8B8drk73MS/pZkWI3vlw223Wc0BFW631!TUeATy4BB861U72juuI9JGVriq8AuLQeaAV1kR4HZSMyF51aHhhW6KUs/m0QlXoXadGMn1QPcoE=
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: 6929
 by: olcott - Fri, 13 May 2022 17:12 UTC

On 5/13/2022 11:35 AM, Ben wrote:
> olcott <NoOne@NoWhere.com> writes:
>
>> On 5/13/2022 6:01 AM, Ben wrote:
>>> olcott <NoOne@NoWhere.com> writes:
>>>
>>>> On 5/12/2022 8:38 PM, Ben wrote:
>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>
>>>>>> On 5/12/2022 7:06 PM, Ben wrote:
>>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>> I've removed the philosophy group and comp.lang.c as this is C++.
>>>>>>>
>>>>>>>> C/C++ people please critique this as the basis for an improvement to
>>>>>>>> std::deque.
>>>>>>> You will get critiques of the code on whatever basis people feel
>>>>>>> inclined to comment! You can't limit the comments to some particular
>>>>>>> context.
>>>>>>>
>>>>>>>> It seems to have the key functionality of std::deque and
>>>>>>>> does it much more simply while saving time and space.
>>>>>>> It does not have any of the functionality of std::deque.
>>>>>>
>>>>>> That is a ridiculously stupid thing to say. It has the key most
>>>>>> important functionality of a std:deque
>>>>> Generally, when you think I am saying something absurd, you should
>>>>> re-consider.
>>>>> A deque has (at least) these operations:
>>>>> front
>>>>> back
>>>>> push_front
>>>>> push_back
>>>>> pop_front
>>>>> pop_back
>>>>> Your Tape_Type has none of these. Even internally it does not maintain
>>>>> the right data to be able to provide them.
>>>>
>>>> I also added a reserve so you could do a pre-allocated speed test.
>>>>
>>>> It was easy to add these in terms of the current implementation:
>>> You have not provided the correct operations, so you have no idea how
>>> hard it might be to do that. This keeps looking more and more like a
>>> distraction to put off having to do what you said.
>>>
>>>> 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); }
>>> Not correct. Test first.
>>
>>
>> They are all correct. I don't see how you can say that they are not
>> when you don't know my design.
>
> You posted the code. Have you fixed it now? I've not see correct code
> for a deque yet.
>
>>>>>> Double ended queue
>>>>>> deque (usually pronounced like "deck") is an irregular acronym of
>>>>>> double-ended queue. Double-ended queues are sequence containers with
>>>>>> dynamic sizes that can be expanded or contracted on both ends (either
>>>>>> its front or its back).
>>>>>>
>>>>>> All of the rest of the functionality of std::deque can be added as
>>>>>> needed.
>>>>> You mean you could implement a deque using two arrays if you chose to?
>>>>> So what? All I am saying is that you haven't got a deque.
>>>>
>>>> If I added these things then I would have a much better deque.
>>>
>>> If you added them correctly and then removed the things that a deque
>>> should not have. In other words, if you implemented a deque.
>>
>> I mere want to know that the most basic functionality of my deque is
>> (a) simpler (b) faster (c) smaller than a std:deque.
>
> And when you've correctly implemented a deque, when you've studied the
> internals of std:deque, adn when you done extensive testing you can say
> which of (a), (b) and (c) you have achieved.
>
>> If Tape_Type.reserve() is used it should be your std::string.
>
> Sure. But that's an odd test.
>
>>>>>> Yes I tested so I don't see what you mean.
>>>>> Testing should have caught the bug in operator[].
>>>>
>>>> It is was a new refactoring of existing working code.
>>> A software engineer runs all the tests after every edit (or at least
>>> before every commit). (I am not a software engineer.)
>>>
>>>>> I plugged your tape class into my C++ TM interpreter and it made it
>>>>> slightly slower for the "big" BB(5) test compared with my naive tape
>>>>> that just uses a single string.
>>>>>
>>>>
>>>> std::string or char * ?
>>> std::string.
>>>
>>>> If char * was pre-allocated that would give it a big speed advantage.
>>> Nothing pre-allocated.
>>>
>>>>> Mind you, I prefer using a string to all the other methods I've tried
>>>>> because it's so convenient. You can set up the TM with an input simply
>>>>> by writing
>>>>> tape = input
>>>>> and you can debug by printing the tape any time you like. And I use a
>>>>> string_view to get the non-blank "result" out of the TM and the end of a
>>>>> run. All easy to get round with a couple of functions, but still, since
>>>>> it's fast I see no reason t change.
>>>>
>>>> What about memory allocation?
>>> What about it? std::string does it.
>>
>> It is probably much slower than my system now that I added reserve.
>> I do like the idea of simplicity, it is my primary design goal.
>
> Using a std::string for the tape is very simple.
>

How does it compare for speed on your test code when you use
Tape_Type::reserve()?

--
Copyright 2022 Pete Olcott

"Talent hits a target no one else can hit;
Genius hits a target no one else can see."
Arthur Schopenhauer

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

<87czghxni1.fsf@bsb.me.uk>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=32320&group=comp.theory#32320

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: ben.use...@bsb.me.uk (Ben)
Newsgroups: comp.theory
Subject: Re: Implementing a two-way Turing Machine tape as an improvement to std::deque
Date: Fri, 13 May 2022 20:04:38 +0100
Organization: A noiseless patient Spider
Lines: 35
Message-ID: <87czghxni1.fsf@bsb.me.uk>
References: <cNWdnXqV1cXzEuD_nZ2dnUU7_8zNnZ2d@giganews.com>
<87wneq1ejm.fsf@bsb.me.uk>
<MeOdncpeZacPMeD_nZ2dnUU7_8zNnZ2d@giganews.com>
<8735he1abh.fsf@bsb.me.uk>
<692dnROYz_PMWeD_nZ2dnUU7_83NnZ2d@giganews.com>
<87sfpdzofd.fsf@bsb.me.uk>
<-LadnQlxFteO4eP_nZ2dnUU7_8zNnZ2d@giganews.com>
<87tu9txued.fsf@bsb.me.uk>
<44CdnU4P0pb4DOP_nZ2dnUU7_81g4p2d@giganews.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 8bit
Injection-Info: reader02.eternal-september.org; posting-host="9d7070da1378146bf8b2ebf4ad06ac0b";
logging-data="23228"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19bf+OjmPsp/Y6Ri9sQIx74zD+pydMnp5I="
Cancel-Lock: sha1:yDJh53zg0oop0d8G7fR+Uni8c0E=
sha1:+H9DR1SjGd3KUC91dKjOWL3Bffw=
X-BSB-Auth: 1.298f26c9d55d235afd1d.20220513200438BST.87czghxni1.fsf@bsb.me.uk
 by: Ben - Fri, 13 May 2022 19:04 UTC

olcott <NoOne@NoWhere.com> writes:

> On 5/13/2022 11:35 AM, Ben wrote:
>> olcott <NoOne@NoWhere.com> writes:
>>
>>> On 5/13/2022 6:01 AM, Ben wrote:
>>>> olcott <NoOne@NoWhere.com> writes:

>>>>> What about memory allocation?
>>>>
>>>> What about it? std::string does it.
>>>
>>> It is probably much slower than my system now that I added reserve.

Odd that you are prepared to guess.

>>> I do like the idea of simplicity, it is my primary design goal.
>>
>> Using a std::string for the tape is very simple.
>
> How does it compare for speed on your test code when you use
> Tape_Type::reserve()?

Using reserve makes no difference to the speed of either one in the only
test case I have that takes long enough to measure. This is what I'd
expect. The test case does 47,176,870 transitions and the tape ends up
being only 12,289 symbols long. The memory allocation will be a tiny
fraction of the cost. It's not measurable.

Of course that's just one test case. What TMs are you using to test?

--
Ben.
"le génie humain a des limites, quand la bêtise humaine n’en a pas"
Alexandre Dumas (fils)

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

<0fqdnZ2p1fvIMuP_nZ2dnUU7_8zNnZ2d@giganews.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=32328&group=comp.theory#32328

 copy link   Newsgroups: comp.theory
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 14:19:49 -0500
Date: Fri, 13 May 2022 14:19:48 -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
References: <cNWdnXqV1cXzEuD_nZ2dnUU7_8zNnZ2d@giganews.com>
<87wneq1ejm.fsf@bsb.me.uk> <MeOdncpeZacPMeD_nZ2dnUU7_8zNnZ2d@giganews.com>
<8735he1abh.fsf@bsb.me.uk> <692dnROYz_PMWeD_nZ2dnUU7_83NnZ2d@giganews.com>
<87sfpdzofd.fsf@bsb.me.uk> <-LadnQlxFteO4eP_nZ2dnUU7_8zNnZ2d@giganews.com>
<87tu9txued.fsf@bsb.me.uk> <44CdnU4P0pb4DOP_nZ2dnUU7_81g4p2d@giganews.com>
<87czghxni1.fsf@bsb.me.uk>
From: NoO...@NoWhere.com (olcott)
In-Reply-To: <87czghxni1.fsf@bsb.me.uk>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <0fqdnZ2p1fvIMuP_nZ2dnUU7_8zNnZ2d@giganews.com>
Lines: 49
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-lgr7L98T1LMtiTbGN/lhNekG5zQFHAoG2HUFoau7eeGwz+xXyGQ4dyvtzKHLp2F9yDhxV4u9+6tk59Y!3rq03clunEquhlAMNZRLf6zyxC/WR3XqE8IvV+gLhLytTIj9mL2Eba+XtUkLg9GoeW0q0MMgKhg=
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: 3019
 by: olcott - Fri, 13 May 2022 19:19 UTC

On 5/13/2022 2:04 PM, Ben wrote:
> olcott <NoOne@NoWhere.com> writes:
>
>> On 5/13/2022 11:35 AM, Ben wrote:
>>> olcott <NoOne@NoWhere.com> writes:
>>>
>>>> On 5/13/2022 6:01 AM, Ben wrote:
>>>>> olcott <NoOne@NoWhere.com> writes:
>
>>>>>> What about memory allocation?
>>>>>
>>>>> What about it? std::string does it.
>>>>
>>>> It is probably much slower than my system now that I added reserve.
>
> Odd that you are prepared to guess.
>
>>>> I do like the idea of simplicity, it is my primary design goal.
>>>
>>> Using a std::string for the tape is very simple.
>>
>> How does it compare for speed on your test code when you use
>> Tape_Type::reserve()?
>
> Using reserve makes no difference to the speed of either one in the only
> test case I have that takes long enough to measure. This is what I'd
> expect. The test case does 47,176,870 transitions and the tape ends up
> being only 12,289 symbols long. The memory allocation will be a tiny
> fraction of the cost. It's not measurable.
>

So maybe yours is better. I am happy to find that you have some
significant programming skill, I never knew this before.

> Of course that's just one test case. What TMs are you using to test?
>

tm> read tm paren
tm> set tape ((()))
tm> set trace tape
tm> go

--
Copyright 2022 Pete Olcott

"Talent hits a target no one else can hit;
Genius hits a target no one else can see."
Arthur Schopenhauer

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/devel/article-flat.php?id=32336&group=comp.theory#32336

 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
Pages:12
server_pubkey.txt

rocksolid light 0.9.7
clearnet tor