|
Look the obvious solution is to chuck out these untrusted mechanized "compilers" and go back to humans reading HLL's and writing equivalent assembly.
|
# ? Jun 20, 2013 22:11 |
|
|
# ? Jun 5, 2024 08:47 |
|
Otto Skorzeny posted:Good grief, there are people out there who use linked lists "for performance" There are situations where linked lists are the better choice for performance. Not many, but a few. Even fewer that matter in a real environment, and then you take out the ones that are simply in the wrong data model for the problem, leaving those choice little situations where the stars align and it's linked list paradise.
|
# ? Jun 20, 2013 23:38 |
|
Yeah, I mean you could be implementing a hash table or some other bucketed data structure, and be looking for a lightweight data structure to chain off each bucket in case of collisions.
|
# ? Jun 21, 2013 00:00 |
|
baquerd posted:There are situations where linked lists are the better choice for performance. Not many, but a few. Even fewer that matter in a real environment, and then you take out the ones that are simply in the wrong data model for the problem, leaving those choice little situations where the stars align and it's linked list paradise. If you're doing modifications a lot and don't care about constant time access (which happens in quite a lot of game scenarios), a doubly-linked list is actually a very good choice.
|
# ? Jun 21, 2013 00:18 |
|
In fact any time efficient removal of elements is important, but random access isn't, a linked list is something to consider. That's why you get a lot of linked lists in kernel code. Don't do that dumb "make a doubly-linked list with only a single pointer field by xoring the pointers together" though, that's pretty dumb.
|
# ? Jun 21, 2013 00:34 |
|
Jabor posted:Yeah, I mean you could be implementing a hash table or some other bucketed data structure, and be looking for a lightweight data structure to chain off each bucket in case of collisions. This is about the best example of common misuses of linked lists. Even a vector-like structure is much better for a hash table that uses separate chaining (rather than the vastly-superior-for-almost-all-purposes scheme of cuckoo hashing) than a linked list - the the time overhead of one extra cache miss blows away the 'inefficiency' of rearranging poo poo in a tiny, tiny array.
|
# ? Jun 21, 2013 00:43 |
|
Suspicious Dish posted:If you're doing modifications a lot and don't care about constant time access (which happens in quite a lot of game scenarios), a doubly-linked list is actually a very good choice. This. There's nothing wrong with using a linked list, just always be aware of the complexity of operations of the various common datastructures that you have available and which operations you need to be optimized. If you're frequently doing things such as removal of arbitrary elements or splicing, or things of that nature, especially if the datatypes involved are not trivial to move around in memory, linked lists are usually a better choice than something like an array, especially if you're not frequently iterating over the elements.
|
# ? Jun 21, 2013 00:50 |
|
Yeah, linked lists are extremely useful; it's just that they're not a drop-in replacement for other kinds of containers. You need to write everything around holding references to individual linked-list nodes, and a lot of languages/libraries make that unnecessarily difficult. Intrusive lists can be cleaner, but depending on your language, you might not be able to re-use your linked-list code effectively with them.
|
# ? Jun 21, 2013 01:14 |
|
Otto Skorzeny posted:This is about the best example of common misuses of linked lists. Even a vector-like structure is much better for a hash table that uses separate chaining (rather than the vastly-superior-for-almost-all-purposes scheme of cuckoo hashing) than a linked list - the the time overhead of one extra cache miss blows away the 'inefficiency' of rearranging poo poo in a tiny, tiny array. Are you rearranging your entire hash table when a single bucket gets bigger? If you chain a vector off a bucket, you eat one cache miss every time you look up that bucket. With a linked list, you don't eat that cache miss if there's only one item in the bucket (or even if there are more than one, but the item you want just happens to be first). Guess how many items are in a given hash table bucket in the typical case?
|
# ? Jun 21, 2013 01:15 |
|
Typical hash table implementations have around 8 buckets, so I'm going to guess 5 or 6 items per bucket? 40-50 items in a hash table on average sounds about right.
|
# ? Jun 21, 2013 01:18 |
|
Suspicious Dish posted:Typical hash table implementations have around 8 buckets, so I'm going to guess 5 or 6 items per bucket? 40-50 items in a hash table on average sounds about right. typical implementations keep the load factor below about .75
|
# ? Jun 21, 2013 01:30 |
|
Suspicious Dish posted:Typical hash table implementations have around 8 buckets, so I'm going to guess 5 or 6 items per bucket? 40-50 items in a hash table on average sounds about right. 8 buckets with 40-50 items? That's quite a high load factor (elements pr bucket), so I doubt that's all too common. In general you want the buckets to be as shallow as possible (ideally only 1 element), while not wasting space due to having way too many buckets. Java, for instance, has a default maximum load factor of 0.75(source) on it's HashMap. When the maximum load factor is reached, the underlying array is reallocated to be larger.
|
# ? Jun 21, 2013 01:34 |
|
I remember investigating Python's dict object and coming up with that, but I could be wrong.
|
# ? Jun 21, 2013 01:41 |
|
Suspicious Dish posted:I remember investigating Python's dict object and coming up with that, but I could be wrong. http://svn.python.org/projects/python/trunk/Objects/dictobject.c posted:If we *usually* find the key we're looking for on the first try (and, it turns
|
# ? Jun 21, 2013 01:45 |
|
I guess 2/3 does look a lot like 2^3. Negligible difference, really.
|
# ? Jun 21, 2013 02:00 |
|
Otto Skorzeny posted:Good grief, there are people out there who use linked lists "for performance" Linked lists of _something_ are the only option if you want to minimize worst-case performance of a thing. Linked lists with 1 element per node are also faster than linked lists of chunks of values, or linked lists of any other kind of helper data structure, in some circumstances.
|
# ? Jun 21, 2013 05:21 |
|
Deus Rex posted:No, people with my background are superior to all others because they're like me.
|
# ? Jun 21, 2013 06:09 |
|
Gazpacho posted:As an EE grad with years of hindsight about myself and other grads, I will admit that EEs tend to latch onto some seriously bogus and antiquated ideas about programming. As an EE myself, I can verify that EEs write the worst, most godawful code you've ever seen.
|
# ? Jun 21, 2013 06:19 |
|
Arcsech posted:As an EE myself, I can verify that EEs write the worst, most godawful code you've ever seen. You have not seen physicist code.
|
# ? Jun 21, 2013 08:31 |
|
KaneTW posted:You have not seen physicist code. You have not seen biologist code.
|
# ? Jun 21, 2013 08:36 |
|
You have not seen my code
|
# ? Jun 21, 2013 08:39 |
|
You have not seen my coworker's code
|
# ? Jun 21, 2013 13:01 |
|
if only we had a thread for showing each other this bad code.
|
# ? Jun 21, 2013 13:50 |
|
KaneTW posted:You have not seen physicist code. Mathematician code is a million times worse. Here's a psuedocode example of something that I saw recently: Python code:
QuarkJets fucked around with this message at 21:15 on Jun 21, 2013 |
# ? Jun 21, 2013 21:07 |
Are you trying to start a tab vs spaces debate?
|
|
# ? Jun 21, 2013 21:22 |
|
Don Mega posted:Are you trying to start a tab vs spaces debate? With Python there's a written standard as to which one is "right", so it's not really a debate there (tabs are considered
|
# ? Jun 21, 2013 21:49 |
A style guide written by one man is not law. He also does not say it is a requirement to use spaces, but merely recommends it. In the end all that matters is that you do not mix and match. How about we argue about text editors next? Edit: I also take blame for starting this tab vs spaces shenanigan! When in doubt conform to your co-workers / source. Don Mega fucked around with this message at 22:04 on Jun 21, 2013 |
|
# ? Jun 21, 2013 21:57 |
|
Don Mega posted:How about we argue about text editors next?
|
# ? Jun 21, 2013 21:58 |
|
Don Mega posted:A style guide written by one man is not law. He also does not say it is a requirement to use spaces, but merely recommends it. In the end all that matters is that you do not mix and match. Okay well, ignoring the tab/space thing his code stuff still has plenty of other horrors, but most regular Python coders would also be miffed at the tab thing though yes indeed you can use whatever the gently caress you want.
|
# ? Jun 21, 2013 22:04 |
|
More loony is:quote:Limit all lines to a maximum of 79 characters. One of the PDP 11 developers no doubt.
|
# ? Jun 21, 2013 22:26 |
|
QuarkJets posted:Mathematician code is a million times worse. Here's a psuedocode example of something that I saw recently: Variable names like that make sense when you're in the middle of implementing an algorithm from a paper or textbook, but you rename them after you get it working e: and you haven't needed to extend object since December 2008 Lysidas fucked around with this message at 22:35 on Jun 21, 2013 |
# ? Jun 21, 2013 22:31 |
|
MrMoo posted:More loony is: Or is it really just some archaic tradition enforced by aging relics?
|
# ? Jun 21, 2013 22:32 |
|
MrMoo posted:More loony is: Or anybody on a notebook computer that wants to see two files side-by-side.
|
# ? Jun 21, 2013 22:33 |
|
For Python, follow PEP or get your poo poo slapped. Or circlejerk with your coworkers who are also wrong, and get your collective poo poo slapped once you sneak a peek outside of your basement ghetto hellhole workplace.
|
# ? Jun 21, 2013 22:42 |
|
RoadCrewWorker posted:I've seen that stuff so much that i still wonder if there's a convincing reason for it these days. Do people use text editors in tiny windows with enormous fonts or does vi scripting/display break over a certain limit? Modern vi clones (vim, probably elvis, etc) can handle long lines fine. There are corner cases where technical limitations make some max line length (not necessarily ~80 chars) reasonable, especially if patches might be discussed on a mailing list where a few levels of quote-induced indentation are likely to come about. Some people do have difficulty reading small fonts as you speculated (esp. coworkers in their 40s or 50s). My vision fine but I usually use a pretty large (12 or 14 point) font regardless, this combined with a light-on-dark colorscheme seems to make my eyes less tired at the end of the day. It is also handy to be able to have a couple of files open side by side while the other monitor is in use for something else (an email asking a question, a diff of one of the files, or whatever), which implies there should be a cutoff, and 80ish characters is the cutoff that has been used by everyone forever.
|
# ? Jun 21, 2013 22:45 |
|
Lysidas posted:e: and you haven't needed to extend object since December 2008 Maybe in Python 3, but in Python 2 if you don't explicitly inherit object you get an old style class.
|
# ? Jun 21, 2013 22:51 |
|
Isilkor posted:Sublime Text 2 is the king of text editors Sublime Text 2 may be a king but Emacs is an Old, Slumbering God.
|
# ? Jun 21, 2013 23:08 |
|
RoadCrewWorker posted:I've seen that stuff so much that i still wonder if there's a convincing reason for it these days. Do people use text editors in tiny windows with enormous fonts or does vi scripting/display break over a certain limit? vi and emacs ahve linewrap so even if you're working in an 80 x 20 terminal window for some reason it's not a problem.
|
# ? Jun 21, 2013 23:23 |
|
Otto Skorzeny posted:It is also handy to be able to have a couple of files open side by side while the other monitor is in use for something else (an email asking a question, a diff of one of the files, or whatever), which implies there should be a cutoff, and 80ish characters is the cutoff that has been used by everyone forever. It's basically this. It makes no sense to waste half your screen area displaying a river of blank space just because some lines occasionally break into it - limiting lines to 80 characters allows you to make better use of that space, at the cost of having to wrap longer lines occasionally. Java is obnoxiously verbose though, so 80 columns really isn't enough there - limit it to 120 or something. (120 is nice because then you fit two Java windows in the space that fits three other-language ones)
|
# ? Jun 21, 2013 23:23 |
|
|
# ? Jun 5, 2024 08:47 |
|
Jabor posted:Java is obnoxious I agree completely, it is obnoxious.
|
# ? Jun 21, 2013 23:27 |