Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.theory > #50367

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

Show all headers | View raw

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.
> 

Back to comp.theory | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Implementing a two-way Turing Machine tape as an improvement to std::deque olcott <NoOne@NoWhere.com> - 2022-05-12 17:51 -0500
  Re: Implementing a two-way Turing Machine tape as an improvement to std::deque Mr Flibble <flibble@reddwarf.jmc> - 2022-05-12 23:56 +0100
    Re: Implementing a two-way Turing Machine tape as an improvement to std::deque olcott <NoOne@NoWhere.com> - 2022-05-12 18:09 -0500
      Re: Implementing a two-way Turing Machine tape as an improvement to std::deque Mr Flibble <flibble@reddwarf.jmc> - 2022-05-13 00:22 +0100
        Re: Implementing a two-way Turing Machine tape as an improvement to std::deque olcott <NoOne@NoWhere.com> - 2022-05-12 18:38 -0500
          Re: Implementing a two-way Turing Machine tape as an improvement to std::deque Mr Flibble <flibble@reddwarf.jmc> - 2022-05-13 00:40 +0100
            Re: Implementing a two-way Turing Machine tape as an improvement to std::deque olcott <NoOne@NoWhere.com> - 2022-05-12 18:49 -0500
              Re: Implementing a two-way Turing Machine tape as an improvement to std::deque Mr Flibble <flibble@reddwarf.jmc> - 2022-05-13 00:53 +0100
                Re: Implementing a two-way Turing Machine tape as an improvement to std::deque olcott <NoOne@NoWhere.com> - 2022-05-12 19:12 -0500
                Re: Implementing a two-way Turing Machine tape as an improvement to std::deque Mr Flibble <flibble@reddwarf.jmc> - 2022-05-13 01:58 +0100
                Re: Implementing a two-way Turing Machine tape as an improvement to std::deque olcott <NoOne@NoWhere.com> - 2022-05-12 20:34 -0500
                Re: Implementing a two-way Turing Machine tape as an improvement to std::deque Mr Flibble <flibble@reddwarf.jmc> - 2022-05-13 08:02 +0100
                Re: Implementing a two-way Turing Machine tape as an improvement to std::deque tth <tth@none.invalid> - 2022-05-13 09:10 +0200
                Re: Implementing a two-way Turing Machine tape as an improvement to std::deque olcott <NoOne@NoWhere.com> - 2022-05-13 10:58 -0500
                Re: Implementing a two-way Turing Machine tape as an improvement to std::deque Mr Flibble <flibble@reddwarf.jmc> - 2022-05-13 17:02 +0100
                Re: Implementing a two-way Turing Machine tape as an improvement to std::deque "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2022-05-13 12:44 -0700
  Re: Implementing a two-way Turing Machine tape as an improvement to std::deque Richard Damon <Richard@Damon-Family.org> - 2022-05-12 19:23 -0400
    Re: Implementing a two-way Turing Machine tape as an improvement to std::deque olcott <NoOne@NoWhere.com> - 2022-05-12 18:32 -0500
  Re: Implementing a two-way Turing Machine tape as an improvement to std::deque Ben <ben.usenet@bsb.me.uk> - 2022-05-13 01:06 +0100
    Re: Implementing a two-way Turing Machine tape as an improvement to std::deque olcott <NoOne@NoWhere.com> - 2022-05-12 19:55 -0500
      Re: Implementing a two-way Turing Machine tape as an improvement to std::deque Mr Flibble <flibble@reddwarf.jmc> - 2022-05-13 02:01 +0100
        Re: Implementing a two-way Turing Machine tape as an improvement to std::deque olcott <NoOne@NoWhere.com> - 2022-05-12 20:36 -0500
          Re: Implementing a two-way Turing Machine tape as an improvement to std::deque Mr Flibble <flibble@reddwarf.jmc> - 2022-05-13 08:04 +0100
            Re: Implementing a two-way Turing Machine tape as an improvement to std::deque olcott <NoOne@NoWhere.com> - 2022-05-13 11:00 -0500
              Re: Implementing a two-way Turing Machine tape as an improvement to std::deque Mr Flibble <flibble@reddwarf.jmc> - 2022-05-13 17:04 +0100
                Re: Implementing a two-way Turing Machine tape as an improvement to std::deque olcott <NoOne@NoWhere.com> - 2022-05-13 12:05 -0500
      Re: Implementing a two-way Turing Machine tape as an improvement to std::deque Ben <ben.usenet@bsb.me.uk> - 2022-05-13 02:38 +0100
        Re: Implementing a two-way Turing Machine tape as an improvement to std::deque olcott <NoOne@NoWhere.com> - 2022-05-12 21:37 -0500
          Re: Implementing a two-way Turing Machine tape as an improvement to std::deque Python <python@example.invalid> - 2022-05-13 04:39 +0200
          Re: Implementing a two-way Turing Machine tape as an improvement to std::deque Ben <ben.usenet@bsb.me.uk> - 2022-05-13 12:01 +0100
            Re: Implementing a two-way Turing Machine tape as an improvement to std::deque olcott <NoOne@NoWhere.com> - 2022-05-13 10:41 -0500
              Re: Implementing a two-way Turing Machine tape as an improvement to std::deque Richard Damon <Richard@Damon-Family.org> - 2022-05-13 11:56 -0400
              Re: Implementing a two-way Turing Machine tape as an improvement to std::deque Ben <ben.usenet@bsb.me.uk> - 2022-05-13 17:35 +0100
                Re: Implementing a two-way Turing Machine tape as an improvement to std::deque olcott <NoOne@NoWhere.com> - 2022-05-13 12:12 -0500
                Re: Implementing a two-way Turing Machine tape as an improvement to std::deque Ben <ben.usenet@bsb.me.uk> - 2022-05-13 20:04 +0100
                Re: Implementing a two-way Turing Machine tape as an improvement to std::deque olcott <NoOne@NoWhere.com> - 2022-05-13 14:19 -0500

csiph-web