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 17:35 +0100 |
| Organization | A noiseless patient Spider |
| Message-ID | <87tu9txued.fsf@bsb.me.uk> (permalink) |
| References | (2 earlier) <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> |
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)
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