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

Groups > comp.theory > #50308 > unrolled thread

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

Back to article view | Back to comp.theory

Contents

  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

Page 2 of 2 — ← Prev page 1 [2]

#50338

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 and referential integrity
requirements offered by std::deque. I have told you this three times
now.

/Flibble

[toc] | [prev] | [next] | [standalone]

#50343

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.

> requirements offered by std::deque. I have told you this three times
> now.
> 
> /Flibble
> 


-- 
Copyright 2022 Pete Olcott

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

[toc] | [prev] | [next] | [standalone]

#50356

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

[toc] | [prev] | [next] | [standalone]

#50370

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

[toc] | [prev] | [next] | [standalone]

#50373

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

[toc] | [prev] | [next] | [standalone]

#50386

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

[toc] | [prev] | [next] | [standalone]

#50345

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
  pop_front
  push_front
  pop_back
  push_back

Your Tape_Type has none of these.  Even internally it does not maintain
the right data to be able to provide them.

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

>> There is a
>> commonly used (though not particularly efficient) way to implement a
>> deque using two arrays, but this is not it.
>> 
>>> #define tape_element unsigned char
>> Use a typedef or using declaration.  Also, I'd put the typedef in the
>> class as the type belongs to the class (as least that appears to be the
>> case from the name you've chosen).
>> 
>>> 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
>> The comments are wrong since you push_back('_').
>> 
>>>    void Write(tape_element Y){ this->operator[](Tape_Head) = Y; };
>>>    tape_element Read()       { return this->operator[](Tape_Head); };
>> I'd write (*this)[Tape_Head] but I suppose that's just a matter of style.
>> 
>>>    Tape_Type(){ Right.push_back('_'); } // constructor
>> The constructor leaves a Tape_Type object in an unusable state, but
>> that's due to a bug in operator[].  Did you test?
>
> Yes I tested so I don't see what you mean.

Testing should have caught the bug in operator[].

>>>    void Output();
>>> };
>>>
>>> tape_element& Tape_Type::operator[](int index)
>>> {
>>>    if (index > 0)
>>>      return Right[index];
>> Bug.  You meant index >= 0 I think.
>
> Yes Richard caught that. That was a new refactoring.
>> 
>>>    int Left_Index = ((index * -1) -1);
>> Why not -index - 1?
>> 
>>>    return Left[Left_Index];
>> Do you think introducing a new variable really make the code clearer
>> that simply writing
>>    return Left[-index - 1];
>> ?  Personally, I'd write the whole thing as
>>    return index >= 0 ? Right[index] : Left[-index - 1];
>> 
>>> }
>>>
>>> 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('_');
>>> }
>>
>> I find the capitalisation odd and unhelpful as there does not seem to be
>> any consistency about it. 
>
> I found all of your suggestions very helpful.
> I don't see the bug in the constructor.

There is none.  I just said the constructor leaves the tape unusable
because of the bug in operator[].

> I like mixed case because it is easier to read, mine not be consistent.
>
> Here they are implemented.
>
> //
> // 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)
> //
> // Tape_Type has functionality very similar to std::deque

This comment is not correct.

> // yet implements this functionality much more simply.
> // This saves time and space.
> //
> class Tape_Type
> {
> typedef unsigned char tape_element;

You probably want that to be a public typedef.  And now that it's in the
class, the name can be sorter.  The usual convention is _t for types:

  typedef unsigned char element_t;

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.

Note: this is not a comment on the design of your tape.  There's nothing
wrong with it (except a little inconvenience, see below).  The speed
will be determined almost entirely by how std::string and std::vector
are implemented.  You might see completely different timings just by
linking with a different library.

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.

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

[toc] | [prev] | [next] | [standalone]

#50350

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:

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); }



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

>>> There is a
>>> commonly used (though not particularly efficient) way to implement a
>>> deque using two arrays, but this is not it.
>>>
>>>> #define tape_element unsigned char
>>> Use a typedef or using declaration.  Also, I'd put the typedef in the
>>> class as the type belongs to the class (as least that appears to be the
>>> case from the name you've chosen).
>>>
>>>> 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
>>> The comments are wrong since you push_back('_').
>>>
>>>>     void Write(tape_element Y){ this->operator[](Tape_Head) = Y; };
>>>>     tape_element Read()       { return this->operator[](Tape_Head); };
>>> I'd write (*this)[Tape_Head] but I suppose that's just a matter of style.
>>>
>>>>     Tape_Type(){ Right.push_back('_'); } // constructor
>>> The constructor leaves a Tape_Type object in an unusable state, but
>>> that's due to a bug in operator[].  Did you 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.

>>>>     void Output();
>>>> };
>>>>
>>>> tape_element& Tape_Type::operator[](int index)
>>>> {
>>>>     if (index > 0)
>>>>       return Right[index];
>>> Bug.  You meant index >= 0 I think.
>>
>> Yes Richard caught that. That was a new refactoring.
>>>
>>>>     int Left_Index = ((index * -1) -1);
>>> Why not -index - 1?
>>>
>>>>     return Left[Left_Index];
>>> Do you think introducing a new variable really make the code clearer
>>> that simply writing
>>>     return Left[-index - 1];
>>> ?  Personally, I'd write the whole thing as
>>>     return index >= 0 ? Right[index] : Left[-index - 1];
>>>
>>>> }
>>>>
>>>> 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('_');
>>>> }
>>>
>>> I find the capitalisation odd and unhelpful as there does not seem to be
>>> any consistency about it.
>>
>> I found all of your suggestions very helpful.
>> I don't see the bug in the constructor.
> 
> There is none.  I just said the constructor leaves the tape unusable
> because of the bug in operator[].

Oh, OK.

> 
>> I like mixed case because it is easier to read, mine not be consistent.
>>
>> Here they are implemented.
>>
>> //
>> // 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)
>> //
>> // Tape_Type has functionality very similar to std::deque
> 
> This comment is not correct.
> 
>> // yet implements this functionality much more simply.
>> // This saves time and space.
>> //
>> class Tape_Type
>> {
>> typedef unsigned char tape_element;
> 
> You probably want that to be a public typedef.  And now that it's in the
> class, the name can be sorter.  The usual convention is _t for types:
> 
>    typedef unsigned char element_t;
> 
> 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 * ?
If char * was pre-allocated that would give it a big speed advantage.

I could add reserve(left/right):
   void reserve(unsigned int N)
                      { Left.reserve(N); Right.reserve(N); }

> Note: this is not a comment on the design of your tape.  There's nothing
> wrong with it (except a little inconvenience, see below).  The speed
> will be determined almost entirely by how std::string and std::vector
> are implemented.  You might see completely different timings just by
> linking with a different library.
> 
> 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?

-- 
Copyright 2022 Pete Olcott

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

[toc] | [prev] | [next] | [standalone]

#50351

Peter Olcott wrote:
> 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:
> 
> 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); }

Could you add eggs, bacon and beans? Thanks Peter.

[toc] | [prev] | [next] | [standalone]

#50360

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.

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

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

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

[toc] | [prev] | [next] | [standalone]

#50366

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.

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

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

-- 
Copyright 2022 Pete Olcott

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

[toc] | [prev] | [next] | [standalone]

#50367

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

[toc] | [prev] | [next] | [standalone]

#50382

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)

[toc] | [prev] | [next] | [standalone]

#50390

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

[toc] | [prev] | [next] | [standalone]

#50406

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)

[toc] | [prev] | [next] | [standalone]

#50414

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

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

Back to top | Article view | comp.theory

csiph-web