| Juha Nieminen <nospam@thanks.invalid>: Nov 17 07:39AM > ... and the way to speed it up is to make a vector of pointers to the > structs, and sort that. > _Then_ move the objects into their new locations. If you have a vector of pointers where each pointer essentially means "the object I'm pointing to should go to my position in the vector", moving the pointed-to elements in the original array to the same positions as the pointers sounds like a rather non-trivial task. At least if you want to do it in-place. I suppose that if it's ok to move the elements to a new vector, then it's easy. However, now it's not in-place sorting anymore, and every time you sort you'll be creating a new dynamically allocated array. |
| Philipp Klaus Krause <pkk@spth.de>: Nov 17 02:23PM +0100 Am 16.11.20 um 11:07 schrieb David Brown: > just holding booleans (I don't know if that's just the simplified > example code or from the real code), then you can use a single uint of > appropriate size. The size of the std::valarray isn't known before runtime. Often it is small, but sometimes it can also be 300 or so. |
| Philipp Klaus Krause <pkk@spth.de>: Nov 17 02:26PM +0100 Am 16.11.20 um 13:59 schrieb David Brown: > with the convenience of access operators and members as a container. As > far as I can tell, using "to_ulong" will let him do the ordering > function as a single comparison. In the non-simplified code, there is also a mask (a boost::container::flat_set<unsigned int>) involved, that selects, which entries of the std::valarray participate in the comparison. I removed it in the simplified code, since qsort seemed easier when not using a mask. |
| David Brown <david.brown@hesbynett.no>: Nov 17 10:13PM +0100 On 17/11/2020 14:26, Philipp Klaus Krause wrote: > boost::container::flat_set<unsigned int>) involved, that selects, which > entries of the std::valarray participate in the comparison. I removed it > in the simplified code, since qsort seemed easier when not using a mask. Again, you have more and more big, complex and time-consuming structures that have constructors, destructors and allocated memory resources - and you are surprised that it takes time to move them around when sorting. You have a background in small microcontroller systems. Think like an embedded programmer. How would you be doing all this in C on an 8051? You would /not/ be using a big, bulky general containers like this. You need a set of values - generally a small number, but occasionally a big number up to 300 - with the value type being bits. You need a mask of bits to say which of these you have in your comparisons. The way to implement this is with bit arrays. You can use uint64_t, or smaller sizes, or you can use std::bitset if you prefer. And you use the equivalent of a "small string optimisation" - your class holds enough of the data for typical use, but allows dynamic allocation for big cases. I've given a sample here to get started - it's obviously missing a constructor and destructor, a swap specialisation, and a method of changing the size (thus adding to the number of bits). It's a nice cache-friendly 32-byte size (for 64-bit systems) - this cache friendliness will outweigh the cost of swapping 32 bytes compared to using an array of pointers. #include <bitset> #include <tuple> #include <array> const int chunk_size = 64; const int big_chunks = 7; struct S { using chunk = std::bitset<chunk_size>; struct extended { std::array<chunk, big_chunks> big_data; std::array<chunk, big_chunks> big_mask; }; std::tuple<float, float> data; // or a pointer to data, or whatever suits chunk small_data; chunk small_mask; extended * pe; bool operator < (const S& s) { if ((small_data & small_mask).to_ulong() < (s.small_data & s.small_mask).to_ulong()) return true; if ((small_data & small_mask).to_ulong() > (s.small_data & s.small_mask).to_ulong()) return false; if (!pe && !s.pe) return false; // equal if (!pe) return true; if (!s.pe) return false; for (auto i = 0; i < big_chunks; i++) { if ((pe->big_data[i] & pe->big_mask[i]).to_ulong() < (s.pe->big_data[i] & s.pe->big_mask[i]).to_ulong()) return true; if ((pe->big_data[i] & pe->big_mask[i]).to_ulong() > (s.pe->big_data[i] & s.pe->big_mask[i]).to_ulong()) return false; } return false; // equal } }; extern const int ss = sizeof(S); extern const int sse = sizeof(S::extended); bool foo(S& a, S& b) { return a < b; } |
| Vir Campestris <vir.campestris@invalid.invalid>: Nov 17 09:32PM On 17/11/2020 07:39, Juha Nieminen wrote: > to move the elements to a new vector, then it's easy. However, now it's > not in-place sorting anymore, and every time you sort you'll be creating > a new dynamically allocated array. But his problem seems to be that he's copying his non-trivial objects lots of times as the sort runs. This way with a bit of faffing about the pointers get copied lots of times, but the objects only get copied once. Andy |
| Brian Wood <woodbrian77@gmail.com>: Nov 16 08:52PM -0800 On Friday, November 13, 2020 at 4:59:05 PM UTC-6, Lynn McGuire wrote: > "Powerful, flexible, complex: The origins of C++ date back 40 years, yet > it remains one of the most widely used programming languages today. > TechRepublic spoke to C++ creator, Bjarne Stroustrup, to find out why." It's an important language, but to say it's the "foundation for everything" is a bit much. And I'm not sure how it's more invisible than other compiled languages. Brian Ebenezer Enterprises - Enjoying programming again. https://github.com/Ebenezer-group/onwards |
| "see.my....@gmail.com" <see.my.homepage@gmail.com>: Nov 17 11:20AM -0800 > It's an important language, but to say it's the "foundation > for everything" is a bit much. Considering that C++ is used to write operating systems (I read Windows had C++ code in it since v. 1.0), database servers, virtual machines (like Java), interpreters, whole computing systems (like Mathematica), web browsers, most of the gaming engines and AI frameworks - yes, it is a foundation for "everything", with a reasonably wide meaning of this word. I cannot think of any other language that would deserve this name more. Note that this has nothing to do with liking or disliking this language. Although, apparently, this state is the result of quite many people liking it. -- Maciej Sobczak * http://www.inspirel.com |
| "daniel...@gmail.com" <danielaparker@gmail.com>: Nov 17 12:26PM -0800 > Considering that C++ is used to write operating systems (I read Windows had C++ code in it since v. 1.0), database servers, virtual machines (like Java), interpreters, whole computing systems (like Mathematica), web browsers, most of the gaming engines and AI frameworks - yes, it is a foundation for "everything", with a reasonably wide meaning of this word. > I cannot think of any other language that would deserve this name more. At the lower levels, I'm pretty sure there is more C code than C++ code. Daniel |
| Lynn McGuire <lynnmcguire5@gmail.com>: Nov 17 03:12PM -0600 On 11/16/2020 10:52 PM, Brian Wood wrote: > Brian > Ebenezer Enterprises - Enjoying programming again. > https://github.com/Ebenezer-group/onwards I ran Windows 1.0 on a Compaq in 1985 when a salesperson came by for a demo. I highly doubt that it had any C++ in it since the first CFront was started in 1982. There was not a commercial release of C++ until 1985. https://en.wikipedia.org/wiki/C%2B%2B Lynn |
| Lynn McGuire <lynnmcguire5@gmail.com>: Nov 17 03:13PM -0600 > Considering that C++ is used to write operating systems (I read Windows had C++ code in it since v. 1.0), database servers, virtual machines (like Java), interpreters, whole computing systems (like Mathematica), web browsers, most of the gaming engines and AI frameworks - yes, it is a foundation for "everything", with a reasonably wide meaning of this word. > I cannot think of any other language that would deserve this name more. > Note that this has nothing to do with liking or disliking this language. Although, apparently, this state is the result of quite many people liking it. I ran Windows 1.0 on a Compaq in 1985 when a salesperson came by for a demo. I highly doubt that it had any C++ in it since the first CFront was started in 1982. There was not a commercial release of C++ until 1985. https://en.wikipedia.org/wiki/C%2B%2B Lynn |
| You received this digest because you're subscribed to updates for this group. You can change your settings on the group membership page. To unsubscribe from this group and stop receiving emails from it send an email to comp.lang.c+++unsubscribe@googlegroups.com. |
No comments:
Post a Comment