Computer Science Lounge - [Too Many Idea Men Edition]

These aren’t intended to be STL data structures. They aren’t meant to be replacements for the general purpose data structures in C++. They’re designed to be useful for people who know they need high performance easy to use data structures for writing highly concurrent or fully persistent programs. I don’t see anyone making a case for them to be in the STL. The library is LGPLv3, certainly not something you would expect to get adopted by a standard library.

The use of persistent data structures is not uncommon in many domains. Scaling cleanly across many cores unlocks much more of a machine’s performance than a carefully tuned single-threaded implementation. Trying to hand optimize every instruction generated by your code is generally not a very beneficial way to get better performance. There is a great slide in this presentation by Sean Parent that illustrates this point pretty well:


The full talk is here, for reference:


Certainly there will be some edge cases where your hot path is stuck on a single core in C++ and you want to focus there to squeeze out the last little drop of performance from the machine. But until you are out of other options, there are much greater gains to be had elsewhere.

Then here’s my sign that I’m reading too much into things because of work drama. Point conceded.

Jumping into this late but very true. You can also apply the reason for this to the reason why Java is still widely used in the industry. In general hardware is cheaper than the cost of programmers and while it would be nice to have the most efficient code for example a well optimized C++ solution, A scalable option is preferable as the cost becomes prohibitively high.

Apply it to what I gather you mentioned, It’s better to scale across hardware than single threaded optimization. One exception to this rule is game but it depends on the expectation of each game.

Applying this to language choices, in say a website application where a website must be able to complete moderately complex algorithms for example an image hosting site. When you compare the extra man hours of developing something in C++ over Java, it becomes more cost efficient depending on the size of the user-base to develop in Java and spend more on hardware than it is to try and save on hardware by using a more efficient language and spending the extra time optimizing.

I could be wrong but that’s my understanding and why languages like Java and C# won’t disappear.

Here I am hoping for SR-IOV from GPUs to come over to consumer grade GPUs so I can move out of Windows. For most things I pretty much already can.

Start off small then. Will be interesting either way

I agree. I work for a software company and they are Agile only in name. Specifically we are supposed to be using Scrum, but in actuality we do what ever the PM states we do. We miss deadlines, our sprints are too long or too short, an our requirements and story writers are not good at their jobs.

When everything is said and done, we look more like a traditional water fall style minus documentation. Did I mention that we do not do much of any documentation because … Agile!

My personal opinion about Agile methodologies is that for small and non-complex applications, Agile is probably best. Once your product gets off the ground and/or your product becomes large and complex, you do best going towards a waterfall method. Agile seems to only work in the long term if you are good at writing stories, adhering to the spec, and that you try to reach feature perfect ( fixing bugs, review specs and stories) before doing major rewrites and major new features. Once you have a solid base, agile helps get development moving on the new stuff.

I mean this is my opinion and all. I have worked for a few shops but by far, the shop I work for now ( very small shop) is the biggest abuser of Agile.

Anyone here got a cheap (sub 500 buck) laptop suggestion for an new engineering student?
I know this is more of a CSE, and SE thread but I think many of the programs I will be using overlap.

Thinking a ThinkPad X220 and slapping windows 10 on it, be around 300 bucks all together from what I can find.
Thinking I wouldn’t be able to do CAD stuff on the go, but I think an i7, 8gb ram spec thinkpad would do the trick for most of my needs and be nigh indestructible.

thoughts?

2 Likes

I suggest you go looking for a surplus store and you can get a good deal in one of those places.
Just search google maps for like computer recycling and see what comes up.

1 Like

Hmmm, hadn’t thought of that to be honest, will look into it.

Kinda iffy on the specs, wanted to see what others are using. Thinking a i7 and 8 gb ram should be fine, I don’t think I would need laptop with a beefy graphics card (unless I need to do cad work) but I could be wrong.

That will be plenty I think to run the basic stuff you will need like Matlab and other general use computing.

1 Like

It’s been 10 years since I left school… need help and opinions

Let’s say you have a pubsub system where people subscribe to events tagged with strings. Events that stream through are many, subscriptions change rarely in comparison. Users can subscribe using exact strings to match (hashmap) or using regexes (might be possible to partially index by extracting prefixes, or substrings).

Would you index prefix subscriptions using radix or interval trees, why?

A radix tree is the standard data structure for string prefixes. It is a trie, which means it is optimized for reTRIEval. The radix tree offers lookup on the order of the length of the key, independent of the number of entries.

I’m not aware of how you could use an interval tree to solve the problem efficiently.


Strings are just arbitrary precision numbers.

For example, they are comparable, they occupy a space starting with NULL and ending with EOF (or $, or whatever you choose to call the value after 0xFFFFFFFF…).

An example of how these map to interval trees, if you have a string e.g. ‘abc’ and are looking to find a matching prefix “ab”, in an interval tree you can encode the matching prefix as [“ab”,“ab$”), and to find it you’d be looking for all intervals that intersect with a point value “abc”.

Anybody with experience with DFA’s or PDA’s?

I have started my more advance courses in theory of computation and algorithms so I will be interested to talk with some colleagues about the subject.

@Zoltan dont you have some knowledge in this field?

Would anybody know of any good ways to test all the strings in a regular expression? Studying for an exam and I need to make a regular expression for all languages of all strings
of a’s, b’s, and c’s where a is never immediately followed by b.

I think it may be
[(a+b*)(cb+)*(ac+)a*]*

where b+ or a+ is a* - epsilon or b* - epsilon.

I dont have any answers so I was wondering if anybody could tell me if you think this is right or wrong.

Sounds like you want to negate a regex without negating a regex.

((^a+$)|(a+c)|(ba+$)|(ca+$)|(bc+)|(cb+))+

Would be my first guess.

You can write a string generator, since you have only 3 “digits” it should be quick enough.

The other option would be to draw a state machine and somehow figure out a way to encode state+transition, but not future state in your regex options, whilst making sure you’re not allowing for invalid transitions.

1 Like

I think this is right. I dont think my guess was correct. I actually said that on my HW but I lost points because I put an extra parenthesis.

Yeah the inner ones are not required,… ship,… sorry!

No I actually had that for my answer before I came here but I thought my theory was wrong so I came on here and you posted what I had originally put. Turns out it can be reduced but the theory I dont think is wrong. Just some syntax. The TA agreed though to give me some points back.

The reduced answer is image

1 Like