Do you ever sort a b-tree(or whatever) in your daily job?
-
B-trees were mentioned in at least 3 different mandatory courses I had to take for my B.Sc. (Introduction to Algorithms, Introduction to Databases and Operating Systems). But yeah, I guess it's not mandatory knowledge, since B-trees are a very specific data structure that is only used under very specific circumstances.
As an EE, I had to take a fair number of CS classes, including Data Structures. We learned about basic binary trees, but not B-trees, red-black trees or other variants. (Nor have I ever had an occasion where I needed to learn about them since.) There may have been an Advanced Data Structures class that covered them, but not the intro class.
-
Confession:
Zoned out on the class about Trees at Uni owing to after-effects of excessive partying. Still have not bothered to read up on those little shits.
-
I suppose a good example would be stuff like bounding volume hierarchies, where your goal is to locate some objects quickly and efficiently. Also look at part 1 and part 2 of this series on collision detection.
That could explain why I got a question about data structures in a job interview a while ago. I thought he was just testing my knowledge of C pointer manipulation, but now, knowing that such structures are used in that domain, I see that it was actually potentially relevant to the job.
-
Yes, I use trees/graphs/etc regularly, and implementing specialized versions of such data structures is frequently a core consideration of whether or not a certain project succeeds.
What kind of project?
Because I've done web analytics, SMS message processing, and medical enrollments/billing, and this shit has never come up.
-
I usually hit that due to someone choosing a "do everything" blackbox library, when then turns out not to support something vastly important we need.
Like WebAPI 2's inability to have a controller accept a JSON array containing objects of different schemas. Or it's utter inability to handle "application/x-www-form-urlencoded" content type.
-
@cvi said:
Yes, I use trees/graphs/etc regularly, and implementing specialized versions of such data structures is frequently a core consideration of whether or not a certain project succeeds.
What kind of project?
Because I've done web analytics, SMS message processing, and medical enrollments/billing, and this shit has never come up.
Projects like mine, "Games"
-
If I made a game, I'd have the guys at Epic or Unity do the heavy lifting, and focus on the stuff that makes my game actually unique.
-
If I made a game, I'd have the guys at Epic or Unity do the heavy lifting, and focus on the stuff that makes my game actually unique.
Tell that to my bosses.
-
Ok, put me in touch with them.
I mean to be fair, if you're doing some new rendering or AI technique that nobody's ever done before, yeah, I get it. You'll need to know some of this stuff. I'm guessing 99% of games do not.
-
I won't either. And I should have been clarify that I don't mean we should recite those nonsense.
Just want to convey the idea that there exist information that we can Google in 2 seconds, but you had better memorize them before we start our job.
-
Usually when a new game is launched, it's expected there are areas that not up-to-expectation in performance, or simply have bugs. Most gamers expected that and if your game is both interesting and not-too-buggy, they'll continue playing it while waiting for updates. We know performance issues in 3D gaming can be tricky and take time to get it right.
That's why Blakey's view is generally correct. Just bring out awesome features and do performance tuning afterwards.
-
I'd say it's more like the opposite: A comparator is “a thing that compares stuff”. linq has made writing them so effortless that you don't even notice it any more.
-
Oops, those were my ex-bosses. When the programmer knows more game design and UX shit than the game designers, who keeps blaming programmers on "game is too slow" while spawning over 1000 AI units into the world and demanded to be able to view their actions in detail at the same time (I know it is an illogical request, how the hell does one view every single unit on a single screen in the first place).
In my previous work place, game designers had more say than the programmers, which reminded me of why I left.
-
robotics.
I wish.
I'm doing graphics stuff (algorithms mostly), plus sometimes some general-purpose GPU computation things.
-
Users tend to frown on randomly ordered items in a table of stuff.
@tufty looks suspiciously at the "related topics" section at the bottom of the page
-
@boomzilla said:
Users tend to frown on randomly ordered items in a table of stuff.
@tufty looks suspiciously at the "related topics" section at the bottom of the page
Did that include a frowny face?
-
It looked like this:
-
Because I've done web analytics, SMS message processing, and medical enrollments/billing, and this shit has never come up.
I've done a lot of stuff with things like hr/payroll and manufacturing and workflow and have probably never needed anything beyond an array, although I learned about all kinds of exotic trees in college.
Certain fields, as mentioned, need more advanced structures. If you're working on a database engine, you might, but that's not exactly a huge field.
-
If you're working on a database engine, you might, but that's not exactly a huge field.
It's also domain knowledge.
I also don't need to know orbital mechanics, unless I'm writing software for NASA (or Kerbal Space Program), and at that point I learn it as part of the domain I'm working in. Nothing wrong with me not knowing it. It doesn't make me less of a programmer. It's just not part of the domain knowledge I need. (And that guy might be able to smoke me on b-trees but I could smoke him on Health Savings Account enrollment rules.)
Unfortunately, I went to a university that didn't fucking understand the concept. I hope they're better now.
-
Unfortunately, I went to a university that didn't fucking understand the concept.
One thing I liked about mine is that it had a couple profs who'd held real jobs. So for example we had a course involving design, as in, the whole semester was "come up with a design for an application to replace a paper workflow for a company." I don't remember any details any more but the prof played the part of half a dozen people at the company so we could interview them, and then come up with a short set of high-level use cases for a hypothetical custom software. It was pretty cool.
-
It's just not part of the domain knowledge I need.
But it's part of the domain knowledge for many possible jobs for computer scientists. General knowledge about data structures (trees, graphs, linked lists, hash maps) is not nearly as domain-specific as knowledge about rockets and their interaction with orbits.
B-trees are very specific, though. I don't care whether anyone knows what they are.
-
But it's part of the domain knowledge for many possible jobs for computer scientists.
True; but GAAP (generally accepted accounting practices) are part of the domain knowledge for a significantly higher percentage of those jobs, and I've never seen a school teach that along with computer science. It's always super math-y stuff, never anything practical.
B-trees are very specific, though. I don't care whether anyone knows what they are.
That's the right attitude.
Far more important than knowing what a b-tree is is having a place like this forum where you can go and say, "hey guys, here's a problem I'm having trouble solving..." and someone will reply, "for that you need a b-tree, here, look at this article."
-
Fun fact: I seriously doubt 99.8% of PHP programmers even know what a tree is, let alone how to balance one.
-
what a tree is, let alone how to balance one.
Do they not just stand up on their own from the ground?
-
-
-
How should they? PHP programmers cannot even tell the difference between arrays and hash maps
-
On a second thought, they probably know about the DOM, though, which is a tree.
-
Fun fact: I seriously doubt 99.8% of PHP programmers even know what a tree is, let alone how to balance one.
How should they? PHP programmers cannot even tell the difference between arrays and hash maps
Do they not just stand up on their own from the ground?
Attack of the PHP clone-o-bots?
Go to the comments section if it doesn't scrolldown on its own.
-
lol, Hadoop
-
Which of course is why you post here for 6 hours a day, on top of your comprehensive video gaming schedule.
Are you insinuating that there's something undesirable about having a comprehensive video gaming schedule? It sure beats dealing with people.
-
@Jaime said:
So... if you had data on the screen and the user wanted the data sorted by a different column, you would discard the data and fetch a new result set just to implement a sort? That's nuts.
Yup. That's what I get told to do in every project.
Sometimes my senior devs and pms say they have to have some sort of sorting because of specific user requirements. Then they just buy a third party commercial "chart/graph component". That's it.
Many of those components also natively support sorting by, say, simply clicking on a grid column. I can't remember the last time I've had to sort a list stored in memory by hand.
-
If you're applying at Boeing to help write the software for their next major aircraft
When blakey read that sentence, the mere thought caused him to have to take a cold shower afterwards.
-
I suppose a good example would be stuff like bounding volume hierarchies, where your goal is to locate some objects quickly and efficiently. Also look at part 1 and part 2 of this series on collision detection.
My rendering and physics engines use octrees and other BVHs, but I haven't had the desire to care about such things for a very long time. Collision detection and response in 3D is a hard problem, but one that other people have solved. I tried implementing a SAT overlap test for oriented bounding boxes and built an octree for testing against triangular meshes, and then decided it would be a much better use of my time to use Bullet.
"Make games, not engines."
-
Usually when a new game is launched, it's expected there are areas that not up-to-expectation in performance, or simply have bugs. Most gamers expected that and if your game is both interesting and not-too-buggy, they'll continue playing it while waiting for updates. We know performance issues in 3D gaming can be tricky and take time to get it right.
Races to the bottom in the form of early release games have also acclimated the public to swallowing half-finished turds, which provides another reason to pursue this strategy.
In all fairness, some of those half-finished turds turned out to be full of chocolatey goodness.
-
True; but GAAP (generally accepted accounting practices) are part of the domain knowledge for a significantly higher percentage of those jobs, and I've never seen a school teach that along with computer science. It's always super math-y stuff, never anything practical.
There's no time to teach practical things when the professors devote an unusual amount of time to proving that √2 is irrational.
-
That proof is like 5 minutes long.
-
Hey, don't make complete generalisations! There is at least one PHP programmer that knows the difference!
Sometimes it does feel like I am the only one, though...
-
Hey, don't make complete generalisations! There is at least one PHP programmer that knows the difference!
How does that knowledge help you if the language shoehorns both concepts into one data structure?
-
Hashmaps are fast!
But this one is slow!
Impossible!
Look at these profile results.
They're wrong!
What's the hash code implementation like.
The what?
It's 2525!
I think that video is funny so I used that.
FFS!
-
Because you can use it to actually get whichever one you need. There are certain behaviours that apply to one, certain behaviours that apply to the other and the two do not always overlap.
-
Which is why I always ask for an example of X in your work. If you're good enough to either remember or make one up on the spot (which is usually fine), then that means you can think on your feet. If you don't know and I explain, you should be able to think of a case where you might end up using X.
-
Kerbal. Space. Program.
-
Because you can use it to actually get whichever one you need. There are certain behaviours that apply to one, certain behaviours that apply to the other and the two do not always overlap.
I know, I was just trolling. But technically, you're still relying on the fact that the PHP implementation (most likely: Zend Engine) "magically" chooses the correct data structure internally. I don't think that's guaranteed anywhere.
-
It's not guaranteed, but it is one of the 3,742 gotchas to deal with. You can "help" it quite a bit though and you can let PHP fuck your data structure over too quite easily.
If you pretend that these two things are separate and use them consistently separately (always treat a given array as if it is an array, or always treat it as a hash map) you're usually safe and PHP will by and large respect it.
Just be careful when using, well, any of the array functions if you happen to have an array with numeric indices that you're using sparsely because you can expect to have it reordered for you.
-
Kerbal. Space. Program.
That was a hell of a lot more fun before it was "finished".
Now it's shit.
-
While I often need to sort things, I rarely need to worry about the exact method for sorting them or the structure of the objects that are representing my data. I either call an existing sort method, pipe to a sorting command, or specify an ORDER BY clause. I'm probably sorting B-trees all day since I'm a DBA and Analyst, but I'm never exposed to the details.
Sorting is very useful as a teaching algorithm, since it provides something that does a non-trivial amount of work (so students feel rewarded) and is complicated enough to require a lot of thought about algorithms. It's especially useful because there are dozens of sorting algorithms and there are cases where very poor algorithms get used. Insertion sorts work very well on nearly sorted data. Selection sorts work well when I/O is very expensive. Bubble sorts require very little code to function. Sorting is one of those areas that looks very simple, but hides a tremendous amount of complexity and depth.
-
but I'm never exposed to the details
Neither are most of the rest of us. Here's how you sort a list of employees by last name in C#, assuming you need a custom sort expression:
employees.Sort((e1, e2) => e1.LastName.CompareTo(e2.LastName))If you're simply sorting by a property, then you can use:
employees = employees.OrderBy(e => e.LastName).ToList();I can't tell you what implementation of sort they use, I only supply the comparison rules.
-
I can't tell you what implementation of sort they use
Someone at MSFT has thought about this.
- If the partition size is fewer than 16 elements, it uses an insertion
sort algorithm. - If the number of partitions exceeds 2 * LogN, where N
is the range of the input array, it uses a Heapsort algorithm. - Otherwise, it uses a Quicksort algorithm.
List<T>.Sort Method (System.Collections.Generic)
Sorts the elements or a portion of the elements in the List<T> using either the specified or default IComparer<T> implementation or a provided Comparison<T> delegate to compare list elements.
- If the partition size is fewer than 16 elements, it uses an insertion
-
But... the point is that a developer doesn't have to care.
