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

Groups > comp.lang.c++ > #121205

Re: Is this program OOP?

Show all headers | View raw

On 14/12/2024 09:22, wij wrote:
> On Thu, 2024-12-12 at 08:59 +0100, David Brown wrote:

> "21 * 33 * 13 * 33 * 33 = 9810801" is a pretty much *optimized* solution.
> Depending on the viewpoint (what kind of problem you want to solve),
> the puzzle solving algorithm can be from O(1) to O(2^N).
> 

"Optimised" would mean, as I see it, as fast as possible within 
reasonably practical limits.  (And of course it would be unreasonable to 
simply pre-calculate the answer.)  For a problem like this, there are 
three kinds of optimisations - algorithmic, choice of language or 
compute platform, and optimisation of the implementation itself.

I have done none of these, so IMHO my solution is far from optimal.  All 
I did was split the problem into two parts based on a simple criteria. 
To me, the split was so obvious that I do not see it as something 
special - but perhaps it is one of these things that seems obvious once 
you have thought of it.

Algorithmic optimisation would involve dividing the problem into more 
parts, probably using a search tree and stack structure of some kind but 
ensuring that it is all allocated and handled with as little dynamic 
allocation as possible.

Language and compute platform choice optimisation would certainly result 
in something other than single-threaded Python.  It might mean Prolog, 
it might mean C++.  Maybe this can be done on a GPU in CUDA - I don't 
know such platforms well.  Certainly it would aim to be multi-threaded 
(at least, for a similar style of problem that is large enough to 
justify the overheads).  And a key consideration would be cache friendly 
structures.

And I didn't bother doing any kind of implementation optimisation at 
all.  There is probably scope for increasing speed by a factor of 5 or 
so in straightforward Python, more from the use of numpy.  But there's a 
lot more possibility in C++.


>>
>> Now I just need to translate my code into C++ :-)
> 
> So far from I know, using C++ to beat those numbers you provided from Python
> is no trivial task. I estimate the limit is 0.08s (on my PC's speed) if nothing
> significantly changed.
> 

I don't think it should be hard to do a lot better than the Python code 
from a fairly direct translation of the Python - lists to std::vector<>, 
and so on.  Translating into more optimal C++ code would lead to a huge 
improvement in speed.  I would not expect the results to be measurable 
with the "time" command without looping the algorithm many times.

Back to comp.lang.c++ | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Is this program OOP? wij <wyniijj5@gmail.com> - 2024-12-09 20:08 +0800
  Re: Is this program OOP? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-09 09:35 -0800
    Re: Is this program OOP? wij <wyniijj5@gmail.com> - 2024-12-10 06:35 +0800
      Re: Is this program OOP? Ross Finlayson <ross.a.finlayson@gmail.com> - 2024-12-09 17:26 -0800
      Re: Is this program OOP? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-09 22:15 -0800
        Re: Is this program OOP? wij <wyniijj5@gmail.com> - 2024-12-10 17:23 +0800
          Re: Is this program OOP? David Brown <david.brown@hesbynett.no> - 2024-12-10 17:04 +0100
            Re: Is this program OOP? Muttley@DastardlyHQ.org - 2024-12-10 16:35 +0000
              Re: Is this program OOP? David Brown <david.brown@hesbynett.no> - 2024-12-11 08:59 +0100
                Re: Is this program OOP? Muttley@DastardlyHQ.org - 2024-12-11 08:40 +0000
                Re: Is this program OOP? Ross Finlayson <ross.a.finlayson@gmail.com> - 2024-12-11 09:41 -0800
                Re: Is this program OOP? Muttley@DastardlyHQ.org - 2024-12-12 08:32 +0000
                Re: Is this program OOP? Ross Finlayson <ross.a.finlayson@gmail.com> - 2024-12-12 10:43 -0800
                Re: Is this program OOP? Ross Finlayson <ross.a.finlayson@gmail.com> - 2024-12-12 17:28 -0800
                Re: Is this program OOP? Paavo Helde <eesnimi@osa.pri.ee> - 2024-12-12 09:59 +0200
                Re: Is this program OOP? Muttley@DastardlyHQ.org - 2024-12-12 08:37 +0000
            Re: Is this program OOP? wij <wyniijj5@gmail.com> - 2024-12-11 01:02 +0800
              Re: Is this program OOP? David Brown <david.brown@hesbynett.no> - 2024-12-11 12:42 +0100
                Re: Is this program OOP? wij <wyniijj5@gmail.com> - 2024-12-12 13:26 +0800
                Re: Is this program OOP? David Brown <david.brown@hesbynett.no> - 2024-12-12 08:59 +0100
                Re: Is this program OOP? wij <wyniijj5@gmail.com> - 2024-12-14 16:22 +0800
                Re: Is this program OOP? David Brown <david.brown@hesbynett.no> - 2024-12-15 10:45 +0100
              Re: Is this program OOP? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-12 08:00 -0800

csiph-web