Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
| From | Ben <ben.usenet@bsb.me.uk> |
|---|---|
| Newsgroups | comp.theory |
| Subject | Re: Implementing a two-way Turing Machine tape as an improvement to std::deque |
| Date | 2022-05-13 12:01 +0100 |
| Organization | A noiseless patient Spider |
| Message-ID | <87sfpdzofd.fsf@bsb.me.uk> (permalink) |
| 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> |
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)
Back to comp.theory | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll 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